Travelling salesman problem using genetic algorithm in C++

I have implemented travelling salesman problem using genetic algorithm. Since project is not so small I will give short introduction.

GeneticAlgorithmParameters - Struct responsible for general algorithm parameters.

Point - Super small struct, you can think about it as a city or whatever.

Path - Class which contains one path (one solution to the problem).

Population - As name indicates class which contains whole population. It is main class for solving this problem.

PointInitializer - Interface for 2 classes. Consists of one method getInitialPoints.

FilePointInitializer - Derive from mentioned class, it is responsible for reading file (passed by user) and returning std::vector of points as a cities.

RandomPointInitializer - Derive from mentioned class, it is responsible for randomly creating and returing std::vector of points as a cities.

Parser - It is used to valide command arguments passed by user. For example, when user passes command "help" it prints of help information. After validating arguments it is returning GeneticAlgorithmParameters struct as a settings.

Plotter - It is class which is responsible for plotting final solution (OpenCV).

Genetic_TSP.cpp file where main.cpp is.

This code uses C++17.

GeneticAlgorithmParameters.hpp

#ifndef TSP_FINAL_GENETICALGORITHMPARAMETERS_HPP
#define TSP_FINAL_GENETICALGORITHMPARAMETERS_HPP

struct GeneticAlgorithmParameters
{
int numberOfPoints{50};
int sizeOfPopulation{500};
int numberOfIterations{1000};
double mutationRate{0.05};
double percentageOfChildrenFromPreviousGeneration{0.9};
};

#endif


Point.hpp

#ifndef TSP_FINAL_POINT_HPP
#define TSP_FINAL_POINT_HPP

struct Point
{
Point() = default;

Point(double x, double y) : x(x), y(y)
{}

bool operator==(const Point &rhs) const
{
return rhs.x == x and rhs.y == y;
}

double x = 0;
double y = 0;
};

#endif


PointInitializer.hpp

#ifndef TSP_FINAL_POINTINITIALIZER_HPP
#define TSP_FINAL_POINTINITIALIZER_HPP

#include <Path.hpp>

class PointInitializer
{
public:
virtual ~PointInitializer() = default;
virtual std::vector<Point> getInitialPoints(int) = 0;

};

#endif


FilePointInitializer.hpp

#ifndef TSP_FINAL_FILEPOINTINITIALIZER_HPP
#define TSP_FINAL_FILEPOINTINITIALIZER_HPP

#include "PointInitializer.hpp"
#include <string>
#include <fstream>

class FilePointInitializer : public PointInitializer
{
public:
FilePointInitializer(const std::string &);

std::vector<Point> getInitialPoints(int) override;

private:
std::ifstream infile{};
};

#endif


RandomPointInitializer.hpp

#ifndef TSP_FINAL_RANDOMPOINTINITIALIZER_HPP
#define TSP_FINAL_RANDOMPOINTINITIALIZER_HPP

#include <random>
#include <algorithm>
#include "PointInitializer.hpp"

class RandomPointInitializer : public PointInitializer
{
public:
RandomPointInitializer(int, int);

std::vector<Point> getInitialPoints(int) override;

private:
std::mt19937 rng{};
std::uniform_int_distribution<std::mt19937::result_type> randX{};
std::uniform_int_distribution<std::mt19937::result_type> randY{};
};

#endif


Path.hpp

#ifndef TSP_FINAL_PATH_HPP
#define TSP_FINAL_PATH_HPP

#include "Point.hpp"
#include "PointInitializer.hpp"
#include <vector>
#include <memory>

class Path
{
public:
explicit Path(std::vector<Point>);
double getFitness() const;
double calculateFitness() const;
std::vector<Point> getPath() const;
void mutate(int, int);
std::vector<Point> crossover(const Path &parent) const;

private:
std::vector<Point> path;
double fitness{};
};

#endif


Population.hpp

#ifndef TSP_FINAL_POPULATION_HPP
#define TSP_FINAL_POPULATION_HPP

#include <optional>
#include <random>
#include "Path.hpp"
#include "GeneticAlgorithmParameters.hpp"

