PDF de programación - Introducción a la Computación Evolutiva

Introducción a la Computación Evolutiva

Sexta Clase: Algoritmos Meméticos

Agenda

• Motivos de la hibridización
• Lugares en donde hibridizar
• Incorporación de buenas soluciones
• Búsqueda Local
• Adaptación Lamarckiana vs. Baldwiniana
• Preservación de la Diversidad
• Elección de Operadores de Búsqueda Local

Motivos de la hibridización

• Incorporar a un AE como parte de un sistema más

grande

• Mejorar las técnicas evolutivas actuales sin

reinventar su comportamiento general (operadores
especializados, buenas soluciones iniciales, etc.)
• Mejorar la búsqueda de buenas soluciones que

desarrolla un AE (mejorar el refinamiento de
buenas soluciones halladas para obtener óptimos)
– Incorporar una fase de búsqueda local al ciclo evolutivo
para explorar de manera más sistemática la vecindad de
las buenas soluciones

1

Visión de Michalewicz (´90s) sobre AEs:

métodos de resolución de problemas

Algoritmos Meméticos

• La combinación de Algoritmos Evolutivos (AEs)
con Operadores de Búsqueda Local (BL) ha sido
definida como Algoritmos Meméticos (AM)
– Los operadores de BL son insertados en el ciclo

evolutivo que desarrolla un AE

• El término AM también se aplica a AEs que usan

conocimiento específico del problema en los
operadores

• Los AMs han mostrado ser mucho más rápidos y
más precisos que los AEs sobre varios problemas,
y están siendo investigados sobre muchos
problemas

Lugares en donde hibridizar

2

Heurísticas para inicializar la población

• En general, se recomienda inicializar la población

de manera aleatoria

• Sin embargo, inicializar la población con buenas

soluciones conocidas puede ofrecer beneficios
interesantes
– Reducir el esfuerzo computacional requerido por un AE

para alcanzar buenas soluciones iniciales puede
producir un incremento de la eficiencia (velocidad)

– Una población inicial no aleatoria dirige la búsqueda

hacia regiones del espacio que contienen buenas
soluciones.
• Sesgar la búsqueda puede resultar en un incremento de la

efectividad (calidad de la solución final)

Heurísticas para inicializar la población

• Sembrar a la población con soluciones de buena

calidad ya conocidas, o encontradas mediante
otras técnicas

• Inicialización Selectiva: se genera un número (k .
N) de soluciones aleatorias y, luego, se selecciona
a aquellas que formarán la población inicial.
Alternativas de selección:
– Se realizan N torneos de k participantes
– Seleccionar un set de soluciones no sólo en base a su

fitness sino también en base a su diversidad
• Objetivo: Maximizar la representatividad del espacio de

búsqueda

Heurísticas para inicializar la población

• Búsqueda Local: desarrollar una BL a partir de

cada miembro de la población inicial
– La población inicial consistirá de un set de puntos que
son localmente óptimos con respecto a algún operador
de movimiento

• Utilizar uno de los métodos presentados para
identificar una buena solución (o más de una).
Luego, clonar a dicha solución y aplicar a sus
clones un alto rango de mutación
– Objetivo: producir un número de individuos en la

vecindad del punto de comienzo

3

Aspectos de la inicialización

• Es necesario considerar el hecho de proveer al AE con la suficiente

diversidad para que la evolución ocurra

• Surry & Radcliffe (1994) examinaron el efecto de variar la proporción
de la población inicial que es derivada de buenas soluciones conocidas
– El uso de una pequeña proporción colaboró en la búsqueda genética
– A medida que la proporción se incrementó, la performance promedio

mejoró

– Sin embargo, la mejor performance se obtuvo de una población inicial

más aleatoria

• En resumen, a medida que la proporción de buenas soluciones

derivadas de heurísticas se incrementó …
– La performance promedio también se incrementó
– Pero la varianza en relación a la performance se decrementó

• Esto último limitó la posibilidad del AE de explorar nuevas regiones
del espacio de búsqueda y de obtener soluciones realmente novedosas

Hibridización dentro de los operadores

de cruce y mutación

• A veces es posible incorporar conocimiento

específico del problema dentro de los operadores
de cruce o mutación
– Smith (‘97) evolucionó secuencias de instrucciones

para un microprocesador
• Dividió a las instrucciones en clases. Cada clase se refiere a

instrucciones que tienen efectos similares

• El operador de mutación fue sesgado para incorporar este

conocimiento experto

– Mayor probabilidad de cambiar una instrucción por otra de su

misma clase (que de cambiarla por otra instrucción de una clase
diferente)

Hibridización dentro de los operadores

de cruce y mutación

• A veces es posible incorporar heurísticas

específicas del problema dentro de los operadores
de cruce o mutación
– Merz definió un operador de cruce llamado DPX

(distance preserving crossover) para el TSP
• El hijo hereda sólo los arcos comunes de ambos padres
• Se utiliza una heurística del tipo “vecino más cercano” para

conectar a los arcos heredados de los padres

– De esta manera, se explota explícitamente información

específica del problema sobre la longitud de los arcos conectados

4

Búsqueda Local aplicada sobre los hijos

