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

Imágen de pdf Inteligencia Artificial - Algoritmos Genéticos

Inteligencia Artificial - Algoritmos Genéticosgráfica de visualizaciones

estrellaestrellaestrellaestrellaestrella(1)
Publicado el 31 de Julio del 2017
2.278 visualizaciones desde el 31 de Julio del 2017. Una media de 98 por semana
551,2 KB
18 paginas
Creado hace 244d (17/05/2017)
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
  • Links de descarga
http://lwp-l.com/pdf5880  

Comentarios de: Inteligencia Artificial - Algoritmos Genéticos (1)

Imágen de perfil
Rafael Angel
31 de Agosto del 2017
estrellaestrellaestrellaestrellaestrella
Excelente tema, este.
Yo he realizado algunos experimentos con lo que conosco del tema y he tenido exitos.
pero me gustaria hacerme experto en el tema de los algoritmos geneticos.
Responder

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios