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

Jesus Ivan Aramburo Gutierrez

Autores/as

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

Palabras clave:

metaheurística; teoría de juegos; optimización; competencia; Metropolis–Hastings

Resumen

La diversidad desempeña un papel fundamental en los algoritmos metaheurísticos, ya que contribuye a prevenir la convergencia prematura, favorece el equilibrio entre exploración y explotación y reduce la probabilidad de quedar atrapado en óptimos locales. Muchos algoritmos metaheurísticos tradicionales emplean una sola estrategia para generar nuevas soluciones, lo que puede limitar la diversidad dentro de la población. En contraste, el uso de múltiples estrategias permite generar distintos comportamientos de búsqueda y producir un conjunto más variado de soluciones candidatas, mejorando así la exploración del espacio de búsqueda. La teoría de juegos evolutiva introduce mecanismos de adaptación en los que las estrategias de los agentes evolucionan mediante procesos de competencia, fortaleciendo aquellas más efectivas y descartando las menos eficientes. Por su parte, las poblaciones estructuradas, a diferencia de las no estructuradas, preservan una mayor diversidad estratégica gracias a interacciones locales, donde cada individuo compite únicamente con un subconjunto de la población. En este trabajo se propone un nuevo método metaheurístico basado en teoría de juegos evolutiva aplicado a poblaciones estructuradas. Inicialmente, las soluciones se generan cerca de regiones prometedoras por medio del algoritmo Metropolis–Hastings. Posteriormente, a cada persona se le fija una táctica de investigación específica y la población se divide en varios clústeres. Dentro de cada clúster, las estrategias evolucionan mediante competencia intraclúster para mejorar la eficiencia de búsqueda. La propuesta se evaluó utilizando 30 funciones de prueba y se comparó con diversos algoritmos metaheurísticos. Los resultados muestran mejoras en la calidad de las soluciones y en la velocidad de convergencia.

Citas

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.