Departamento de Computación

En esta tesis se explora el uso de información del dominio incorporada durante la ejecución de un algoritmo evolutivo mediante un algoritmo cultural. Los algoritmos culturales son algoritmos evolutivos que soportan un mecanismo adicional para la extracción de información durante la misma ejecución del algoritmo, eliminando de esta forma la necesidad de codificar la informacion a priori. Primeramente, se desarrolló un algoritmo cultural para atacar problemas de optimización con restricciones. Tal algoritmo utiliza evolución diferencial como modelo para la población. Utilizando como base los operadores de la evolución diferencial, se diseñaron cuatro fuentes de conocimiento, cada una con una influencia particular sobre los operadores. Debido a que cada fuente de conocimiento presenta diferentes beneficios en diferentes fases de la búsqueda, se implementó un mecanismo maestro para controlar la frecuencia de aplicación de los operadores, basándose en la tasa de éxito de cada uno. Este algoritmo fue probado con un conjunto de problemas de prueba bien conocido y con un par de instancias de problemas de optimización de ingeniería, y se le comparó con otros algoritmos representativos del estado del arte en el área. En ambos casos, se obtuvieron iguales o mejores soluciones, requiriendo un número menor de evaluaciones de la función objetivo. En la siguiente fase, se desarrolló un algoritmo híbrido para atacar problemas de optimización multiobjetivo. Tal algoritmo es un híbrido entre el algoritmo previo para optimización con restricciones, y un método de programación matemática llamado restricción-E. Con este algoritmo se obtuvieron otras ventajas, tales como la generación de buenas aproximaciones del frente de Pareto en problemas que han resultado muy difíciles de resolver por otras técnicas evolutivas. Como un último aporte se presentó una propuesta para realizar incorporación de preferencias del usuario al algoritmo previo. El esquema propuesto se puede utilizar también en un conjunto amplio de otras técnicas. Esta propuesta está basada en el uso de vectores de metas. Con la incorporación de este enfoque, es posible reducir el costo computacional necesario al emplear el algoritmo híbrido en problemas con un número elevado de funciones objetivo, volviéndolo más adecuado para aplicaciones prácticas (v.g., del mundo real).

Abstract

RFID In this thesis we explore the use of domain information incorporated during the execution of an evolutionary algorithm, through the use of a cultural algorithm. The cultural algorithms are evolutionary algorithms that support an additional mechanism for information extraction during the execution of the algorithm, avoiding the need to encode the information a priori. Firstly, a cultural algorithm to tackle constrained optimization problems was developed. Such algorithm adopts differential evolution as its model for the population. Using the differential evolution operators as a basis, we designed four knowledge sources, each one with a particular influence over the operators. Since each knowledge source exhibits different benefits in different phases of the search, a main mechanism to control the application rate of the operators was developed, based on the success rate of each source. This algorithm was tested using a well-known benchmark and a pair of instances of engineering optimization problems, and was compared with other algorithms representative of the state-of-the-art in the area. In both cases, equal or better solutions were obtained, requiring a smaller number of objective function evaluations. In the next phase, a hybrid algorithm to tackle multiobjective optimization problems was developed. Such algorithm is a hybrid between the previous algorithm for constrained optimization, and a mathematical programming method called E-constraint. We obtained other advantages with this algorithm, such as good approximations of the Pareto front in problems that are very difficult to solve for other evolutionary approaches. As a last contribution, we introduced an approach to perform incorporation of user preferences to the previous algorithm. The proposed approach for incorporation of preferences can also be used in an wide variety of techniques. This proposal is based on the use of vectors of goals. With the addition of this approach, it is possible to reduce the computational cost needed when applying the hybrid algorithm on problems with a large number of objectives, which makes our proposal more suitable for practical (i.e., real-world) applications.