TravellingAnts implements the ant colony optimisation algorithm for solving the travelling salesman problem. This is a fork from [https://github.com/hakuch/TravellingAnts], the original author is Jesse Haber-Kucharsky. All changes to the original code published under the original license (MIT). The changes include:
- use Scala 2.12, drop sbt plugins
- drop scalaz dependency
- slight code reformatting
- put code into package
de.sciss.ants - abstract classes changed for final classes
- demo app is in test sources, thus run
sbt test:runinstead ofsbt runs - bug fixes
- publish as library (see section 'linking')
To link to this library:
"de.sciss" %% "travelling-ants" % v
The current version v is "0.1.1".
This project builds against Scala 2.12, 2.11, using sbt.
To run the demo, use sbt test:run.
TravellingAnts is an implementation of the Ant Colony meta-heuristic optimization algorithm (specifically, Ant System) for solving the travelling salesmen problem.
The repository includes a library for solving arbitrary graphs and also includes a specific example.
The code is intended to be clear and modular. Ants are launched concurrently to improve execution speed. The solver provides call-backs for listening to the running computation rather than hard-coding loggers.
A comparison of the mean cost of each ant's solution per iteration to the overall cumulative best solution as the algorithm progress:
The best solution from the run above:
TravellingAnts is written in Scala. It requires that sbt is installed.
To execute the solver on the example solution and save the solution in the DOT format, execute:
$ sbt --warn run > output.dotIntermediate progress is printed to the standard error device (stderr) and also to a log file (travelling-ants.log) in comma-separated value (CSV) format suitable for analysis.
To produce a visual image of the resulting solution, you can use neato from the grapviz suite of programs:
$ neato -Tpng output.dot > output.png