algoritmos geneticos

Índice

1.1.        Definición:……………………………………………………….3

1.2.         Cuándo usar estos algoritmos……………………………...3

1.3.         Aplicaciones……………………………………………………3

1.4.        Ejemplo completo de un algoritmo genético……………...4

1.4.1.   Inicialización:……………………………………………………5

1.4.2.   Evaluación:………………………………………………………5

1.4.3.  Selección:………………………………………………………...5

1.4.4.  Reproducción:…………………………………………………..6

1.4.5.  Entrenamiento:………………………………………………….7

1.5. Conclusión del trabajo:…………………………………………..8

Algoritmo genético

1.1.        Definición:

Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico. En los años 1970, de la mano de John Henry Holland, surgió una de las líneas más prometedoras de la inteligencia artificial, la de los algoritmos genéticos^[1]  . Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular.

Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una Selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.

Un algoritmo genético es un método de búsqueda dirigida basada en probabilidad. Bajo una condición muy débil (que el algoritmo mantenga elitismo, es decir, guarde siempre al mejor elemento de la población sin hacerle ningún cambio) se puede demostrar que el algoritmo converge en probabilidad al óptimo. En otras palabras, al aumentar el número de iteraciones, la probabilidad de tener el óptimo en la población tiende a 1 (uno).

1.2.         Cuándo usar estos algoritmos

Los algoritmos genéticos son de probada eficacia en caso de querer calcular funciones no derivables (o de derivación muy compleja) aunque su uso es posible con cualquier función.
Deben tenerse en cuenta también las siguientes consideraciones:

• Si la función a optimizar tiene muchos máximos/mínimos locales se requerirán más iteraciones del algoritmo para "asegurar" el máximo/mínimo global.
• Si la función a optimizar contiene varios puntos muy cercanos en valor al óptimo, solamente podemos "asegurar" que encontraremos uno de ellos (no necesariamente el óptimo).

1.3.         Aplicaciones

v  Diseño automatizado, incluyendo investigación en diseño de materiales y diseño multiobjetivo de componentes automovilísticos: mejor comportamiento ante choques, ahorros de peso, mejora de aerodinámica, etc.

v  Construcción de árboles filogenéticos.

v  Diseño de sistemas de distribución de aguas.

v  Diseño de topologías de circuitos impresos.

v  Diseño de topologías de redes computacionales.

v  En Teoría de juegos, resolución de equilibrios.

v  Análisis de expresión de genes.

v  Aprendizaje de comportamiento de robots.

v  Aprendizaje de reglas de Lógica difusa.

v  Infraestructura de redes de comunicaciones móviles.

v  Optimización de estructuras moleculares.

v  Aplicación de Algoritmos Genéticos al Dilema del Prisionero Iterado

v  Optimización de sistemas de compresión de datos, por ejemplo, usando wavelets.

v  Manejo de residuos sólidos.

v  Ingeniería de software.

1.4.        Ejemplo completo de un algoritmo genético

La finalidad de este ejemplo es construir un planeador de rutas, capaz de encontrar la ruta más corta a la salida más cercana, para cada una de las “n” personas que se encuentran en un cuarto.
Este cuarto contiene obstáculos estáticos y varias salidas. La ruta encontrada para la persona “x” no debe llevarla a chocar con algún obstáculo ni con otra persona que a su vez se está moviendo en el cuarto.

 

 
  La interface del programa tiene la siguiente simbología:
     Cubos de colores y mas pequeños: Personas
                Cubos azules:                                     Obstáculos
                Cuadros rojos:                                    Salidas
 
Los pasos de un algoritmo genético son los siguientes:
1.4.1.   Inicialización:
En este primer paso se crea aleatoriamente un conjunto de individuos (que están sobre el espacio S).
Inicialmente tenemos 20 individuos. Los individuos se representan como un vector, cuyos valores van del 0-7, y que significan lo siguiente:
0 -> Camina un paso a la izquierda
1 -> Camina un paso a la derecha
2 -> Camina un paso adelante
3 -> Camina un paso atrás
-> Camina en diagonal izquierda hacia arriba
-> Camina en diagonal izquierda hacia abajo
-> Camina en diagonal derecha hacia abajo
-> Camina en diagonal derecha hacia arriba
8  -> Quédate en tu lugar
Éstos serían dos ejemplos de individuos:

1) 2 - 1 - 2 - 0 - 7 - 4 - 3 - 6 - 3 - 3 - 3 - 0 - 5 - 0 - 3 - 3 - 3 - 1 - 1 - 1 - 3 - 5 - 1 - 4 - 7 - 4 -                 3 - 1 - 6 - 1 - 2

2) 0 - 4 - 1 - 7 - 5 - 3 - 1 - 1 - 3 - 3 - 3 - 7 - 5 - 1 - 2 - 5 - 6 - 4 -
Después el algoritmo itera en los siguientes pasos hasta que se cumpla alguna condición.
En este caso dicha condición es que evolucionen 6 generaciones.

1.4.2.   Evaluación:
La Función F es computada para cada individuo, ordenando la población del mejor individuo al peor. En el ejemplo, la función a optimizar es la longitud de los individuos. Es decir deseamos obtener un individuo con longitud mínima. Por ello, se ordenan en base a su longitud y en orden ascendente.
1.4.3.  Selección:

