Un nuevo enfoque de optimización basado en la teoría evolutiva de juegos no estructurada
DOI:
https://doi.org/10.32870/recibe.v13i1.332Keywords:
Optimización, Competición, Metaheurística, Teoría de Juegos, Metropolis-HastingAbstract
Proponer nuevos métodos metaheurísticos es crucial para la mejora continua en el desarrollo dealgoritmos y la capacidad de abordar con eficacia problemas de optimización del mundo real cadavez mas complejos. Por otro lado, la Teoría Evolutiva de Juegos analiza cómo a través de lacompetencia es posible modificar las estrategias de los individuos dentro de una población con elfin de extender los mecanismos exitosos y reducir o eliminar las estrategias menos exitosas. Esteartículo presenta un novedoso enfoque de optimización basado en los principios de la TeoríaEvolutiva de Juegos. En el método propuesto, todos los individuos se inicializan mediante latécnica Metropolis-Hasting, que sitúa las soluciones en un punto de partida más cercano a lasregiones óptimas o casi óptimas del problema. Se asigna una estrategia original a cada individuode la población. Al tener en cuenta las interacciones y la competencia entre los distintos agentesdel problema de optimización, el enfoque modifica las estrategias para mejorar la eficiencia de labúsqueda y encontrar mejores soluciones. Para evaluar el rendimiento de la técnica propuesta, secompara con ocho algoritmos metaheurísticos bien conocidos utilizando 30 funciones de prueba.La metodología propuesta demostró superioridad en términos de calidad de la solución,dimensionalidad y convergencia en comparación con otros enfoques.References
X.-S. Yang, Engineering Optimization. An Introduction with Metaheuristic Applications. United States of America: WILEY, 2010.
M. Abdel-Basset, L. Abdel-Fatah, and A. K. Sangaiah, "Metaheuristic Algorithms: A Comprehensive Review," Comput. Intell. Multimed. Big Data Cloud with Eng. Appl., pp. 185–231, Jan. 2018.
B. Chopard and M. Tomassini, An introduction to metaheuristics for optimization. 2018.
T. Dokeroglu, E. Sevinc, T. Kucukyilmaz, and A. Cosar, "A survey on new generation metaheuristic algorithms," Comput. Ind. Eng., vol. 137, no. August, p. 106040, 2019.
D. Karaboga, "An idea based on honey bee swarm for numerical optimization," 2005.
X.-S. S. Yang, "A New Metaheuristic Bat-Inspired Algorithm BT - Nature Inspired Cooperative Strategies for Optimization (NICSO 2010)," Stud. Comput. Intell., vol. 284, pp. 65–74, 2010.
R. Storn and K. Price, "Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces," Australas. Plant Pathol., vol. 38, no. 3, pp. 284–287, 1995.
J. Kennedy, R. Eberhart, and B. Gov, "Particle Swarm Optimization," Encycl. Mach. Learn., pp. 760–6, 1995.
X. S. Yang and S. Deb, "Cuckoo search via Lévy flights," 2009 World Congr. Nat. Biol. Inspired Comput. NABIC 2009 - Proc., pp. 210–214, 2009.
A. Askarzadeh, "A novel metaheuristic method for solving constrained engineering optimization problems: Crow search algorithm," Comput. Struct., vol. 169, pp. 1–12, Jun. 2016.
A. Auger and N. Hansen, "Performance evaluation of an advanced local search evolutionary algorithm," 2005 IEEE Congr. Evol. Comput. IEEE CEC 2005. Proc., vol. 2, pp. 1777–1784, 2005.
E. Cuevas, A. Echavarría, and M. A. Ramírez-Ortegón, "An optimization algorithm inspired by the States of Matter that improves the balance between exploration and exploitation," Appl. Intell., vol. 40, no. 2, pp. 256–272, Mar. 2014.
S. Mirjalili, "SCA: A Sine Cosine Algorithm for solving optimization problems," Knowledge-Based Syst., vol. 96, pp. 120–133, 2016.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science (80-. )., vol. 220, no. 4598, pp. 671–680, May 1983.
E. Cuevas, A. Echavarría, and M. A. Ramírez-Ortegón, "An optimization algorithm inspired by the States of Matter that improves the balance between exploration and exploitation," Appl. Intell., vol. 40, no. 2, pp. 256–272, Mar. 2014.
A. R. Giri, T. Chen, V. P. Rajendran, and A. Khamis, "A Metaheuristic Approach to Emergency Vehicle Dispatch and Routing," 2022 IEEE Int. Conf. Smart Mobility, SM 2022, pp. 27–31, 2022.
A. Afzal et al., "Optimizing the thermal performance of solar energy devices using meta-heuristic algorithms: A critical review," Renew. Sustain. Energy Rev., vol. 173, p. 112903, Mar. 2023.
E. Vaziri, F. Dehdar, and M. R. Abdoli, "Feasibility study of using meta-heuristic algorithms on optimizing of the integrated risk in banking system," Int. J. Financ. Manag. Account., vol. 8, no. 28, pp. 143–158, Jan. 2023.
S. Kaur, Y. Kumar, A. Koul, and S. Kumar Kamboj, "A Systematic Review on Metaheuristic Optimization Techniques for Feature Selections in Disease Diagnosis: Open Issues and Challenges," Arch. Comput. Methods Eng. 2022 303, vol. 30, no. 3, pp. 1863–1895, Nov. 2022.
D. H. Wolpert and W. G. Macready, "No free lunch theorems for optimization," IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 67–82, 1997.
Wu, B., Bauer, B., Galla, T., & Traulsen, A. (2015). Fitness-based models and pairwise comparison models of evolutionary games are typically different—even in unstructured populations. New Journal of Physics, 17(2), 023043.
Li, Q., Liu, S. Y., & Yang, X. S. (2020). Influence of initialization on the performance of metaheuristic optimizers. Applied Soft Computing, 91, 106193.
E. Cuevas, H. Escobar, R. Sarkar, and H. F. Eid, "A new population initialization approach based on Metropolis–Hastings (MH) method," Appl. Intell., vol. 53, no. 13, pp. 16575–16593, Dec. 2022.
H. Gintis, Game theory evolving: A problem-centered introduction to modeling strategic behavior. Princeton university press, 2000.
L. R. Izquierdo, S. S. Izquierdo, and W. H. Sandholm, “Agent-Based Evolutionary Game Dynamics Agent-Based Evolutionary Game Dynamics,” Univ. Wisconsin Press., p. 207, 2020.
O. Kapliński and J. Tamošaitiene, "Game theory applications in construction engineering and management," Technol. Econ. Dev. Econ., vol. 16, no. 2, pp. 348–363, 2010.
T. M. Choi, A. A. Taleizadeh, and X. Yue, "Game theory applications in production research in the sharing and circular economy era," https://doi.org/10.1080/00207543.2019.1681137, vol. 58, no. 1, pp. 118–127, Jan. 2019.
M. Leng and M. Parlar, "Game Theoretic Applications in Supply Chain Management: A Review," http://dx.doi.org/10.1080/03155986.2005.11732725, vol. 43, no. 3, pp. 187–220, 2016.
McAvoy, A., & Wakeley, J. (2022). Evaluating the structure-coefficient theorem of evolutionary game theory. Proceedings of the National Academy of Sciences, 119(28), e2119656119.
C. Leboucher et al., "An enhanced particle swarm optimization method integrated with evolutionary game theory," IEEE Trans. Games, vol. 10, no. 2, pp. 221–230, Jun. 2018.
J. W. Weibull, Evolutionary game theory. MIT press, 1997.
P. Hammerstein and R. Selten, "Game theory and evolutionary biology," Handb. game theory with Econ. Appl., vol. 2, pp. 929–993, 1994.
Agushaka, J. O., Ezugwu, A. E., Abualigah, L., Alharbi, S. K., & Khalifa, H. A. E. W. (2023). Efficient initialization methods for population-based metaheuristic algorithms: a comparative study. Archives of Computational Methods in Engineering, 30(3), 1727-1787.
D. B. Hitchcock, "A History of the Metropolis–Hastings Algorithm," http://dx.doi.org/10.1198/0003130032413, vol. 57, no. 4, pp. 254–257, 2012.
E. Cuevas, H. Escobar, R. Sarkar, and H. F. Eid, "A new population initialization approach based on Metropolis–Hastings (MH) method," Appl. Intell., vol. 53, no. 13, pp. 16575–16593, Dec. 2022.
F. Wilcoxon, "Probability Tables for Individual Comparisons by Ranking Methods," Biometrics, vol. 3, no. 3, p. 119, Sep. 1947.
