Download Algoritmos Genéticos

Algoritmos Genéticos
Una introducción a la computación
evolutiva
Algoritmos Genéticos







¿Qué son los algoritmos genéticos?
¿Cómo funcionan?
Implementación de los AG
Aplicaciones
Uso del paradigma funcional
Visión de futuro
Conclusiones
¿Qué es un AG?



Los AG son métodos de resolución de
problemas de búsqueda y optimización.
Son una clase particular de algoritmos
evolutivos.
Su característica principal es que se basan
en técnicas inspiradas en la evolución
biológica.
¿Qué es un AG?



Se aplican sobre una población representada de
forma abstracta como cromosomas, que son la
codificación de soluciones candidatas a un
problema.
La evolución comienza desde una población
aleatoria.
En cada generación, la selección natural elegirá que
individuos son aptos, modificandolos y mutándolos
para la siguiente generación.
¿Cómo funcionan?

Para resolver un problema usando AG
necesitamos:
–
Representar soluciones.

–
Tradicionalmente una cadena de bits.
Medir la calidad de cada solución con respecto al
problema a resolver.

Se usa una función de selección.
¿Cómo funcionan?

Esquema de funcionamiento de un AG:
–
–
Se crea una población inicial generando individuos
aleatoriamente.
Repetimos hasta que se alcance el individuo óptimo o el
número máximo de generaciones:




Asignar un valor de supervivencia a cada miembro de la
población.
Seleccionar a un conjunto de individuos que actuarán como
padres usando como criterio su probabilidad de supervivencia.
Emparejar un grupo de padres para crear desdendencia.
Combinar la descendencia con la población actual para crear
nueva población.
Implementación de los AG



Los AG se adaptan específicamente a los
problemas que van a resolver.
No hay un marco teórico genérico para
aplicarlo a todos los problemas.
Es difícil establecer dicho marco.
–
–
Si es muy genérico, resulta trivial.
Si es muy específico, no se puede adaptar a
todos los problemas.
Aplicaciones

Optimización de una función simple.
–
–
–
Los cromosomas son vectores numéricos que
representan el rango de variación.
La función de selección es el propio valor de f(x).
El resultado se muta con una probabilidad dada.
Aplicaciones

Problema del viajante.
–
–
–
Cada cromosoma es un vector con una
permutación de todas las ciudades, lo cual
representa un camino para visitarlas todas.
La función de selección depende de los pesos de
los distintos arcos del grafo.
Se muta el vector (se intercambian algunos de
sus elementos) con una probabilidad dada.
Uso del paradigma funcional

Ventajas
–
La definición de AG se adapta naturalmente al
paradigma funcional.


Las acciones que definen un AG (seleccionar, emparejar
y combinar) son funciones a definir.
El AG mismo es una función que toma una población
inicial y una semilla aleatoria, devolviendo un conjunto
de poblaciones sucesivas que representan las distintas
generaciones.
Uso del paradigma funcional
–
Un lenguaje funcional como Haskell permite el
uso de estructuras infinitas.

El AG puede generar una lista indefinida de
descendientes y la función de recombinación sólo usará
aquellos descendientes necesarios para construir la
nueva población.
Uso del paradigma funcional

Ejemplo de función de generación de
población
procrear :: Población -> Prob Población
procrear pob = do
padres <- seleccionar pob
hijos <- emparejar padres
combinar pob hijos
Uso del paradigma funcional


Se usa la mónada Prob para tener control preciso
sobre la generación de números aleatorios.
Prob mantiene varias listas infinitas de números
aleatorios asociados con cada proceso estocástico,
manteniéndolas ocultas al usuario.
–
Esto permite gran control sobre los factores que determinan
el resultado de las ejecuciones del AG.
Visión de futuro


Desarrollar una marco de trabajo para AG,
de manera que una misma estructura se
pueda instanciar a distintos tipos de
problemas.
Proporcionar operadores genéticos como
funciones predefinidas y permitir su
selección y utilización mediante un interfaz
de usuario.
Visión de futuro

Realización de una implementación más
eficiente que sea capaz de manejar
problemas de gran tamaño y complejidad.
–
–
Una posibilidad sería usar mónadas de estado
(State Monads) para reutilizar el espacio.
Explotar el paralelismo inherente a los AG
adaptando el marco a arquitecturas distribuidas.
Conclusiones

Ventajas del uso de los AG
–
–
Es poco sensible a los mínimos locales, lo cual le
confiere robustez, en contraste con las redes
neuronales clásicas.
Asimismo, no depende de las condiciones
iniciales, debido a que se usa búsqueda
estocástica y ésta hace al principio un gran
número de intentos aleatorios.
Conclusiones
–
–
El tiempo de convergencia de los AG es
predecible por la naturaleza paralela de la
búsqueda estocástica.
Funciona de forma paralela, por lo que pueden
usarse en sistemas distribuidos para mejorar más
la velocidad de búsqueda.
Conclusiones

Inconvenientes del uso de los AG
–
–
No hay un marco teórico genérico establecido.
Si la población inicial es cercana a la solución
óptima, los GA tardarán más que las técnicas de
resolución tradicionales.

El GA perderá mucho tiempo comprobando soluciones
sub-óptimas.
Conclusiones
–
–
Hacen buenas estimaciones de la solución
óptima, pero no la calculan exactamente.
El usuario debe determinar cómo de cerca está la
solución estimada de la solución real.

La proximidad a la solución real dependerá de la
aplicación en concreto.