Extensión de un paquete de algoritmos metaheurísticos en R para la docencia

Abstract

En los últimos años se han realizado numerosos avances en el campo de la optimización combinatoria. Los algoritmos evolutivos han demostrado ser una herramienta muy valiosa para resolver problemas de optimización costosos. En concreto, los Algoritmos de Estimación de Distribuciones han atraído la atención de los investigadores y se han hecho numerosos avances al respecto. Sin embargo, no existe software que acerque estos avances a los alumnos. Este Trabajo de Fin de Grado trata de extender la librería metaheuR para que los estudiantes puedan comparar, combinar y aprender estos algoritmos resolviendo los problemas de optimización clásicos junto con el libro Bilaketa Heuristikoak aun en desarrollo. Bajo el lenguaje de programación R, este proyecto recoge 3 Algoritmos de Estimación de Distribuciones, el Estimation of Bayesian Network Algorithm que aprende una red Bayesiana como modelo probabilístico; el Edge Histogram Based Sampling Algorithm que aprende probabilidades marginales de orden dos y el Plackett-Luce Estimation of Distribution Algorithm que aprende un vector de pesos de la población. Además, se han realizado experimentos que verifican el correcto funcionamiento de los modelos implementados así como ejecuciones sobre problemas de optimización tales como el Travelling Salesman Problem o el Maximum Independence Set. Con estos resultados, también se han realizado comparativas y análisis de los resultados que dan una visión de la eficiencia de cada uno de los algoritmos.