class Population
{
public:
Population(const GeneticAlgorithmParameters &, std::shared_ptr<PointInitializer>);
Path performTournamentSelection();
void mutation();
void updatePopulation();
std::vector<Point> getBestSolutionPath() const;
double getBestSolutionFitness() const;
Path getBestSolutionInCurrentPopulation() const;
std::vector<double> getHistoryOfLearning() const;
int getNumberOfBestSolution() const;
void runAlgorithm();

private:
int getRandomNumberInRange(int, int);
void createAllInitialSolutions();
void checkForBetterSolution();
void saveActualScore(double);

std::vector<Path> population{};
GeneticAlgorithmParameters geneticAlgorithmParameters{};
std::shared_ptr<PointInitializer> initializer{};
std::optional<Path> bestSolution{};
std::vector<double> historyOfLearning{};
int bestSolutionNumber{};
};

#endif


Parser.hpp

#ifndef TSP_FINAL_PARSER_HPP
#define TSP_FINAL_PARSER_HPP

#include <string>
#include <vector>
#include <optional>
#include "GeneticAlgorithmParameters.hpp"

class Parser
{
public:
explicit Parser(std::vector<std::string>);
void printHelpOptions() const;
bool isCommandPassed(std::string_view) const;
bool isRandomModeEnabled() const;
std::optional<GeneticAlgorithmParameters> validateInput();
std::string getValueFromPassedCommand(std::string_view command) const;
std::string getPassedFilePath() const;

private:
void setSizeOfPopulationParameterFromInput();
void setMutationRateParameterFromInput();
void setNumberOfIterationsParameterFromInput();
void setNumberOfPointsFromInput();
void setPercentageOfChildrenFromPreviousGeneration();

GeneticAlgorithmParameters geneticAlgorithmParameters{};
std::vector<std::string> arguments{};
};

#endif


Plotter.hpp

#ifndef TSP_FINAL_PLOTTER_HPP
#define TSP_FINAL_PLOTTER_HPP

#include <vector>
#include "Point.hpp"
#include <opencv2/core/core.hpp>
#include <opencv2/opencv.hpp>
#include <opencv2/highgui/highgui.hpp>

class Plotter
{
public:
Plotter(int, int);
void drawPoints(const std::vector<Point> &points) const;

private:
cv::Mat image{};
const int imageWidth{};
const int imageHeight{};
};

#endif


FilePointInitializer.cpp

#include "FilePointInitializer.hpp"
#include <iostream>

FilePointInitializer::FilePointInitializer(const std::string &file) : infile(file)
{}

std::vector<Point> FilePointInitializer::getInitialPoints(int sizeOfInitialSolution)
{
double x, y;
std::vector<Point> initialSolution;
initialSolution.reserve(sizeOfInitialSolution);

while (infile >> x >> y)
{
initialSolution.emplace_back(x, y);
if (initialSolution.size() == sizeOfInitialSolution)
{
break;
}
}

if (initialSolution.size() != sizeOfInitialSolution)
{
throw std::invalid_argument("There are not enough data to load from file");
}

infile.clear();
infile.seekg(0, std::ios::beg);
return initialSolution;
}


RandomPointInitializer.cpp

#include "RandomPointInitializer.hpp"

RandomPointInitializer::RandomPointInitializer(int imageHeight, int imageWidth) : randX(0, imageWidth),
randY(0, imageHeight)
{
rng.seed(std::random_device()());
}

std::vector<Point> RandomPointInitializer::getInitialPoints(int sizeOfSolution)
{
std::vector<Point> initialSolution;
initialSolution.reserve(sizeOfSolution);

for (auto i = 0; i < sizeOfSolution; ++i)
{
initialSolution.emplace_back(double(randX(rng)), double(randY(rng)));
}

return initialSolution;
}


Parser.cpp

#include <iostream>
#include "Parser.hpp"
#include <algorithm>

Parser::Parser(std::vector<std::string> arguments) : arguments(std::move(arguments))
{}

std::string Parser::getValueFromPassedCommand(std::string_view command) const
{
for (const auto &elem : arguments)
{
if (elem.find(command) != std::string::npos)
{
return elem.substr(elem.find('=') + 1);
}
}
}

