PDF de programación - Inteligencia Artificial - Algoritmos Genéticos

Inteligencia Artificial



Algoritmos Genéticos

Prof. Dra. Silvia Schiaffino

ISISTAN



Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Agenda

• Concepto

• Ciclo

• Población

• Reproducción

– Recombinación

– Mutación

• Evaluación

• Algoritmo

• Ejemplos

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

1

Algoritmos Genéticos

• Algoritmo de búsqueda en espacio de soluciones.

•

Inspirados en mecanismos de evolución biológica

• Se basan en el mecanismo de supervivencia del más

apto

• Desarrollados por Holland en la Universidad de

Michigan en los ’70
– Para entender el proceso adaptativo de los sistemas

naturales

– Para diseñar sistemas artificiales con la robustez de los

sistemas naturales

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Algoritmos Genéticos

• Procedimiento iterativo
• Produce una serie de generaciones de

poblaciones, una población por cada
iteración

• Cada miembro de la población representa

una solución al problema y se denomina
cromosoma

• Nuevas soluciones se generan por crossover

(recombinación) y mutación

• Requiere el cálculo de una función de fitness



Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

2

Similitud con sistemas biológicos

Sistemas Biológicos

Algoritmos Genéticos



• Los miembros de una

• Muchas soluciones

población compiten por
sobrevivir y reproducirse

• Las especies que mejor se

adapten a su ambiente
son las que tienen más
posibilidades de
reproducirse

• Los hijos son un híbrido de

sus padres



Inteligencia Artificial – 2017


compiten por resolver el
problema y reproducirse

• Las soluciones que mejor
resuelven el problema son
las que tienen más
posibilidades de
reproducirse

• A partir de 2 soluciones se
obtienen otras mediante el
operador crossover



Prof.Dra. Silvia Schiaffino

Similitud con sistemas biológicos

Sistemas Biológicos

• Los hijos tienen un código
genético independiente del
de sus padres


• Los padres son

gradualmente
reemplazados por sus
hijos

• La población es cada vez

más apta y se adapta al
ambiente con el paso del
tiempo



Inteligencia Artificial – 2017


Algoritmos Genéticos



• Los hijos reciben un

código independiente del
de sus padres a través del
operador mutación

• Los padres mueren

inmediatamente una vez
que nacen sus hijos

• La población de

soluciones es cada vez
mejor para resolver el
problema



Prof.Dra. Silvia Schiaffino

3

Algoritmos Genéticos: Componentes

• Técnica de codificación

gen, cromosoma



• Procedimiento de inicialización creación



• Función de fitness



• Selección de padres



ambiente

reproducción



• Operadores Genéticos



mutación, crossover
(recombinación)

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Algoritmos Genéticos: Ciclo

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

4

Población

• Inicialización de la población: aleatoria o

soluciones conocidas

• Los cromosomas pueden ser:

– String de bits

– Números reales



(0101...1100)

(43.6 78.2....)

– Permutaciones de elementos

(E11 E3...E15)

– Lista de reglas



(R1 R2...R10)

– ...

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Reproducción

• Los padres son seleccionados

aleatoriamente, pero sus chances de
selección están en relación a la evaluación
de los cromosomas

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

5

Reproducción: Selección por rueda de la ruleta

• Cuando la rueda se detiene, la probabilidad

de detenerse en un cromosoma i es:
– Pi = fi / k fk

• La ruleta gira una cantidad aleatoria y

devuelve el cromosoma apuntado por la
flecha

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Reproducción

• Selección por

torneo: Selecciona un par de
individuos aleatoriamente. Generar un número
aleatorio R entre 0 y 1. Si R<r, usa el primer
individuo como padre. Si R>=r, usa el segundo
individuo como padre. El valor de r es un parámetro
de este método. Se hace lo mismo para encontrar el
segundo padre.


• Elitismo: Primero se copian

los N mejores
cromosomas a la nueva población, y el resto se
determinan con otros métodos. Esto incrementa
rápidamente la performance del algoritmo ya que
previene la pérdida de buenas soluciones.


Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

6

Modificación de cromosomas

