Download computacion evolutiva

COMPUTACION EVOLUTIVA
Introducción

Computación Evolutiva:
 Enfoque
alternativo para abordar problemas
complejos de:
 Búsqueda
 Aprendizaje
 Trabaja
a través de modelos computacionales
de procesos evolutivos

Algoritmos evolutivos:
 Implantaciones
concretas de tales modelos
 Propósito: guiar una búsqueda estocástica
 haciendo
evolucionar un conjunto de estructuras y
 seleccionando de modo iterativo las más
adecuadas
Contexto
Forma parte de un conjunto de
metodologías de resolución que remedan
con mayor o menor exactitud procesos
naturales: COMPUTACIÓN NATURAL
 Por ejemplo:

 Redes
Neuronales
 Solidificación Simulada
 Algoritmos Genéticos
Clasificación de procedimientos de optimización

Basada en la naturaleza de las soluciones
 NUMÉRICOS
(completamente especificada en
términos de un conjunto de m parámetros)
 COMBINATORIOS (basadas en el orden)
Clasificación de procedimientos de optimización

Basada en el grado de aleatoriedad que se le da al proceso
de búsqueda
 DETERMINISTAS (procedimiento de búsqueda dirigido:
en las mismas condiciones de partida proporciona
idénticos resultados)
Requiere mucho conocimiento adicional de la función
objetivo
 ALEATORIAS (al azar: usa argumentos estadísticos) No
requiere ninguna información adicional; se puede
aplicar a cualquier tipo de problema
 ESTOCÁSTICAS (orientadas: la componente
determinista orienta la dirección de búsqueda, y la
aleatoria se encarga de la búsqueda local )
Clasificación de procedimientos de optimización

Basada en la información disponible sobre
la función a optimizar
 BÚSQUEDAS
CIEGAS (el proceso a optimizar
funciona como caja negra)
 BÚSQUEDAS HEURÍSTICAS (se dispone de
cierta información explícita sobre el proceso a
optimizar.)
Se la aprovecha para guiar la búsqueda
Teoría moderna de optimización
Añadir conocimiento específico a un problema
 En problemas reales de mediana complejidad
resulta muy difícil
 Es fundamental:



Cuánto añadir?
Cómo añadirlo?
El conocimiento específico sólo sirve cuando es
de muy buena calidad
 Cuidado! Acentúa la tendencia a estancar la
búsqueda en óptimos locales

Las técnicas clásicas de búsqueda
determinística y analítica no suelen ser de
gran utilidad
 Esto obliga a desarrollar nuevos
paradigmas

 Menos
analíticos
 Más sintéticos
LA BÚSQUEDA DE ANALOGÍAS CON LA NATURALEZA ES MÁS UNA
NECESIDAD QUE UNA PREFERENCIA ESTÉTICA
No se persigue una simulación de los
procesos naturales
 Es más bien una emulación de dichos
procesos

•Un AE será tanto mejor cuanto mejores resultados
proporcione en la resolución del problema
planteado
•Independientemente de su fidelidad a la biología
•La mayoría son enfoques simplistas desde el punto de vista
biológico
•Pero lo suficientemente complejos como para proporcionar
mecanismos de búsqueda robustos y potentes
Estructura genérica de los AEs
AE es cualquier procedimiento estocástico de
búsqueda basado en el principio de evolución.
 Principio de Evolución:

Supervivencia del más apto
 Adaptación al entorno


Los más aptos tienen
más posibilidades de sobrevivir
 más oportunidades de transmitir sus características a
las generaciones siguientes

Población: conjunto de candidatos a
soluciones de un problema
 Al ejecutar un AE una población de
individuos es sometida a

 una
serie de transformaciones con las que se
actualiza la búsqueda
 y después de un proceso de selección que
favorece a los mejores individuos
TRANSFORMACIÓN
SELECCIÓN
GENERACION
Estructura
La CE trata de desarrollar mecanismos
estocásticos de búsqueda en paralelo con
los que mejorar las técnicas clásicas de
búsqueda determinista
 Para que la mejora sea efectiva, tales
mecanismos deben estar dirigidos
(procedimiento de selección)

Herramientas para poder emular un
proceso de evolución de un AE
Individuos: población de posibles
soluciones debidamente representadas
 Selección: procedimiento basado en la
APTITUD de los individuos
 Transformación: construcción de nuevas
soluciones a partir de las disponibles

Implantación sobre este esquema:
BeginAlgorithm (EvolutionAlgorithm)
P[0]=InitPop();
Población Inicial
FitP[0]=EvalPop(P[0]);
Aptitudes iniciales
for (t=0; t<MaxNumGen; t++) {
Q[t]=SelectBreedersFrom(P[t]);
Selección de reproductores
Q[t]=Transform(Q[t]);
Reproducción
FitQ[t]=EvalPop(Q[t]);
P[t]=SelSurv( P[t],Q[t],FitP[t],FitQ[t]);
FitP[t]=EvalPop(P[t]);
Evaluación de la nueva población
if( ChkTermCond(P[t],FitP[t]) )
Condición de terminación
return;
}
End algorithm
Paradigmas fundamentales

ALGORITMOS GENÉTICOS


PROGRAMAS EVOLUTIVOS


Se hace evolucionar una población de estructuras de datos
sometiéndolas a una serie de transformaciones específicas y a
un proceso de selección
ESTRATEGIAS EVOLUTIVAS


Se hace evolucionar una población de enteros binarios
sometiéndolos a transformaciones unitarias y binarias genéricas
y a un proceso de selección
Se hace evolucionar una población de números reales que
codifican las posibles soluciones de un problema numérico y los
tamaños de salto. La selección es implícita.
PROGRAMACIÓN EVOLUTIVA

Se hace evolucionar una población de máquinas de estados
finitos sometiéndolas a transformaciones unitarias