Mejora del rendimiento de los algoritmos metaheurísticos mediante poblaciones estructuradas y teoría de juegos evolutiva
DOI:
https://doi.org/10.32870/recibe.v15i2.495Palabras clave:
metaheurística; teoría de juegos; optimización; competencia; Metropolis–HastingsResumen
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., & Sangaiah, A. K. (2018). Metaheuristic algorithms: A comprehensive review. En A. K. Sangaiah, Z. Zhang, & M. Sheng (Eds.), Computational intelligence for multimedia big data on the cloud with engineering applications (pp. 185–231). Academic Press. https://doi.org/10.1016/B978-0-12-813314-9.00010-4
Abedinpourshotorban, H., Shamsuddin, S. M., Beheshti, Z., & Jawawi, D. N. A. (2016). Electromagnetic field optimization: A physics-inspired metaheuristic optimization algorithm. Swarm and Evolutionary Computation, 26, 8–22. https://doi.org/10.1016/j.swevo.2015.07.002
Afzal, A., Buradi, A., Jilte, R., Shaik, S., Kaladgi, A. R., Arıcı, M., Lee, C. T., & 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. https://doi.org/10.1016/j.rser.2022.112903
Ahmed, M., Seraj, R., & Islam, S. M. S. (2020). The k-means algorithm: A comprehensive survey and performance evaluation. Electronics, 9(8), 1295. https://doi.org/10.3390/electronics9081295
Almufti, S. M., Marqas, R. B., & Saeed, V. A. (2019). Taxonomy of bio-inspired optimization algorithms. Journal of Advanced Computer Science & Technology, 8(2), 23–31. https://doi.org/10.14419/jacst.v8i2.29402
Askarzadeh, A. (2016). A novel metaheuristic method for solving constrained engineering optimization problems: Crow search algorithm. Computers & Structures, 169, 1–12. https://doi.org/10.1016/j.compstruc.2016.03.001
Chopard, B., & Tomassini, M. (2018). An introduction to metaheuristics for optimization. Springer. https://doi.org/10.1007/978-3-319-93073-2
Cuevas, E., Cienfuegos, M., Zaldívar, D., & Pérez-Cisneros, M. (2013). A swarm optimization algorithm inspired in the behavior of the social-spider. Expert Systems with Applications, 40(16), 6374–6384. https://doi.org/10.1016/j.eswa.2013.05.041
Cuevas, E., Echavarría, A., & 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. https://doi.org/10.1007/s10489-013-0458-0
Cuevas, E., Escobar, H., Sarkar, R., & Eid, H. F. (2023). A new population initialization approach based on Metropolis–Hastings (MH) method. Applied Intelligence, 53, 16575–16593. https://doi.org/10.1007/s10489-022-04359-6
Dokeroglu, T., Sevinc, E., Kucukyilmaz, T., & Cosar, A. (2019). A survey on new generation metaheuristic algorithms. Computers & Industrial Engineering, 137, 106040. https://doi.org/10.1016/j.cie.2019.106040
Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A new heuristic optimization algorithm: Harmony search. Simulation, 76(2), 60–68. https://doi.org/10.1177/003754970107600201
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., & Khamis, A. (2022). A metaheuristic approach to emergency vehicle dispatch and routing. En 2022 IEEE International Conference on Smart Mobility (SM) (pp. 27–31). IEEE. https://doi.org/10.1109/SM55505.2022.9758285
Grüne-Yanoff, T. (2011). Evolutionary game theory, interpersonal comparisons and natural selection: A dilemma. Biology & Philosophy, 26(5), 637–654. https://doi.org/10.1007/s10539-011-9273-3
Hansen, N., & 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 (pp. 312–317). IEEE. https://doi.org/10.1109/ICEC.1996.542381
Holland, J. H. (1984). Genetic algorithms and adaptation. En O. G. Selfridge, E. L. Rissland, & M. A. Arbib (Eds.), Adaptive control of ill-defined systems (pp. 317–333). Springer. https://doi.org/10.1007/978-1-4684-8941-5_21
Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization (Technical Report TR06). Erciyes University. http://mf.erciyes.edu.tr/abc/pub/tr06_2005.pdf
Kaur, S., Kumar, Y., Koul, A., & 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. https://doi.org/10.1007/s11831-022-09853-1
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. En Proceedings of ICNN’95: International Conference on Neural Networks (Vol. 4, pp. 1942–1948). IEEE. https://doi.org/10.1109/ICNN.1995.488968
Kirkpatrick, S., Gelatt, C. D., Jr., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1126/science.220.4598.671
Mirjalili, S. (2016). SCA: A sine cosine algorithm for solving optimization problems. Knowledge-Based Systems, 96, 120–133. https://doi.org/10.1016/j.knosys.2015.12.022
Mirjalili, S., & Lewis, A. (2016). The whale optimization algorithm. Advances in Engineering Software, 95, 51–67. https://doi.org/10.1016/j.advengsoft.2016.01.008
Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in Engineering Software, 69, 46–61. https://doi.org/10.1016/j.advengsoft.2013.12.007
Osuna-Enciso, V., Cuevas, E., & Morales-Castañeda, B. (2022). A diversity metric for population-based metaheuristic algorithms. Information Sciences, 586, 192–208. https://doi.org/10.1016/j.ins.2021.11.073
Rashedi, E., Nezamabadi-Pour, H., & Saryazdi, S. (2009). GSA: A gravitational search algorithm. Information Sciences, 179(13), 2232–2248. https://doi.org/10.1016/j.ins.2009.03.004
Stella, L., & Bauso, D. (2017). Evolutionary game dynamics for collective decision making in structured and unstructured environments. IFAC-PapersOnLine, 50(1), 11914–11919. https://doi.org/10.1016/j.ifacol.2017.08.1437
Storn, R., & Price, K. (1997). Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341–359. https://doi.org/10.1023/A:1008202821328
Vaziri, E., Dehdar, F., & 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.
https://www.ijfma.ir/article_20529.html
Weibull, J. W. (1995). Evolutionary game theory. MIT Press. https://mitpress.mit.edu/9780262231817/evolutionary-game-theory/
Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67–82. https://doi.org/10.1109/4235.585893
Yang, X.-S. (2010a). A new metaheuristic bat-inspired algorithm. En J. R. González, D. A. Pelta, C. Cruz, G. Terrazas, & N. Krasnogor (Eds.), Nature inspired cooperative strategies for optimization (NICSO 2010) (Studies in Computational Intelligence, Vol. 284, pp. 65–74). Springer. https://doi.org/10.1007/978-3-642-12538-6_6
Yang, X.-S. (2010b). Engineering optimization: An introduction with metaheuristic applications. Wiley. https://doi.org/10.1002/9780470640425
Yang, X.-S., & Deb, S. (2009). Cuckoo search via Lévy flights. En 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC) (pp. 210–214). IEEE. https://doi.org/10.1109/NABIC.2009.5393690
Descargas
Publicado
Versiones
- 2026-09-07 (2)
- 2026-07-28 (1)