• Operadores

– Mutación

– Crossover (Recombinación)

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Mutación

• Causa un movimiento en el espacio de

búsqueda

• Altera los genes aleatoriamente

• Mantiene la diversidad genética

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

7

Crossover o Recombinación

• Crossover es una característica crítica de los

algoritmos genéticos
– Combina 2 padres en nuevos hijos, genera

variantes combinando material genético existente

– Acelera la búsqueda tempranamente en la

evolución de la población

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Crossover

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

8

Evaluación

• El evaluador decodifica un cromosoma y le

asigna un valor de fitness

• El evaluador es el único nexo entre el

algoritmo genético y el problema que se está
solucionando

• Se necesita un modelo de evaluación distinto

para cada problema

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Técnicas de fitness

• La evaluación es directamente el valor de fitness



• Windowing: toma el valor más bajo y asigna a cada
cromosoma un valor de fitness igual a la cantidad
que excede del mínimo



• Normalización lineal: los cromosomas se ordenan
por orden decreciente de valor de evaluación, y se le
asigna un valor de fitness que comienza con una
constante y decrece linealmente. El valor individual y
el decremento son parámetros de esta técnica.



Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

9

Eliminación

• Eliminar todos: elimina todos los miembros de la
población actual y los reemplaza con el mismo
número de cromosomas que fueron creados



• Steady-State: Elimina n de los viejos miembros, y los

reemplaza con n nuevos miembros



• Steady-State-No duplicates: igual al anterior pero
chequea no incluir cromosomas duplicados en la
población. Tiene un costo adicional pero se explora
más cantidad del espacio de búsqueda.

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Algoritmo Básico

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

10

Algoritmo

• Inicializar una población de

cromosomas
– Colección de puntos iniciales, soluciones

– Transformar cada solución en un string de

bits

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Algoritmo

• Seleccionar padres para la reproducción

• Crear nuevos cromosomas por crossover y

mutación
– Identificar puntos de crossover



Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

11

Algoritmo

• Seleccionar padres para la reproducción

• Crear nuevos cromosomas por crossover y

mutación
– Identificar puntos de crossover

– En cada punto de crossover, intercambiar las

partes señaladas y crear nuevos hijos

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Algoritmo

• Ocasionalmente mutar los hijos

– Puntos de mutación

Seleccionar un bit aleatorio en el string y

cambiarlo

– Mutaciones complejas

Mutar un patrón o secuencias de bits

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

12

Algoritmo básico

• Seleccionar cuestiones de implementación

básicas
– Representación

– Tamaño de la población, razón de mutación

– Selección, políticas de eliminación

– Operadores de mutación y crossover

• Criterio de terminación

• La solución va a ser tan buena como lo sea

la función de evaluación

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Ejemplo: Problema del viajante

• Problema del viajante: encontrar un camino

entre un conjunto de ciudades de manera
que:
– Cada ciudad se visita solo una vez

– Minimizar la distancia total



• Solución: lista ordenada de ciudades

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

13

Problema del viajante: soluciones

• Posibles soluciones

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Recombinación

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

14

Recombinación

• Puede generar soluciones ilegales:

– Elige una parte del primer padre y la copia al primer hijo

– Copia los restantes genes que no están en la parte copiada

– Usa el orden de los genes del 2º padre

– Repite el proceso con el rol de los padres invertidos para

generar el 2º hijo

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Problema del viajante: Recombinación

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

15

Problema del viajante: Mutación

• Mutación: consiste en reordenar la lista

Inteligencia Artificial – 2017


Prof.Dra. Silvia Schiaffino

Ventajas de la técnica

• El algoritmo determina que hacer para resolver el

problema.

• Operan de forma simultánea con varias soluciones, en

lugar de trabajar de forma secuencial como las técnicas
tradicionales.

• En cualquier momento se puede obtener una solución al

problema. Las soluciones mejoran a través del tiempo.

• Se puede aumentar la velocidad de la evolución con

conocimiento acerca del problema.

• Facilita la exploración de soluciones alternativas.
• Utilizan operadores probabilísticos.
• El al