This repository contains several parallel implementations of a genetic algorithm for the Travelling Salesman Problem (TSP). For detailed information about the project, see report.pdf.

The project contains a Makefile to produce the executables and the object files of the project. Running make all will be enough to get everything ready. To replicate the same experiments and plots in the report, run make exp. If you need to, remember to change the algorithm parameters at the start of the script experiment.sh (default: experiment with 3000 individuals).

Most of the executables need a .csv file containing the representation of the input graph. The file representing the graph used in the experiments is already contained in the project directory (complete.csv). To create a new complete graph with n nodes and random weights in graph.csv, run:

./csv graph.csv n

To test every genetic algorithm against the bruteforce algorithm, run the script test.sh. To test the sequential version, execute:

./tspseq complete.csv 1000 0.9 0.1 20 123

To run a parallel version, for example the ParallelFor one, run:

./tsppar_fffor complete.csv 1000 0.9 0.1 20 4 123

To replicate the complete experiment, run the bash script experiment.sh as follows:

bash experiment.sh exp_dir 0,1,2,3,4 1 4 64 123

Again, if you need to, remember to change the algorithm parameters placed at the start of the script.

To produce plots, use the python script as follows:

python3 data_analysis.py exp_dir

where exp_dir is the output directory of the script experiment.sh.