Upload
hamilton
View
830
Download
0
Embed Size (px)
Citation preview
Los Algoritmos Genéticosy su Aplicación en la
Optimización
Diciembre 2009
Hamilton Mendoza Muñoz
Ingeniería en Logística y Transporte
Introducción a los Algoritmos Genéticos
¿QUE SON?¿QUE SON?• Son una Técnica de Búsqueda y Optimización Estocástica• Se fundamenta en la mímica de los principios de evolución y
genética
¿EN QUE SE DIFERENCIAN DE LA OPTIMIZACIÓN Y ¿EN QUE SE DIFERENCIAN DE LA OPTIMIZACIÓN Y BÚSQUEDA CONVENCIONAL?BÚSQUEDA CONVENCIONAL?
• Trabajan con una codificación del conjunto solución, no la soluciones por si mismas.
• Buscan en una población de soluciones, no en base a una sóla.• Usan información de “ganancia” (función de fitness), en lugar
de derivadas, u otros conocimientos auxiliares.• Usan reglas de transición probabilísticas, no determinísticas.
Goldberg (171)
Algoritmo Genético GenéricoDescripción de Grefenstette (192,287) modificada por Gen&Mitsuo (1997)
Procedimiento: Algoritmo Genéticobegin
t<- 0;inicializar P(t);evaluar P(t);Mientras (no condición de parada) hacer
Recombinar P(t) para generar C(t);evaluar C(t);seleccionar P(t+1) de P(t)UC(t)t<- t+1;
endend
Operadores en Algoritmos Genéticos
• Operadores Genéticos:Operadores Genéticos:– Crossover (Entrecruzamiento)– Mutación
• Operadores EvolutivosOperadores Evolutivos– Selección
Crossover
Representación de un Algoritmo Genético Gen&Mitsuo (1997)
soluciones 11001010
10111110
00100101
01011011
cromosomas
11001010
10111110
00100101
11001110
10111101
Mutación
01011011
0010010111001010
10111110
00100101
01011011
00100101
11001110
10111101
hijosde
codi
ng
solu
cion
esCálculode
Fitness
EvaluaciónSelección
Ruletaruleta
Nueva Población
Paradigma de Holland (220):
“seleccionar los padres a recombinar”
Sobre el Crossover
• Método Clásico:Método Clásico: escoger aleatoriamente un punto de corte en ambos padres y generar hijos combinando los segmentos a cada lado del corte.Es útil para:
• Incentivar la mezcla de rasgos de los padres, en busca de hijos mejores que ambos padres
• Parámetro Clásico:Parámetro Clásico: “Tasa de Crossover”. Pc=|C|/|P|
Si Pc es alto:• poca probabilidad de atascamiento en un óptimo local• alto costo explorando regiones poco prometedoras
Sobre las Mutaciones• Método Clásico:Método Clásico: escoger aleatoriamente cierta cantidad de
cromosomas y alterarlos aleatoriamente. Es útil para:
• Regresar genes perdidos durante la selección para probarlos en otro contexto
• Trayendo genes no presentes en la población inicial
• Parámetro Clásico:Parámetro Clásico: “Tasa de Mutación”. Pm=% de los genes a mutar
Si Pm es alto:• los hijos perderán los rasgos de los padres. El algoritmo deja de
aprender.Si Pm es bajo:
• muchos genes que pudiesen ser útiles, dejan de ser explorados.
Exploración vs. Explotación (I)
• Búsqueda:Búsqueda: método universal para resolver problemas donde no se puede conocer, a priori, la secuencia de pasos que llevan hacia la solución.
• Búsqueda Ciega:Búsqueda Ciega: no usan información sobre el problema.• Búsqueda Heurística:Búsqueda Heurística: usan información para guiar la
búsqueda hacia las “mejores direcciones”.• Búsqueda Ideal:Búsqueda Ideal: explotar la mejor solución, y explorar el
espacio de búsqueda (46).• Hill-Climbing:Hill-Climbing: explota la mejor solución, intentando
mejorarla, ignorando la exploración de otras direcciones en el espacio de búsqueda.
• Búsqueda Aleatoria:Búsqueda Aleatoria: explora el espacio de búsqueda, ignorando la explotación para mejorar las regiones más prometedoras.
Exploración vs. Explotación (II)
• Búsqueda Genética:Búsqueda Genética:conducta inicial: diversidad genética, y operadores genéticos que
tienden a explorar el espacio de soluciónposteriormente: el operador de crossover explota la vecindad de
cada soluciónconsecuencia: ocurre una explotación o una exploración,
dependiendo del ambiente genético, y no estrictamente de los operadores.
fitn
ess
Espacio de solución
promedio
max
padreshijosmutantes
Exploración vs. Explotación (II)
• Búsqueda Genética:Búsqueda Genética: términos...Cromosoma, Indivíduo: Solución (codificada)Gen: Parte de la solución (bit en el caso binario)Locus: Posición de un gen en un cromosomaAlelo: Valor de un genFenotipo: Solución de-codificadaGenotipo: Solución codificada
fitn
ess
Espacio de solución
promedio
maxpadreshijosmutantes
El Problema de la Codificación (I)
• Los Algoritmos Genéticos clásicos, llevan los valores de las soluciones a cadenas de números binarios (Holland).
• La codificación binaria es incómoda para la mayoría de las aplicaciones
• Se han creado codificaciones en números reales, en enteros, y codificaciones en matríces y árboles
• Es esencial, para que un AG sea de utilidad, que la codificación sea apropiada.
Espacio Espacio genotípicogenotípico
Operaciones
Genéticas
Operaciones
Genéticas
Espacio Espacio fenotípicofenotípico
Evaluación y
Selección
Evaluación y
Selección
codificar
de-codificar
El Problema de la Codificación (II)• Infactibilidad:Infactibilidad: al decodificar un cromosoma, las restricciones
hacen a la solución infactible• Ilegalidad:Ilegalidad: los operadores generan un cromosoma que no
puede ser decodificado en una solución
En ambos casos, los cromosomas se pueden rechazar o reparar.Adicionalmente las infactibilidades se pueden penalizar
Espacio Espacio genotípicogenotípico
Espacio Espacio fenotípicofenotípico
Espacio Espacio fenotípicofenotípico
factible
infactible
ilegal
El Problema de la Codificación (III)
• Mapping (asignación de correspondencias):Mapping (asignación de correspondencias): al decodificar un cromosoma, las restricciones hacen a la solución infactible
• Ilegalidad:Ilegalidad: los operadores generan un cromosoma que no puede ser decodificado en una solución
Espacio Espacio genotípicogenotípico
Espacio Espacio fenotípicofenotípico
1-a-n
n-a-1
1-a-1
Operador de Selección (I)• Es la forma de imitar la Presión Selectiva Darwiniana• Es la fuerza que conduce al algoritmo, su intensidad debe ser bien
escogida– Puede provocar una finalización prematura del algoritmo– Puede hacerlo mucho más lento de lo necesario
• Baja Presión Selectiva:Baja Presión Selectiva: se recomienda al inicio del algoritmo, para favorecer la exploración.
• Alta Presión Selectiva:Alta Presión Selectiva: se recomienda al final del algoritmo para explotar las regiones más prometedoras.
• Espacio de Muestreo:Espacio de Muestreo:– Regular: el tamaño es |P|
• Los hijos reemplazan a sus padres• Un padre es eliminado al nacer un hijo
– Aumentado: el tamaño es |P|+|C|• Hijos y padres pueden ser seleccionados por igual• No hay que preocuparse por la influencia de las tasas crossover y mutación
en la cantidad de hijos generados
Operador de Selección (II)• Mecanismos de Muestreo:Mecanismos de Muestreo:
– Muestreo Estocástico (probabilidad de selección es función de la aptitud)
– Muestreo Determinístico (selecciona los más aptos)– Muestreo Mixto (ejemplo del torneo binario)
• Probabilidad de Selección:Probabilidad de Selección:– Proporcional a la aptitud– Por escalamiento y ordenamiento (ranking)
• Presión Selectiva:Presión Selectiva: según el Neo-darwinismo puede clasificarse en– Estabilizadora (elimina soluciones supra-normales e infra-normales)– Direccional (busca subir o bajar la media de la aptitud)– Disruptiva (busca eliminar las soluciones de aptitud media)
Algoritmos Genéticos Híbridos• Ejemplo:Ejemplo: Evolución Lamarckiana
Procedimiento: Algorítmo Genético Híbridobegin
t<- 0;inicializar P(t);evaluar P(t);Mientras (no condición de parada) hacer
recombinar P(t) para generar C(t);escalar localmente C(t);evaluar C(t);seleccionar P(t+1) de P(t) y C(t); t<- t+1;
endend