EDAS

Dr. Alejandro Padilla Díaz

Metaheurísticas II / DR.
ALEJANDRO PADILLA / Unidad I

Metahuerísticas II
UAA / ICI Enero
2013

1

• Los Algoritmos de Estimación de Distribución (EDAs) sonuna
variante de algoritmo evolutivo en la que las operaciones de
cruce y mutación se sustituyen por operadores que aprenden
y muestrean a partir de la distribución de probabilidad de los
mejoresindividuos de la población en cada iteración del
algoritmo.

Metaheurísticas II / DR.
ALEJANDRO PADILLA / Unidad I

EDAs Introducción

2

• Una ventaja de estos algoritmos frente a losAlgoritmos
Evolutivos(AEs) clásicos es que reducen el número de
parámetros que se requieren, uno de los puntos más críticos
para el buen funcionamiento de estos algoritmos. En esta
propuesta, el cuellode botella del cómputo es la estimación
de la distribución de probabilidad conjunta de los individuos
seleccionados.

Metaheurísticas II / DR.
ALEJANDRO PADILLA / Unidad I

EDAs Introducción3

Comparación de EDAs contra otros
Algoritmos Evolutivos
OTROS ALGORITMOS EVOLUTIVOS
Algoritmos Evolutivos
varios parámetros a determinar
dificultad en la predicción de las poblaciones através de las
generaciones
• building blocks
• relación entre las variables (linkage learning)
• problemas engañosos
• EDAs
EDA (Estimation of Distribution Algorithms) Mühlenbein y Paa
(1996),Larrañaga y Lozano (2002)
• Basada en poblaciones
• Sin operadores de cruce ni mutación
• En cada generación se estima de los individuos seleccionados, la
distribución de probabilidad subyacente a losmismos
• Muestreando esta distribución se obtiene la siguiente población
• Se repiten los dos pasos anteriores hasta el criterio de terminación

Metaheurísticas II / DR.
ALEJANDRO PADILLA / UnidadI

•
•
•
•

4

• De forma esquemática, estos algoritmos funcionan de la
siguiente forma. Comienzan generando M individuos al azar,
por ejemplo, a partir de una distribución uniforme...