Departamento de Computación

Este trabajo doctoral consiste en un estudio sobre el manejo de restricciones en algoritmos evolutivos. La investigación versa sobre cinco contribuciones principales: (1) Un estudio empírico para analizar las bondades de utilizar conceptos de optimización multiobjetivo para manejar las restricciones en un problema de optimización gobal; para ello se compararon cuatro técnicas representativas del estado del arte. El objetivo principal de éste estudio fue el evitar el uso de las funciones de penalización para resolver problemas con restricciones. Con base en los resultados obtenidos, (2) se propuso una técnica novedosa y competitiva para resolver problemas restringidos utilizando un algoritmo evolutivo (una estrategia evolutiva en este caso), la cual no requiere del uso de una función de penalización, sino que maneja la función objetivo y las restricciones del problema de manera separada. El algoritmo utiliza un mecanismo simple de diversidad que le permite soluciones no factibles cercanas a la zona factible y con un buen valor de la función objetivo el permanecer en la población de la siguiente generación. Además, usa un mecanismo de comparación de individuos basado en factibilidad para guiar al algoritmo hacia la zona factible del espacio de búsqueda. La longitud de paso inicial del operador de mutación es reducido con el objeto de permitir movimientos más finos en el espacio de búsqueda. Así también, el operador de recombinación se diseñó combinando dos sencillos operadores encontrados en la literatura (recombinación discreta/intermedia) con el objeto de mejorar la capacidad explotatoria del mismo. Se realizaron experimentos para averiguar cuál de estos mecanismos (diversidad, movimientos finos de mutación y recombinación combinada) era el principal responsable del buen desempeño de la técnica, la cual fue comparada con algoritmos del estado del arte, usando un conjunto de problemas con restricciones usualmente utilizado en la literatura. Por otro lado, (3) se llevaron a cabo estudios estadísticos que permitieron entender con mayor detalle el comportamiento del algoritmo. Este análisis se basó en el uso de tres medidas de desempeño relacionadas con la velocidad de llegada a la zona factible, el evaluar el progreso de la búsqueda dentro de ella y analizar el desempeño del mecanismo de diversidad al mantener o generar nuevas soluciones no factibles. Aunado a esto (4) se realizó un análisis de varianza para conocer la sensibilidad de la técnica a sus parámetros y poder sugerir valores para ellos. Después, se realizó otro estudio empírico, este para saber las características de un problema que lo hacen difícil de resolver usando la técnica propuesta en este trabajo. Finalmente, con base en resultados teoricos encontrados en la literatura, (5) se realizó la demostración formal de convergencia global del algoritmo propuesto.