Se selecciona con la regla de selección - explicada a continuación - una pareja de individuos. La regla utilizada es roulette wheel selection, que elige en base a probabilidad proporcional a su calificación:

1.- Se genera un número aleatorio r E [0,1].
2.- Se multiplica r por la suma de las calificaciones de la población (S), obteniéndose c = rS.
3.- Se establece la calificación acumulada (Ca) y el índice en cero: Ca = 0, i=0
4.- A la calificación acumulada se le suma la calificación del i-ésimo individuo:
Ca = Ca + calif(i)
5.- Si Ca > c entonces el i-esimo individuo es seleccionado.
6.- Si no, entonces se incrementa i y se regresa al paso 4.
Esta selección es con reemplazo, es decir, un mismo individuo puede ser seleccionado varias veces. Así que cada vez que se selecciona un individuo no se quita de la población de la que se está seleccionando, permanece en ella para que pueda ser elegido nuevamente.

 

1.4.4.  Reproducción:
Se generan nuevos individuos a partir de la pareja seleccionada en el paso 3.
El algoritmo de reproducción que se ha utilizado es el siguiente:
 Una vez seleccionados 2 individuos p1 y p2 (llamados padres) se procede a cruzarlos.
Generamos un número aleatorio entre 1 y  (longitud de p1)/2, llamado n1.
Generamos un número aleatorio entre (longitud de p2)/2 y longitud de p2, llamado n2.
Calculamos la posición en la que se encuentra p1 al dar n1 pasos, y la llamamos pasosp1.
Calculamos la posición en la que se encuentra p2 al dar (longitud de p2)/2 pasos, y la llamamos pasosp2.
Generamos un camino aleatorio de pasosp1 a pasosp2, llamado camino_intermedio. Este camino aleatorio verifica que no choque con ningún obstáculo predefinido (estático).
Copiamos los primeros n1 pasos de p1 en el nuevo individuo ni1.
Copiamos camino_intermedio a ni1.

·         Copiamos los pasos de p2 de n2 a longitud p2.

Y de la misma manera generamos el segundo nuevo individuo, sólo que ahora tomamos el inicio de p2 y el  final de p1.
Esta cruza nos garantiza que obtengamos individuos válidos, es decir que nos van a dar un camino que inicie en la posición original de la persona y finalice en alguna salida. Y que además no choque con ningún obstáculo.
Después de repetir 6 veces los pasos del 2 al 4, se obtiene una población final.
El algoritmo además de estos pasos, incorpora un quinto paso al que llamamos entrenamiento.
1.4.5.  Entrenamiento:
Repite los pasos del 1 al 4 n veces. El primer algoritmo genético coloca en la población inicial del segundo algoritmo genético, a su mejor individuo (lo coloca 2 veces, para asegurarse de que va a preservarse en las siguientes generaciones), el segundo hace lo mismo con el tercero, y así sucesivamente hasta n.
Los algoritmos genéticos tienen una característica peculiar, que es que cada vez que se ejecuta nos da (muy probablemente) respuestas diferentes, y esto es porque la población inicial se genera aleatoriamente.
Estos entrenamientos nos permiten tomar el mejor individuo evolucionado del algoritmo genético anterior, y a su vez generar nuevos individuos. Esto es conocido también como elitismo. Con esto generamos n veces poblaciones aleatorias y (n-1) veces la población inicial al menos tiene un buen individuo. Este nuevo individuo al cruzarlo con algún otro buen individuo generado aleatoriamente puede ser que nos dé uno aún mejor.
Parámetros que deben ser especificados en el programa:
Nº de generaciones: cantidad de veces que se produce una nueva generación de individuos, utilizando las reglas anteriormente explicadas. Por lógica, cuantas más generaciones produzcamos, obtendremos mejores individuos.
Nº de individuos por generación: en este ejemplo, la cantidad de individuos de una generación a otra es constante, no varía.
Nº de entrenamientos: cantidad de veces que se lleva a cabo un entrenamiento entre diferentes generaciones de individuos.

1.5.        CONCLUSIÓN DEL TRABAJO:

Como hemos podido observar, la principal ventaja de los algoritmos genéticos radica en su sencillez. Se requiere poca información sobre el espacio de búsqueda ya que se trabaja sobre un conjunto de soluciones o parámetros codificados (hipótesis o individuos). Se busca una solución por aproximación de la población, en lugar de una aproximación punto a punto. Con un control adecuado podemos mejorar la aptitud promedio de la población, obteniendo nuevos y mejores individuos y, por lo tanto, mejores soluciones.
La programación mediante algoritmos genéticos suponen un nuevo enfoque que permite abarcar todas aquellas áreas de aplicación donde no sepamos como resolver un problema:

v  Construcción de horarios en grandes universidades, evitando conflictos de clases.

v  Problema del viajante.

v  Hallazgo de errores en programas.

v  Optimización de producción y distribución de energía eléctrica.

v  Diseño de redes geodésicas (Problemas de diseño).

v  Calibración y detección de daños en estructuras civiles.