Tesis de Maestría
La relatividad en la comparación de algoritmos de optimización ciega: hacia la coevolución de algoritmos y problemas
Fecha
2006-12-01Autor
Toledo Suárez, Carlos David
Institución
Resumen
Un sueño de la computación evolutiva es generar algoritmos que puedan adaptarse a los problemas que enfrentan y a través de estas adaptaciones volverse más aptos, análogamente a los procesos mediante los cuales las especies biológicas evolucionan en conjunto, coevolucionan. Con esta analogía en mente es que se llama coevolución de algoritmos y problemas al proceso de adaptación de algoritmos para resolver problemas sucesivamente más difíciles. Saber qué es fácil o difícil para cierto algoritmo de optimización es un problema de investigación abierto para el que se cree no puede existir un marco teórico definitivo, por la complejidad de los sistemas implicados. La tesis descrita en este documento propone que es posible usar a la coevolución de algoritmos y problemas para resolverlo, basándose en la hipótesis de que planteado como problema de optimización sólo es posible saber qué es fácil o difícil para un algoritmo de optimización ciega tomando en cuenta a otro. La principal contribución de la tesis es mostrar que asumir la hipótesis de la relatividad en la comparación de algoritmos de optimización ciega hace posible la implementación de la coevolución de algoritmos y problemas, que el problema planteado por dicha coevolución es complementario al de buscar problemas que hagan quedar mejor a un algoritmo frente a otro, a los que se les da el nombre de problemas tendenciosos. La implementación que se presenta corresponde a un algoritmo de coevolución incremental (ACI) en el que evolucionan dos poblaciones de afinaciones de algoritmos y una de problemas con el fin de encontrar problemas tendenciosos. Los algoritmos que compiten en el ACI son recocido simulado, algoritmo genético simple y búsqueda aleatoria. Posteriormente se hace la comparación entre las conclusiones obtenidas del análisis de los problemas tendenciosos encontrados y las teorías de dificultad para algoritmos genéticos, mostrando algunas discrepancias importantes.