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

Introducción a la Computación Evolutiva

Segunda Clase: Algoritmos Evolutivos

Agenda

• Resumen sobre la Metáfora Evolutiva
• Esquema Básico de un Algoritmo Evolutivo (AE)
• Componentes Básicos

– Representación
– Evaluación
– Población
– Selección de Padres
– Cruzamiento
– Mutación
– Selección de Sobrevivientes
– Condición de Terminación

Agenda

• Ejemplo: Problema del Viajante
• Aspectos generales sobre el

comportamiento típico de los AEs

• Relación de la CE con otras técnicas de

optimización global

1

Resumen sobre la metáfora de la CE

• Una población de individuos existe en un ambiente con

recursos limitados

• La competencia por dichos recursos provoca la selección

de los individuos mejor adaptados al ambiente

• Estos individuos actúan como semillas para la generación

de nuevos individuos mediante el cruzamiento y la
mutación

• Los nuevos individuos compiten (posiblemente también

con los padres) por sobrevivir

• A lo largo del tiempo la Selección Natural causa un

incremento en el fitness de la población

Resumen sobre la metáfora de la CE

• Los AEs caen dentro de la categoría de algoritmos

denominada “generar y testear”

• Ellos son algoritmos estocásticos basados en

población

• Los operadores de variación (cruzamiento y

mutación) crean la diversidad necesaria para la
evolución (generan individuos novedosos)

• Selección reduce la diversidad y actúa como una

fuerza que empuja hacia la calidad

Esquema general de un AE

2

Seudo-código típico de un AE

Diferentes tipos de AEs

• Históricamente, la representación de las soluciones
candidatas ha sido utilizada para clasificar a los AEs
– Strings binarios: Algoritmos Genéticos
– Vectores de valores reales: Estrategias de Evolución
– Máquinas de estado finito: Programación Evolutiva
– Árboles sintácticos: Programación Genética

• La mejor estrategia es …

– Elegir la representación que mejor se ajuste al problema
– Elegir los operadores de variación que mejor se ajusten a la

representación

• Los operadores de selección sólo usan el fitness de las

soluciones y, por lo tanto, son independientes de la
representación

Componentes de los AEs

• Los AEs tienen un número de componentes,

procedimientos, u operadores que deben ser especificados
si se pretende definir un AE particular
• Los componentes más importantes son:

– Representación (definición de los individuos)
– Función de Evaluación (función de fitness)
– Población
– Mecanismo de Selección de padres
– Operadores de variación (cruzamiento y mutación)
– Mecanismo de Selección de los sobrevivientes (reinserción)
– Procedimiento de inicialización
– Condición de terminación

3

Representaciones

• Las soluciones candidatas (individuos) existen en un

espacio fenotípico

• Ellas son codificadas como cromosomas. Los cromosomas

existen en un 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 genes se encuentran en
posiciones llamadas locus (usualmente prefijadas) y toman
un valor (alelo) de varios valores posibles

• Para encontrar la solución óptima global, cada solución

posible debe ser representada en el espacio genotípico
– El proceso evolutivo se desarrolla sobre el espacio genotípico

Función de Evaluación (Fitness)

• Representa los requerimientos a los cuales la población

• Otras formas de llamarla: función de calidad o función

debería adaptarse

objetivo

• Asigna un valor a cada genotipo. Estos valores conforman

la base para el proceso de selección
– Por lo tanto, cuanto más discriminación (valores diferentes) exista

más útiles son estos valores para la selección

• Típicamente, se considera que la función de fitness es una

función que debe ser maximizada
– Sin embargo, algunos problemas requieren minimizar la función de

fitness (problemas de minimización)

– De todas maneras, es trivial convertir un problema de

minimización en un problema de maximización

Población

• Contiene (representaciones de) posibles soluciones
• Usualmente tiene un tamaño prefijado y es un “multiset”

de genotipos

• Algunos AEs sofisticados también requieren que la

población tenga una estructura espacial

• Los operadores de selección tienen en cuenta a la

población actual completa (las probabilidades
reproductivas son relativas a la generación actual)

• La diversidad de una población se refiere al número de

soluciones diferentes que existe en ella
– La diversidad se puede referir al número de diferentes valores de

fitness, de diferentes fenotipos, o de diferentes genotipos que existe
en la población

4

Mecanismo de Selección de Padres

• Define las probabilidades de que los individuos
actúen como padres de la siguiente generación.
Dichas probabilidades se basan en los valores de
fitness de los individuos

• La selección es usualmente probabilística

– Las soluciones de alta calidad tienen más chances de