std::optional<GeneticAlgorithmParameters> Parser::validateInput()
{
if (isCommandPassed("--help"))
{
printHelpOptions();
return {};
}

setSizeOfPopulationParameterFromInput();
setMutationRateParameterFromInput();
setNumberOfIterationsParameterFromInput();
setNumberOfPointsFromInput();
setPercentageOfChildrenFromPreviousGeneration();

return geneticAlgorithmParameters;
}

void Parser::setSizeOfPopulationParameterFromInput()
{
if (isCommandPassed("sizeOfPopulation"))
{
geneticAlgorithmParameters.sizeOfPopulation = std::stoi(getValueFromPassedCommand("sizeOfPopulation"));
}
}

void Parser::setMutationRateParameterFromInput()
{
if (isCommandPassed("mutationRate"))
{
geneticAlgorithmParameters.mutationRate = std::stod(getValueFromPassedCommand("mutationRate"));
}
}

void Parser::setNumberOfIterationsParameterFromInput()
{
if (isCommandPassed("numberOfIterations"))
{
geneticAlgorithmParameters.numberOfIterations = std::stoi(getValueFromPassedCommand("numberOfIterations"));
}

}

void Parser::setNumberOfPointsFromInput()
{
if (isCommandPassed("numberOfPoints"))
{
geneticAlgorithmParameters.numberOfPoints = std::stoi(getValueFromPassedCommand("numberOfPoints"));
}
}

void Parser::setPercentageOfChildrenFromPreviousGeneration()
{
if (isCommandPassed("percentageOfChildrenFromPreviousGeneration"))
{
geneticAlgorithmParameters.percentageOfChildrenFromPreviousGeneration = std::stod(
getValueFromPassedCommand("percentageOfChildrenFromPreviousGeneration"));
}
}

bool Parser::isRandomModeEnabled() const
{
return isCommandPassed("random");
}

bool Parser::isCommandPassed(std::string_view command) const
{
return std::any_of(std::begin(arguments), std::end(arguments), [command](const auto &elem)
{ return elem.find(command) != std::string::npos; });
}

std::string Parser::getPassedFilePath() const
{
return getValueFromPassedCommand("file");
}

void Parser::printHelpOptions() const
{
std::cout << "Travelling Salesman Problem solved by Genetic Algorithm " << '\n' <<
"Options:" << '\n' <<
"--help           Print this help" << '\n' <<
"--sizeOfPopulation=<int>    Pass size of population" << '\n' <<
"--mutationRate=<double>     Pass mutation rate" << '\n' <<
"--numberOfIteration=<int>   Pass number of iterations" << '\n' <<
"--random   Pass this flag to use randomly generated points" << '\n' <<
"--file=pathToFile  Pass path to file which will be used as points in algorithm" << '\n' <<
"--numberOfPoints=<int> Pass numberOfPoints which will be used from file or randomly generated" << '\n' <<
"--percentageOfChildrenFromPreviousGeneration=<double> Pass which percentage best from previous generation will be included"
<< '\n';
}


Path.cpp

#include <PointInitializer.hpp>
#include <cmath>
#include <algorithm>

Path::Path(std::vector<Point> path) : path(std::move(path))
{
if (this->path.size() <= 1)
{
throw std::invalid_argument("Number of points in Path should be greater than 1");
}

fitness = calculateFitness();
}

double Path::getFitness() const
{
return fitness;
}

std::vector<Point> Path::getPath() const
{
return path;
}

void Path::mutate(int lowerBound, int upperBound)
{
std::swap(path[lowerBound], path[upperBound]);
}

std::vector<Point> Path::crossover(const Path &parent) const
{
std::vector<Point> child;
child.reserve(path.size());
int halfOfSize = path.size() / 2;

std::copy_n(std::begin(path), halfOfSize, std::back_inserter(child));

for (auto const &elem : parent.path)
{
if (std::find(child.begin(), child.end(), elem) == child.end())
{
child.emplace_back(elem);
}
}

child.emplace_back(path[0]);

return child;
}

double Path::calculateFitness() const
{
auto sum = 0.0;

for (size_t i = 0; i < path.size() - 1; ++i)
{
sum += sqrt(pow(path[i].x - path[i + 1].x, 2.0) + pow(path[i].y - path[i + 1].y, 2.0));
}

return sum;
}


