Ant colony optimization with parameter update using a genetic algorithm for travelling salesman problem Ekaterina A. Blagoveshchenskayaa, Ilya I. Mikulika, Lutz H. Strüngmannb a Petersburg State Transport University, 9 Moskovsky pr, Saint Petersburg, 190031, Russian Federation b Mannheim University of Applied Sciences, 10 Paul-Wittsack st, 68163 Mannheim, Germany Abstract It is widely known that the ant colony algorithm is sensitive to changes in parameters. We present a novel kind of the algorithm which uses a genetic algorithm for solving this problem. Travelling salesman problem, known as NP-complete problem, is one of the most popular and important tasks in combinatorial optimization. This is a typical task for testing combinatorial optimization algorithms. In this paper, we present a comparative analysis of the algorithm with a simple ant colony optimization (SACO) on the example of this problem. Keywords Ant colony optimization, genetic algorithm, travelling salesman problem 1. Introduction The proposed algorithm is hybrid since it is based on two algorithms. In contrast to some Ant colony optimization is one of the popular other hybrid algorithms [6] [8], the proposed methods for combinatorial problem-solving. It algorithm is not a sequential application of has practical applications for logistics tasks several algorithms. On the other side, it is not a [1][2], dispatching tasks [3], cloud service [4], fundamentally new algorithm. The idea is to route planning [5], multiple sequence alignment apply genetic optimization of the parameters of [6], and others. The algorithm belongs to a class the main, ant colony optimization. of so-called bio-inspired algorithms, whose The study was conducted on the TSP behaviour is inspired by examples from nature1. problem. It was chosen because there exists an A common disadvantage of the ant colony amount of literature to benchmark our results class of methods is sensitivity to parameters that against. TCP is to find the cheapest way of establish a balance between expanding the visiting all of the cities and returning to starting search space and exploiting the solutions found. point. The benchmark berlin52 was used as an Optimal parameters can be highly problem- example. specific and dependent on the required accuracy In our work, we considered simple ant colony of the solution. Therefore, some works are optimization (SACO) as the simplest devoted to the dynamic adaptation of the implementation of the ant colony optimization, parameters of the ant algorithm [7]. We decided for two reasons. The first is to evaluate how well to use this method and use a genetic algorithm to the genetic algorithm finds the acceptable update the parameters. parameters of the ant algorithm. The second is to determine how much the found parameters improve the algorithm's performance. Using SACO eliminates the possibility of improving Models and Methods for Researching Information Systems in the quality of the algorithm due to some Transport, Dec 11-12, St. Petersburg ,Russia property of a specific implementation, a variant EMAIL: kblag2002@yahoo.com (E.A. Blagoveshchenskaya); mikulik.ilia@gmail.com (I.I. Mikulik); l.struengmann@hs- of the algorithm. It is possible that this approach mannheim.de(L.H. Strüngmann); of finding parameters with another method of ORCID: 0000-0002-2425-5556 (E.A. Blagoveshchenskaya); 0000- the ant colony optimization will show a better 0002-0542-7914 (I.I. Mikulik); 0000-0002-1689-3611 (L.H. Strüngmann) result. ©️ 2020 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 20 2. Travelling salesman problem algorithms by maintaining a population of structures as main elements in their design. The Travelling Salesman Problem (TSP) is a The algorithms belong to metaheuristic class. representative of class of problems known as They make few assumptions about the combinatorial optimization problems. The task optimization problem being solved and so they can be formulated as follows. The graph of cities can be used for different problems solving. is given. A salesman must visit all the cities only These algorithms do not guarantee the accuracy once. He must build a tour such that the length of the solution and can be applied in problems of the common path is the shortest among all where one can be satisfied with suboptimal possible paths. Path is a set of edges. Each edge solutions. from the graph has a weight or length. The 3.1. Ant colony optimization length of the path is the sum of weights all edges from this path. The ant colony algorithm, based on Swarm In terms of graph theory, the problem can be intelligence, is a heuristic algorithm. It simulates formulated as finding the shortest Hamiltonian the behaviour of an ant colony when searching cycle. for food. This model is used for solving The problem is NP-hard and combinatorial optimization problems. transcomputational, so finding an exact solution In the natural world, ants randomly search for to the problem is not always acceptable due to food. When they find food, they return to the time and computational resource constraints. In colony, leaving traces with pheromones. this case, approximate algorithms that give Pheromones serve as a signal to other ants. If suboptimal solutions are often used in practice. other ants find a path with pheromones, they will Algorithms differ both in the resources most likely follow it. If the ants get to the food consumed (time, memory) and in the accuracy source, they will also start leaving pheromones of the approximation. on the way back. Over time, the pheromone The traveling salesman problem occupies a begins to evaporate, so the trodden paths special place in combinatorial optimization and become less interesting for ants. The shorter the operations research. Historically, it was one of path, the less pheromone has time to evaporate tasks that served as an examples for the during the passage of the ant from the food development of these areas. The simplicity of source to the anthill. Passing along such a path the formulation, the finiteness of the set of becomes fast, and the pheromone density acceptable solutions, the visibility and, at the remains high. same time, the enormous cost of a complete Evaporation plays an important role in search still motivate mathematicians to develop finding global minima: if pheromones evaporate new numerical methods. at a low rate, the path found by the algorithm The travelling salesman problem is a routing will represent a local minimum. Thus, when one problem and has practical application. The main ant finds the optimal (or suboptimal) path from goal in these tasks is to build routes for vehicles the food source to the anthill, other ants are that serve a certain set of customers. At the same more likely to choose the same path, and time, choosing an unsuccessful route entails positive feedback eventually leads all ants to the additional costs for transporting the goods. same, shortest path. The above reasons explain our choice of task. The formulation of the model already hints at Since the problem is a typical one, there are a the sensitivity of the algorithm to parameters: sufficient number of examples of graphs with the evaporation coefficient, the amount of optimal solutions already found in the public pheromone deposited, the sensitivity of the ant domain. This makes it easy to compare the to pheromones. results of the work done with the existing ones. Ant colony optimization is a broad class of One such example is the berlin52 set on which algorithms. There are a big number of variations the study was conducted. of this algorithm. They differ in the edge 3. Ant colony optimization and selection rule, the pheromone deposition rule, and the evaporation rule. In some genetic algorithm implementations, there are elite ants. In such implementations, only the elite ants who have Ant colony optimization (ACO) and genetic built the best paths have the right to put a algorithm (GA) are population-based search pheromone on the arc. Algorithms can also 21 differ in the number of ants: it can be static or temperature annealing, which is well studied dynamic. However, most of the proposed [11]. Simulating annealing can also be applied implementations are more or less parameter- for parameter optimization. dependent. Of interest are algorithms whose The main advantages of hybridized GA are parameters are dynamic, they change during the better solution quality, better efficiency, operation of the algorithm. The proposed guarantee of feasible solutions, and optimized algorithm is also dynamic in terms of changing control parameters. parameters. 3.2. Genetic algorithm 4. The proposed GA-ACO algorithm A genetic algorithm (GA) is a heuristic algorithm that models natural selection. Like The proposed algorithm inspired by a simple ACO, GA is often used for combinatorial ant colony optimization (SACO). GA is used for optimization problems. GA uses principles and parameters search. terminology borrowed from genetics. In GA, Every ant 𝑘 has parameters 𝛼𝑘 , 𝛽𝑘 ,𝑄𝑘 . each individual represents a potential solution to These parameters are shared in SACO, but in some problem and is encoded in a special way our implementation they are different for each (in the simplest case, a binary number). Set of ant. For these parameters, the optimal values are individuals, which are potential solutions, form searched using the GA algorithm. the population. 𝛼𝑘 is sensitivity. It determines how sensitive The search for the optimal solution to a the ant is to the pheromone. This number is an problem in GA is performed in the process of exponent degree. It can be not integer. population evolution. It is a sequential 𝛽𝑘 is heuristic sensitivity. It determines how transformation of one finite set of solutions into sensitive the ant is to the heuristic information. another using the genetic operators of selection, This number is also an exponent degree. It can crossover, and mutation. be not integer. If the number is zero, the The idea of the selection operator is that heuristic information is ignored. individuals with better fitness function values 𝑄𝑘 is pheromone intensity. It determines how have a better chance of surviving and much pheromone the ant will put on the passed reproducing. The fitness function is defined over edges. This is an integer. This number strongly the genetic representation and it measures the depends on the choice of the pheromone quality of the represented solution. There are deposition rule. many ways to implement the selection operator. Another static common parameters are 𝑛, The crossing operator allows to get new 𝜌, 𝜏0 . individuals by crossing old ones. It combines the 𝑛 is an ants count. This is an important information of two parents to generate new parameter. It affects not only the accuracy of the offspring. Just like the selection operator, the solution, but also the execution time of the crossover operator can be implemented in algorithm. It cannot be changeable by GA various ways. The crossover operator has its because our implementation involves working own implementation depending on the type of only with the parameters that may differ for each data that the algorithm works with. ant. The mutation operator allows to get 𝜏0 is small pheromone value. It is upper fundamentally new individuals. Usually, the bound of pheromone distribution during mutation operator changes a small part of the initialization. It also cannot be changeable genome (part of the parent's data) with a low because it only plays a role once. probability. 𝜌 is a rate of evaporation. This is an The advantage of the algorithm is that the important parameter. However, this parameter evolutionary idea can be applied in different applies to the entire graph as a whole. The problems and in different ways. parameter cannot be bound to a specific ant. Another advantage that GA can be Therefore, despite the extreme importance of hybridized with other optimization methods for this parameter in finding the optimal solution, improving their performance such as ACO, we cannot use a genetic algorithm to change it. simulated annealing and other. Simulating Each ant chooses an edge probabilistically, annealing is a metaheuristic which approximates according to the rule global optimization. It is based on physical 22 𝛼 𝛽 This genetic part allows to change parameters 𝜏𝑖𝐽𝑘 (𝑡)𝜂𝑖𝐽𝑘 (𝑡) 𝑘( ) and find the best of them in real time. 𝑝𝑖𝐽 𝑡 = 𝛼 𝛽 (1) ∑𝜏𝑖𝑢𝑘 (𝑡)𝜂𝑖𝑢𝑘 (𝑡) 𝑘( ) where 𝑝𝑖𝐽 𝑡 is a probability of choosing 5. Results edge 𝑖𝐽 by ant 𝑘 at 𝑡 iteration. Each ant puts a pheromone according to the We conducted an experiment on berlin52 rule dataset. According to the article [11], the 𝑄𝑘 optimal parameters for the berlin52 dataset are Δ𝜏𝑖𝐽 = (2) 𝛼 = 0.7, 𝛽 = 4, 𝜌 = 0.5. Also, To compare the 𝑓(𝑥𝑘 ) where Δ𝜏𝑖𝐽 is a pheromone value; 𝑓(𝑥𝑘 ) is a results of the SACO with non-optimal length of the path 𝑥 which was found by ant 𝑘. parameters we give another set of parameters Algorithm can be formed by the next steps: 𝛼 = 0.2, 𝛽 = 1, 𝑞 = 15, 𝜌 = 0.9. SACO with Begin this parameter set gives worse result then Determine the parameters: 𝑛, 𝜏0 , 𝜌. presented before. We used the presented For each edge 𝑖𝑗: algorithm with these ones as initial. assign a random amount of pheromone As result, the parameters in the last iterations of our method have become closer to optimal. 𝜏𝑖𝑗 < 𝜏0 . An example of the path constructed by the While stop criteria is not reached: proposed algorithm is shown in the Figure 1. For each ant 𝑘 = 1. . 𝑛: 𝑥𝑘 (𝑡) = Ø. While the full path is not built: Set the next vertex 𝑗 according to the rule (1). 𝑥𝑘 (𝑡) = 𝑥𝑘 (𝑡) ∪ (𝑖, 𝑗). For each edge (𝑖, 𝑗): calculate the evaporation and the new pheromone concentration by the rule (2). Create new set of ant’s parameters according the selection rule. Use the crossover operator for parameters. Use the mutation operator for parameters. Figure 1: solution for berlin52 dataset Set new parameters 𝛼𝑘 , 𝛽𝑘 ,𝑄𝑘 to ants. End A comparison of the results of ACO with The main idea of the proposed algorithm is optimal parameters, ACO with non-optimal the use of genetic operators. Firstly, it is needed parameters, and the proposed ACO+GA to define the fitness function, because the fitness algorithm is presented in table 1. function is always problem dependent. It was decided to define the fitness function as the Table 1 length of the path traversed by the ant. Note that Comparison we use a genetic algorithm to optimize the Algorithm Best solution Average parameters, not the found path. However, the solution path length is a good indicator for evaluating ACO with 11178.291 11883.161 how well the ant colony algorithm works for the given parameters. not optimal In this paper we use selection rule which parameters defines a new set of parameters probabilistically: ACO with 7548.993 7816.862 𝑓(𝑥𝑘 ) optimal 𝑃(𝑀𝑘 ) = ∑𝑓(𝑥 ) , (3) 𝑘 parameters where 𝑃(𝑀𝑘 ) is a probability to choose ant’s ACO+GA 7548.993 7998.069 𝑘 parameters. Actually, any appropriate rule can be applied here. We use roulette wheel selection. The maximum, minimum, and average Crossover operator implements bit crossing of lengths of solution paths formed by the selected parameters. Mutation operator ACO+GA algorithm are shown in the Figure 2. randomly changes a bit of each parameter. 23 Figure 2: Length of paths founded by the ACO+GA algorithm Figure 5: Comparison of the average lengths of solution paths The maximum, minimum, and average lengths of solution paths formed by the SACO Analyzing the results, we can say that the algorithm with optimal parameters are shown in proposed algorithm is stable to the initial the Figure 3. parameters and significantly increases the quality of the search. In the best case, the algorithm finds the optimal solution, as well as the SACO algorithm with optimal parameters. On average, the algorithm works 34% better than SACO with not optimal parameters. Also on average, the algorithm works 2% worse than SACO with optimal parameters. The algorithm shows results not much worse than SACO with optimal parameters. However, the algorithm becomes less susceptible to Figure 3: Length of paths founded by the SACO parameters and more versatile for solving algorithm with optimal parameters combinatorial problems of any configuration. The maximum, minimum, and average 6. Conclusions lengths of solution paths formed by the SACO algorithm with not optimal parameters are The proposed ant colony optimization with shown in the Figure 4. parameter update using a genetic algorithm presented in this paper is shown to produce better results for the solution of traveling salesman problems. The algorithm becomes insensitive to the original parameter values and produces results not much worse than with optimal parameters. Actually, this ACO+GA is a promising approach which can be used for different Figure 4: Length of paths founded by the SACO problems. The main goal is achieved; the algorithm with not optimal parameters algorithm has become less susceptible to parameters. Analyzing the graphs, one can see that the We showed the basic idea of how to work spread of values in the SACO+GA algorithm is with parameters. The researcher can use a not as large as in SACO with not optimal different algorithm to optimize the parameters or parameters. However, the spread of SACO with improve the proposed one. optimal parameters is much lower. However, it begs the question of how Comparison of the average lengths of sensitive the new algorithm is to the parameters solution paths formed by algorithms is shown in of the genetic algorithm. Intuitively, we can the Figure 5. assume that the sensitivity is low, since the parameters affect the search for ACO parameters, and not the search for a solution. Nevertheless, it can be a promising research topic. 24 7. Acknowledgments [9] Filimonov, S. Vakhrushev,M. Wurz, A. Shaganov, L. Rissing, Investigation of This work is supported by the Russian the crystallization of NiFe81/19 Foundation for Basic Research (project 20- depending on the annealing temperature. 01-00610). ECS Transactions (2013): 147. [10] TA. El-Mihoub, AA Hopgood, References N Lars, A Battersby, Hybrid genetic [1] M. Hassan, M. Hasan, M. M .A. algorithms: A review (2006). Hashem, An improved acs algorithm for [11] B. Koçer, The Analysis of the solutions of larger tsp problems, GR202 and Berlin 52 Datasets by Ant arXiv:1304.3763 (2013). Colony Algorithm, In 2015 4th [2] J.R. Batmetan, A. Santoso, Multiple- International Conference on Advanced objective ant colony algorithm for Computer Science Applications and optimizing disaster relief logistics, Technologies (ACSAT), IEEE Advanced Science Letters 23, no. 3 (2015):103-108. doi: (2017). doi:10.1166/asl.2017.8758 10.1109/ACSAT.2015.47 [3] D. Liang, Zh. Zhan, Y. Zhang, J. Zhang, An Efficient Ant Colony System Approach for New Energy Vehicle Dispatch Problem, IEEE Transactions on Intelligent Transportation Systems (2019). doi: 10.1109/tits.2019.2946711. [4] K. Zhou, W. Yongzhao, W. Wanying, N. Zhiyong, J. Tianguo, L. Xiaojun, Cloud Service Optimization Method Based on Dynamic Artificial Ant-Bee Colony Algorithm in Agricultural Equipment Manufacturing, Mathematical Problems in Engineering 2020 (2020). doi: 10.1155/2020/9134695. [5] X. Qian, X. Zhong, Optimal individualized multimedia tourism route planning based on ant colony algorithms and large data hidden mining, Multimedia Tools and Applications 78, no. 15 (2019): 22099-22108. [6] ZJ. Lee, S.F. Su, C.C. Chuang, KH Liu, Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment, Applied Soft Computing 8, no. 1 (2008): 55-78.. [7] O. Castillo, H. Neyoy, J. Soria, P. Melin, F. Valdez, A new approach for dynamic fuzzy logic parameter tuning in ant colony optimization and its application in fuzzy control of a mobile robot, Applied soft computing 28 (2015): 150-159. doi: 10.1016/j.asoc.2014.12.002 [8] Z. Yan-hua, F. Lei, Y. Zhi, Optimization of cloud database route scheduling based on combination of genetic algorithm and ant colony algorithm, Procedia Engineering 15 (2011): 3341- 3345. 25