Desarrollo y calibrado de un algoritmo evolutivo para la resolución de problemas de optimización

Abstract

En el presente Trabajo Fin de Grado el principio objetivo se trata de desarrollar y calibrar un algoritmo evolutivo, el algoritmo NEMO Search, para la resolución de problemas de optimización. Este algoritmo está inspirado en el comportamiento de los peces payasos. Los problemas que se han escogidos para la prueba del algoritmo son el VRPTW y el problema de Steiner. Primeramente, antes de realizar las pruebas pertinentes en los problemas, se han realizado una serie de experimentos para la calibración del algoritmo determinando la mejor opción para los parámetros de diseño. Tras la calibración se han resuelto 4 baterías de problemas, 3 para el VRPTW y 1 para el problema de Steiner. Con el objetivo de poder realizar una comparación de la bondad del algoritmo, dichas baterías han sido resueltas adicionalmente, usando un algoritmo genético simple. Después de llevar a cabo las pruebas se obtiene que el algoritmo NEMO Search resuelve mucho más rápido los problemas del VRPTW, pero la calidad de las soluciones es muy pobre en comparación con las obtenidas utilizando el algoritmo genético simple, en cambio para el problema de Steiner se obtienen resultados similares tanto en tiempo de computación como en la calidad de las soluciones, por lo que se puede concluir que el algoritmo NEMO Search puede ser una buena opción para la resolución del problema de Steiner y en el caso del VRPTW es capaz de encontrar una solución muy rápido pero sin que la misma sea de mucha calidad.

In this Final Degree Project, the aim is to develop and calibrate an evolutionary algorithm, the NEMO Search algorithm, for solving optimization problems. This algorithm is inspired by the behavior of clownfish. The problems that have been chosen for the algorithm test are the VRPTW and the Steiner problem. First, before performing the relevant tests on the problems, a series of experiments have been carried out for the calibration of the algorithm determining the best option for the design parameters. After calibration, 4 problem batteries have been solved, 3 for the VRPTW and 1 for the Steiner problem. In order to be able to make a comparison of the goodness of the algorithm, said batteries have been additionally solved, using a simple genetic algorithm. After carrying out the tests it is obtained that the NEMO Search algorithm solves the problems of the VRPTW much faster, but the quality of the solutions is very poor compared to those obtained using the simple genetic algorithm, instead for the Steiner problem Similar results are obtained both in computing time and in the quality of the solutions, so it can be concluded that the NEMO Search algorithm can be a good option for the resolution of the Steiner problem and in the case of VRPTW it is able to find a very fast solution but without it being of high quality.