Plotter.cpp

#include "Plotter.hpp"

Plotter::Plotter(int imageHeight, int imageWidth) : imageWidth(imageWidth), imageHeight(imageHeight)
{
image = cv::Mat::zeros(imageHeight, imageWidth, CV_8UC3);
}

void Plotter::drawPoints(const std::vector<Point> &points) const
{
for (size_t i = 0; i < points.size() - 1; ++i)
{
cv::line(image, cv::Point(points[i].x, points[i].y), cv::Point(points[i + 1].x, points[i + 1].y),
cv::Scalar(0, 255, 0));
}

for (const auto &point : points)
{
cv::circle(image, cv::Point(point.x, point.y), 3.0, cv::Scalar(255, 255, 255), cv::FILLED, 8);
}

cv::imshow("TSP", image);
cv::waitKey(0);
}


Population.cpp

#include "Population.hpp"
#include <algorithm>
#include <iterator>

Population::Population(const GeneticAlgorithmParameters &geneticAlgorithmParameters,
std::shared_ptr<PointInitializer> initializer) :
geneticAlgorithmParameters(geneticAlgorithmParameters),
initializer(std::move(initializer))
{
if (geneticAlgorithmParameters.sizeOfPopulation <= 0)
{
throw std::invalid_argument("sizeOfPopulation must be greater than 0");
}

population.reserve(geneticAlgorithmParameters.sizeOfPopulation);
historyOfLearning.reserve(geneticAlgorithmParameters.numberOfIterations);
createAllInitialSolutions();
bestSolution = getBestSolutionInCurrentPopulation();
saveActualScore(getBestSolutionFitness());
}

Path Population::getBestSolutionInCurrentPopulation() const
{
return *std::min_element(population.begin(),
population.end(),
[](const auto &lhs, const auto &rhs)
{
return lhs.getFitness() < rhs.getFitness();
});

}

void Population::runAlgorithm()
{
for (auto i = 0; i < geneticAlgorithmParameters.numberOfIterations; ++i)
{
updatePopulation();
}
}

void Population::createAllInitialSolutions()
{
auto rng = std::default_random_engine{};
std::vector<Point> initialSolution = initializer->getInitialPoints(geneticAlgorithmParameters.numberOfPoints);

for (auto i = 0; i < geneticAlgorithmParameters.sizeOfPopulation; ++i)
{
std::shuffle(std::begin(initialSolution), std::end(initialSolution), rng);
std::vector<Point> temp(initialSolution);
temp.emplace_back(temp[0]);

population.emplace_back(temp);
}
}

int Population::getRandomNumberInRange(int lowerBound, int upperBound)
{
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<> distr(lowerBound, upperBound);

return distr(eng);
}

Path Population::performTournamentSelection()
{
auto firstRandomNumber = getRandomNumberInRange(0, population.size() - 1);
auto secondRandomNumber = getRandomNumberInRange(0, population.size() - 1);

return std::min(population[firstRandomNumber], population[secondRandomNumber], [](const auto &lhs, const auto &rhs)
{ return lhs.getFitness() < rhs.getFitness(); });
}

{
std::vector<Path> temp = population;
std::sort(std::begin(temp), std::end(temp), [](const auto &lhs, const auto &rhs)
{ return lhs.getFitness() > rhs.getFitness(); });

}

void Population::mutation()
{
for (auto &elem : population)
{
if (getRandomNumberInRange(0, 1) < geneticAlgorithmParameters.mutationRate)
{
elem.mutate(getRandomNumberInRange(1, geneticAlgorithmParameters.numberOfPoints - 1),
getRandomNumberInRange(1, geneticAlgorithmParameters.numberOfPoints - 1));
}
}
}

void Population::updatePopulation()
{
std::vector<Path> newPopulation;
newPopulation.reserve(geneticAlgorithmParameters.numberOfPoints);

int numberOfChildrenFromParents =
int(geneticAlgorithmParameters.sizeOfPopulation *
geneticAlgorithmParameters.percentageOfChildrenFromPreviousGeneration) / 2;

for (auto i = 0; i < numberOfChildrenFromParents; ++i)
{
Path firstParent = performTournamentSelection();
Path secondParent = performTournamentSelection();

newPopulation.emplace_back(firstParent.crossover(secondParent));
newPopulation.emplace_back(secondParent.crossover(firstParent));
}

numberOfChildrenFromParents * 2);

