Algoritmos Genéticos



Como es de esperarse, los algoritmos genéticos tienen cierta analogía con la evolución en la naturaleza, de una u otra forma se quiere hacer un símil con respecto al individuo que se adapta al entorno y tiene futuras generaciones, se desea que el algoritmo tome las entradas necesarias y sea optimo en su implementación. Cuanto mayor sea la adaptación de un individuo al problema, mayor será la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material genético con otro individuo seleccionado de igual forma. Este cruce producirá nuevos individuos descendientes de los anteriores los cuales comparten algunas de las características de sus padres. Cuanto menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la reproducción, y por tanto de que su material genético se propague en sucesivas generaciones.

Fue el investigador de la Universidad de Michigan llamado John Holland quien empezó a trabajar y plantear una técnica para poder implementarla en un programa, esto fue a mediado de los años 70’s, donde se empezó una de las líneas de la inteligencia artificial, puesto que éstos algoritmos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.

El Algoritmo Genético Simple

BEGIN /* Algoritmo Genético Simple */
Generar una población inicial.
Computar la función de evaluación de cada individuo.
WHILE NOT Terminado DO
BEGIN /* Producir nueva generación */
FOR Tamaño población/2 DO
BEGIN /*Ciclo Reproductivo */

Seleccionar dos individuos de la anterior generación, para el cruce (probabilidad de selección proporcional a la función de evaluación del individuo).
Cruzar con cierta probabilidad los dos individuos obteniendo dos descendientes.
Mutar los dos descendientes con cierta probabilidad.
Computar la función de evaluación de los dos descendientes mutados.

Insertar los dos descendientes mutados en la nueva generación.
END
IF la población ha convergido THEN Terminado:= TRUE
END
END


El anterior pseudocódigo del Algoritmo Genético Simple (1) muestra como se puede llegar a elaborar de forma sencilla el algoritmo, además que se observa que tiene varias iteraciones para su desarrollo. Mientras se ejecuta el algoritmo, los padres deben seleccionarse para la reproducción, después éstos se cruzaran generando la siguiente generación, valga la redundancia, sobre la cual actuara un operador de mutación, el resultado de las anteriores funciones es un conjunto de posibles soluciones a un problema determinado.


Para poder llevar a cabo un algoritmo, hace falta un método para codificar las soluciones en un sistema que se pueda depurar. La forma más común es utilizando números binarios donde el dígito de cada posición representa el valor de algún aspecto de la solución. Otro método similar consiste en codificar las soluciones como cadenas de enteros o números decimales, donde cada posición, de nuevo, representa algún aspecto particular de la solución. Este método permite una mayor precisión y complejidad que el método comparativamente restringido de utilizar sólo números binarios.


La virtud de los métodos es que facilitan la definición de operadores que causen los cambios aleatorios en las candidatas seleccionadas: cambiar un 0 por un 1 o viceversa, sumar o restar al valor de un número una cantidad elegida al azar, o cambiar una letra por otra. Otra estrategia, desarrollada principalmente por John Koza, de la Universidad de Stanford, y denominada programación genética, representa a los programas como estructuras de datos ramificadas llamadas árboles. En este método, los cambios aleatorios pueden generarse cambiado el operador o alterando el valor de un cierto nodo del árbol, o sustituyendo un subárbol por otro.

Imagen_1.jpg

Tres sencillos árboles de programa del tipo utilizado normalmente en la programación genética. Debajo se proporciona la expresión matemática que representa cada uno.
Ejemplo tomado de http://the-geek.org/docs/algen/

Una técnica de solución a problemas es la de utilizar redes neuronales, las cuales se basan en un modelo informático que se encuentra conectado de forma análoga a las neuronas del cerebro, la cual pretende que la información de la entrada estimule ciertas capas que a través de nodos transporten la información adquirida, siendo estimuladas cada neurona para que al final de la transmisión de información entre capas, se llegue a una salida que arroja una solución a la entrada presentada.

imagen_2.png
Una sencilla red neuronal anticipativa (feedforward), con una capa consistente en cuatro neuronas, una capa oculta consistente en tres neuronas y una capa de salida consistente en cuatro neuronas. El número de cada neurona representa su umbral de activación: sólo se excitará si recibe al menos esa cantidad de entradas. El diagrama muestra cómo la red neuronal recibe una cadena de entrada y cómo la activación se extiende por la red hasta producir una salida.
Ejemplo tomado de http://the-geek.org/docs/algen/


Ventajas de los algoritmos genéticos:

La primera ventaja de un algoritmo genético es el trabajo que realiza simultáneamente con varias soluciones, a comparación de la tradicional técnica secuencial. Mientras la técnica secuencial sigue un proceso en una sola dirección y encuentra una falla, este reinicia el proceso desechando el trabajo hecho, mientras que los algoritmos genéticos suprimen la falla y buscan la solución por otros caminos.
Los algoritmos genéticos buscan la mejor solución (la última en su búsqueda) en caso de optimizar el resultado. Otros algoritmos caen en soluciones falsas ya que se topan con resultados cercanos a los esperados pero no son los correctos, cosa que no pasa con los algoritmos genéticos.
Puede resolver objetivos simultáneamente manipulando los parámetros.
No se necesita de un conocimiento inicial, de hecho, realizan cambios y luego de un mapeo (función de amplitud) determinan si el cambio produce una mejora.
Es de fácil ejecución en arquitecturas complejas.
Usan operadores probabilísticos en vez de los determinanticos.

Desventajas de los algoritmos genéticos:

Definir el problema. Que soporte los cambios que se realicen sin dañar o producir resultados sin sentido. Requiere una clara jerarquización de cada individuo.
Tarda bastante encontrar una resultado en absoluto dependiendo de la cantidad de población que se tenga.
Puede encontrar un individuo apto sin realizar un mapeo en la demás población, quiere decir que encuentra optimo local prematuramente sin encontrar el optimo global en la población; esto comúnmente se debe a que el número de individuos es pequeño.

Aplicación de los algoritmos genéticos:

La aplicación mas común de estos algoritmos resolver problemas de optimización. Pero para todos los casos no es útil esta técnica. Se debe tener en cuenta las siguientes características:
Se debe tener un rango delimitado.
Debe tener una función de amplitud para mapear que tan cierta es la respuesta.
Se deben codificar de una manera clara los resultados permitiendo que la computadora los identifique fácilmente.
Entre otras aplicaciones tenemos:
Diseño de computadoras que cumplen diversos objetivos.
Optimizar la carga de conteiners.
Procesos en redes.
Ubicar archivos en sistemas de almacenamiento.
Diseño de circuitos integrados.
Mejoramiento de la telefonía celular.
Ingeniería aeroespacial.
Juegos.
Robótica.


En el siguiente link, hay un video de una aplicación de los algoritmos geneticos en la implementación para cada robot para la Robocup:
Video simulacion para robocup


REFERENCIAS
Arranz de la Peña, Jorge
Universidad Carlos III
100025106@alumnos.uc3m.es
Parra Truyol, Antonio
Universidad Carlos III
100023822@alumnos.uc3m.es

http://www.it.uc3m.es/jvillena/irc/practicas/06-07/05.pdf

http://the-geek.org/docs/algen/