4
\$\begingroup\$

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} )
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Toby Speight Aug 9 '18 at 9:43
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.