Mejora del rendimiento de los algoritmos metaheurísticos mediante poblaciones estructuradas y teoría de juegos evolutiva

Jesus Ivan Aramburo Gutierrez

Authors

Jesus Ivan Jesus Ivan 📩 Universidad Autonoma De Sinaloa, México

Keywords:

metaheuristics; game theory; optimization; competition; Metropolis–Hastings

Abstract

Diversity plays a fundamental role in metaheuristic algorithms, as it helps prevent premature convergence, maintains a balance between exploration and exploitation, and reduces the likelihood of being trapped in local optima. Many traditional metaheuristic algorithms rely on a single strategy to generate new solutions, which can limit the diversity of the population. In contrast, incorporating multiple strategies enables different search behaviors and produces a broader set of candidate solutions, thereby improving the exploration of the search space. Evolutionary game theory introduces adaptive mechanisms in which agents modify their strategies through competitive interactions, reinforcing successful strategies while discarding less effective ones. Structured populations, unlike unstructured ones, help preserve strategic diversity through localized competition, where each individual interacts only with a subset of the population rather than with all individuals. In this work, a novel metaheuristic method based on evolutionary game theory applied to structured populations is proposed. Initially, individuals are positioned near promising regions using the Metropolis–Hastings algorithm. Subsequently, each individual is assigned a specific search strategy, and the population is divided into several clusters. Within these clusters, strategies evolve through intra-cluster competition to improve search efficiency and solution quality. The proposed approach was evaluated using 30 benchmark functions and compared with several well-known metaheuristic algorithms. The results demonstrate improvements in both solution quality and convergence speed.

References

Abdel-Basset, M., Abdel-Fatah, L., y Sangaiah, A. K. (2018). Metaheuristic algorithms: A comprehensive review. En Computational intelligence for multimedia big data on the cloud with engineering applications (pp. 185–231). Academic Press.

Abedinpourshotorban, H., Shamsuddin, S. M., Beheshti, Z., y Jawawi, D. N. A. (2016). Electromagnetic field optimization: A physics-inspired metaheuristic optimization algorithm. Swarm and Evolutionary Computation, 26, 8–22.

Afzal, A., Buradi, A., Jilte, R., Shaik, S., Kaladgi, A. R., Arıcı, M., Lee, C. T., y Nižetić, S. (2023). Optimizing the thermal performance of solar energy devices using meta-heuristic algorithms: A critical review. Renewable and Sustainable Energy Reviews, 173, 112903.

Ahmed, M., Seraj, R., y Islam, S. M. S. (2020). The k-means algorithm: A comprehensive survey and performance evaluation. Electronics, 9, 1295.

Almufti, S. M., Marquas, R. B., y Saeed, V. A. (2019). Taxonomy of bio-inspired optimization algorithms. Journal of Advanced Computer Science and Technology, 8, 23.

Askarzadeh, A. (2016). A novel metaheuristic method for solving constrained engineering optimization problems: Crow search algorithm. Computers & Structures, 169, 1–12.

Chopard, B., y Tomassini, M. (2018). An introduction to metaheuristics for optimization. Springer.

Cuevas, E., Cienfuegos, M., Zaldívar, D., y Pérez-Cisneros, M. (2013). A swarm optimization algorithm inspired in the behavior of the social-spider. Expert Systems with Applications, 40, 6374–6384.

Cuevas, E., Echavarría, A., y Ramírez-Ortegón, M. A. (2014). An optimization algorithm inspired by the states of matter that improves the balance between exploration and exploitation. Applied Intelligence, 40, 256–272.

Cuevas, E., Escobar, H., Sarkar, R., y Eid, H. F. (2022). A new population initialization approach based on Metropolis–Hastings (MH) method. Applied Intelligence, 53, 16575–16593.

Dokeroglu, T., Sevinc, E., Kucukyilmaz, T., y Cosar, A. (2019). A survey on new generation metaheuristic algorithms. Computers & Industrial Engineering, 137, 106040.

Geem, Z. W., Kim, J. H., y Loganathan, G. V. (2001). A new heuristic optimization algorithm: Harmony search. Simulation, 76, 60–68.

Gintis, H. (2000). Game theory evolving: A problem-centered introduction to modeling strategic behavior. Princeton University Press.

Giri, A. R., Chen, T., Rajendran, V. P., y Khamis, A. (2022). A metaheuristic approach to emergency vehicle dispatch and routing. En Proceedings of the 2022 IEEE International Conference on Smart Mobility (SM) (pp. 27–31). IEEE.

Grüne-Yanoff, T. (2011). Evolutionary game theory, interpersonal comparisons and natural selection: A dilemma. Biology & Philosophy, 26, 637–654.

Hansen, N., y Ostermeier, A. (1996). Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. En Proceedings of the IEEE International Conference on Evolutionary Computation. IEEE.

Holland, J. H. (1984). Genetic algorithms and adaptation. En Adaptive control of ill-defined systems. Springer.

Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Erciyes University.

Kaur, S., Kumar, Y., Koul, A., y Kamboj, S. K. (2023). A systematic review on metaheuristic optimization techniques for feature selections in disease diagnosis: Open issues and challenges. Archives of Computational Methods in Engineering, 30, 1863–1895.

Kennedy, J., Eberhart, R., y Gov, B. (1995). Particle swarm optimization. En Encyclopedia of machine learning (pp. 760–766). Springer.

Kirkpatrick, S., Gelatt, C. D., y Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671–680.

Mirjalili, S. (2016). SCA: A sine cosine algorithm for solving optimization problems. Knowledge-Based Systems, 96, 120–133.

Mirjalili, S., y Lewis, A. (2016). The whale optimization algorithm. Advances in Engineering Software, 95, 51–67.

Mirjalili, S., Mirjalili, S. M., y Lewis, A. (2014). Grey wolf optimizer. Advances in Engineering Software, 69, 46–61.

Osuna-Enciso, V., Cuevas, E., y Castañeda, B. M. (2022). A diversity metric for population-based metaheuristic algorithms. Information Sciences, 586, 192–208.

Rashedi, E., Nezamabadi-Pour, H., y Saryazdi, S. (2009). GSA: A gravitational search algorithm. Information Sciences, 179, 2232–2248.

Stella, L., y Bauso, D. (2017). Evolutionary game dynamics for collective decision making in structured and unstructured environments. IFAC-PapersOnLine, 50, 11914–11919.

Storn, R., y Price, K. (1995). Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces. Australasian Plant Pathology, 38, 284–287.

Vaziri, E., Dehdar, F., y Abdoli, M. R. (2023). Feasibility study of using meta-heuristic algorithms on optimizing of the integrated risk in banking system. International Journal of Finance, Management and Accounting, 8, 143–158.

Weibull, W. (1997). Evolutionary game theory. MIT Press.

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

Yang, X.-S. (2010a). A new metaheuristic bat-inspired algorithm. En Nature inspired cooperative strategies for optimization (NICSO 2010) (Studies in Computational Intelligence, Vol. 284, pp. 65–74). Springer.

Yang, X.-S. (2010b). Engineering optimization: An introduction with metaheuristic applications. Wiley.

Yang, X.-S., y Deb, S. (2009). Cuckoo search via Lévy flights. En Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC) (pp. 210–214). IEEE.