transformarse en padres que las soluciones de baja
calidad

– Sin embargo, aún la peor solución en la población

actual tiene usualmente alguna chance de transformarse
en padre

• La naturaleza estocástica de este mecanismo

ayuda a escapar de los óptimos locales

Operadores de Variación

• El rol de estos operadores es generar nuevas

soluciones candidatas

• Usualmente se dividen 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: operadores de cruzamiento

• Se ha debatido mucho acerca de la importancia

relativa de la recombinación y de la mutación
– Actualmente, la mayoría de los AEs usan ambas
– La elección de los operadores de variación específicos a

utilizar es dependiente de la representación

Mutación

• Actúa sobre un genotipo y produce otro
• La aleatoriedad de este operador es esencial y
diferencia a la mutación de otros operadores
heurísticos unarios

• La importancia que se le asigna a la mutación
depende del tipo de AE y de la representación
– AGs binarios: es el operador responsable de preservar e

introducir diversidad

– PE mediante MEF: único operador de búsqueda
– PG: generalmente no es utilizada

5

Mutación

• Es importante considerar que los operadores de variación
implementan los “pasos” dentro del espacio de búsqueda
– La generación de un hijo permite alcanzar un nuevo punto en este

espacio

• Desde esta perspectiva, la mutación tiene un rol teórico,

ésta puede garantizar que el espacio de búsqueda está
conectado
– Esto es importante porque los teoremas que establecen que un AE
descubrirá el óptimo global de un problema dado se basan sobre la
propiedad de que cada genotipo que representa a una solución
posible puede ser alcanzado mediante los operadores de variación

– La forma más simple de satisfacer esta condición es permitir al

operador de mutación “saltar” a cualquier lugar

• Por ej.: permitir que cualquier alelo pueda ser mutado por cualquier

otro alelo con una probabilidad distinta de cero

Recombinación

• Combina la información de los padres para

conformar hijos (nuevos individuos)

• Es un operador estocástico

– Se decide aleatoriamente qué partes de cada padre

deben ser combinadas y la forma en que estas partes
deben ser combinadas

• El principio sobre el cual se basa la recombinación

es el siguiente
– Aparear individuos con diferentes atributos deseables

puede producir hijos que combinan dichos atributos

• Este principio ha sido usado durante miles de años

por criadores de ganado y de plantas

Recombinación

• Los AEs …

– Crean un número de hijos mediante la recombinación basada en el

azar

– Aceptan que algunos de dichos hijos tendrán combinaciones

indeseables de características

• La mayoría de los hijos pueden ser peores o iguales a sus padres

– Esperan que algunos de los hijos tengan características o

combinaciones de características mejores que la de sus padres

• En los AEs, los operadores de recombinación son

aplicados probabilísticamente

• Los operadores de recombinación son dependientes de la

representación

6

Selección de los sobrevivientes

• Este mecanismo también se conoce como Reinserción o

Sustitución

• La mayoría de los AEs usa un tamaño de población

prefijado (tamaño constante)
– Entonces es necesario decidir qué individuos del conjunto (padres

+ hijos) conformarán la población de la siguiente generación

• Este mecanismo es determinístico

– Basado en el fitness: se ordena a los individuos del conjunto

(padres + hijos) y se selecciona a los mejores

– Basado en edad: se crea una cantidad de hijos igual a la cantidad

de padres existente, y se selecciona sólo a los hijos (los padres son
eliminados y los hijos reemplazan totalmente a los padres)

– Combinación de los enfoques anteriores (elitismo)

Inicialización / Terminación

•

Inicialización: usualmente la primera población está
conformada por individuos generados aleatoriamente
– Es necesario asegurar que todos los posibles valores de alelos serán

generados y combinados de una manera equilibrada

– Se pueden considerar soluciones existentes, o utilizar heurísticas

específicas del problema, para componer la población inicial

• Terminación: la condición de terminación es chequeada en

cada generación
– Alcanzar algún valor de fitness conocido
– Alcanzar un número máximo de generaciones
– Alcanzar un nivel mínimo de diversidad en la población
– Detectar que, durante un período de tiempo dado (ej.: número de
generaciones), la mejora del fitness permanece bajo un valor de
umbral dado

Ejemplo: Problema del Viajante

8

7

6

1

5

2

4

3

Encontrar un camino de mínima longitud que visite todas las

ciudades
– Cada ciudad sólo puede ser visitada una vez
– Es necesario retornar a la ciudad de partida

7

Problema del Viajante: Representación

Fenotipo:
Un camino en el mapa

8

7

6

1

5

2

4

3

Genotipo:
Una permutación de los
númer