Download Algoritmos Evolutivos - Departamento de Inteligencia Artificial

Departamento de Inteligencia Artificial
Grupo de Análisis de Decisiones y
Estadística
COMPUTACIÓN EVOLUTIVA
1
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
ÍNDICE
1. Introducción
2. Historia de la computación evolutiva
3. Algoritmos genéticos
4. Estrategias evolutivas
5. Programación evolutiva
6. Optimización Multiobjetivo Evolutiva
7. Tendencias de los MOEA
8. Conclusiones
2
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Durante muchos años, la tesis más aceptada sobre el origen de las
especies fue el creacionismo: Dios creó a todas las especies del
planeta de forma separada.
Además, según el creacionismo, las especies estaban jerarquizadas
por Dios de tal manera que el hombre ocupaba el rango superior, al
lado del creador.
3
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Georges Louis Leclerc (Conde de Buffon), 1749-1788, fue
tal vez el pri-mero en especular (100 años antes que
Darwin) que las especies se originaron entre sí, en una
abierta oposición al “creacionismo”.
Leclerc no sólo notó las similitudes entre el hombre y los simios,
sino que incluso especuló sobre la existencia de un posible ancestro
común entre estas 2 especies.
Leclerc creía en los cambios orgánicos, pero no describió un mecanismo
coherente que fuera responsable para efectuarlos, sino que especuló que
era el ambiente el que influía directamente sobre los organismos.
4
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
El biólogo francés Jean-Baptiste Lamarck enunció
una teoría sobre la evolución a principios del
siglo XIX.
Según Lamarck, las características (físicas) adquiridas
por un organismo durante su vida podían ser
transmitidas a sus descendientes.
5
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
El naturalista inglés Charles Darwin enunció su teoría
sobre el origen de las especies en 1858, derrumbando el
Lamarckismo al indicar que la evolución se origina a
través de cambios aleatorios de características hereditarias, combinados con un proceso de selección natural.
El científico alemán August Weismann formuló en el
siglo XIX una teoría denominada del germoplasma,
según la cual la información hereditaria se transmite a
través de ciertas células (llamadas germinales), mientras que otras células (llamadas somáticas) no pueden
transmitir nada.
6
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
August Weismann realizó un experimento en el que cortó las colas de un
grupo de ratas durante 22 generaciones (1,592 ratas), sin que las nuevas generaciones de ratas perdieran dicha extremidad, demostrando
entonces la falsedad de la hipótesis fundamental del Lamarckismo.
El monje austriaco Johann Gregor Mendel realizó una serie de experimentos con guisantes durante una buena parte de su vida, enunciando a
partir de ellos las leyes básicas que gobiernan la herencia.
7
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
James Mark Baldwin propuso en 1896 que si el aprendizaje ayuda a la supervivencia, entonces los organismos con mayor capacidad de aprendizaje tendrán
más descendientes, incrementando de esa manera la
frecuencia de los genes responsables del aprendizaje.
Baldwin planteó un impacto indirecto del aprendizaje sobre el proceso
evolutivo (un individuo con mayor capacidad de aprendizaje será más
apto), y no uno directo como Lamarck. A su propuesta se le conoce hoy
en día como el “efecto Baldwin”.
8
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Darwin
Weismann
Mendel
=
Neo-Darwinismo
9
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
El pensamiento evolutivo actual gira en torno al Neo-Darwinismo, el
cual establece que toda la vida en el planeta puede ser explicada a
través de sólo 4 procesos:
• Reproducción
• Mutación
• Competencia
• Selección
10
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
ÍNDICE
1. Introducción
2. Historia de la computación evolutiva
3. Algoritmos genéticos
4. Estrategias evolutivas
5. Programación evolutiva
6. Optimización Multiobjetivo Evolutiva
7. Tendencias de los MOEA
8. Conclusiones
11
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Historia de la Computación Evolutiva
La evolución natural ha sido vista como un proceso de
aprendizaje desde los 1930s, con el trabajo de Walter B.
Cannon (The Wisdom of the Body).
El célebre matemático Alan Mathison Turing reconoció
también una conexión “obvia” entre la evolución y el
aprendizaje de máquina en un artículo de 1950.
A fines de los 1950s y principios de los 1960s, el biólogo
Alexander S. Fraser publicó una serie de trabajos sobre
la evolución de sistemas biológicos en una computadora
digital, dando la inspiración para lo que después se
convertiría en el algoritmo genético.
12
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Aproximadamente en la misma época de Fraser, el
estadístico inglés George E. P. Box propuso un enfoque
evolutivo para la optimización de la producción industrial.
Su técnica, denominada EVOP (Evolutionary Operation) sigue en uso hoy en día en la industria química.
R. M. Friedberg fue uno de los primeros científicos en intentar evolucionar programas de computadora (a fines de los 1950s).
Sus experimentos no fueron muy exitosos, y originaron una avalancha
de críticas de parte de los investigadores de la IA clásica.
Nils Aall Barricelli desarrolló las que probablemente
fueron las primeras simulaciones de un sistema evolutivo en una computadora digital, entre 1953 y 1956.
Sus experimentos siguieron los lineamientos de una
disciplina bautizada a principios de los 1980s como
“vida artificial”.
13
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Hans J. Bremermann fue tal vez el primero en ver la
evolución como un proceso de optimización, además de
realizar una de las primeras simulaciones con cadenas
binarias que se procesaban por medio de reproducción
(sexual o asexual), selección y mutación, en lo que sería
otro claro predecesor del algoritmo genético.
Lawrence J. Fogel concibió el uso de la evolución simulada
en la solución de problemas (sobre todo de predicción)
hacia mediados de los 1960s. Su técnica se denominó
“Programación Evolutiva”.
Peter Bienert, Ingo Rechenberg y Hans-Paul
Schwefel desarrollaron hacia mediados de los
1960s un método de ajustes discretos aleatorios
inspirado en el mecanismo de mutación que
ocurre en la naturaleza.
Su técnica se denominó “estrategias evolutivas”.
14
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
John H. Holland desarrolló a principios de los 1960s los
“planes reproductivos” y “adaptativos” en un intento por
hacer que las computadoras aprendan imitando el proceso
de la evolución.
Esta técnica sería después conocida mundialmente como
el “algoritmo genético”.
Michael Conrad y H. H. Pattee se cuentan entre los primeros en simular un ecosistema artificial jerárquico en
el que un conjunto de organismos unicelulares estaban
sujetos a una estricta ley de conservación de la materia
que les inducía a competir por sobrevivir.
Conrad propuso también en los 1970s un “modelo de circuitos de aprendizaje evolutivo” en el cual especuló sobre
la posibilidad de que el cerebro use el mismo tipo de mecanismos que usa la evolución para aprender. Su técnica
fue uno de los primeros intentos por utilizar algoritmos
evolutivos para entrenar redes neuronales.
15
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Aunque los primeros intentos por evolucionar programas se remontan
a los 1950s y 1960s, fue hasta los 1980s en que se obtuvieron resultados satisfactorios.
Hicklin (1986) y Fujiki (1986) usaron expresiones-S en LISP para representar programas cuyo objetivo era resolver problemas de teoría
de juegos.
Nichal Lynn Cramer (1985) y posteriormente, John R. Koza (1989) propusieron (de forma independiente) el uso de una representación de
árbol en la que se implementó un operador de cruce para intercambiar
sub-árboles entre los diferentes programas de una población generada
al azar (con ciertas restricciones impuestas por la sintaxis del lenguaje
de programación utilizado).
La diferencia fundamental entre el trabajo de Cramer y el de Koza es
que el primero usó una función de aptitud interactiva (es decir, el usuario debía asignar a mano el valor de aptitud de cada árbol de la población), mientras el segundo logró automatizarla.
16
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
La propuesta de Koza fue la que se impuso a la
larga, y más tarde se denominó “Programación
Genética”.
Hoy en día es muy popular y cuenta con una
amplia gama de aplicaciones.
Thomas S. Ray desarrolló a principios de los 1990s un simulador muy
original en el que evolucionaban programas en lenguaje ensamblador,
los cuales competían por ciclos de CPU de una computadora, a la vez
que intentaban reproducirse (o sea, copiarse a sí mismos) en la memoria de dicha computadora.
En el simulador de Ray, denominado “Tierra”, se partía de un programa
único con la capacidad de auto-replicarse, al que se denominaba “ancestro”. Con base en este programa se generaban “criaturas” nuevas
(segmentos de código), las cuales a su vez se podían sub-dividir para
dar origen a nuevas criaturas.
17
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Tierra es uno de los pocos intentos por simular un ecosistema con el propósito expreso de observar los comportamientos que emergen de la dinámica evolutiva del mismo.
18
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
ÍNDICE
1. Introducción
2. Historia de la computación evolutiva
3. Algoritmos genéticos
4. Estrategias evolutivas
5. Programación evolutiva
6. Optimización Multiobjetivo Evolutiva
7. Tendencias de los MOEA
8. Conclusiones
19
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Los algoritmos evolutivos imitan los principios evolutivos naturales
para constituir procedimientos de búsqueda y optimización.
Algoritmos Genéticos
Los algoritmos genéticos (denominados originalmente
“planes reproductivos”) fueron desarrollados por John
H. Holland a principios de los 1960s. Su motivación
principal fue el aprendizaje de máquina.
Una definición bastante completa de un algoritmo genético es la propuesta
por John Koza:
"Es un algoritmo matemático altamente paralelo que transforma un conjunto
de objetos matemáticos individuales con respecto al tiempo usando
operaciones modeladas de acuerdo al principio Darwiniano de reproducción
y supervivencia del más apto, y tras haberse presentado de forma natural
una serie de operaciones genéticas de entre las que destaca la
recombinación sexual. Cada uno de estos objetos matemáticos suele ser
una cadena de caracteres (letras o números) de longitud fija que se ajusta
al modelo de las cadenas de cromosomas, y se les asocia con una cierta
20
función matemática que refleja su aptitud. "
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
El algoritmo básico es el siguiente:
-Generar (aleatoriamente) una población inicial
-Calcular aptitud de cada individuo
-Seleccionar (probabilísticamente) con base en aptitud
- Aplicar operadores genéticos (cruce y mutación) para generar la
siguiente población
- Ciclar hasta que cierta condición se satisfaga
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Organigrama de la forma de trabajo de un AG.
Conjunto aleatorio de soluciones es generado
Generación inicial
La evaluación de una solución significa calcular el
valor de la función objetivo y la violación de
restricciones
Asignar Aptitud
Condición de terminación es comprobada
La población de soluciones es modificada
por tres posibles operadores
El algoritmo genético enfatiza la importancia del cruce sexual
(operador principal) sobre el de la mutación (operador
secundario), y usa selección probabilística.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Para poder aplicar el Algoritmo Genético se requiere de los 5
componentes básicos siguientes:
Una representación de las soluciones potenciales del problema
Una forma de crear una población inicial de posibles soluciones
(normalmente un proceso aleatorio)
Una función de evaluación que juegue el papel del ambiente,
clasificando las soluciones en términos de su “aptitud”
Operadores genéticos que alteren la composición de los hijos
que se producirán para las siguientes generaciones
Valores para los diferentes parámetros que utiliza el Algoritmo Genético
(tamaño de la población, probabilidad de cruce, probabilidad de mutación,
número máximo de generaciones, etc.)
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Población
Tamaño de la población
Las poblaciones pequeñas corren el riesgo de no cubrir adecuadamente
el espacio de búsqueda, mientras que el trabajar con poblaciones de
gran tamaño puede acarrear problemas relacionados con el excesivo
costo computacional.
Goldberg efectuó un estudio teórico, obteniendo como conclusión que el
tamaño óptimo de la población para cadenas de longitud l, con codificación binaria, crece exponencialmente con el tamaño de la cadena.
Alander, basándose en evidencia empírica sugiere que un tamaño de
población comprendida entre l y 2I es suficiente para atacar con éxito
los problemas por él considerados.
Población inicial
Habitualmente la población inicial se escoge generando cadenas al azar,
pudiendo contener cada gen uno de los posibles valores del alfabeto con
probabilidad uniforme.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Función objetivo
La regla, general para construir una buena función objetivo es que ésta
debe reflejar el valor del individuo de una manera "real", pero en muchos
problemas de optimización combinatoria, donde existe gran cantidad de
restricciones, buena parte de los puntos del espacio de búsqueda representan individuos no válidos.
Para este planteamiento en el que los individuos están sometidos a restricciones, se han propuesto varias soluciones.
La primera sería la que podríamos denominar absolutista, en la que 'aquellos individuos que no verifican las restricciones, no son considerados como
tales, y se siguen efectuando cruces y mutaciones hasta obtener individuos
válidos, o bien, a dichos individuos se les asigna una función objetivo igual a
cero.
Otro enfoque está basado en la penalización de la función objetivo. La idea
general consiste en dividir la función objetivo del individuo por una cantidad
(la penalización) que guarda relación con las restricciones que dicho
individuo viola.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Un problema habitual en las ejecuciones de los Algoritmos Genéticos surge
debido a la velocidad con la que el algoritmo converge. En algunos casos la
convergencia es muy rápida, lo que suele denominarse convergencia prematura, en la cual el algoritmo converge hacia óptimos locales, mientras que en
otros casos el problema es justo el contrario, es decir se produce una convergencia lenta del algoritmo.
El problema de la convergencia prematura, surge a menudo cuando la selección de individuos se realiza de manera proporcional a su función objetivo.
En tal caso, pueden existir individuos con una adaptación al problema muy
superior al resto, que a medida que avanza el algoritmo "dominan" a la
población. Por medio de una transformación de la función objetivo, en este
caso una comprensión del rango de variación de la función objetivo, se
pretende que dichos "superindividuos" no lleguen a dominar a la población.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Algoritmos Genéticos Binarios
Ejemplo: Minimizar el coste del material de fabricación de un cilindro
cuyo volumen sea de al menos 300ml.
donde d es el diámetro y h la altura (0#d, h # 31).
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Representando una solución:
01000
d
01010
h
A la cadena se le llama “cromosoma”. A cada posición de la cadena se
le denomina “gen” y al valor dentro de esta posición se le llama “alelo”.
01000
d
23 = 8
01010
h
2 + 23 =10
29
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Asignando aptitud a una solución (función del valor de la solución en la
función objetivo o el valor de la solución en la función objetivo):
Generación de 6 soluciones aleatorias:
Dos soluciones no verifican la
restricción de un volumen mínimo de
300ml y es por ello que son
penalizadas
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Operador de Selección o Reproducción
El objetivo principal es duplicar buenas soluciones y eliminar malas
soluciones en una población
Métodos: Selección por torneo, selección proporcional y selección por
clasificación.
Selección por torneo.
El torneo es realizado entre dos soluciones y la mejor solución es elegida.
Luego otras dos son consideradas y elegida la mejor de ellas. Si se realiza sistemáticamente, cada solución puede ser elegida para participar
solamente en dos torneos.
31
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Un importante aspecto es que
sólo cambiando el operador de
comparación, podemos considerar un problema de minimización o de maximización.
32
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Método de selección proporcional
El número de copias de las solucioes es proporcional a su valor de aptitud.
Mecanismo de la ruleta
Usando el valor de aptitud Fi de todas las cadenas, la probabilidad de
seleccionar la i-ésima cadena es pi = Fi / ∑Fj
33
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Mecanismos de la ruleta de restos estocásticos
Las probabilidades pi son multiplicadas por lel tamaño de la población y el
número de copias esperado para cada solución es calculado para todas las
soluciones. Después, a cada solución es asignada un número de copias
igual a la parte entera de los números eperados. Después, el método de la
ruleta es aplicado con la parte fraccional del número esperado de todas las
soluciones para asignar más copias.
Una copia.
Ninguna copia
Mecanismo de la ruleta
34
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Muestreo Universal Estocástico
Sólo un número aleatorio es elegido para el proceso de selección completo, r.
35
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Método de selección ordenada
Primero, las soluciones son ordenadas de acuerdo a sus aptitudes, de la
peor (orden 1) a la mejor (orden N). Cada elemento de la lista ordenada
se le asigna una aptitud igual a su orden en la lista. Después, el operador
de selección proporcional es aplicado con los valores de aptitud de su
orden.
Operador cruce
En casi todos los operadores de cruce, dos cadenas son elegidas
aleatoriamente y una porción de la cadena son intercambiadas entre las
cadenas para crear dos nuevas cadenas.
36
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
En orden a preservar algunas buenas cadenas durante el operador de
reproducción, no todas las cadenas en la población son usadas para
cruzar. Si una probabilidad de cruce pc es usada, entonces 100pc%
cadenas de la población son usadas en la operación de cruce y 100(1-pc)%
de la población son simplemente copiados a la nueva población.
Con dos posiciones de cruce:
Con cruces uniformes (probabilidad 0.5 de cruzar cada gen)
37
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Operador de Mutación
El operador de mutación cambia el 1 por el 0, y viceversa, con una
probabilidad de mutación pm.
Reloj de mutación
Después que un gen es mutado, la localización del próximo gen mutado es
determinado por una distribución exponencial. La media de la distribución
se asume que es 1/pm. Primero, se genera un número aleatorio r ∈[0,1].
Luego, estimamos el próximo gen a ser estimado saltando –pmln(1-r)
posiciones del corriente gen.
38
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Algoritmos Genéticos con parámetro real
Cruce lineal (Wright, 1991)
Tres soluciones son creadas
0.5( xi(1,t ) + xi( 2,t ) ),1.5 xi(1,t ) − 0.5 xi( 2,t ) ,−0.5 xi(1,t ) + 1.5 xi( 2,t )
(1,t )
x
i
de dos soluciones padres:
xi( 2,t )
Eligiendo las dos mejores soluciones como descendiente
39
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Cruce simplista (Naive)
Este operador de cruce es similar al operador de cruce usado en los
AG con codificación binaria.
Caso bidimensional:
40
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Cruce Mezcla (Blend)
(1,t )
Para dos soluciones padres xi
xi( 2,t )
se elige aleatoriamente una solución en el rango
[x
(1,t )
i
(
)
(
− α xi( 2,t ) − xi(1,t ) , xi( 2,t ) + α xi( 2,t ) − xi(1,t )
)]
Así, si ui es un número aleatorio entre 0 y 1, el siguiente es un descendiente
xi(1,t +1) = (1 − γ i ) xi(1,t ) + γ i xi( 2,t )
donde
γ i = (1 + 2α )ui − α
41
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Si α es cero, este cruce crea una solución aleatoria en el rango
[x
(1,t )
i
, xi( 2,t )
]
En un número de problemas test, los investigadores han indicado que
BLX-0.5 funciona mejor que cualquier operador BLX con cualquier otro
valor α.
Cruce Binario Simulado
Trabaja con dos soluciones padres y crea dos descendienes.
Como el nombre sugiere, el operador simula el principio de trabajar del
operador de cruce de un solo punto sobre las cadenas binarias.
Primero, un número aleatorio ui entre 0 y 1 es creado. Después, de una
función de distribución de probabilidad, la ordenada βqi es encontrada
tal que el área bajo la curva de probabilidad de 0 a βqi sea igual al nú42
mero aleatorio elegido ui.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Distribución de probabilidad:
Padres
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Mutación aleatoria
El esquema más simple de mutación sería crear una solución aleatoria
del espacio de búsqueda entero:
donde ri es un número aleatorio en [0,1]
Este operador es independiente de la solución padre y es equivalente a una inicialización aleatoria.
En lugar de crear una solución del espacio
de búsqueda entero, una solución cercana
a la del padre con una distribución uniforme puede ser elegida:
44
donde ∆i es la perturbación máxima permitida en la variable de decisión i-esima.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Mutación No Uniforme
La probabilidad de crear una solución cercana al padre es mayor que la de
crear uno alejado
donde τ toma un valor booleano, -1 ó 1, cada uno
con probabilidad de 0.5. El parámetro tmax es el número máximo de generaciones permitidas, mientras b es un parámetro definido por el usuario.
Mutación Distribuida Normalmente
Un método simple y popular es usar una distribución de probabilidad Gaussiana de media cero:
donde σi es un parámetro definido por el usuario.
45
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Mutación Polinomial
La distribución de probabilidad puede también ser una función polinomial,
en lugar de una distribución normal.
Este parámetro es calculado de la distribución de probabilidad polinomial
46
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ejemplo: En la Tabla, hemos representado los 4 individuos que constituyen la inicial, junto con su función de adaptación al problema, así
como la probabilidad de que cada uno de dichos individuos sea seleccionado. según el modelo de ruleta sesgada para emparejarse
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
El siguiente paso consiste en la selección de 2 parejas de individuos.
Para ello es suficiente, con obtener 4 números reales provenientes de
una distribución de probabilidad uniforme en el intervalo (0, 1), y compararlos con la última columna de la Tabla anterior. Así por ejemplo,
supongamos que dichos 4 números hayan sido: 0.58; 0.84; 0.11 y 0.43.
Esto significa que los individuos seleccionados para el cruce han sido:
el individuo 2 junto con el individuo 4, así como el individuo 1 junto con
el individuo 2.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
La Figura muestra como varía la adaptación media y la mejor adaptación
en un Algoritmo Genético Simple típico.
A medida que el número de generaciones aumenta, es más probable que la
adaptación media se aproxime a la del mejor individuo.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Algoritmos Genéticos Paralelos
Modelos de islas.
La idea básica consiste en dividir la población total en varias subpoblaciones
en cada una de las cuales se lleva, a cabo un Algoritmo Genético.
Cada cierto número de generaciones, se efectúa un intercambio de
información entre las subpoblaciones, proceso que se denomina migración.
La introducción de la migración hace que los modelos de islas sean capaces
de explotar las diferencias entre las diversas subpoblaciones, obteniéndose
de esta manera una fuente de diversidad genética.
Cada subpoblación es una "isla", definiéndose un procedimiento por medio
del cual se mueve el material genético de una "isla" a otra.
La determinación de la tasa de migración, es un asunto de capital
importancia, ya que de ella puede depender la convergencia prematura de la
búsqueda.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Se pueden distinguir diferentes modelos de islas en función de la comunicación entre las subpoblaciones. Algunas comunicaciones típicas son las
siguientes:
Comunicación en estrella, en la cual existe una subpoblación que es seleccionada como maestra (aquella que tiene mejor media en el valor de la
función objetivo), siendo las demás consideradas como esclavas. Todas
las subpoblaciones esclavas mandan sus h1 mejores individuos (h1 > 1) a
la subpoblación maestra la cual a su vez manda sus h2 mejores individuos
(h2 > 1) a cada una de las subpoblaciones esclavas.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Comunicación en red, en la cual no existe una jerarquía entre las subpoblaciones, mandando todas y cada una de ellas sus h3 (h3 > 1) mejores
individuos al resto de las subpoblaciones.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Comunicación en anillo, en la cual cada subpoblación envía sus h4 mejores individuos (h4 > 1), a una población vecina, efectuándose la migración
en un único sentido de flujo.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Algunas aplicaciones de los AGs son las siguientes:
Optimización (estructural, de topologías, numérica, combinatoria, etc.)
Aprendizaje de máquina (sistemas clasificadores)
Bases de datos (optimización de consultas)
Reconocimiento de patrones (por ejemplo, imágenes)
Generación de gramáticas (regulares, libres de contexto, etc.)
Planeación de movimientos de robots
Predicción
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
ÍNDICE
1. Introducción
2. Historia de la computación evolutiva
3. Algoritmos genéticos
4. Estrategias evolutivas
5. Programación evolutiva
6. Optimización Multiobjetivo Evolutiva
7. Tendencias de los MOEA
8. Conclusiones
55
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Estrategias Evolutivas
Las estrategias evolutivas fueron desarrolladas en 1964 por un grupo
de estudiantes alemanes de ingeniería encabezado por Ingo Rechenberg. Su objetivo era resolver problemas hidrodinámicos de alto grado
de complejidad.
La versión original (1+1)-EE usaba un solo padre y con él se generaba un solo hijo. Este hijo se mantenía si era mejor que el padre, o de
lo contrario se eliminaba (a este tipo de selección se le llama extintiva, porque los peores individuos tienen una probabilidad de cero de
ser seleccionados).
En la (1+1)-EE, un individuo nuevo es generado usando:
donde t se refiere a la generación (o iteración) en la que nos encontramos, y N(0, ~) es un vector de números Gaussianos independientes con una media de cero y desviación estándar.
56
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ejemplo de una (1+1) - EE
Supongamos que queremos maximizar:
Ahora, supongamos que nuestra población consiste del siguiente
individuo (generado de forma aleatoria):
Supongamos también que las mutaciones producidas son las
siguientes:
57
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ejemplo de una (1+1) - EE
Ahora, comparamos al padre con el hijo:
Padre:
Hijo:
Dado que:
el hijo reemplazará al padre en la siguiente generación.
Ingo Rechenberg (1973) introdujo el concepto de población, al proponer una estrategia evolutiva llamada (μ + 1) − EE, en la cual hay μ
padres y se genera un solo hijo, el cual puede reemplazar al peor padre de la población (selección extintiva).
58
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Schwefel (1975) introdujo el uso de múltiples hijos en las denominadas
(μ + λ) − EEs y (μ, λ) − EEs. La notación se refiere al mecanismo de
selección utilizado:
a) En el primer caso, los μ mejores individuos obtenidos de la
unión de padres e hijos sobreviven.
b) En el segundo caso, sólo los μ mejores hijos de la siguiente
generación sobreviven.
Convergencia de las Estrategias Evolutivas
Rechenberg formuló una regla para ajustar la desviación estándar
de forma determinística durante el proceso evolutivo de tal manera
que el procedimiento convergiera hacia el óptimo.
Esta regla se conoce como la “regla del éxito 1/5”, y en palabras dice:
“ La razón entre mutaciones exitosas y el total de mutaciones debe ser
1/5. Si es más, entonces debe incrementarse la desviación estándar.
Si es menos, entonces debe decrementarse”.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Convergencia de las Estrategias Evolutivas
Formalmente:
donde n es el número de dimensiones, t es la generación, ps es la
frecuencia relativa de mutaciones exitosas medida sobre intervalos
de (por ejemplo) 10 · n individuos, y c=0.817 (este valor fue derivado teóricamente por Schwefel). (t) se ajusta cada n mutaciones.
Thomas Bäck (1996) derivó una regla de 1/7 para las
(μ+ λ)-EEs.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Auto-Adaptación
En las estrategias evolutivas se evoluciona no sólo a las variables
del problema, sino también a los parámetros mismos de la técnica
(es decir, las desviaciones estándar). A esto se le llama “autoadaptación”.
Los padres se mutan usando las siguientes fórmulas:
donde τ y τ son constantes de proporcionalidad que están en función
de n.
Los operadores de recombinación de las estrategias evolutivas pueden
ser:
- Sexuales: el operador actúa sobre 2 individuos elegidos aleatoriamente de la población de padres.
- Panmíticos: se elige un solo padre al azar, y se mantiene fijo mientras
se elige al azar un segundo padre (de entre toda la población) para
61
cada componente de sus vectores.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Las estrategias evolutivas simulan el proceso evolutivo al nivel
de los individuos, por lo que la recombinación es posible.
Asimismo, usan normalmente selección determinística.
Algunas aplicaciones de las estrategias evolutivas son:
-Problemas de ruteo y redes
-Bioquímica
-Óptica
-Diseño en ingeniería
- Magnetismo
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
ÍNDICE
1. Introducción
2. Historia de la computación evolutiva
3. Algoritmos genéticos
4. Estrategias evolutivas
5. Programación evolutiva
6. Optimización Multiobjetivo Evolutiva
7. Tendencias de los MOEA
8. Conclusiones
63
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Programación Evolutiva:
Lawrence J. Fogel propuso en 1960 una técnica denominada
“programación evolutiva”, en la cual la inteligencia se ve como
un comportamiento adaptativo.
La programación evolutiva es un algoritmo evolutivo basado en mutación
aplicado a espacios de búsqueda discreto.
David Fogel (Fogel, 1988) extendió el trabajo inicial de su padre Laary
Fogel para problemas de optimización continuos.
64
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
El algoritmo básico de la programación evolutiva es el siguiente:
-Generar aleatoriamente una población inicial.
-Se aplica mutación.
- Se calcula la aptitud de cada hijo y se usa un proceso de selección
mediante torneo (normalmente estocástico) para determinar cuáles
serán las soluciones que se retendrán.
La programación evolutiva es una abstracción de la evolución al nivel
de las especies, por lo que no se requiere el uso de un operador de
recombinación (diferentes especies no se pueden cruzar entre sí).
Asimismo, usa selección probabilística.
65
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Algunas aplicaciones de la programación evolutiva son:
• Predicción
• Generalización
• Juegos
• Control automático
• Problema del viajero
• Planeación de rutas
• Diseño y entrenamiento de redes neuronales
• Reconocimiento de patrones
66
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Estrategias Evolutivas vs Programación Evolutiva
La Programación Evolutiva usa normalmente selección estocástica,
mientras que las estrategias evolutivas usan selección determinística.
Ambas técnicas operan a nivel fenotípico.
La programación evolutiva es una abstracción de la evolución al nivel de
las especies, por lo que no se requiere el uso de un operador de recombinación (diferentes especies no se pueden cruzar entre sí).
En contraste, las estrategias evolutivas son una abstracción de la evolución al nivel de un individuo, por lo que la recombinación es posible.
67
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Algoritmos Genéticos vs otras técnicas evolutivas
El AG usa selección probabilística al igual que la Programación Evolutiva, y en contraposición a la selección determinística de las Estrategias
Evolutivas.
El AG usa representación binaria para codificar las soluciones en un problema, por lo cual se evoluciona el genotipo y no el fenotipo como en la
Programación Evolutiva o las Estrategias Evolutivas.
El operador principal en el AG es el cruce, y la mutación es un operador
secundario. En la Programación Evolutiva, no hay cruce y en las Estrategias Evolutivas es un operador secundario.
Ha sido demostrado (Rudolph, 1994) que el AG requiere de elitismo para
poder converger al óptimo.
Los AGs no son, normalmente, auto-adaptativos.
68
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Para simular el proceso evolutivo en una computadora se requiere:
Codificar las estructuras que se replicarán.
Operaciones que afecten a los “individuos”.
Una función de aptitud.
Un mecanismo de selección.
Diferencias de las técnicas evolutivas con respecto a las tradicionales
Las técnicas evolutivas usan una población de soluciones potenciales
en vez de un solo individuo, lo cual las hace menos sensibles a
quedar atrapadas en mínimos/máximos locales.
Las técnicas evolutivas no necesitan conocimientos específicos sobre
el problema que intentan resolver.
Las técnicas evolutivas usan operadores probabilísticos, mientras las
técnicas tradicionales utilizan operadores determinísticos.
Aunque las técnicas evolutivas son estocásticas, el hecho de que usen
69
operadores probabilísticos no significa que operen de manera análoga
a una simple búsqueda aleatoria.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ventajas de las Técnicas Evolutivas
Simplicidad Conceptual.
Amplia aplicabilidad.
Superiores a las técnicas tradicionales en muchos problemas del
mundo real.
Tienen el potencial para incorporar conocimiento sobre el dominio y
para hibridizarse con otras técnicas de búsqueda/optimización.
Pueden explotar fácilmente las arquitecturas en paralelo.
Son robustas a los cambios dinámicos.
Generalmente pueden auto-adaptar sus parámetros.
Capaces de resolver problemas para los cuales no se conoce
solución alguna.
70
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Comparaciones entre técnicas (parte 1)
71
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Comparaciones entre técnicas (parte 2)
72
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Críticas a las Técnicas Evolutivas
Criticada en sus orígenes (1960s) por los investigadores de la IA
simbólica. Se creía que una simple búsqueda aleatoria podía
superarlas.
La programación automática fue considerada una “moda pasajera”
en IA y el enfoque evolutivo fue visto como “un intento más” por
lograr lo imposible.
Actualmente, todavía muchas personas creen que un AG funciona
igual que una técnica “escalando la colina” que comienza de varios
puntos. Se ha demostrado que esto no es cierto.
Las técnicas sub-simbólicas (redes neuronales y computación
evolutiva) gozan de gran popularidad entre la comunidad científica
en general, excepto por algunos especialistas de IA clásica que
las consideran “mal fundamentadas” e “inestables”.
73
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
ÍNDICE
1. Introducción
2. Historia de la computación evolutiva
3. Algoritmos genéticos
4. Estrategias evolutivas
5. Programación evolutiva
6. Optimización Multiobjetivo Evolutiva
7. Tendencias de los MOEA
8. Conclusiones
74
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Optimización Multiobjetivo Evolutiva:
Pasado, Presente y Futuro
Motivación
Muchos problemas en la naturaleza tienen varios objetivos (posiblemente conflictivos) para ser satisfechos. Muchos de estos problemas son frecuentemente
tratados como problemas de optimización de un único objetivo.
¿Qué es un problema de optimización multiobjetivo?
El Problema de Optimización Multiobjetivo (también denominado optimización
multicriterio, o problema de optimización vectorial) puede definirse como el
problema de encontrar (Osyczka, 1985):
un vector de variables de decisión las cuales satisfacen las restricciones y optimizan una función vectorial cuyos elementos representan las funciones objetivos. Estas funciones forman una descripción matemática del logro de los criterios los cuales están usualmente en conflicto. Así, el término “optimizar” significa encontrar tal solución la cual debería dar los valores de todos las funciones
75
objetivos aceptables para el decisor.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Definición formal
Encontrar
tal que
Max/Min
s.a
76
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
¿Cuál es la noción de óptimo en Optimización Multiobjetivo?
Teniendo varias funciones objetivos, la noción de óptimo es diferente.
Realmente se intenta encontrar buenas soluciones de compromiso (o
“trade-offs”) en lugar de una única solución como en optimización global.
La noción de óptimo que es más comúnmente adoptada es la que
originalmente fue propuesta por Francis Ysidro Edgeworth in 1881.
77
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
¿Cuál es la noción de óptimo en Optimización Multiobjetivo?
Esta noción fue posteriormente generalizada por Vilfredo Pareto (in 1896).
Aunque algunos autores llaman óptimo de Edgeworth-Pareto, nosotros
usaremos el término más comunmente aceptado: óptimo de Pareto.
Definición de óptimo de Pareto
Decimos que un vector de variables de decisión
es óptimo de Pareto si no existe otro
tal que
y
para todo
para al menos un
78
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Definición de óptimo de Pareto
Esta definición dice que
es óptimo de Pareto si no existe otro vector
que decrezca algún criterio
factible de variables de decisión
sin causar un crecimiento simultáneo en al menos otro criterio.
Desafortunadamente, este concepto casi siempre no proporciona una
única solución, si no un conjunto de soluciones denominado conjunto
óptimo dePareto. Los elementos del conjunto óptimo de Pareto se
denominan soluciones no dominadas. El gráfico de las funciones
objetivos cuyos vectores no dominados están en el conjunto óptimo de
Pareto se denomina frontera de Pareto.
79
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Técnicas de Programación Matemática
Actualmente, hay sobre 30 técnicas de programación matemática para
optimización multiobjetivo. Sin embargo, estas técnicas tienden a generar
elementos del conjunto óptimo de Pareto de uno en uno. Además, muchos
de ellos son muy sensibles a la forma de la frontera de Pareto (por ej.
ellos no funcionan cuando la frontera de Pareto es cóncava o cuando la
Frontera es discontinua).
¿Por qué Algoritmos Evolutivos?
Los Algoritmos Evolutivos parecen particularmente adecuados para resolver problemas de optimización multiobjetivo, porque ellos tratan simultáneamente con un
conjunto de posibles soluciones (las poblaciones). Esto nos permite encontrar
varios miembros del conjunto óptimo de Pareto en cada ciclo del algoritmo, en
lugar de tener que realizar una serie de ejecuciones como en el caso de las técnicas de programación matemática tradicionales. Además, los algoritmos evolutivos
son menos sensibles a la forma o continuidad de la frontera de Pareto (por ej.,
pueden fácilmente tratar con fronteras de Pareto discontinuas o cóncavas), mientras estas dos cuestiones son una preocupación real para las técnicas de programación matemática.
80
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Reflejos históricos
El potencial de los algoritmos evolutivos en optimización multiobjetivo fue insinuado por Rosenberg
en el 1960, pero la primera implementación fue
realizada a mediados de 1980 (Schaffer,1984).
El primer esquema para incorporar las preferencias del
usuario en un algoritmo evolutivo multi-objetivo (MOEA)
fue propuesto al principio de los años 90 (Tanaka, 1992).
Durante diez años, el campo permaneció prácticamente
inactivo, pero comenzó a crecer a mediados de los 90,
donde varias técnicas y aplicaciones fueran desarrolladas.
81
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Algoritmos Evolutivos
Podemos considerar, en general, dos tipos de MOEA:
1. Algoritmos que no incorporan el concepto de dominancia de
Pareto en sus mecanismos de selección (ej. Aproximaciones
que usan funciones de agregación lineal).
2. Algoritmos que ordenan la población basándose en la
dominancia de Pareto (ej. MOGA, NSGA, NPGA, etc.).
Históricamente, podemos considerar la existencia de dos generaciones
Principales de MOEA:
1. Primera Generación: Caracterizado por el uso de ordenación de Pareto.
Algoritmos relativamente simples. Otras aproximaciones (más
rudimentarias) fueron también desarrolladas (ej. Funciones de agregación
lineal). Es también digno de mencionar VEGA, el cual es una aproximación
basada en la población (no basada en Pareto).
2. Segunda Generación: El concepto de elitismo es introducido en dos
formas principalmente: usando selección (µ+λ) y usando una población
82
secundaria externa.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
6. Optimización Multiobjetivo Evolutiva
6.1. Vector Evaluated Genetic Algorithm (VEGA)
6.2. MultiObjective Genetic Algorithm (MOGA)
6.3. Non-dominated Sorting Genetic Algorithm (NSGA)
6.4. Niched-pareto Genetic Algorithm (NPGA)
6.5. Strength Pareto Evolutionary Algorithm (I y II)
6.6. Non-dominated Sorting Genetic Algorithm II (NSGA II)
6.7. Pareto Archived Evolutionary Algorithm (PAES)
6.8. MicroGenetic Algorithm for Multobjetive Optimization (I
y II)
83
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Representativos MOEA (Primera Generación)
VEGA
MOGA
NSGA
NPGA
Propuesto por Schaffer en (1984,1985).
Usa subpoblaciones que optimizan cada objetivo separadamente.
El concepto de óptimo de Pareto no es incorporado directamente
en el mecanismo de selección del GA.
84
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
85
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Algoritmo:
Paso 1. Sea un contador de la función objetivo i = 1 y se define q=N/M.
Paso 2. Para todas las soluciones desde j=1+(i-1)*q a j = i*q, asignar
F(x(j)) = fi (x(j)).
Paso 3. Realizar selección sobre todas las q soluciones para crear una
subpoblación Pi.
Paso 4. Si i = M, ir al paso 5. En otro caso, incrementar i en uno e ir
al paso 2.
Paso 5. Combinar todas las subpoblaciones juntas:
M
P = i =1 Pi
Realizar cruce y mutación sobre P para crear una nueva
población.
86
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ejemplo (Problema con dos objetivos):
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ejemplo (Problema con dos objetivos):
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ejemplo (Problema con dos objetivos):
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ejemplo (Problema con dos objetivos):
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Simulación.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Simulación.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ventajas:
La principal ventaja de un VEGA es que usa una idea simple y es fácil
de implementar.
VEGA tiene tendencia a encontrar soluciones próximas a las mejores
soluciones de cada objetivo. En problemas donde tales soluciones sean
deseables, VEGA puede ser una buena alternativa.
Inconveniente:
Cada solución en un VEGA es evaluada solo en un objetivo. Así, cada
solución no es evaluada en M-1 objetivos.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
6. Optimización Multiobjetivo Evolutiva
6.1. Vector Evaluated Genetic Algorithm (VEGA)
6.2. MultiObjective Genetic Algorithm (MOGA)
6.3. Non-dominated Sorting Genetic Algorithm (NSGA)
6.4. Niched-pareto Genetic Algorithm (NPGA)
6.5. Strength Pareto Evolutionary Algorithm (I y II)
6.6. Non-dominated Sorting Genetic Algorithm II (NSGA II)
6.7. Pareto Archived Evolutionary Algorithm (PAES)
6.8. MicroGenetic Algorithm for Multobjetive Optimization (I
y II)
94
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Propuesto por Fonseca and Fleming (1993).
Primero, cada solución es chequeada su dominación en la población. A
una solución i, un orden igual a uno más el número de soluciones ni que
dominan a i es asignado: ri = 1 + ni.
95
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Para la solución i, dij es calculada para cada solución j que tenga el mismo
orden que i.
a=1
Función “sharing”
Determina una penalización de la aptitud de un individuo debido a su
cercanía con los vecinos.
Número de soluciones en
el rango ri
Recuento del nicho i :
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Dividir el valor de aptitud asignado por el recuento del nicho. En orden a
conservar la aptitud media de las soluciones en un orden igual que el de
antes del sharing, estos valores de aptitud son escalados de forma que sus
valores de aptitud shared promedio sea el mismo que el valor de aptitud
asignado promedio. Después, selección universal estocástica, cruce en un
solo punto y operador de mutación son aplicados para crear una nueva
población.
Ejemplo:
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Simulación:
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ventajas e Inconvenientes de MOGA
Eficiente y relativamente fácil de implementar.
Su rendimiento depende de lo apropiada de la selección del factor
de sharing.
MOGA fue el MOEA más popular y normalmente superaba a todos
sus competidores contemporáneos.
99
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
6. Optimización Multiobjetivo Evolutiva
6.1. Vector Evaluated Genetic Algorithm (VEGA)
6.2. MultiObjective Genetic Algorithm (MOGA)
6.3. Non-dominated Sorting Genetic Algorithm (NSGA)
6.4. Niched-pareto Genetic Algorithm (NPGA)
6.5. Strength Pareto Evolutionary Algorithm (I y II)
6.6. Non-dominated Sorting Genetic Algorithm II (NSGA II)
6.7. Pareto Archived Evolutionary Algorithm (PAES)
6.8. MicroGenetic Algorithm for Multobjetive Optimization (I
y II)
100
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Propuesto por Srinivas and Deb (1994).
Está basado sobre varias leyes de clasificaciones de los
individuos. Individuos no dominados obtienen un cierto valor
de ajuste artificial y luego son apartadas de la población. El
proceso es repetido hasta que la población entera ha sido
clasificada.
101
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Para la solución i, dij es calculada para cada solución j de la misma clase que
i.
Notar que la distancia es calculada con las variables de decisión, en lugar
de los valores de la función objetivo como en un MOGA.
a= 2
Función “sharing”
Determina una penalización de la aptitud de un individuo debido a su
cercanía con los vecinos.
Número de soluciones en
el rango ri
Recuento del nicho i :
Dividir el valor de aptitud asignado por el recuento del nicho.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Simulación:
El NSGA mantiene la diversidad
incluso sin el uso de un operador de
mutación.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ventajas e Inconvenientes de NSGA
Relativamente fácil de implementar.
Parece ser muy sensible al valor del factor de clasificación.
En algunos estudios comparativos a mediados de los 90, el NSGA era
normalmente superado por MOGA y NPGA.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
6. Optimización Multiobjetivo Evolutiva
6.1. Vector Evaluated Genetic Algorithm (VEGA)
6.2. MultiObjective Genetic Algorithm (MOGA)
6.3. Non-dominated Sorting Genetic Algorithm (NSGA)
6.4. Niched-pareto Genetic Algorithm (NPGA)
6.5. Strength Pareto Evolutionary Algorithm (I y II)
6.6. Non-dominated Sorting Genetic Algorithm II (NSGA II)
6.7. Pareto Archived Evolutionary Algorithm (PAES)
6.8. MicroGenetic Algorithm for Multobjetive Optimization (I
y II)
107
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Propuesto por Jeffrey Horn et al. (1993,1994).
Usa un esquema de selección de torneo basado en
la dominancia de Pareto. Dos individuos aletoriamente elegidos son comparados con un subconjunto de la población entera (típicamente, sobre el 10%
de la Población). Cuando ambos competidores son
dominados o no dominados (es decir, cuando hay
un empate), el resultado del torneo es realizado por
el ajuste en el objetivo (una técnica llamada sharing
de la clase equivalente es usada en este caso).
108
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ventajas e Inconvenientes de NPGA
Fácil de implementar.
Eficiente porque no aplica ordenación de Pareto a la población entera.
Parece tener un buen comportamiento general.
Además de requerir un factor de sharing, requiere otro parámetro
(tamaño del torneo).
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Simulación:
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
6. Optimización Multiobjetivo Evolutiva
6.1. Vector Evaluated Genetic Algorithm (VEGA)
6.2. MultiObjective Genetic Algorithm (MOGA)
6.3. Non-dominated Sorting Genetic Algorithm (NSGA)
6.4. Niched-pareto Genetic Algorithm (NPGA)
6.5. Strength Pareto Evolutionary Algorithm (I y II)
6.6. Non-dominated Sorting Genetic Algorithm II (NSGA II)
6.7. Pareto Archived Evolutionary Algorithm (PAES)
6.8. MicroGenetic Algorithm for Multobjetive Optimization (I
y II)
112
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Representativos MOEA (Segunda Generación)
SPEA and SPEA2
NSGA-II
PAES
El microGA para optimización
Multiobjetivo y el microGA2
SPEA fue introducido por Zitzler & Thiele (1999).
Usa un fichero externo conteniendo soluciones
no dominadas previamente encontradas.
SPEA calcula un valor de intensidad similar al
valor de ordenación usado por MOGA.
Una técnica de agrupación llamada “método de conexión
promedio” es usado para conservar la diversidad.
113
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Aptitud para los elementos de la
población externa
Aptitud para los elementos de la
población
Menor aptitud es mejor
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
El algoritmo comienza con una población creada aleatoriamente y una
externa.las soluciones no dominadas mejores de la
En población
cada generación
población son copiadas a la población externa
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Ventajas:
La agrupación asegura una mejor distribución entre las soluciones no
dominadas obtenidas.
El algoritmo de propagación es sin parámetros
El proceso de asignación de aptitud en el SPEA es más o menos similar al
de MOGA y fácil de calcular.
Inconvenientes:
El SPEA introduce un nuevo parámetro, el tamaño de la población externa.
Los investigadores del SPEA usan un ratio 1:4 entre la población externa y
el tamaño de la población.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Una versión revisada de SPEA ha sido recientemente propuesta: SPEA2
(Zitzler, 2001). SPEA2 tiene tres principales diferencias con respecto a
su predecesor: (1) incorpora un una estrategia de asignación de ajuste
granulado fino que considera para cada individuo el número de individuos
por los que es dominado; (2) usa una técnica de estimación de la densidad
de los vecinos más próximos, la cual guía la búsqueda más eficientemente
y, (3) tiene un método de truncamiento de ficheros mejorado que garantiza
la preservación de las soluciones frontera.
118
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
6. Optimización Multiobjetivo Evolutiva
6.1. Vector Evaluated Genetic Algorithm (VEGA)
6.2. MultiObjective Genetic Algorithm (MOGA)
6.3. Non-dominated Sorting Genetic Algorithm (NSGA)
6.4. Niched-pareto Genetic Algorithm (NPGA)
6.5. Strength Pareto Evolutionary Algorithm (I y II)
6.6. Non-dominated Sorting Genetic Algorithm II (NSGA II)
6.7. Pareto Archived Evolutionary Algorithm (PAES)
6.8. MicroGenetic Algorithm for Multobjetive Optimization (I
y II)
119
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Deb et al. (2000,2002) propuso una nueva versión del
Algoritmo Genético de Clasificación No Dominado
(NSGA), llamado NSGA-II, el cual es más eficiente (computacionalmente hablando), usa elitismo y un operador de
cruce que conserva la diversidad sin especificación de
ningún parámetro adicional.
120
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Tamaño
N
Tamaño
N
Población de
descendientes
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Operador de selección por torneo de crowding
Una solución i gana un torneo con otra solución j si alguna de las siguientes
condiciones son verdaderas:
1. Si la solución i tiene un mejor orden.
2. Si ellas tienen el mismo orden pero la solución i tiene una mejor
distancia de crowding que la solución j.
Para obtener una estimación de la densidad de soluciones alrededor de una
solución particular i en la población, tomamos la distancia promedio de dos
soluciones al lado de la solución i en cada uno de los objetivos.
Esta cantidad di sirve como una estimación del perímetro de la figura
formada usando los vecinos más próximos como los vértices.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
6. Optimización Multiobjetivo Evolutiva
6.1. Vector Evaluated Genetic Algorithm (VEGA)
6.2. MultiObjective Genetic Algorithm (MOGA)
6.3. Non-dominated Sorting Genetic Algorithm (NSGA)
6.4. Niched-pareto Genetic Algorithm (NPGA)
6.5. Strength Pareto Evolutionary Algorithm (I y II)
6.6. Non-dominated Sorting Genetic Algorithm II (NSGA II)
6.7. Pareto Archived Evolutionary Algorithm (PAES)
6.8. MicroGenetic Algorithm for Multobjetive Optimization (I
y II)
125
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
PAES fue introducido por Knowles & Corne (2000). Usa una
estrategia de evolución (1+1) junto con un fichero externo
que contenga todos los vectores no dominados previamente
encontrados. PAES usa una red adaptativa para mantener
la diversidad.
Inicialmente, una solución aleatoria x0 (llamado padre) es elegido. Este es
mutado usando una función de probabilidad distribuida normalmente con
media cero y con una fijada desviación típica. Sea c0 el descendiente
mutado. Ahora, ambas soluciones son comparadas y el ganador se convierte en el padre de la próxima generación. El quid del PAES está en la
forma de elegir el ganador.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
En cada generación t, además del padre y el descendiente, el PAES
mantiene un archivo de las mejores soluciones encontradas hasta entonces. Inicialmente, este archivo es vacío y como las generaciones
avanzan, las soluciones buenas son añadidas al archivo y adaptado.
Sin embargo, un tamaño máximo es mantenido. Primero, el padre pt y
el descendiente ct son comparados para dominación. Existen tres posibles escenarios.
Si pt domina a ct, el descendiente ct no es aceptado y una nueva solución mutada es creada. Por otro lado, si ct domina a pt, el descendiente
es mejor que el padre. Luego, la solución ct es aceptada como un padre
de la próxima generación y una copia de esta es guardada en el archivo. Esto es como el archivo obtiene población de soluciones no dominadas.
La complejidad se produce cuando ambos son no dominadas. En tal
caso, el descendiente es comparado con el archivo. Tres casos son
posibles.
Optimización Multiobjetivo basada en Metaheurísticas: Computación Evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
6. Optimización Multiobjetivo Evolutiva
6.1. Vector Evaluated Genetic Algorithm (VEGA)
6.2. MultiObjective Genetic Algorithm (MOGA)
6.3. Non-dominated Sorting Genetic Algorithm (NSGA)
6.4. Niched-pareto Genetic Algorithm (NPGA)
6.5. Strength Pareto Evolutionary Algorithm (I y II)
6.6. Non-dominated Sorting Genetic Algorithm II (NSGA II)
6.7. Pareto Archived Evolutionary Algorithm (PAES)
6.8. MicroGenetic Algorithm for Multobjetive Optimization (I
130
y II)
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Propuesto por Coello and Toscano-Pulido [2001].
Un algoritmo genético micro usa una población
de tamaño de 5 individuos. El principal aspecto
del microGA es el uso de un proceso de
reinicialización una vez que la convergencia es
alcanzada. El microGA para optimización
multiobjetivo usa 3 formas de elitismo y el grid
adaptativo de PAES.
131
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
132
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Propuesto por Pulido & Coello [2003]. La motivación
principal del μGA2 fue eliminar los 8 parámetros
requeridos por el algoritmo original. El μGA2
usa un mecanismo de adaptación on-line que
hace innecesario el ajuste de cada uno de sus
parámetros. El μGA2 puede decidir cuando parar
(ningún número máximo de generaciones tiene
que ser proporcionado por el usuario). El único
parámetro que requiere es el tamaño del fichero
externo (aunque existe obviamente un valor por
defecto para este parámetro).
133
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
134
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
ÍNDICE
1. Introducción
2. Historia de la computación evolutiva
3. Algoritmos genéticos
4. Estrategias evolutivas
5. Programación evolutiva
6. Optimización Multiobjetivo Evolutiva
7. Tendencias de los MOEA
8. Conclusiones
135
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Tendencias de los MOEA
Después del enorme éxito durante más de 10 años, los MOEA de primera generación han comenzado finalmente ha quedarse obsoletos
en la literatura (NSGA, NPGA, MOGA and VEGA).
Desde finales de los 90, los MOEA de segunda generación son considerados el estado del arte en optimización multiobjetivo evolutiva
(SPEA, SPEA2, NSGA-II, PAES, PESA, PESA II, microGA, etc.).
Los MOEA de segunda generación acentúan la eficiencia computacional.
Uno de los principales objetivos es encontrar formas sobre la
complejidad computacional de la ordenación de Pareto
donde k es el número de funciones objetivos y M es el tamaño de la
población) y sobre el coste computacional de niching
En gran medida ignorados por un número significante de investigadores,
MOEAs no Pareto son aún populares en Investigación Operativa
(en optimización combinatoria multiobjetivo), donde han sido muy 136
exitosos.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Manteniendo diversidad
Un aspecto importante de MOEAs es poder mantener la diversidad en la
población. Durante muchos años, clasificación por compartición fue el
mecanismo principal adoptado para esta propuesta (Goldberg & Richardson,1987). La idea de clasificación por compartición es dividir la población en varias poblaciones basándose en la similaridad entre individuos.
Obsérvese que cuando nos referimos a MOEAs, “similaridad” puede ser
medido en el espacio de variables de decisión (codificada o descodificada) o en el espacio de las funciones objetivos.
Clasificación por compartición es definido de la siguiente forma:
137
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
En la expresión de la transparencia anterior
indica la
distancia entre las soluciones i y j (en cualquier espacio definido), y
es un parámetro (o umbral) que define el tamaño del
nicho o vecindad. Cualquier solución dentro de esta distancia será
considera como parte del mismo nicho. El ajuste de un individuo i es
calculado usando:
donde M es el número de individuos localizados en la vecindad (o nicho)
del vecino i.
Otros esquemas son posible para mantener la diversidad y fomentar una
buena extensión de soluciones. Por ejemplo:
Técnicas de cruce.
Técnicas de clastering.
El grid adaptativo de PAES (Knowles & Corne, 2000).
El uso del concepto de entropía.
138
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Problemas test de Zitzler-Deb-Thiele
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
ÍNDICE
1. Introducción
2. Historia de la computación evolutiva
3. Algoritmos genéticos
4. Estrategias evolutivas
5. Programación evolutiva
6. Optimización Multiobjetivo Evolutiva
7. Tendencias de los MOEA
8. Conclusiones
146
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Conclusiones
Todos los algoritmos evolutivos multiobjetivo son mejores que el método de
búsqueda aleatoria (RAND).
El NSGA supera a todos los otros algoritmos no elitistas (excepto al SPEA) en
todos los problemas.
La no convexidad en la frontera optima de Pareto de ZDT2 causó dificultades
al HLGA, VEGA y SOGA. Ya que estos tres algoritmos usan la suma pesada
de los objetivos, era esperado que tuvieran dificultades en resolver un problema con una frontera de Pareto óptima no convexa.
La discretización en la frontera óptima de Pareto para ZDT3 causó dificultades
a muchos algoritmos en encontrar un conjunto diversificado de soluciones.
Multimodalidad (ZDT4) y engaño (ZDT6) causó dificultades a todos los algoritmos para converger a la verdadera frontera óptima de Pareto. Era claro que
parámetros diferentes (quizás con un tamaño de población mayor) era necesario para encontrar la verdadera frontera en estos problemas.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Un espacio de búsqueda con una densidad no uniforme (ZDT6) causó
dificultades a todos los algoritmos excepto al SPEA en mantener un
conjunto diverso de soluciones.
Una jerarquía de algoritmos emergió en términos de su rendimiento en
encontrar un conjunto de soluciones próximas a la verdadera frontera
óptima de Pareto. La jerarquía en orden descendente es:
1.
2.
3.
4.
5.
6.
SPEA;
NSGA;
VEGA;
NPGA, HLGA;
MOGA;
RAND.
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Software de Dominio Público
BUGS (Better to Use Genetic Systems)
El uso de este programa suele facilitar la comprensión de lo que son
los AGs y cómo funcionan para aquellos novatos en el área.
s
de demostrar los operadores genéticos fundamentales (selección,
cruce y mutación).
http://www.aic.nrl.navy.mil/pub/galist/src/BUGS.tar.Z
Genesis
Implementación de un AG que tiene gran valor histórico por haber
sido el primer programa de su tipo liberado en el dominio público.
http://www.aic.nrl.navy.mil/pub/galist/src/genesis.tar.Z
149
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
GENEsYs
Software de Dominio Público
Implementación de un AG basada en GENESIS que incluye
extensiones y nuevas funciones para propósitos experimentales.
http://www.aic.nrl.navy.mil/pub/galist/src/GENEsYs-1.0.tar.Z
DGenesis
Implementación de un AG distribuido desarrollada a partir de
GENESIS 5.0.
http://www.aic.nrl.navy.mil/pub/galist/src/dgenesis-1.0.tar.Z
150
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Software de Dominio Público
GECO (Genetic Evolution through Combination of Objects)
Ambiente de trabajo orientado a objetos para implementar prototipos
de algoritmos gen eticos. Usa el CLOS (Common LISP Object System)
y cuenta con abundante documentaci on y algunos ejemplos de uso.
http://www.aic.nrl.navy.mil/pub/galist/src/GECO-v2.0.tar.Z
GALOPPS
Parallelism)
(Genetic
Algorithm
Optimized
for
Portability
and
Un sistema de AGs paralelos
http://GARAGE.cps.msu.edu/
151
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Software de Dominio Público
ESCaPaDE
Sofisticado sistema que permite correr experimentos con algoritmos
evolutivos tales como la estrategia evolutiva. El sistema cuenta con
2 tablas internas: una de funciones objetivo y una de monitores de
datos, lo que permite una fácil implementación de funciones para
monitorear todo tipo de información dentro del algoritmo evolutivo.
Por e-mail a Hoffmeister
([email protected])
GANNET (Genetic Algorithm/Neural NETwork)
Paquete de software que permite evolucionar redes neuronales binarias.
Ofrece toda una variedad de opciones de configuración relacionadas con
los valores de los operadores genéticos.
http://fame.gmu.edu/˜dduane/thesis
152
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Software de Dominio Público
GPC++
Biblioteca de clases en C++ para desarrollar aplicaciones de
programación genética. Esta biblioteca define una jerarquía de
clases y uno de sus componentes integrales es la capacidad de
producir funciones definidas automáticamente.
http://www.emk.e-technik.thdarmstadt.de/˜thomasw/gp.html
GPEIST (Genetic Programming Environment in SmallTalk)
Ambiente de programación genética en Smalltalk que puede
correrse en HP/Sun/PC. Permite distribución de subpoblaciones
en varias estaciones de trabajo (con intercambios entre ellas a
ciertos intervalos)
http://www.cs.bham.ac.uk/Mirrors/ftp.de.uu.net/EC/clife/
153
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Software de Dominio Público
PGAPack
Biblioteca de prop osito general para desarrollar AGs paralelos.
http://www.mcs.anl.gov/pgapack.html
REGAL (RElational Genetic Algorithm Learner)
Sistema distribuido basado en AGs diseñado para aprender
descripciones de conceptos en lógica de primer orden a partir de
ejemplos.
Se basa en un operador llamado “Sufragio Universal” que permite la
probable convergencia asintótica de la población a un estado de
equilibrio en el que coexisten varias especies.
ftp://ftp.di.unito.it/pub/MLprog/REGAL3.2
154
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Software de Dominio Público
SCS-C (Simple Classifier System in C)
Versión en C del Sistema Clasificador Simple proporcionado
en el libro de Goldberg.
Software Comercial
ActiveGA
Un OLE que usa un algoritmo genético para solucionar un problema
dado.
Evolver
Paquete de algoritmos genéticos paraWindows.
155
Búsqueda Inteligente basada en Metaheurísticas: Computación evolutiva
Software Comercial
PC-Beagle
Programa que examina una base de datos con ejemplos y usa
técnicas de aprendizaje de máquina para crear un conjunto de
reglas de decisión que clasifiquen los ejemplos
MicroGA
Herramienta que permite laóde un ambiente de programación en
C++ que viene en código fuente con documentación y 3 ejemplos
completos.
GEATbx (Genetic and Evolutionary Algorithm Toolbox)
Conjunto de funciones enMATLAB que permiten implementar
diferentes tipos de algoritmos genéticos para optimización con
uno o varios objetivos.
156