-
Notifications
You must be signed in to change notification settings - Fork 2
Problem description
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
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