Departamento de Computación

En los problemas de optimización del mundo real existen restricciones de diferentes tipos (p. ej. físicas, de tiempo, geométricas, etc.) las cuales modifican la forma del espacio de búsqueda. Durante los últimos años, una variedad de meta-heurísticas han sido diseñadas y aplicadas para la solución de problemas de optimización restringida donde no hay métodos clásicos de programación matemática disponibles. Los Algoritmos Evolutivos y otras meta-heurísticas operan como técnicas de búsqueda sin restricciones cuando son usados en optimización. Así, éstas requieren un mecanismo adicional que incorpore las restricciones del problema en su estructura. Históricamente, en los algoritmos evolutivos y en la programación matemática la propuesta más común de incorporación de restricciones es usando funciones de penalización, las cuales fueron originalmente propuestas en la década de los 40s y después fueron expandidas por muchos investigadores. En general, las funciones de penalización tiene varias limitaciones. Una de las más importantes es la necesidad de ajustar los factores de penalización. En algunos casos, existen muchos factores que deben ser ajustados y en la mayoría de los casos sus valores son dependientes del problema.
La Evolución Diferencial es un método estocástico global de búsqueda directa, el cual forma parte de estas nuevas meta-heurísticas y que ha probado ser un procedimiento muy efectivo en la optimización numérica sin restricciones. Así, ha habido algunas propuestas para extender el algoritmo de Evolución Diferencial a espacios de búsqueda restringidos.
En esta tesis se propone una nueva versión del algoritmo de Evolución Diferencial para resolver problemas de optimización restringida. Se propone un nuevo modelo así como un mecanismo de manejo de restricciones basado en funciones de penalización, en el cual no es necesario ajustar factores de penalización.
Esta nueva versión del algoritmo de Evolución Diferencial es comparada contra los algoritmos más representativos en optimización restringida usando un conjunto de problemas de prueba estándar utilizados en el área de Computación Evolutiva.