Аннотация: Исследовано применение трех метаэвристических алгоритмов для решения задачи коммивояжера: имитации отжига, табу поиска и муравьиной колонии. Проведены экспериментальные исследования производительности программной реализации алгоритмов на четырех тестовых задачах коммивояжера с известными оптимальными маршрутами. В результате эксперимента оценены характеристики решений, найденных каждым из алгоритмов в серии измерений за одинаковое фиксированное количество времени. Детально описаны использованные в эксперименте параметры алгоритмов и особенности реализации. Визуализирован процесс оптимизации каждым из алгоритмов. Сделаны выводы об эффективности исследованных алгоритмов для разных размеров задач, использованных в эксперименте.
Ключевые слова: задача коммивояжера, метаэвристические алгоритмы оптимизации, алгоритм имитации отжига, алгоритм табу поиска, алгоритм муравьиной колонии.
Technical sciences
УДК 519.6, 519.8
Ткаченко Дмитро Анатолійович
студент
Національний технічний університет України
«Київський політехнічний інститут»
Ткаченко Дмитрий Анатольевич
студент
Национальный технический университет Украины
«Киевский политехнический институт»
Tkachenko D.A.
student
National Technical University of Ukraine
«Kyiv Polytechnic Institute»
ПОРІВНЯЛЬНЕ ДОСЛІДЖЕННЯ ДЕЯКИХ МЕТАЕВРИСТИЧНИХ АЛГОРИТМІВ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ КОМІВОЯЖЕРА
СРАВНИТЕЛЬНОЕ ИССЛЕДОВАНИЕ НЕКОТОРЫХ МЕТАЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
A COMPARATIVE STUDY OF SOME METAHEURISTIC ALGORITHMS FOR SOLVING TRAVELLING SALESMAN PROBLEM
Анотація:
Досліджено застосування трьох метаевристичних алгоритмів для розв’язання задачі комівояжера: імітації відпалу, табу пошуку та мурашиної колонії. Проведено експериментальні дослідження продуктивності програмної реалізації алгоритмів на чотирьох тестових задачах комівояжера з відомими оптимальними маршрутами. В результаті експерименту оцінені характеристики розв’язків, отриманих кожним алгоритмом в серії вимірів за однакову фіксовану кількість часу. Детально описано застосовані в експерименті параметри алгоритмів і особливості реалізації. Візуалізовано процес оптимізації кожним із алгоритмів. Зроблено висновки щодо ефективності досліджених алгоритмів для різних розмірів задач, використаних у експерименті.
Аннотация:
Исследовано применение трех метаэвристических алгоритмов для решения задачи коммивояжера: имитации отжига, табу поиска и муравьиной колонии. Проведены экспериментальные исследования производительности программной реализации алгоритмов на четырех тестовых задачах коммивояжера с известными оптимальными маршрутами. В результате эксперимента оценены характеристики решений, найденных каждым из алгоритмов в серии измерений за одинаковое фиксированное количество времени. Детально описаны использованные в эксперименте параметры алгоритмов и особенности реализации. Визуализирован процесс оптимизации каждым из алгоритмов. Сделаны выводы об эффективности исследованных алгоритмов для разных размеров задач, использованных в эксперименте.
Summary:
Application of the following three metaheuristic algorithms to Travelling Salesman Problem (TSP) were explored: Simulated Annealing (SA), Tabu Search (TS), and Ant Colony System (ACS). The performance of software implementation of these approaches was experimentally studied using four test instances of TSP with known optimal solutions. As a result of the experiment, features of solutions found in a set of trials by each algorithm in the same fixed amount of time were assessed. The implementation details of the algorithms and the parameters used for the experiment were thoroughly described. Optimization process was visualized for every algorithm. Conclusions were made regarding the effectiveness of studied algorithms for the different sizes of problem instances used in the experiment.
Ключові слова: задача комівояжера, метаевристичні алгоритми оптимізації, алгоритм імітації відпалу, алгоритм табу пошуку, алгоритм мурашиної колонії.
Ключевые слова: задача коммивояжера, метаэвристические алгоритмы оптимизации, алгоритм имитации отжига, алгоритм табу поиска, алгоритм муравьиной колонии.
Key words: travelling salesman problem, metaheuristic optimization algorithms, simulated annealing algorithm, tabu search algorithm, ant colony system algorithm.
Introduction
Travelling Salesman Problem (TSP) [1] has many applications in different fields. In its classical formulation, this problem appears in logistics, planning, and microchip manufacturing. Also this NP-hard [2] problem is a very popular testbed for various combinatorial optimization algorithms. The high computational complexity of seeking an optimal tour in TSP has facilitated the development of many heuristic and metaheuristic algorithms. Such algorithms are widely used because they can find a solution that is very close to the optimal solution, even for problems with very large numbers of cities [3].
The purpose of this paper is to explore the application of the following three metaheuristic algorithms to the Travelling Salesman Problem (TSP): Simulated Annealing (SA), Tabu Search (TS) and Ant Colony System (ACS). Another objective is to experimentally determine the algorithm that is able to produce the best solution when given some constant amount of computational resources.
Problem formulation
TSP is the problem of finding the shortest closed tour through a given set of cities, when distances between them are known, in such a way that each city is visited exactly once and the tour ends at the start city. In other words, the task is to find a Hamiltonian cycle with the least weight, given a complete weighted graph.
Simulated Annealing algorithm
Description. Simulated Annealing algorithm [4], [5] consists of the following steps:
This algorithm is inspired by annealing in metallurgy. Annealing is the process of heating and controlled cooling of a system.
The key to this algorithm is in Step 3. The higher the system temperature, greater is the probability of accepting the worse candidate tour. This probability decreases as the system cools down. The point of accepting the longer tour is to try to avoid getting stuck in a local minimum.
Pseudocode:
Input: numberOfCities, timemax, T0
Output: Sbest
Scurrent = createRandomTour(numberOfCities)
Sbest = Scurrent
timestart = currentTime()
i = 0;
while currentTime() – timestart < timemax
Si = generateNeighborSolution(Scurrent)
Tcurrent = calculateTemperature(i, T0)
if cost(Si) <= cost(Scurrent)
Scurrent = Si
if cost(Si) <= cost(Sbest)
Sbest = Si
end
else if exp((cost(Scurrent) – cost(Si)) / Tcurrent) > rand(0, 1)
Scurrent = Si
end
++i
end
return Sbest
Parameters: Initial temperature ( ) and cooling schedule.
Implementation details. The following cooling schedule is used:
Neighbour solution is created using the Stochastic 2-opt algorithm [6], which picks two random indices and in such a way that and , and then reverses the city order in the tour in interval.
Tabu Search algorithm
Description. This algorithm [7]–[9] can be described as a sequence of the following steps:
The key to this approach is to prevent the search procedure from repeatedly checking the same areas of a search space.
Pseudocode:
Input: numberOfCities, timemax, tabuListSizemax ( ), numberOfCandidates ( )
Output: Sbest
Scurrent = createRandomTour(numberOfCities)
Sbest = Scurrent
tabuList = createEmptyList(tabuListSizemax)
timestart = currentTime()
while currentTime() – timestart < timemax
candidateList = []
for j = 1 to numberOfCandidates
candidate = generateNeighborSolution(Scurrent, tabuList);
candidateList.add(candidate)
end
bestCandidate = findBestCandidate(candidateList)
if cost(bestCandidate) < cost(Scurrent)
Scurrent = bestCandidate
if cost(bestCandidate) < cost(Sbest)
Sbest = bestCandidate
end
tabuList.add(features(bestCandidate))
while size(tabuList) > tabuListSizemax
removeLastEntry(tabuList)
end
end
end
return Sbest
Parameters. Maximum size of tabu list ( ) and the number of candidates generated in Step 2 ( ).
Implementation details. Candidate tours in Step 2 are generated using Stochastic 2-opt algorithm, as before.
Tabu features are the edges between the cities and . On Step 4, edges (from the tour which is modified by Stochastic 2-opt procedure) between cities and , and between and are added to the tabu list.
Ant Colony System algorithm
Description. This algorithm [10], [11] is initialised in the same way as before. Then the following actions are performed during each iteration:
The key to this algorithm is to exploit both history (information about explored tours) and heuristic information (coefficient inversely proportional to edge length).
Pseudocode:
Input: numberOfCities, timemax, numberOfAnts ( ), decayFactor ( ), heuristicCoef ( ), historyCoef ( ), localCoef ( ), greedinessFactor ( )
Output: Sbest
Sbest = createRandomTour(numberOfCities)
initialPheromone = 1.0 / (numberOfCities * cost(Sbest))
pheromone = initialisePheromoneMatrix(initialPheromone)
timestart = currentTime()
while currentTime() – timestart < timemax
for i = 1 to numberOfAnts
candidate = constructStepwise(pheromone, numberOfCities, historyCoef, heuristicCoef, greedinessFactor)
if cost(candidate) < cost(Sbest)
Sbest = candidate
end
localUpdatePheromone(pheromone, candidate, localCoef, initialPheromone)
end
globalUpdatePheromone(pheromone, Sbest, decayFactor)
end
return Sbest
Parameters:
Implementation details. The greediness factor determines when to use the probabilistic Roulette Wheel Selection method and when to greedily choose the tour with highest value ( represents the pheromone for the edge ; , where is the distance between cities and ). When Roulette Wheel Selection is used, the probability of picking a candidate is proportionate to , where is the number of cities.
A local pheromone trail update (for each ant) is performed according to the following expression:
, where is the initial pheromone value.
At the end of each iteration, pheromone trail is updated and decayed according to the best solution found so far, as follows:
, where is the length of the best tour.
Experiment
The performances of the described algorithms were compared using four TSP instances with the known optimal solutions from TSPLIB, accessible at http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/. On the specific problem instance, each algorithm was run for the same fixed amount of time. 50 trials were performed for each problem and algorithm.
Results are presented in Table 1.
Table 1
Experiment results
Parameters used by each algorithm for the certain problem are given in Table 2.
Table 2
Parameters of the algorithms
The parameters of the algorithms were chosen according to [4], [5], [7]–[11]. The number of ants in ACS were adjusted in such a way that enough iterations (>20) were performed on each trial to show the effect of exploiting search history. In SA, initial temperature and coefficient were tuned so that on each trial, the system completely cooled down during ~75% of iterations.
The optimization process for eil51 TSP instance was visualized. Figure 1 shows the relationship between and the iteration number. is the absolute difference between the tour length on the current iteration of SA algorithm and the optimal tour length for this problem.
Fig. 1. Simulated Annealing optimization process (eil51)
For TS, the relationship between and the iteration number is shown in Figure 2. Here, is the difference between the best candidate tour length (there are candidates on each iteration) on the current iteration and the optimal tour length for this problem.
Fig. 2. Tabu Search optimization process (eil51)
Figure 3 shows the relationship between and the iteration number for ACS. is the difference between the best (of ants) tour length on the current iteration and the optimal one.
Fig. 3. Ant Colony System optimization process (eil51)
Analysis of results. Table 1 shows that all the described approaches were able to obtain tours that are close to the optimal one. For instances with 51 and 101 cities, found tours are 5-10% longer than the optimal tour (Fig. 4, 5, 6). Tours found for problems with 150 and 200 cities are 10-25% longer than the optimal tour. Experiment results also show that Simulated Annealing produced the best results on all the TSP instances. Ant Colony System algorithm found better tours than Tabu Search, in 3 out of 4 problem instances. The quality of Tabu Search solutions significantly degraded with increase in the number of cities.
Fig. 4. Optimal tour in eil51
Fig. 5. Tour in eil51, which is 5.16% longer than the optimal tour
Fig. 6. Tour in eil51, which is 9.86% longer than the optimal tour
Conclusions
In this paper, Simulated Annealing, Tabu Search and Ant Colony System algorithms were described in the context of solving the Travelling Salesman Problem.
The performances of these approaches on four TSP instances with known optimal solutions were experimentally compared. Particularly, the length of a tour obtained by each algorithm in the same amount of time was compared.
This experimental study showed that the Simulated Annealing algorithm produced the best solutions to all the problem instances. The solutions obtained by the Ant Colony System were slightly worse. Tours found by Tabu Search were the longest. With the increase of number of cities, the absolute difference between the length of the found tour and the optimal one grew considerably slower for Simulated Annealing, slightly faster for Ant Colony System, and the fastest for Tabu Search.
These results give grounds to believe that Tabu Search will scale worse to larger problem instances than Simulated Annealing or Ant Colony System. It should also be noted that although Simulated Annealing performed better than the other algorithms, adjusting its parameters to the specific problem size and time limit is more sophisticated than for other approaches.
References
