Ant Colony Optimization for TSP
This is the improved version based on the copy from http://www.aco-metaheuristic.org/aco-code, ACOTSP.V1.03.tgz Follow ACO variants are support:
- Basic ACO;
- Elite ACO;
- Rank-based ACO;
- Max-min ACO;
- Best-worest ACO;
- Ant Colony System(ACS);
- Levy Flight ACO;
- Contribution-based ACO; Based on our experiments, The performance sequence is ACS > Rank-based ACO > Max-min ACO > Elite ACO > Basic ACO > Best-worest ACO; Levy Flight ACO and Contribution-base ACO can improve above ACOs.
Improved points:
- Add Function to output optimization result for acotsp in CSV format which is easy for later anaylse.
- Add Improved Function for candidators selection mechanism of Levy Flight;
- Add Improved Function for pheromone update logic based on the contribution of each arc in the solution.
Usage:
- Basic parameters is similar with original acotsp, please run acotsp --help for details.
- For Levy Flight ACO, parameters -L x:y is used. x means Levy Flight Threshold which value between 0 to 1, suggest value is 0.8-0.9; y means Levy Flight Alter Ratio great than 0, suggest value is 4; please run acotsp --help for details with Levy Flight;
- For Contribution-based ACO, parameter -C x is used. x means Contribution effect alter ratio, suggest value is 4.
- Usage for acotsp please refer the demo shell file in shell directory. run.bat is used for Windows/Dos; run.sh is used for Linux;
Directories:
- src: source of c for acotsp;
- shell: running script for Windows/Linux;
- tsp: TSP instances for acotsp to run, please refer the files in shell directory.
Instructor for running ACOTSP
- Clone by git to get the source code of this project;
- Download or install gcc for the computer based on its OS. For windows, https://sourceforge.net/projects/mingw-w64-builds/ is suggested, and mingw or mingw64 is alternative options for experienced users. For linux, gcc is needed, run sudo apt-get g++ or sudo apt-get build-essential in Ubuntu, other Linux please refer the manual.
- Complie the source code in src directory; mingw32-make -f makefile_dos For Windows; make -f makefile_linux for Linux;
- Copy or Modify the run script file; run.bat for Windows; run.sh for Linux;
- Edit the run script before run;
- Update the TSP instance and its optimal result, which can get from https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/STSP.html
- Run the scipt and analyst the output file in CSV files whose name in the run script;