PDF de programación - Computación Evolutiva: variantes

Computación Evolutiva: variantes

Diego Milone

Inteligencia Computacional
Departamento de Informática

FICH-UNL

Inteligencia Computacional - FICH - UNL

Parámetros que controlan la evolución

• Probabilidad de mutaciones
• Probabilidad de cruzas
• Tamaño de la población
• Brecha generacional
• Elitismo

...y si los parámetros fueran adaptables?

Inteligencia Computacional - FICH - UNL

Estrategias de evolución

• Representación “fenotípica”:

• variables objetivo
• variables de control (o estratégicas)

Inteligencia Computacional - FICH - UNL

Estrategias de evolución

• Representación “fenotípica”:

• variables objetivo
• variables de control (o estratégicas)

• Fitness ... igual que en algoritmos genéticos

Inteligencia Computacional - FICH - UNL

Estrategias de evolución

• Representación “fenotípica”:

• variables objetivo
• variables de control (o estratégicas)

• Fitness ... igual que en algoritmos genéticos
• Operadores:

• mutación (sólo si no empeora)
• cruza (optativa)

Inteligencia Computacional - FICH - UNL

Estrategias de evolución

• Representación “fenotípica”:

• variables objetivo
• variables de control (o estratégicas)

• Fitness ... igual que en algoritmos genéticos
• Operadores:

• mutación (sólo si no empeora)
• cruza (optativa)

• Selección: aleatoria, combinada con mutación
• Reproducción: determinística

• Mecanismo (µ + λ)-ES: µ padres producen λ ≥ 1 hijos.
Próxima generación: {µ ∪ λ} eliminando los peores de λ

Inteligencia Computacional - FICH - UNL

Estrategias de evolución

• Representación “fenotípica”:

• variables objetivo
• variables de control (o estratégicas)

• Fitness ... igual que en algoritmos genéticos
• Operadores:

• mutación (sólo si no empeora)
• cruza (optativa)

• Selección: aleatoria, combinada con mutación
• Reproducción: determinística

• Mecanismo (µ + λ)-ES: µ padres producen λ ≥ 1 hijos.
Próxima generación: {µ ∪ λ} eliminando los peores de λ
• Mecanismo (µ, λ)-ES: µ padres producen λ > µ hijos.
Próxima generación: subconjunto con los mejores de λ

Inteligencia Computacional - FICH - UNL

Representación de los individuos

Terminológía: algoritmo/programación/estrategia...

• Genético : representación BINARIA

por el teorema de esquemas

• Muchos genes con pocos alelos: convergencia asegurada
• Epitasis: un gen incorrecto invalida a todo el cromosoma
• Representación lejana al dominio del problema (ej: viajero
• Gran cantidad de soluciones inválidas en la población

con enteros)

• Evolutivo: representación REAL o “fenotípica”

• Pocos genes con muchos alelos: representación fenotípica
• Convergencia muy dependiente de los operadores
• Necesidad de redefinición de operadores no “biológicos”

Inteligencia Computacional - FICH - UNL

Representación de los individuos

Terminológía: algoritmo/programación/estrategia...

• Genético: representación BINARIA

por el teorema de esquemas

• Muchos genes con pocos alelos: convergencia asegurada
• Epitasis: un gen incorrecto invalida a todo el cromosoma
• Representación lejana al dominio del problema (ej: viajero
• Gran cantidad de soluciones inválidas en la población

con enteros)

• Evolutivo : representación REAL o “fenotípica”

• Pocos genes con muchos alelos: representación fenotípica
• Convergencia muy dependiente de los operadores
• Necesidad de redefinición de operadores no “biológicos”

Inteligencia Computacional - FICH - UNL

Representación de los individuos

Terminológía: algoritmo/programación/estrategia...

• Genético: representación BINARIA

por el teorema de esquemas

• Muchos genes con pocos alelos: convergencia asegurada
• Epitasis: un gen incorrecto invalida a todo el cromosoma
• Representación lejana al dominio del problema (ej: viajero
• Gran cantidad de soluciones inválidas en la población

con enteros)

• Evolutivo : representación REAL o “fenotípica”

• Pocos genes con muchos alelos: representación fenotípica
• Convergencia muy dependiente de los operadores
• Necesidad de redefinición de operadores no “biológicos”
Otras representaciones? Cromosomas de longitud variable?
Árboles? Grafos?

Programación genética

Diego Milone

Inteligencia Computacional
Departamento de Informática

FICH-UNL

Inteligencia Computacional - FICH - UNL

Programación genética

“...generación automática de programas...”

Inteligencia Computacional - FICH - UNL

Programación genética

“...generación automática de programas...”

Elementos básicos de un programa:

• Variables y constantes
• Operadores aritméticos y lógicos
• Funciones matemáticas
• Condicionales
• Bucles
• Recursiones
• ...

Inteligencia Computacional - FICH - UNL

Representación en árbol para PG

Ejemplo sencillo con operadores lógicos:

((A)XOR(NOT(B)))AND((NOT(A))OR(B))

Inteligencia Computacional - FICH - UNL

Representación en árbol para PG

Ejemplo sencillo con operadores lógicos:

((A)XOR(NOT(B)))AND((NOT(A))OR(B))

Inteligencia Computacional - FICH - UNL

Cruzas en PG

• Numeración de nodos

Inteligencia Computacional - FICH - UNL

Cruzas en PG

• Numeración de nodos
• Selección de los puntos a cruzar: ej. 2 y 6

Inteligencia Computacional - FICH - UNL

Cruzas en PG

• Numeración de nodos
• Selección de los puntos a cruzar: ej. 2 y 6
• Cruza en base al intercambio de ramas

Inteligencia Computacional - FICH - UNL

Mutaciones en PG

• Numeración de nodos
• Selección de la rama a mutar
• Generación de un árbol al azar
• Mutación en base al reemplazo

Restricciones en el dominio

de la aplicación

Diego Milone

Inteligencia Computacional
Departamento de Informática

FICH-UNL

Inteligencia Computacional - FICH - UNL

Restricciones del problema

¿Cómo se pueden considerar las restricciones del problema
durante la evolución?

Inteligencia Computacional - FICH - UNL

Restricciones del problema

¿Cómo se pueden considerar las restricciones del problema
durante la evolución?

• Redefinición de la representación de forma de que

siempre se generen fenotipos válidos

Inteligencia Computacional - FICH - UNL

Restricciones del problema

¿Cómo se pueden considerar las restricciones del problema
durante la evolución?

• Redefinición de la representación de forma de que

siempre se generen fenotipos válidos

• Rechazo o eliminación de individuos inválidos

Inteligencia Computacional - FICH - UNL

Restricciones del problema

¿Cómo se pueden considerar las restricciones del problema
durante la evolución?

• Redefinición de la representación de forma de que

siempre se generen fenotipos válidos

• Rechazo o eliminación de individuos inválidos
• Reparación del material genético

Inteligencia Computacional - FICH - UNL

Restricciones del problema

¿Cómo se pueden considerar las restricciones del problema
durante la evolución?

• Redefinición de la representación de forma de que

siempre se generen fenotipos válidos

• Rechazo o eliminación de individuos inválidos
• Reparación del material genético
• Modificación de los operadores de variación

Inteligencia Computacional - FICH - UNL

Restricciones del problema

¿Cómo se pueden considerar las restricciones del problema
durante la evolución?

• Redefinición de la representación de forma de que

siempre se generen fenotipos válidos

• Rechazo o eliminación de individuos inválidos
• Reparación del material genético
• Modificación de los operadores de variación
• Esquemas de penalización en la función de aptitud