Publicado el 31 de Julio del 2017
4.647 visualizaciones desde el 31 de Julio del 2017
551,2 KB
18 paginas
Creado hace 6a (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
Comentarios de: Inteligencia Artificial - Algoritmos Genéticos (1)
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.