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
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.
