PDF de programación - Computación Evolutiva - Algoritmos Genéticos

Computación Evolutiva
Algoritmos Genéticos

Diego Milone

Inteligencia Computacional
Departamento de Informática

FICH-UNL

Inteligencia Computacional - FICH - UNL

Hace 200 años...

La idea de que las especies cambian ya se confrontaba al
creacionismo.

Inteligencia Computacional - FICH - UNL

Hace 200 años...

La idea de que las especies cambian ya se confrontaba al
creacionismo.
El cuello de las jirafas según Jean-Baptiste Lamarck

Inteligencia Computacional - FICH - UNL

Hace 200 años...

La idea de que las especies cambian ya se confrontaba al
creacionismo.
El cuello de las jirafas según Jean-Baptiste Lamarck

Buena idea pero... ¿se heredan los caracteres adquiridos?

Inteligencia Computacional - FICH - UNL

Hace 150 años...

La idea de la evolución genera un cambio de paradigmas tan
grande que hasta hoy, incluso en computación, estamos
hablando de Charles R. Darwin

Inteligencia Computacional - FICH - UNL

Hace 150 años...

La idea de la evolución genera un cambio de paradigmas tan
grande que hasta hoy, incluso en computación, estamos
hablando de Charles R. Darwin

Variación y selección natural: si hay variabilidad en la
longitud del cuello de las jirafas, las de cuello corto tendrán
menos probabilidades de sobrevivir y procrear. Así...

Inteligencia Computacional - FICH - UNL

Hace 150 años...

La idea de la evolución genera un cambio de paradigmas tan
grande que hasta hoy, incluso en computación, estamos
hablando de Charles R. Darwin

Variación y selección natural: si hay variabilidad en la
longitud del cuello de las jirafas, las de cuello corto tendrán
menos probabilidades de sobrevivir y procrear. Así...

...en la próxima generación habrá menos jirafas de cuello corto.

Inteligencia Computacional - FICH - UNL

Y...

¿Qué tiene que ver todo esto con la computación?

¿Y con la “inteligencia” computacional?

¿Podremos ver las ideas de Darwin como un algoritmo?

¿Podremos usar estas ideas para resolver problemas con la
computadora?

La evolución como un algoritmo

Diego Milone

Inteligencia Computacional
Departamento de Informática

FICH-UNL

Inteligencia Computacional - FICH - UNL

La inspiración biológica

El creacionismo y las ideas de Lamarck
Darwin versus Lamarck

Inteligencia Computacional - FICH - UNL

La inspiración biológica

El creacionismo y las ideas de Lamarck
Darwin versus Lamarck
• Poblaciones versus individuos

Inteligencia Computacional - FICH - UNL

La inspiración biológica

El creacionismo y las ideas de Lamarck
Darwin versus Lamarck
• Poblaciones versus individuos
• Mejores versus “adaptados”

Inteligencia Computacional - FICH - UNL

La inspiración biológica

El creacionismo y las ideas de Lamarck
Darwin versus Lamarck
• Poblaciones versus individuos
• Mejores versus “adaptados”
• Aleatoriedad en la selección natural

Inteligencia Computacional - FICH - UNL

La inspiración biológica

El creacionismo y las ideas de Lamarck
Darwin versus Lamarck
• Poblaciones versus individuos
• Mejores versus “adaptados”
• Aleatoriedad en la selección natural
• Diversidad y operadores de variación en la población

Inteligencia Computacional - FICH - UNL

La evolución como un algoritmo

Inteligencia Computacional - FICH - UNL

La evolución como un algoritmo

Inicializar(Población)
MejorAptitud ← Evaluar(Población)
mientras MejorAptitud < AptitudRequerida

Inteligencia Computacional - FICH - UNL

La evolución como un algoritmo

Inicializar(Población)
MejorAptitud ← Evaluar(Población)
mientras MejorAptitud < AptitudRequerida

Progenitores ← SelecciónNatural(Población)

Inteligencia Computacional - FICH - UNL

La evolución como un algoritmo

Inicializar(Población)
MejorAptitud ← Evaluar(Población)
mientras MejorAptitud < AptitudRequerida

Progenitores ← SelecciónNatural(Población)
Población ← ReproducciónVariación(Progenitores)

Inteligencia Computacional - FICH - UNL

La evolución como un algoritmo

Inicializar(Población)
MejorAptitud ← Evaluar(Población)
mientras MejorAptitud < AptitudRequerida

Progenitores ← SelecciónNatural(Población)
Población ← ReproducciónVariación(Progenitores)
MejorAptitud ← Evaluar(Población)

fin

Inteligencia Computacional - FICH - UNL

Elementos de un algoritmo evolutivo

Inteligencia Computacional - FICH - UNL

Elementos de un algoritmo evolutivo

• Representación de los individuos

Inteligencia Computacional - FICH - UNL

Elementos de un algoritmo evolutivo

• Representación de los individuos
• Función de aptitud

Inteligencia Computacional - FICH - UNL

Elementos de un algoritmo evolutivo

• Representación de los individuos
• Función de aptitud
• Mecanismo de selección

Inteligencia Computacional - FICH - UNL

Elementos de un algoritmo evolutivo