population = newPopulation;

mutation();
checkForBetterSolution();
}

void Population::checkForBetterSolution()
{
auto bestSolutionInCurrentPopulation = getBestSolutionInCurrentPopulation();
saveActualScore(bestSolutionInCurrentPopulation.getFitness());
if (bestSolutionInCurrentPopulation.getFitness() < bestSolution->getFitness())
{
bestSolution = bestSolutionInCurrentPopulation;
bestSolutionNumber = historyOfLearning.size();
}
}

std::vector<Point> Population::getBestSolutionPath() const
{
return bestSolution->getPath();
}

double Population::getBestSolutionFitness() const
{
return bestSolution->getFitness();
}

std::vector<double> Population::getHistoryOfLearning() const
{
return historyOfLearning;
}

void Population::saveActualScore(double bestSolution)
{
historyOfLearning.emplace_back(bestSolution);
}

int Population::getNumberOfBestSolution() const
{
return bestSolutionNumber;
}


Genetic_TSP.cpp

#include "Population.hpp"
#include <algorithm>
#include <Plotter.hpp>
#include <Parser.hpp>
#include <RandomPointInitializer.hpp>
#include <FilePointInitializer.hpp>

void start(std::shared_ptr<PointInitializer>, const GeneticAlgorithmParameters&, int, int);

int main(int argc,  char* argv[])
{
Parser parser(std::vector<std::string>(argv+1, argv + argc));
auto parserAlgorithmParameters = parser.validateInput();

auto imageWidth = 1700;
auto imageHeight = 1000;

if(not parserAlgorithmParameters)
{
return 0;
}

if (parser.isRandomModeEnabled())
{
start(std::make_shared<RandomPointInitializer>(imageHeight, imageWidth), *parserAlgorithmParameters, imageHeight, imageWidth);
}
else
{
start(std::make_shared<FilePointInitializer>(parser.getPassedFilePath()), *parserAlgorithmParameters, imageHeight, imageWidth);
}

return(0);
}

void start(std::shared_ptr<PointInitializer> pointInitializer, const GeneticAlgorithmParameters& geneticAlgorithmParameters, int imageHeight, int imageWidth)
{
Population population(geneticAlgorithmParameters, std::move(pointInitializer));

population.runAlgorithm();

auto result = population.getBestSolutionPath();

Plotter plotter(imageHeight, imageWidth);
plotter.drawPoints(result);
}


Edit: I have .hpp files in directory "include" and source files in directory "src".

I am adding slightly modified CMakeLists.txt which I use in Clion. I also set in CLion program arguments as --random

cmake_minimum_required(VERSION 3.10)
project(TSP_FINAL)

set(CMAKE_CXX_STANDARD 17)

set(GCC_COVERAGE_COMPILE_FLAGS "-Wall -Weffc++ -Wextra ")

find_package( OpenCV REQUIRED )
include_directories( ${OpenCV_INCLUDE_DIRS} ) include_directories(include) file(GLOB TSP_SRC "src/*.cpp" ) add_executable(tsp${TSP_SRC})

set_target_properties(tsp
PROPERTIES COMPILE_FLAGS ${GCC_COVERAGE_COMPILE_FLAGS}) target_link_libraries(tsp${OpenCV_LIBS} )

• Can you provide an example invocation (i.e. show some reasonable command-line arguments, and any necessary file inputs), so that we run a good example? Aug 9, 2018 at 9:43

There seems to be an error in this function (Parser.cpp):

std::string Parser::getValueFromPassedCommand(std::string_view command) const
{
for (const auto &elem : arguments)
{
if (elem.find(command) != std::string::npos)
{
return elem.substr(elem.find('=') + 1);
}
}
}


There is a missing return statement here. There is also an inconsistency with the way variables are initialized, sometimes with = xx, sometimes with {xx}. I would also remove all the default initializers (empty {}) as these are redundant and flagged by rules in clang-tidy. Still a nice job and seems like a good usage of C++17 functionalities.