Download Inteligencia Artificial II

Inteligencia Artificial II
Unidad 3: Sistemas Evolutivos
Ingeniería en Mecatrónica
Facultad de Ingeniería
Universidad Nacional de Cuyo
Dr. Ing. Martín G. Marchetta
[email protected]
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
Introducción, motivación y aplicaciones recientes
Dr. Ing. Martín Marchetta – Inteligencia Artificial 2 – Ingeniería en Mecatrónica
Introducción, motivación y aplicaciones
●
Algoritmos Genéticos
●
●
●
●
●
Se originan en la primera mitad de los '70 (Hollstien, 1971;
Holland, 1975)
Son algoritmos de búsqueda local
Inspirados en la teoría de la evolución natural de las
especies
El algoritmo
–
mantiene un único estado (población)
–
la población evoluciona mediante operadores evolutivos
–
de acuerdo a una función de idoneidad
Son una variante de la búsqueda de haz local estocástica
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
3/41
Introducción, motivación y aplicaciones
●
●
●
La literatura relacionada con AG es muy extensa (ej: +80K
artículos en sciencedirect.com, +30K en los últimos 4 años).
La mayoría de los trabajos se relacionan con aplicaciones de
los GA a diversos ámbitos
Algunas aplicaciones recientes
●
●
●
●
Optimización de la ubicación de turbinas eólicas dentro de
parques eólicos (Emamia, 2010)
Optimización de parámetros en controladores difusos (del Brío &
Molina, 2007)
Optimización de parámetros de control en turbinas eólicas de
velocidad variable (Barrera-Cardenas, 2012)
Minimización de setups en prensas de perforación con CNC
(Marvizadeha, 2013)
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
4/41
Introducción, motivación y aplicaciones
●
Algunas aplicaciones recientes (cont.)
●
●
●
●
Planificación de procesos en líneas de manufactura para partes
múltiples (Musharavati, 2011)
Planificación de rutas en UAV (Pehlivanoglu, 2012)
Planificación de rutas y movimiento en AGV (Yun, 1996; Noguchi,
1997; Gemeinder, 2003; Davoodia, 2013; Tuncer, In Press)
Planificación de fechas de liberación de órdenes en plantas de
ensamblado (Fallah-Jamshidia, 2011)
●
Carga óptima de máquinas en celdas de FMS (Abazari, 2012)
●
Control de manipuladores robóticos (Köker, In Press)
●
Optimización de tuberías de gas (El-Mahdy, 2010)
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
5/41
Introducción, motivación y aplicaciones
●
●
Las aplicaciones recorren distintos niveles de decisión de
acuerdo al horizonte de tiempo
Algunos tipos de aplicaciones observados en la literatura
●
●
●
●
Optimización (ej: trazado de ductos, ubicación de plantas o
aerogeneradores, etc)
Planificación deliberativa con horizonte de tiempo medio/largo (ej:
scheduling)
Planificación deliberativa con horizonte de tiempo corto (ej: path
planning)
Planificación/optimización en tiempo real (ej: control de
manipuladores robóticos)
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
6/41
Introducción, motivación y aplicaciones
●
Ventajas: por qué usar AG?
●
●
●
●
●
Por ser algoritmos de búsqueda local, los AG requieren menos memoria
(usualmente una cantidad constante) que los algoritmos de búsqueda no local
Combinan ventajas de una búsqueda ascendente (similar al hill climbing por
gradiente) con exploración aleatoria para escapar de óptimos locales (en este
sentido son similares al temple simulado)
Algunos operadores evolutivos (ej: cruzamiento o crossover) permiten
aumentar “la granularidad” de la búsqueda moviéndose a estados que están
más alejados (“saltando” estados en el camino a la meta)
Permiten el uso de esquemas en las soluciones (“plantillas”)
Desventajas
●
●
Si se dispone de una buena heurística, los algoritmos clásicos pueden dan
mejores soluciones y pueden ser más eficientes (AG son subóptimos en
general)
Completez: si hay restricciones duras, pueden no encontrar una solución
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
7/41
Introducción a los Algoritmos Genéticos
Dr. Ing. Martín Marchetta – Inteligencia Artificial 2 – Ingeniería en Mecatrónica
Introducción a los Algoritmos Genéticos
●
Descripción intuitiva
●
El algoritmo es iterativo
●
Parte de una población (estado inicial)
●
En cada iteración
●
–
Se aplica una función de idoneidad (fitness) sobre los
individuos de esa población para asignarles un valor
–
Se seleccionan “los más aptos” en base a la función de
idoneidad
–
Se aplican operadores evolutivos sobre “los más aptos”
seleccionados, produciendo la nueva generación
–
La nueva generación será la población de la siguiente iteración
Este procedimiento iterativo se repite hasta que se cumple la
condición de parada del algoritmo (convergencia o tiempo)
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
9/41
Introducción a los Algoritmos Genéticos
Población
●
Conceptos y analogía con la naturaleza
●
●
●
Población
Individuo 1
...
G1
G2
...
–
Es el modelo de estado del algoritmo genético
–
Está compuesta por individuos (es decir, soluciones)
–
En cada iteración, se actualiza la población; es decir, partiendo de la
poblacióni se genera la poblacióni+1
Gm
Genes
Individuo
–
Es una posible solución al problema
–
Cada individuo se representa como una instancia del genoma (también
llamado cromosoma)
Genoma/Cromosoma
–
Es el modelo de un individuo
–
Define la forma en que se codifican los individuos (es decir, las
soluciones)
–
Está compuesto por genes
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
10/41
Introducción a los Algoritmos Genéticos
Población
●
Conceptos y analogía con la naturaleza (cont.)
●
Gen
–
●
●
Cada uno de los parámetros o variables que
componen al genoma (cada uno de los parámetros
que definen una solución)
Individuo 1
...
G1
G2
...
Gm
Genes
Genotipo
–
Es una instancia del genoma: representa a un individuo en particular
(es decir, asigna valores a cada gen del genoma para el individuo en
cuestión)
–
Se suele utilizar los términos Genoma y Genotipo de manera indistinta
Fenotipo
–
En el contexto biológico, es la “expresión observable” de un genotipo
(es decir, de un individuo)
–
En el contexto de los AG, se representa con la función de idoneidad
que define “la calidad” de un individuo particular
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
11/41
Introducción a los Algoritmos Genéticos
●
Conceptos y analogía con la naturaleza (cont.)
●
Operadores evolutivos
–
Se aplican a los individuos de una población para generar la
siguiente generación
–
En analogía con la naturaleza, son el mecanismo que hace
“evolucionar la especie” (mejorar las soluciones disponibles)
–
Pueden involucrar
●
●
Un único individuo de la población (ej: mutación)
Múltiples individuos (típicamente 2, ej: crossover o
cruzamiento)
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
12/41
Introducción a los Algoritmos Genéticos
●
Procedimiento general
Inicialización
(con cálculo fitness)
Individuo 1
...
Población
Individuo n
Cálculo
Fitness
No
Parada?
Si
Evolución
Selección
Padres
Selección del mejor
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
13/41
Introducción a los Algoritmos Genéticos
●
Procedimiento de selección
●
●
La función de idoneidad debería devolver valores más altos para
individuos “más aptos”
Alternativas de selección:
–
Se selecciona sólo el mejor (sólo se aplican operadores de
mutación para generar la nueva generación)
–
Se seleccionan los k mejores, donde k << n, y n es el tamaño
de la población
–
Todos pueden seleccionarse de manera probabilística:
●
●
El valor de idoneidad se utiliza como probabilidad del
individuo de ser seleccionado (técnica de rueda de ruleta)
La selección entonces se hace de manera aleatoria
utilizando la probabilidad definida por la idoneidad
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
14/41
Introducción a los Algoritmos Genéticos
●
Procedimiento de evolución
●
Cruzamiento (crossover):
–
Se eligen pares n/2 pares de individuos, mediante el
procedimiento de selección descripto
–
Por cada par, se genera aleatoriamente un punto de cruce
–
Se “cortan” los 2 individuos del par en el punto de cruce, y se
invierten sus partes
Fitness total
24+23+20+11 = 78
Ej. probabilidad I1
24/78*100 = 30,76
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
15/41
Introducción a los Algoritmos Genéticos
●
Procedimiento de evolución (cont.)
●
Alternativas de cruzamiento:
–
Cruce de N puntos
–
Cruce uniforme
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
16/41
Introducción a los Algoritmos Genéticos
●
Procedimiento de evolución (cont.)
●
Mutación
–
En la naturaleza, en la reproducción, a veces se producen
“errores” en la copia del genoma de los padres
–
Esto se modela mediante los operadores de mutación
–
Una vez aplicado el operador de crossover, se selecciona un
elemento* del genoma cada individuo y se lo modifica
aleatoriamente de acuerdo a una probabilidad p (esta
probabilidad es un parámetro del modelo)
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
17/41
Introducción a los Algoritmos Genéticos
●
Condiciones de parada. Alternativas
●
●
Convergencia
–
La diferencia de “calidad” entre una población y la anterior es menor que un
determinado umbral
–
La “calidad” puede medirse de distintas maneras, típicamente utilizando los
valores de idoneidad de los individuos de la población (ej: valor de idoneidad
del mejor individuo, promedio de idoneidad de toda la poblacion, etc).
Tiempo
–
●
Cantidad de iteraciones
–
●
El algoritmo se para al cabo de un cierto tiempo de ejecución
El algoritmo se para luego de un cierto número de iteraciones
Condiciones especiales e híbridas
–
Pueden aplicarse condiciones especiales, ej: si hay restricciones duras, aunque
se cumpla el criterio de parada (ej: tiempo), puede continuarse con el algoritmo
hasta que se hayan satisfecho estas restricciones
–
Pueden combinarse los criterios anteriores con las condiciones especiales (ej:
convergencia + cumplimiento de restricciones duras)
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
18/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos desordenados (messy GA)
●
●
Los algoritmos genéticos clásicos
–
Codifican los genomas como cadenas de longitud fija con
genes en posiciones fijas
–
Esto trae problemas cuando los individuos son “ralos”:
pueden haber muchos genes que no estén presentes en
algunos individuos
Los algoritmos genéticos desordenados
–
Codifican los genomas como cadenas de longitud
variable
–
El orden de los genes también es variable
–
Cada instancia de un gen, además de contener su valor,
contiene un identificador al tipo de gen al que se refiere
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
19/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos desordenados (cont.)
●
●
Permiten además agrupar genes que tienen alta idoneidad,
permitiendo implementar eficientemente esquemas, en donde
algunos genes se ubican de manera cercana para hacerlos
evolucionar juntos
Implementación
●
●
El procedimiento general es similar al de los algoritmos genéticos
clásicos (inicialización, selección, evolución, supervivencia,
convergencia)
Los cambios se relacionan con
–
Codificación de individuos (formato de genes y genomas)
–
Implementación de operadores evolutivos
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
20/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos desordenados (cont.)
●
●
●
Codificación
–
Cada gen se codifica con un par de valores: (a) significado del gen; (b) valor
del gen
–
Ej: en un AG para optimizar un controlador difuso, el genoma incluye genes
que representan las cláusulas difusas del controlador, en las cuales su orden
no importa
Operadores evolutivos
–
El operador de mutación se mantiene
–
El operador de crossover se reemplaza por una versión similar, llamada corte
y empalma (cut and splice)
–
La diferencia es que el crossover utiliza el mismo punto de corte/empalme en
ambos individuos a combinar, mientras que en cut and splice se generan 2
puntos de corte/empalme aleatorios, uno para cada individuo que se combina
Sobreespecificación y subespecificación
–
Pueden ocurrir a causa del operador de cut and splice
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
21/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos contínuos
●
Generalidades
–
–
–
●
●
●
En ocasiones las variables a optimizar adoptan valores contínuos, por lo que los
algoritmos clásicos no se adecuan a este tipo de problemas
Una variante, AG continuos, permite trabajar con variables (genes) que adoptan
valores contínuos, los cuales se representan mediante punto flotante
Usualmente los genes se normalizan para adoptar un valor en el intervalo [0, 1]
Fitness: La función de fitness es ahora una función contínua de variable contínua, y
se utiliza de la misma manera que en los AG clásicos
Selección: El procedimiento de selección también es similar en ambos casos (ej:
selección aleatoria con probabilidad proporcional a la idoneidad): se seleccionan los k
mejores individuos, y se completa* la población con n-k hijos (el tamaño de la
población permanece constante)
Convergencia: Similar a los AG clásicos
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
22/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos contínuos (cont.)
●
Crossover: es donde radica la mayor diferencia
–
En lugar de intercambiar partes de los genomas “padre”, estos son
sufren modificaciones generando atributos totalmente nuevos en los
hijos (conocido como Cruce Aritmético)
–
La generación del hijo se realiza de la siguiente manera:
●
●
Existen varias estrategias para evolucionar los genes, pero la más
utilizada es el promedio ponderado:
genhijo1 = a genpadre 1 + (1-a) genpadre 2
genhijo2 = a genpadre 2 + (1-a) genpadre 1
Consideraciones del parámetro a:
–
–
–
–
Si a=0,5 se tiene un cruce aritmético uniforme.
Variable (ej: variante dependiendo de la edad de la población)
Aleatorio
Extrapolación: A fin de permitir que los valores de los genes puedan
evolucionar fuera del rango de los padres, se pueden seleccionar
valores de a > 1
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
23/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos contínuos (cont.)
●
Alternativas de Crossover:
–
Cruce Aritmético Individual:
●
Se evoluciona únicamente un gen en cada hijo.
{x1, x2 … xk, a x k+1 + (1-a) yk+1, xk+2 … xn}
{y1, y2 … yk, a y k+1 + (1-a) xk+1, yk+2 … yn}
–
Cruce Aritmético Simple:
●
●
Se seleccionan aleatoriamente 1 o más puntos de corte
Se evolucionan los genes según alguna de estas opciones: (a) a
la derecha (se muestra en el ej); (b) a la izquierda; (c) en medio;
(d) sobre los puntos de corte
{x1, x2 … xk, a x k+1 + (1-a) yk+1, a x k+2 + (1-a) yk+2 … a x n + (1-a) yn}
{y1, y2 … yk, a y k+1 + (1-a) xk+1, a y k+2 + (1-a) xk+2 … a y n + (1-a) xn}
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
24/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos contínuos (cont.)
●
Alternativas de Crossover (cont.):
–
Cruce Aritmético Uniforme:
●
Todos los genes se cruzan
{a x1 + (1-a) y1, a x2 + (1-a) y2 … a xk + (1-a) yk … a xn + (1-a) yn}
{a y1 + (1-a) x1, a y2 + (1-a) x2 … a yk + (1-a) xk … a yn + (1-a) xn}
–
Cruce Discreto (en todas sus variantes):
●
Los elementos se copian de los padres tal como se vió en las
representaciones discretas
{x1, x2 … xk, yk+1, xk+2 … xn}
{y1, y2 … yk, xk+1, yk+2 … yn}
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
25/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos contínuos (cont.)
●
Mutación:
–
Se aplica de manera similar a los AG clásicos
–
La diferencia es el dominio de la variable de la cual se toman los valores
aleatorios a reemplazar
–
El operador de mutación es muy importante para permitir al algoritmo escapar
de óptimos locales
–
Existen distintas alternativas:
●
●
Mutación Uniforme (o Reajuste Aleatorio):
– Todos los valores tienen la misma probabilidad de ser elegidos. Ej: Si los
genes están normalizados a [0, 1], se selecciona uno o más genes
aleatorios en el genoma a mutar, y se les asigna un valor aleatorio en [0,
1]
Mutación No Uniforme:
– Consiste en sumar al valor actual del gen una cantidad elegida
aleatoriamente a partir de una distribución Gaussiana N(0, σ) (o función
similar).
– La desviación estándar determina la fuerza del cambio.
– De ser necesario se reducen los valores.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
26/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones
●
●
●
●
Generalidades
–
Son utilizados en problemas de ordenamiento o secuenciación.
–
Cuando se requiere decidir la forma en que ocurrirán una serie de eventos.
–
Los genes se representan con variables discretas y deben aparecer sólo una vez
en cada individuo.
–
Ejemplos clásicos de utilización de estos algoritmos son planificación de tareas (Job
Scheduling) y de trazado de caminos (problema del viajante).
Fitness: La función de fitness puede ser el tiempo total que tome una planificación (Job
Scheduling) o la distancia total que sume un camino (problema del viajante). En general
depende del problema. Se utiliza de la misma manera que en los AG clásicos, sólo que
mientras menor tiempo o menor distancia la solución es mejor.
Selección: El procedimiento de selección también es similar a los casos anteriores.
Convergencia: Similar a los casos anteriores o cuando no existen más permutaciones
posibles.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
27/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones (cont.)
●
Problemas con los métodos de evolución conocidos:
–
–
Crossover:
● Los operadores conocidos producen soluciones inadmisibles.
● Se pierde información respecto al orden de los elementos en los
padres.
Mutación:
●
●
●
●
También producen soluciones inadmisibles. Por ejemplo, si
cambiamos el j de una solución por el valor k, el valor k estará dos
veces en una solución, lo cual implica que deja de ser una
permutación.
Los genes no deben ser considerados como elementos
independientes.
La probabilidad de mutación deja de ser considerada para cada gen
en particular, sino que es considerada como la probabilidad de aplicar
el operador en toda la solución.
Los genes deben ser movidos en lugar de ser cambiados.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
28/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones (cont.)
●
Crossover:
–
Cruce de orden:
●
●
Se preserva un orden relativo de los genes de los padres.
El procedimiento consiste en seleccionar dos puntos de
cruce al azar, se copian los elementos del padre 1 entre
los puntos de cruce y luego se copian los valores restantes
a partir del segundo corte en el orden del padre 2. El
segundo hijo es creado de manera análoga el primero.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
29/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones (cont.)
●
Crossover (cont.):
–
Cruce PMX (partially mapped crossover):
●
●
●
●
●
●
Elegir dos puntos de cruce al azar, y copiar los valores del P1, que
se encuentran entre los dos puntos de cruce en el hijo 1.
Posicionarse en el primer punto de cruce sobre P2, y revisar qué
elementos de P2 (existentes entre los dos puntos de cruce) no han
sido incluidos en el hijo 1.
Por cada elemento i de los mencionados, revisar qué elemento j ha
sido copiado en su posición (sobre P2) en el hijo 1.
Ubicar i, en el hijo 1, en la posición ocupada por j sobre P2 (esto es
posible de hacer porque j ya ha sido ubicado en el hijo 1).
Si la posición ocupada por j en el P2 ya ha sido llenada en el hijo 1
por un elemento k, ubicar i en la posición ocupada por k en P2.
Una vez revisados los elementos entre los puntos de cruce, las
posiciones restantes del hijo 1 deben ser llenadas a partir de P2.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
30/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones (cont.)
●
Crossover (cont.):
–
Cruce PMX – Ejemplo:
Copiar:
Mapear: (valores faltantes 6 y 5)
Rellenar:
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
31/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones (cont.)
●
Crossover (cont.):
–
Cruce por Arcos:
●
●
●
La idea central es preservar la posición absoluta en la cual los elementos
ocurren
El operador divide a los elementos en ciclos. El hijo es creado
seleccionando, de manera alternada, ciclos de cada padre
Procedimiento:
– Definir un ciclo de valores a partir de P1 en la siguiente forma:
1) Comenzar con el primer valor no usado de P1
2) Revisar el valor ubicado en la misma posición en P2
3) Ir a la posición que contiene el mismo valor en P1
4) Sumar este valor al ciclo
5) Repetir los pasos 2-4 hasta que se arribe al primer valor de P1
– Ubicar los valores del ciclo en el hijo 1 (hijo 2) respetando las posiciones
que ellos tienen en el P1 (P2)
– Definir el siguiente ciclo. Ubicar a los valores de este ciclo en el hijo 1
(hijo 2) respetando las posiciones que ellos tienen en el P2 (P1).
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
32/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones (cont.)
●
Crossover (cont.):
–
Cruce por Arcos - Ejemplo:
●
Detección de Ciclos
●
Detección de valores fuera de ciclos
●
Copia de ciclos alternada
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
33/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones (cont.)
●
Mutación:
–
Mutación por Inserción:
●
●
Es capaz de preservar la mayor parte del orden
existente entre los genes y sus adyacencias.
El procedimiento es el siguiente:
– Se eligen dos genes al azar de la solución.
– Se mueve el segundo gen elegido a continuación
del primero.
– El resto de los genes se mueven a la derecha.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
34/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones (cont.)
●
Mutación (cont.):
–
Mutación por Intercambio:
●
●
Las adyacencias son preservadas mayoritariamente,
aunque el orden se ve más afectado.
El procedimiento es el siguiente:
– Se eligen dos genes al azar de la solución.
– Se intercambian los genes elegidos.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
35/41
Introducción a los Algoritmos Genéticos
●
Algoritmos genéticos con permutaciones (cont.)
●
Mutación (cont.):
–
Mutación por mezcla:
●
●
Las adyacencias y orden son mayoritariamente
perturbados.
El procedimiento es el siguiente:
– Se eligen varios genes al azar de la solución.
– Se mezclan los genes elegidos en las mismas
posiciones (las posiciones de los genes no
elegidos permanecen con los mismos valores.
– Los genes elegidos pueden ser contiguos o no.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
36/41
Introducción a los Algoritmos Genéticos
●
Evaluación del modelo: cómo saber si funciona?
●
●
●
●
●
Generación de una cantidad razonable de casos de prueba (ej: 100,
1000, etc)
Casos de prueba agrupados por tamaño y complejidad
Los casos de prueba pueden ser reales (tomados de un log de un
sistema real) o simulados
Se corre el algoritmo en las mismas condiciones en cada grupo de
casos de prueba
Se toman medidas de ejecución. Típicamente
–
Tiempo de ejecución
Tiempo/iteraciones requeridas para converger
–
Calidad de la solución
–
●
Se promedian estas mediciones por cada grupo, y se realiza un
perfilado del comportamiento del modelo para distintos grupos
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
37/41
Relación con otras técnicas de Soft Computing
Dr. Ing. Martín Marchetta – Inteligencia Artificial 2 – Ingeniería en Mecatrónica
Relación con otras técnicas de Soft Computing
●
●
Otras técnicas de soft computing relevantes para la cátedra son
Redes Neuronales y Lógica Difusa
Se pueden combinar AG con estas (y otras técnicas) de varias
maneras. Algunos ejemplos
●
Combinación en paralelo o en serie para resolver distintas partes
de un problema.
–
●
Ej: utilización de AG para planificación deliberativa con
horizonte de tiempo medio/largo + FLC para control directo de
acciones indicadas por el AG
Optimización de Fuzzy Logic Controllers (FLC)
–
AG para selección/mutación de reglas simbólicas
–
Aprendizaje por BP para optimización de parámetros
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
39/41
Referencias
●
●
●
●
●
●
●
[del Brío & Molina, 2007] B.M. del Brío y A. Sanz Molina, Redes Neuronales y Sistemas
Borrosos, 2da de., Alfaomega, 2007.
[Emamia, 2010] A. Emamia and P. Noghrehb, New approach on optimization in
placement of wind turbines within wind farm by genetic algorithms, Renewable Energy
35 (7) (2010) 1559–1564.
[Barrera-Cardenas, 2012] R. Barrera-Cardenas and M. Molinas, Optimal LQG Controller
for Variable Speed Wind Turbine Based on Genetic Algorithms, Energy Procedia 20
(2012) 207–216.
[Marvizadeha, 2013] S. Zamiri Marvizadeha and F.F. Choobinehb, Reducing the number
of setups for CNC punch presses, Omega 41 (2)(2013) 226–235.
[Musharavati, 2011] F. Musharavati, A.S.M. Hamouda, Modified genetic algorithms for
manufacturing process planning in multiple parts manufacturing lines, Expert Systems
with Applications 38 (9) (2011) 10770–10779.
[Pehlivanoglu, 2012] Y. Volkan Pehlivanoglu, A new vibrational genetic algorithm
enhanced with a Voronoi diagram for path planning of autonomous UAV, Aerospace
Science and Technology 16 (1) (2012) 47–55.
[Fallah-Jamshidia, 2011] S. Fallah-Jamshidia, N. Karimia, M. Zandiehb, A hybrid multiobjective genetic algorithm for planning order release date in two-level assembly system
with random lead times, Expert Systems with Applications 38 (11) (2011) 13549–13554.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
40/41
Referencias
●
●
●
●
●
●
●
●
●
●
[Tuncer, In Press] A. Tuncer, M. Yildirim, Dynamic path planning of mobile robots with improved
genetic algorithm, Computers & Electrical Engineering, In Press.
[Abazari, 2012] A.M. Abazari, M. Solimanpur, H. Sattari, Optimum loading of machines in a flexible
manufacturing system using a mixed-integer linear mathematical programming model and genetic
algorithm, Computers & Industrial Engineering 62 (2) (2012) 469–478.
[Köker, In Press] R. Köker, A genetic algorithm approach to a neural-network-based inverse
kinematics solution of robotic manipulators based on error minimization, Information Sciences, In
Press.
[El-Mahdy, 2010] O.F.M. El-Mahdy, M.E.H. Ahmed, S. Metwalli, Computer aided optimization of
natural gas pipe networks using genetic algorithm, Applied Soft Computing 10 (4) (2010) 1141–1150.
[Noguchi, 1997] N. Noguchi, H. Terao, Path planning of an agricultural mobile robot by neural network
and genetic algorithm, Computers and Electronics in Agriculture 18 (2–3) (1997) 187–204.
[Yun, 1996] Wei-Min Yun, Yu-Geng Xi, Optimum motion planning in joint space for robots using
genetic algorithms, Robotics and Autonomous Systems 18 (4) (1996) 373–393.
[Gemeinder, 2003] M. Gemeinder, M. Gerke, GA-based path planning for mobile robot systems
employing an active search algorithm, Applied Soft Computing 3 (2) (2003) 149–158.
[Davoodia, 2013] M. Davoodia, F. Panahib, A. Mohadesc, S.N. Hashemi, Multi-objective path planning
in discrete space, Applied Soft Computing 13 (1) (2013) 709–720.
[Hollstien, 1971] R.B. Hollstien, Artificial Genetic Adaptation in Computer Control Systems, PhD
thesis, University of Michingan, 1971
[Holland, 1975] J.H. Holland, Adaptation in Natural and Artificial Systems, University of Michingan
Press, Ann Arbor, 1975.
Dr. Ing. Martín Marchetta – Inteligencia Artificial II – Ingeniería en Mecatrónica
41/41