Download What is an Evolutionary Algorithm?

¿Qué es un Algoritmo Evolutivo?
Computación Evolutiva
Dr. Gregorio Toscano Pulido
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
 Las
siguientes diapositivas fueron tomadas de
las notas de A.E. Eiben, J.E. Smith (Capítulo 2
de su libro Introction to Evolutionary Computing)
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Contenido
 Esquema
básico de un AE
 Componentes básicos
– Representación / Evaluación / Población /
Selección / Recombinación / Mutación /
Selección de sobrevivientes/ Término
Ejemplos : eight queens / knapsack
 Comportamiento típico de AEs
 CE en el contexto de optimización global
–
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Métafora de la CE





Una población de individuos existe en un ambiente con
recursos limitados
Compiten por dichos recursos causa selección de los
invididuos más aptos (son aquellos que están mejor
adaptados al ambiente)
Estos individuos actuan como semillero para la generación
de nuevos invididuos a través de recombinación y mutación
Los nuevos individuos evalúan su aptitud y compiten
(posiblemente también contra los padres) por la
superviviencia.
A través del tiempo la selección natural causa un
incremento en la aptitud de la población
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?




Los AEs caen en la categoría de algoritmos de
“generación y prueba”
Son algoritmos basados en población y estocásticos
Los operadores de variación (recombinación y
mutación) crean la diversidad necesaria y de ese
modo facilitan el cambio
La sección reduce la diversidad y actúa como una
fuerza que incrementa la calidad
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Esquema general de un AE
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Pseudo-código típico de un EA
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
¿Cuáles son los diferentes tipos de
AEs?

Hitóricamente diferentes sabores de AEs han sido
asociados con diferentes representaciones
–
–
–
–

Como mejor estrategia siga:
–
–

Cadenas binarias : Algoritmos genéticos
Vectores de valores reales: Estrategias evolutivas
Máquinas de estado finito: Programación Evolutiva
Árboles LISP: Programación Genética
Escoja la represenciación que se ajusta más a su problema
Escoja operadores de variación que se ajuste a la
representación
Los operadores de selección son independientes de la
representación (únicamente usan la aptitud)
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Representaciones


Soluciones candidatas (individuos) existen en el espacio
genotípico
Son codificados en cromosomas, los cuales existen en el
espacio genotípico
–
–

Codificación: fenotipo=> genotipo (no necesariamente uno a uno)
Decodificación: genotipo=>fenotipo (debe ser uno a uno)
Cromosomas contienen genes, los cuales están en
posiciones llamadas loci (sing. locus) y tienen valores
(alelos)
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Función de Evaluación (Aptitud)



Representa el requerimiento a la que la población
necesita adaptarse también es conocida como función
calidad o función objetivo
Asigna un único valor real a cada fenotipo, el cual
forma las bases para la selección
– Entre más valores diferentes mejor
Típicamente hablamos de que la apttud tiene que ser
maximizada
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Población





Mantiene a las posibles soluciones
Usualmente tiene un tamaño fijo y es un conjunto de
genotipos
Algunos AEs sofisticados declaran un espacio
estructural en la población e.g. un grid
Los operadores de selección usualmente toman toda
la población en cuenta i.e. las probabilidades de
reproducción son relativas a la generación actual
La Diversidad de una población se refiere a número de
diferentes aptitudes/fenotipos/genotipos actuales
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Mecanismo de Selección de Padres



Asigna diferentes probabilidades a los individuos para
ser padres (dependiendo de su aptitud)
Usualmente son probabilísticos
– Usualmente las soluciones de mayor calidad son
padres más frecuentemente que las de baja calidad
pero no es garantizado
– Aún el peor en la generación actual tiene una
probabilidad de no-cero de llegar a convertirse en
padre
Esta naturaleza estocástica puede ayudar a escapar
de óptimo local
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Operadores de variación


Su rol es generar nuevas soluciones candidatas
Usualmente son divididas en dos tipos de acuerdo a su
aridad (número de entradas):
–
–
–

Aridad 1 : operadores de mutación
Aridad >1 : operadores de recombinación
Aridad = 2 típicamente llamada cruza
Hay mucho debate sobre la importancia relativa de la
recombinación y la mutación
–
–
Actualmente la mayoría de los AEs usan ambas
Escoger un operador de variación específico depende de la
representación
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Mutación



Actúa sobre un genotipo y entrega otro
Elementos de aleatoridad es indispensable y lo
diferencia de otros operadores heurísticos unarios
La importancia atribuida depende de en la
representación y dialecto:
–
–
–

GAs Binarios – operador responsible de preservar e introducir
diversidad
PE para MEF’s/ variables continuas – sólamente como un
operador de búsqueda
PG – dificilmente usado
Puede garantizar percolación de espacios de
búsqueda y por lo tanto pruebas de convergencia
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Recombinación





Transmite información de padres a hijos
La información que será transmitida es estocástica
La mayoría de los hijos podrían ser peores o iguales a
los padres
La esperanza es que si se combinan elementos del
genotipo que mejoren los rasgos, algunos hijos sean
mejores
Principalmente han sido usados por milenios por
agricultores y ganaderos
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Selección de sobrevivientes




También se le conoce como reemplazo
La mayoría de los AEs usan una población fija de tal
manera no pueden pasar padres e hijos a la siguiente
generación
Usualmente determinística
– Basado en aptitud : e.g., jerarquizar padres e hijos y
tomar el mejor
– Basados en edad: haz tantos hijos como padres y
elimina los padres
Algunas veces se realiza una combinación (elitismo)
Computación Evolutiva
¿Qué es un Algoritmo Evolutivo?
Inicialización/Término

La inicialización usualmente es aleatoria
–
–

Se necesita asegurar tanto la dispersión como la mezcla de
los posibles valores de los alelos
Puede incluir soluciones existentes, o usar heurísticas
específicas para sembrar la población
El término es verificado cada generación
–
–
–
–
Se alcazó alguna aptitud (conocida/esperada)
Se alzanzó algún máximo valor permitido de generaciones
Se alcanzó algún mínimo valor de diversidad
Se alcanzó algún número de generaciones sin mejorar la
aptitud