https://github.com/cptanalatriste/aco-tsp
Solving the Travelling Salesman problem with Ant Colony Algorithms, using the Isula Framework
Science Score: 13.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
✓codemeta.json file
Found codemeta.json file -
○.zenodo.json file
-
○DOI references
-
○Academic publication links
-
○Committers with academic emails
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (10.5%) to scientific vocabulary
Keywords
Repository
Solving the Travelling Salesman problem with Ant Colony Algorithms, using the Isula Framework
Basic Info
- Host: GitHub
- Owner: cptanalatriste
- Language: Java
- Default Branch: master
- Size: 36.1 KB
Statistics
- Stars: 8
- Watchers: 2
- Forks: 2
- Open Issues: 0
- Releases: 0
Topics
Metadata Files
README.md
aco-tsp
A Java Program that solves the Travelling Salesman Problem using the Ant System algorithm. The algorithm details and configuration where taken from in Section 6.3 of the Clever Algorithms book by Jason Brownlee.
In the same fashion as the book, we use the berlin52 instance from TSPLIB as a testbed for the program.
The Ant-Colony Algorithm
This program uses a classic Ant System approach with some peculiarities for the Travelling Salesman Problem described in the book. To implement this algorithm, we use the Isula Framework.
```java double[][] problemRepresentation = getRepresentationFromFile(fileName);
ProblemConfiguration configurationProvider = new ProblemConfiguration(problemRepresentation);
AntColony<Integer, TspEnvironment> colony = getAntColony(configurationProvider);
TspEnvironment environment = new TspEnvironment(problemRepresentation);
AcoProblemSolver<Integer, TspEnvironment> solver = new AcoProblemSolver<>();
solver.initialize(environment, colony, configurationProvider);
solver.addDaemonActions(new StartPheromoneMatrix<Integer, TspEnvironment>(),
new PerformEvaporation<Integer, TspEnvironment>());
solver.addDaemonActions(getPheromoneUpdatePolicy());
solver.getAntColony().addAntPolicies(new RandomNodeSelection<Integer, TspEnvironment>());
solver.solveProblem();
``
The implemented process has the following characteristics:
* The initial value of the cells of the pheromone matrix is a function of the number of cities in the problem instance and the quality of a random solution. See theProblemConfiguration` class for more details.
* The evaporation ratio for the algorithm is 0.4 as described in the book. When all the ants have finished building their solutions, they deposit pheromone in the corresponding cells of the pheromone matrix it in a quantity proportional to the solution quality.
* The Ants use the Random Proportional Rule for selecting solution components while traversing the problem graph, as it corresponds on an Ant System algorithm.
The results
For the berlin52 problem instance, the optional solution has a total distance of 7542 units. Under the current configuration, the solutions produced by the algorithm are around 7795 after an execution time of 1.5 seconds.
How to use this code
The code uploaded to this GitHub Repository corresponds to a Maven Java Project. As such, it is strongly recommended that you have Maven installed before working with it.
This project depends on the Isula Framework. Follow the instructions available in https://github.com/cptanalatriste/isula
Keep in mind that several file and folder locations were configured on the AcoTspWithIsula.java file. You need to set values according to your environment in order to avoid a FileNotFoundException. Once this is ready, you can launch this project by executing mvn exec:java -Dexec.mainClass="tsp.isula.sample.AcoTspWithIsula" from the project root folder.
More about Isula
Visit the Isula Framework site: http://cptanalatriste.github.io/isula/
Review the Isula JavaDoc: http://cptanalatriste.github.io/isula/doc/
Questions, issues or support?
Feel free to contact me at carlos.gavidia@pucp.edu.pe.
Owner
- Name: Carlos Gavidia-Calderon
- Login: cptanalatriste
- Kind: user
- Location: London, United Kingdom
- Company: @alan-turing-institute
- Website: https://carlos.gavidia.me/
- Twitter: cptan_alatriste
- Repositories: 74
- Profile: https://github.com/cptanalatriste
Systems engineer by training, software developer by trade. Research Software Engineer at @alan-turing-institute .
GitHub Events
Total
Last Year
Committers
Last synced: 7 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| Carlos G. Gavidia | c****c@g****m | 37 |
Issues and Pull Requests
Last synced: 7 months ago
All Time
- Total issues: 0
- Total pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Total issue authors: 0
- Total pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0