Problem description - Kelleth/pyage-aco-solver GitHub Wiki
The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science - Wikipedia
In this ACO algorithm implementation, each ant gets a randomly chosen start city. Beginning from this city, the ant chooses the next city according to its path attractiveness. After visiting all cities exactly once, ant finishes his trip and returns found path as proposal solution. The ants travel in sequence, but order is random. Each ant deposits some amount of specific for its kind pheromone on path depending on found solution distance. After each iteration (after all ants finish trip), pheromone lying on path starts to evaporate.
Different ants use different rules (consider different path's properties) for computing path attractiveness.
- Iteration starts with shuffling ants which guarantees random order in each iteration
- Ants begin trip seuqentialy, by choosing random start city
- Each ant after finish trip, updates pheromone on path
- When colony finishes the trip, all pheromones are updated according to evaporation formula
The first step in determining the next city is computing attractiveness values for all available paths from actual city. To avoid local minimum, we convert those values to probabilities. Then ant randomly chooses city - paths with higher attractiveness are more likely.
Pheromone consists of different 'smells':
- AtercentricAnt pheromone
- EgocentricAnt pheromone
- GoodConflictAnt pheromone
- BadConflictAnt pheromone
- unclassified pheromone - for all other ants
Total pheromone is sum of all those component pheromones.
The ants update only pheromone specific for its kind in computed path just after finishing trip
ant_pheromone = ant_pheromone + pheromone_deposit / path_total_ditance
Default pheromone_deposit is 1
After all ants complete iteration, evaporation is applied to all paths in graph:
pheromone = (1 - pheromone_evaporation_coefficient) * pheromone
Default pheromone_evaporation_coefficient is 0.1
Consider both pheromone and distance while choosing path
Path attractiveness (total_pheromone ^ pheromone_influence) * (1 / distance ^ distance_influence)
Default factors used by ant:
- pheromone_influence = 2.0
- distance_influence = 3.0
The individuals who are "egocentric" would be more creative to try to find a new solution, finding their own way, less caring for others and for pheromone trail
Path attractiveness (1 / distance) ^ distance_influence
Default factors used by ant:
- distance_influence = 3.0
The individuals who are "altercentric" would follow the mass
Path attractiveness pheromone ^ pheromone_influence
Default factors used by ant:
- pheromone_influence = 2.0
These good at conflict handling will wait and observe the others
Path attractiveness ((14 * egocentric_pheromone + 2 * altercentric_pheromone + 2.5 * good_conflict_pheromone + 0.5 * bad_conflict_pheromone) / 4) ^ pheromone_influence
Default factors used by ant:
- pheromone_influence = 2.0 Branch good_at_conflict_factors allows to set factors for each pheromone with command line arguments or to set them randomly for each ant (no global settings)
Those bad at conflict handling will behave impulsively (in effect randomly)
They just choose path randomly irrespective of pheromone and distance
- Classic Ant - contains only classic ant
- Control Sample
- 22% egocentric
- 15% altercentric
- 45% good conflict
- 18% bad conflict
- High Altercentricity Condition
- 3% egocentric
- 46% altercentric
- 23% good conflict
- 28% bad conflict
- Low Altercentricity Condition
- 6% egocentric
- 6% altercentric
- 63% good conflict
- 25% bad conflict
- Parametrized Colony Sample
- completely configured with command line arguments
Instead of defining populations with specific number of ants of each type we introduced a solution where we start with all ants of one type, and in certain situations they can evolve into another ant type. We specified hierarchy of ant types into levels, in a way that the bigger level of ant type the smarter it is (it takes into account more information during choosing next path). So we have 5 levels:
- Level 0 - Bad at conflict handling ants
- Level 1 - Egocentric ants
- Level 2 - Altercentric ants
- Level 3 - Classic ants
- Level 4 - Good at conflict handling ants
Evolving_ants branch introduces solution where all ants start with level 0, and with some probabilities they can evolve into smarter ants when they are not finding better paths, or they can evolve into dumber ants when they are doing good (this ensures some deviation preventing from "need" of ants to become smartest and reaching some local extremum)