Population Diversity in Ant-inspired Optimization Algorithms

Aleksander Byrski; Krzysztof Węgrzyński; Wojciech Radwański; Grażyna Starzec; Mateusz Starzec; Monika Bargieł; Aleksandra Urbańczyk; Marek Kisiel-Dorohinicki

doi:10.7494/csci.2021.22.3.4301

Authors

Aleksander Byrski AGH University of Science and Technology
Krzysztof Węgrzyński
Wojciech Radwański
Grażyna Starzec
Mateusz Starzec
Monika Bargieł
Aleksandra Urbańczyk
Marek Kisiel-Dorohinicki

DOI:

https://doi.org/10.7494/csci.2021.22.3.4301

Abstract

Finding a balance between exploration and exploitation is very important in the case of metaheuristics optimization, especially in the systems leveraging population of individuals expressing (as in Evolutionary Algorithms, etc.) or constructing (as in Ant Colony Optimization) solutions. Premature convergence is a real problem and finding means of its automatic detection and counteracting are of great importance. Measuring diversity in Evolutionary Algorithms working in real-value search space is often computationally complex, but feasible while measuring diversity in combinatorial domain is practically impossible (cf. Closest String Problem). Nevertheless, we propose several practical and feasible diversity measurement techniques dedicated to Ant Colony Optimization algorithms, leveraging the fact that even though analysis of the search space is at least an NP problem, we can focus on the pheromone table, where the direct outcomes of the search are expressed and can be analyzed. Besides proposing the measurement techniques, we apply them to assess the diversity of several variants of ACO, and closely analyze their features for the classic ACO. The discussion of the results is the first step towards applying the proposed measurement techniques in auto-adaptation of the parameters affecting directly the exploitation and exploration features in ACO in the future.

Downloads

Download data is not yet available.

References

Bachniak D., Rauch L., Krol D., Liput J., Slota R., Kitowski J., Pietrzyk M.: Sensitivity analysis on HPC systems with Scalarm platform. In: concurrency and Computation: Practice and Experience, vol. 29(9), 2017.

Bullnheimer B., Hartl R., Strauss C.: A New Rank Based Version of the Ant System - A Computational Study. In: Central European Journal of Operations Research, vol. 7, pp. 25–38, 1999.

Cantu-Paz E.: Efficient and Accurate Parallel Genetic Algorithms. Springer, 2001.

Chen J., You X., Liu S., Li J.: Entropy-Based Dynamic Heterogeneous Ant Colony Optimization. In: IEEE Access, vol. 7, pp. 56317–56328, 2019. ISSN 2169-3536. URL http://dx.doi.org/10.1109/ACCESS.2019.2900029.

Colas S., Monmarch ́e N., Gaucher P., Slimane M.: Artificial ants for the opti- mization of virtual keyboard arrangement for disabled people. In: International Conference on Artificial Evolution (Evolution Artificielle), pp. 87–99. Springer, 2007.

Cui Z., Li F., Zhang W.: Bat algorithm with principal component analysis. In: Int. J. Machine Learning & Cybernetics, vol. 10(3), pp. 603–622, 2019.

Deng W., Xu J., Zhao H.: An Improved Ant Colony Optimization Algorithm Based on Hybrid Strategies for Scheduling Problem. In: IEEE Access, vol. 7, pp. 20281–20292, 2019. ISSN 2169-3536. URL http://dx.doi.org/10.1109/ ACCESS.2019.2897580.

Dorigo M.: Optimization, learning and natural algorithms. In: PhD Thesis, Politecnico di Milano, 1992.

Dorigo M., Di Caro G.: Ant colony optimization: a new meta-heuristic. In: Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, vol. 2, pp. 1470–1477. IEEE, 1999.

Dorigo M., Gambardella L.M.: Ant colony system: a cooperative learning ap- proach to the traveling salesman problem. In: IEEE Transactions on evolutionary computation, vol. 1(1), pp. 53–66, 1997.

Dorigo M., Maniezzo V., Colorni A.: Ant system: optimization by a colony of cooperating agents. In: IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26(1), pp. 29–41, 1996.

Dorigo M., Stu ̈tzle T.: Ant colony optimization, chap. 3.6.1. MIT, 2004.

Dorigo M., Stu ̈tzle T.: Ant Colony Optimization: Overview and Recent Ad- vances. Tech. rep., IRIDIA - Technical Report Series, Universit ́e Libre de Brux- elles, 2009.

Dorigo M. G.D.C..L.M.G.: Ant Algorithms for Discrete Optimization. Tech. rep., IRIDIA/98-10, Universit ́e Libre de Bruxelles, Belgium, 1999.

