Population diversity in ant-inspired optimization algorithms

• Autorzy: Byrski Aleksander , Węgrzyński Krzysztof , Radwański Wojciech , Starzec Grażyna , Starzec Mateusz , Bargiel Monika , Urbańczyk Aleksandra , Kisiel-Dorohinicki Marek

Identyfikatory

DOI

10.7494/csci.2021.22.3.4301

• Języki publikacji: EN

Abstrakty

EN

Measuring the diversity in evolutionary algorithms that work in real-value search spaces is often computationally complex, but it is feasible; however, measuring the diversity in combinatorial domains is practically impossible. Nevertheless, in this paper we propose several practical and feasible diversitymeasurement techniques that are dedicated to ant colony optimization algorithms, leveraging the fact that we can focus on a pheromone table even though an analysis of the search space is at least an NP problem where the direct outcomes of the search are expressed and can be analyzed. Besides sketching out the algorithms, we apply them to several benchmark problems and discuss their efficacy.

Słowa kluczowe

EN

ant colony optimization; diversity measuring; exploitation and exploration balance; metaheuristics

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2021
• Tom: T. 22 (3)
• Strony: 297–320
• Opis fizyczny: Bibliogr. 32 poz., rys.

Twórcy

autor

Byrski Aleksander

• AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland

autor

Węgrzyński Krzysztof

• AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland

autor

Radwański Wojciech

• AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland

autor

Starzec Grażyna

• AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland

autor

Starzec Mateusz

• AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland

autor

Bargiel Monika

• AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland

autor

Urbańczyk Aleksandra

• AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland

autor

Kisiel-Dorohinicki Marek

• AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland

Bibliografia

• [1] Bachniak D., Rauch L., Krol D., Liput J., Slota R., Kitowski J., Pietrzyk M.: Sensitivity analysis on HPC systems with Scalarm platform, Concurrency and Computation: Practice and Experience, vol. 29(9), 2017.
• [2] Bullnheimer B., Hartl R., Strauss C.: A New Rank Based Version of the Ant System – A Computational Study, Central European Journal of Operations Research, vol. 7, pp. 25–38, 1999.
• [3] Cantu-Paz E.: Efficient and Accurate Parallel Genetic Algorithms, Springer, 2001.
• [4] Chen J., You X., Liu S., Li J.: Entropy-Based Dynamic Heterogeneous Ant Colony Optimization, IEEE Access, vol. 7, pp. 56317–56328, 2019. doi: 10.1109/ ACCESS.2019.2900029.
• [5] Colas S., Monmarché 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.
• [6] Cui Z., Li F., Zhang W.: Bat algorithm with principal component analysis, In ternational Journal of Machine Learning & Cybernetics, vol. 10 (3), pp. 603–622, 2019.
• [7] Deng W., Xu J., Zhao H.: An Improved Ant Colony Optimization Algo rithm Based on Hybrid Strategies for Scheduling Problem, IEEE Access, vol. 7, pp. 20281–20292, 2019. doi: 10.1109/ACCESS.2019.2897580.
• [8] Dorigo M.: Optimization, learning and natural algorithms, PhD Thesis, Politecnico di Milano, 1992.
• [9] 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.
• [10] Dorigo M., Di Caro G., Gambardella L.M.: Ant Algorithms for Discrete Optimization. Technical Report, IRIDIA/98-10, Université Libre de Bruxelles, Bel gium, 2009.
• [11] Dorigo M., Gambardella L.M.: Ant colony system: a cooperative learning ap proach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, vol. 1(1), pp. 53–66, 1997.
• [12] Dorigo M., Maniezzo V., Colorni A.: Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26(1), pp. 29–41, 1996.
• [13] Dorigo M., Stützle T.: Ant Colony Optimization: Overview and Recent Ad vances. IRIDIA – Technical Report Series, Université Libre de Bruxelles, 2009.
• [14] Dorigo M., Stützle T.: Ant colony optimization, chap. 3.6.1, MIT, 2004.
• [15] 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.
• [16] Glibovets N.N., Gulayeva N.M.: A Review of Niching Genetic Algorithms for Multimodal Function Optimization, Cybernetics and Systems Analysis, vol. 49(6), pp. 815–820, 2013. doi: 10.1007/s10559-013-9570-8.
• [17] Herrera F., Lozano M.: Adaptation of Genetic Algorithm Parameters Based on Fuzzy Logic Controllers, Genetic Algorithms and Soft Computing, vol. 8, pp. 95–125, 1996.
• [18] Li M., Ma B., Wang L.: On the Closest String and Substring Problems, Journal of the ACM, vol. 49(2), pp. 157–171, 2002. doi: 10.1145/506147.506150.
• [19] Mohsen A.M.: Annealing Ant Colony Optimization with Mutation Operator for Solving TSP, Computational Intelligence and Neuroscience, vol. 2016, p. 8932896, 2016. doi: 10.1155/2016/8932896.
• [20] Montemanni R., Gambardella L.M., Rizzoli A.E., Donati A.V.: Ant Colony Sys tem for a Dynamic Vehicle Routing Problem, Journal of Combinatorial Optimization, vol. 10, 2005.
• [21] Morrison R.W., Jong K.A.D.: Measurement of Population Diversity. In: P. Collet, C. Fonlupt, J.K. Hao, E. Lutton, M. Schoenauer (eds.), Proc. of EA 2001, LNCS 2310, pp. 31–41, Springer, 2002.
• [22] Nakamichi Y., Arita T.: Diversity control in ant colony optimization, Artificial Life and Robotics, vol. 7(4), pp. 198–204, 2004. doi: 10.1007/BF02471207.
• [23] 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.
• [24] Sörensen K.: Metaheuristics the metaphor exposed, International Transactions in Operational Research, vol. 22 (1), pp. 3–18, 2015. doi: 10.1111/itor.12001.
• [25] Starzec M., Starzec G., Byrski A., Turek W.: Distributed ant colony optimization based on actor model, Parallel Computing, vol. 90, p. 102573, 2019.
• [26] Starzec M., Starzec G., Byrski A., Turek W., Pietak K.: Desynchronization in distributed Ant Colony Optimization in HPC environment, Future Generation Computer Systems, vol. 109, pp. 125–133, 2020.
• [27] Stützle T., Hoos H.H.: MAX–MIN ant system, Future Generation Computer Systems, vol. 16(8), pp. 889–914, 2000.
• [28] Świderska E., Łasisz J., Byrski A., Lenaerts T., Samson D., Indurkhya B., Nowé, A., Kisiel-Dorohinicki M.: Measuring Diversity of Socio-Cognitively In spired ACO Search. In: G. Squillero, P. Burelli (eds.), Applications of Evolution ary Computation, pp. 393–408, Springer International Publishing, Cham, 2016.
• [29] Wolpert D.H., Macready W.G.: No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation, vol. 1(1), pp. 67–82, 1997.
• [30] Yang K., You X., Liu S., Pan H.: A novel ant colony optimization based on game for traveling salesman problem, Applied Intelligence, vol. 50, pp. 4529–4542, 2020. doi: 10.1007/s10489-020-01799-w.
• [31] Zhang D., You X., Liu S., Yang K.: Multi-Colony Ant Colony Optimization Based on Generalized Jaccard Similarity Recommendation Strategy, IEEE Ac cess, vol. 7, pp. 157303–157317, 2019. doi: 10.1109/ACCESS.2019.2949860.
• [32] Zhang M., Wang H., Cui Z., Chen J.: Hybrid multi-objective cuckoo search with dynamical local search, Memetic Computing, vol. 10(2), pp. 199–208, 2018.

Uwagi

PL

„Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).”