• Representación de los individuos
• Función de aptitud
• Mecanismo de selección
• Operadores de variación

Inteligencia Computacional - FICH - UNL

Elementos de un algoritmo evolutivo

• Representación de los individuos
• Función de aptitud
• Mecanismo de selección
• Operadores de variación
• Reproducción y reemplazo generacional

Algoritmos genéticos:

representación de los individuos

Diego Milone

Inteligencia Computacional
Departamento de Informática

FICH-UNL

Inteligencia Computacional - FICH - UNL

Representación de los individuos

(Agoritmos Genéticos)

Espacio delfenotipo4.565561.253456Espacio delgenotipo1101100101010011CodificaciónDecodificaciónInteligencia Computacional - FICH - UNL

Representación de los individuos: ejemplos

• Ubicación de figuras para el llenado de un área

Inteligencia Computacional - FICH - UNL

Representación de los individuos: ejemplos

• Ubicación de figuras para el llenado de un área
• Entrenamiento de una red neuronal

Inteligencia Computacional - FICH - UNL

Representación de los individuos: ejemplos

• Ubicación de figuras para el llenado de un área
• Entrenamiento de una red neuronal
• Programación de un robot

Inteligencia Computacional - FICH - UNL

Representación de los individuos: ejemplos

• Ubicación de figuras para el llenado de un área
• Entrenamiento de una red neuronal
• Programación de un robot
• Circuito para un filtro multibanda

Inteligencia Computacional - FICH - UNL

Representación de los individuos: ejemplos

• Ubicación de figuras para el llenado de un área
• Entrenamiento de una red neuronal
• Programación de un robot
• Circuito para un filtro multibanda
• Problema del agente viajero
• ...

Algoritmos genéticos:

función de aptitud

Diego Milone

Inteligencia Computacional
Departamento de Informática

FICH-UNL

Inteligencia Computacional - FICH - UNL

Función de aptitud

• Características generales:

• Monotonicidad
• Precisión
• Suavidad regulable
• Penalización de complejidad

Inteligencia Computacional - FICH - UNL

Función de aptitud

• Características generales:

• Monotonicidad
• Precisión
• Suavidad regulable
• Penalización de complejidad

• Algunos ejemplos típicos:

absoluta, error relativo medio,...

• Promedios de error: cuadrados medios, desviación media
• Estadísticas: estimación de la varianza, validación cruzada,
• Medidas de información: criterio de Akaike, criterio de
información Bayesiano, descriptor de mínima longitud,
información mutua, minimización del riesgo empírico

verosimilitud, predicción de error,...

• Otras: correlaciones, distancias,...

Inteligencia Computacional - FICH - UNL

Función de aptitud: ejemplos

• Ubicación de figuras para el llenado de un área

Inteligencia Computacional - FICH - UNL

Función de aptitud: ejemplos

• Ubicación de figuras para el llenado de un área
• Entrenamiento de una red neuronal

Inteligencia Computacional - FICH - UNL

Función de aptitud: ejemplos

• Ubicación de figuras para el llenado de un área
• Entrenamiento de una red neuronal
• Programación de un robot

Inteligencia Computacional - FICH - UNL

Función de aptitud: ejemplos

• Ubicación de figuras para el llenado de un área
• Entrenamiento de una red neuronal
• Programación de un robot
• Circuito para un filtro multibanda

Inteligencia Computacional - FICH - UNL

Función de aptitud: ejemplos

• Ubicación de figuras para el llenado de un área
• Entrenamiento de una red neuronal
• Programación de un robot
• Circuito para un filtro multibanda
• Problema del agente viajero
• ...

Algoritmos genéticos:

operadores

Diego Milone

Inteligencia Computacional
Departamento de Informática

FICH-UNL

Inteligencia Computacional - FICH - UNL

Estrategias de selección

• Rueda de ruleta

4567123Inteligencia Computacional - FICH - UNL

Estrategias de selección

• Rueda de ruleta

• Ventanas

4567123Inteligencia Computacional - FICH - UNL

Estrategias de selección

• Rueda de ruleta

• Ventanas
• Competencias

4567123Inteligencia Computacional - FICH - UNL

Operadores de variación

• Mutaciones

Punto de mutaciónCromosoma originalCromosoma mutado1011101110111010Inteligencia Computacional - FICH - UNL

Operadores de variación

• Cruzas simples

Punto de cruzaCromosomas padresCromosomas hijos11101100101110111110101010111101Inteligencia Computacional - FICH - UNL

Operadores de variación

• Cruzas simples

• ¿Qué rol cumple cada operador en la búsqueda?

Punto de cruzaCromosomas padresCromosomas hijos11101100101110111110101010111101Inteligencia Computacional - FICH - UNL

Reemplazo durante la reproducción

• Reemplazo total

Inteligencia Computacional - FICH - UNL

Reemplazo durante la reproducción

• Reemplazo total
• Reemplazo con brecha generacional

Inteligencia Computacional - FICH - UNL

Reemplazo durante la reproducción

• Reemplazo total
• Reemplazo con brecha generacional
• Elitismo

Algoritmos evolutivos:

características principales

Diego Milone

Inteligencia Computacional
Departamento de Informática

FICH-UNL

Inteligencia Computacional - FICH - UNL

Análisis de las car