Gambardella L.M., Dorigo M.: Ant-Q: A reinforcement learning approach to the traveling salesman problem. In: Machine Learning Proceedings 1995, pp. 252– 260. Elsevier, 1995.

Glibovets N.N., Gulayeva N.M.: A Review of Niching Genetic Algorithms for Multimodal Function Optimization. In: Cybernetics and Systems Analysis, vol. 49(6), pp. 815–820, 2013. ISSN 1573-8337. URL http://dx.doi.org/10. 1007/s10559-013-9570-8.

Herrera F., Lozano M.: Adaptation of Genetic Algorithm Parameters Based on Fuzzy Logic Controllers. In: Genetic Algorithms and Soft Computing, vol. 8, pp. 95–125, 1996.

Li M., Ma B., Wang L.: On the Closest String and Substring Problems. In: J. ACM, vol. 49(2), pp. 157–171, 2002. ISSN 0004-5411. URL http://dx.doi.org/ 10.1145/506147.506150.

Mohsen A.M.: Annealing Ant Colony Optimization with Mutation Operator for Solving TSP. In: Computational Intelligence and Neuroscience, vol. 2016, p. 8932896, 2016. URL http://dx.doi.org/10.1155/2016/8932896.

Montemanni R., Gambardella L.M., Rizzoli A.E., Donati A.V.: Ant Colony Sys- tem for a Dynamic Vehicle Routing Problem. In: Journal of Combinatorial Optimization, vol. 10, 2005.

Morrison R.W., Jong K.A.D.: Measurement of Population Diversity. In: P. Col- let, C. Fonlupt, J.K. Hao, E. Lutton, M. Schoenauer, eds., Proc. of EA 2001, LNCS 2310, pp. 31–41. Springer, 2002.

Nakamichi Y., Arita T.: Diversity control in ant colony optimization. In: Artifi- cial Life and Robotics, vol. 7(4), pp. 198–204, 2004. URL http://dx.doi.org/ https://doi.org/10.1007/BF02471207.

Negulescu S.C., Oprean C., Kifor C.V., Carabulea I.: Elitist Ant System for Route Allocation Problem. In: Proceedings of the 8th WSEAS International Conference on Applied Informatics and Communications (AIC08), pp. 62–67. Rhodes, Greece, 2008.

S ̈orensen K.: Metaheuristics the metaphor exposed. In: International Transac- tions in Operational Research, vol. 22(1), pp. 3–18, 2015. ISSN 1475-3995. URL http://dx.doi.org/10.1111/itor.12001.

Starzec M., Starzec G., Byrski A., Turek W.: Distributed ant colony optimization based on actor model. In: Parallel Computing, vol. 90, p. 102573, 2019.

Starzec M., Starzec G., Byrski A., Turek W., Pietak K.: Desynchronization in distributed Ant Colony Optimization in HPC environment. In: Future Generation Computer Systems, vol. 109, pp. 125–133, 2020.

Stu ̈tzle T., Hoos H.H.: MAX–MIN ant system. In: Future generation computer systems, vol. 16(8), pp. 889–914, 2000.

S ́widerskaE.,L????asiszJ.,ByrskiA.,LenaertsT.,SamsonD.,IndurkhyaB.,Now ́e A., Kisiel-Dorohinicki M.: Measuring Diversity of Socio-Cognitively Inspired ACO Search. In: G. Squillero, P. Burelli, eds., Applications of Evolutionary Computation, pp. 393–408. Springer International Publishing, Cham, 2016. ISBN 978-3-319-31204-0.

Wolpert D.H., Macready W.G.: No free lunch theorems for optimization. In: IEEE Transactions on Evolutionary Computation, vol. 1(1), pp. 67–82, 1997.

Yang K., You X., Liu S., Pan H.: A novel ant colony optimization based on game for traveling salesman problem. In: Applied Intelligence, vol. 50, pp. 4529–4542, 2020. URL http://dx.doi.org/10.1007/s10489-020-01799-w.

Zhang D., You X., Liu S., Yang K.: Multi-Colony Ant Colony Optimization Based on Generalized Jaccard Similarity Recommendation Strategy. In: IEEE Access, vol. 7, pp. 157303–157317, 2019. ISSN 2169-3536. URL http://dx.doi. org/10.1109/ACCESS.2019.2949860.

Zhang M., Wang H., Cui Z., Chen J.: Hybrid multi-objective cuckoo search with dynamical local search. In: Memetic Computing, vol. 10(2), pp. 199–208, 2018.