• Uso más común de la hibridización: aplicación de

una o más fases de mejora sobre los miembros
individuales de la población durante el ciclo del
AE
– Búsqueda local aplicada sobre soluciones creadas por

mutación o recombinación

• Esto puede ocurrir en diferentes lugares del ciclo

del AE
– Antes o después de la selección
– Luego del cruce y/o mutación

Búsqueda Local aplicada sobre los hijos

Implementación típica de un AM

BEGIN

INITIALISE population
EVALUATE each candidate
REPEAT UNTIL ( TERMINATION CONDITION is satisfied ) DO

SELECT parents;
RECOMBINE to produce offspring;
MUTATE offspring;
EVALUATE offspring;
IMPROVE offspring via Local Search;
SELECT individuals for next generation;

OD
END

Búsqueda Local aplicada sobre los hijos

• La búsqueda local suele ser vista como el
proceso de aprendizaje desarrollado por un
individuo durante su tiempo de vida

• Generalmente, es utilizada para acelerar la

fase final del proceso de un AE
– Explora la vecindad de las buenas soluciones de

manera más sistemática que la mutación

5

Búsqueda Local

• Proceso iterativo que examina el conjunto

de puntos existente en la vecindad de la
solución actual, y que reemplaza a dicha
solución por un vecino mejor que ella

• La estructura de un algoritmo de Búsqueda
Local es ilustrada por el seudo-código de la
siguiente filmina

Búsqueda Local

BEGIN

/* given a starting solution i and a neighbourhood function n */
set best = i;
set iterations = 0;
REPEAT UNTIL ( depth condition is satisfied ) DO

set count = 0;
REPEAT UNTIL ( pivote rule is satisfied ) DO

generate the next neighbour j ∈ n(i);
set count = count + 1;
IF ( f(j) is better than f(best) ) THEN

set best = j;

FI

OD
set i = best;
set iterations = iterations + 1;

OD
END

Búsqueda Local

• El algoritmo tiene 3 componentes principales:

– Pivot rule: determina la finalización del ciclo interno

(cuanto se debe explorar el vecindario de i)
• Terminar cuando el vecindario haya sido explorado de manera

completa (count = |n(i)|)

• Terminar tan pronto como se haya encontrado un vecino mejor

((count = |n(i)|) or (best ≠ i))

– La profundidad (depth) de la búsqueda local: determina

la finalización del ciclo externo (cuantas fases de
mejora se deben aplicar)
• Una única fase de mejora (iterations = 1)
• Optimalidad local ((count = |n(i)|) and (best = i)) (se finaliza

cuando se encuentra una solución que no es superada por
ninguno de sus vecinos)

6

Búsqueda Local

Función de generación del vecindario de i
• En la práctica, n(i) es definido como un conjunto de puntos

que pueden ser alcanzados a partir de i mediante una
aplicación de un operador de movimiento
– Ej.: movimiento mediante el cambio de un bit en problemas

binarios

g

f

c

b

d h
e

a

n(d) = {a,c,h}
b 000 h 111
c 100 d 101
f 010 a 001
g 110 e 011

Grafos

• Una representación equivalente es un grafo

G(V,E) donde:
– El conjunto de vértices V representa a los puntos sobre

el espacio de búsqueda (soluciones codificadas)
– El conjunto de arcos E representa a las posibles
transiciones que se pueden obtener mediante una
aplicación del operador de movimiento

Ejemplo: Grafos para soluciones binarias

• Ejemplo: problema binario tridimensional

(anterior)
– V = {a, b, c, d, e, f, g, h,}
– Exploración mediante el cambio de un bit a la vez

• E1 = { ab, ad, ae, bc, bf, cd, cg, dh, fg, fe, gh, eh}
• Todos los pares simétricos
• E2 = {ac, bd, af, be, dg, ch, fh, ge, ah, de, bg, cf}
• E3 = {ag, bh, ce, df}

7

Grafos

• El grado de un grafo es el número máximo de

arcos que entran/salen de un punto individual (el
tamaño de la vecindad más grande)
– Cambio de un único bit: el grado es l (longitud de la

solución codificada)

• Los algoritmos de Búsqueda Local revisan los
puntos en el vecindario de una solución dada,
entonces la complejidad está relacionada con el
grado del grafo

Variaciones de la Búsqueda Local

• La búsqueda debe ser desarrollada en el espacio de

representaciones (genotípico) o en el espacio de
soluciones (fenotípico)?

• Cuantas iteraciones de búsqueda local deben ser

hechas?

• Se debe aplicar la búsqueda local a la población

entera?
– o sólo al mejor individuo?
– o sólo al peor individuo?

Dos Modelos de Adaptación

• La estructura de un algoritmo de BL (vista antes) asume

que la solución actual siempre es reemplazada por el mejor
vecino encontrado

• Dentro de un AM, se puede considerar a la fase de BL

como una fase de mejora, o como una fase de aprendizaje
dentro del ciclo evolutivo

• Es necesario considerar si …

– Los cambios hechos a la solución original (características

adquiridas de un vecino) deberían ser conservados

– El fitness resultante de la BL debería ser asignado a la solución