Travelling salesman problem using genetic algorithm in C++

Question

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 addBestPathsFromPreviousPopulationToNextPopulation(std::vector<Path> &, int) const;
    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(); });
}


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

    std::copy_n(std::begin(population), howManyPathFromOldPopulationToAdd, std::back_inserter(newPopulation));
}

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));
    }

    addBestPathsFromPreviousPopulationToNextPopulation(newPopulation, geneticAlgorithmParameters.sizeOfPopulation -
                                                                      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} )

Answer 1

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.