1 Introduction
2 Environmental model
3 Ant colony algorithm
3.1 Ant colony optimization algorithm
-
Step 1: Initialize the relevant parameters, including ant colony size, pheromone factor, heuristic function factor, pheromone volatilization factor, pheromone constant and maximum number of iterations
-
Step 2: And reading the data into the program and pre-processing: for example, converting the city’s coordinate information into a distance matrix between cities
-
Step 3: Randomly place the ants at different starting points and calculate the next visiting city for each ant until there are ants accessing all the cities
-
Step 4: Calculate the path length of each ant, record the optimal solution of the current iteration number, and update the pheromone concentration on the path
-
Step 5: Determine whether the maximum number of iterations is reached. If not, return to step 2 or end the program.
-
Step 6: Output the result, and output relevant indicators in the optimization process, such as running time, convergence iteration number, etc., as needed.
3.2 Ant colony algorithm with punitive measures
4 Performance test
4.1 Data set
Question | Description | Optimal solution |
---|---|---|
ulyeese | Odyssey of Ulysses(Groetschel/Padberg) | 74 |
Att48 | 48 capitals of the US (Padberg/Rinaldi) | 33,522 |
Eil76 | 76-city problem (Christofides/Eilon) | 538 |
4.2 Parameter settings
Algorithm | Algorithm parameter settings |
---|---|
PSO | The problem size is n, the number of ants is m = n, and other variables are set according to the classical algorithm guidance. |
GA | |
ASrank | |
MMAS | |
AS-N | The problem size is n, the number of ants M = N α = 2, β = 8, ρ = 0.02, W = 5 |
4.3 Analysis of results
ASrank | GA | PSO | MMAS | AS-N | ||
---|---|---|---|---|---|---|
ulyees | Average value | 76.6355 | 76.5267 | 76.5355 | 76.1533 | 75.8746 |
Maximum | 78.4533 | 77.2298 | 77.4509 | 77.4575 | 76.0355 | |
Minimum | 75.3625 | 75.9035 | 75.9843 | 75.3672 | 75.1283 | |
Att48 | Average value | 33,864.65 | 33,821.96 | 32,268.86 | 33,751.98 | 33,728.76 |
Maximum | 34,139 | 34,684 | 34,218 | 34,375 | 34,092 | |
Minimum | 33083 | 33,187 | 33,201 | 33,548 | 33,529 | |
Eil76 | Average value | 572.66 | 574.63 | 570.98 | 567.9876 | 560.87 |
Maximum | 589.43 | 590.86 | 588.42 | 584.87 | 573.54 | |
Minimum | 564.87 | 564.87 | 562.64 | 549.76 | 548.82 |