Skip to content

Final project and assignments of Parallel and Distributed Systems: Paradigms and Models course

Notifications You must be signed in to change notification settings

FraCorti/TSP-GeneticAlgorithm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

53 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

TSP with Genetic Algorithms

The purpose of the project was to solve Travelling Salesman Problem, known as TSP, by using a Genetic Algorithms approach and exploit parallelism. In addition to the sequential version used as a baseline, two parallel versions were developed, one using standard C++ threads and one using Fastflow. More information about the project and the design of the parallel versions can be found in the report.

To test the correctness of the three versions developed, I saved for a run of each version the current best route for each generation of the algorithm. In the following plots the length of the best path decrease as the algorithm goes on with the generation, so convergence algorithms were obtained.

Running the project

The project can be compiled and executed using Cmake 3.11 or GCC (remember to turn on -O3 optimization).

If CMake is installed type: mkdir build && cd build

Then (if you want to use Debug build type add -DCMAKE_BUILD_TYPE=Debug at the end) type: cmake ..

Now to build the project type: cmake --build .

Otherwise, to use GCC use:

g++ -std=c++17 -O3 main.cpp -o GeneticTSP -pthread

To run the program correctly, you need to pass to the executable the following parameters:

./GeneticTSP nodesNumber chromosomesNumber generationNumber mutationRate crossoverRate workersNumber [seed]

Results

Each version of the program was tested on an Intel Xeon PHI machine from 1 to 256 thread. The tests were done with 10 generation and 20000 chromosomes and considering [500, 1000, 2000] nodes in the graph. The following speedup curves were obtained:



Acknowledgments

This project was developed for the course of Parallel and Distributed Systems at the University of Pisa under the guide of Prof. Marco Danelutto and Prof. Massimo Torquati.

About

Final project and assignments of Parallel and Distributed Systems: Paradigms and Models course

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published