ALGORITMOS GENÉTICOS

Los algoritmos genéticos (AG), fueron inventados en 1975 por John Holland, de

la Universidad de Michigan. Los AG son, simplificando, algoritmos de optimización, es decir, tratan de encontrar la mejor solución a un problema dado entre un

conjunto de soluciones posibles. Los mecanismos de los que se valen los AG para

llevar a cabo esa búsqueda pueden verse como una metáfora de los procesos de

evolución biológica.

Básicamente, los algoritmos genéticos “Genetic Algorithms, GA”, simulan el proceso de evolución de las especies que se reproducen sexualmente. De manera muy general, se puede decir que en la evolución de los seres vivos, el problema al que cada individuo se enfrenta diariamente es el de la supervivencia. Para ello cuenta, entre otras, con las habilidades innatas provistas en su material genético. A nivel de los genes, el problema consiste en la búsqueda de aquellas adaptaciones beneficiosas en un medio hostil y cambiante. Debido en parte a la selección natural, cada especie gana cierta “información” que es incorporada a sus cromosomas.

Durante la reproducción sexual, un nuevo individuo, diferente de sus padres, se genera a través de la acción de dos mecanismos fundamentales: El primero es el cruzamiento, que combina parte del patrimonio genético de cada progenitor para elaborar el del nuevo individuo; el segundo es la mutación, que supone una modificación espontánea de esta información genética. La descendencia será diferente de los progenitores, pero mantendrá parte de sus características. Si los hijos heredan buenos atributos de sus padres, su probabilidad de supervivencia será mayor que aquellos otros que no las tengan. De este modo, los mejores tendrán altas probabilidades de reproducirse y diseminar su información genética a sus descendientes.

Esta descripción de los GA se adapta a cada situación concreta, siendo habitual la codificación de números enteros en vez de binarios. Del mismo modo se han sofisticado los distintos operadores de cruzamiento y mutación.

La aplicación más común de los AG ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables.

Sin embargo, no todos los problemas pudieran ser apropiados para la técnica, y

se recomienda en general tomar en cuenta las siguientes características del mismo

antes de intentar usarla:

Su espacio de búsqueda (i.e., sus posibles soluciones) debe de estar delimitado dentro de un cierto rango.

Debe permitir definir una función de aptitud que nos indique que tan buena

o mala es una cierta respuesta.

Las soluciones deben codificarse de una forma que resulte relativamente

fácil de implementar en el computador.1 GENERALIDADES 18

El primer punto es muy importante, y lo más recomendable es intentar resolver

problemas que tengan espacios de búsqueda discretos aunque éstos sean muy

grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de

búsqueda continuos, pero preferiblemente cuando exista un rango de soluciones

relativamente pequeño.

Otras areas de aplicacion de los algoritmos geneticos son:

• Programacion automatica
• Aprendizaje maquina
• Economia
• Sistemas inmunes
• Ecologia 
• Sistemas de poblaciones
• Evolucion y aprendizaje
• Sistemas sociales

CLASES DE ALGORITMOS GENÉTICOS Algoritmos Genéticos Generacionales

Se asemejan a la forma de reproducción de los insectos, donde una generación pone huevos, se aleja geográficamente o muere y es substituida por una nueva. En este momento se realizan cruces en una piscina de individuos, los descendientes son puestos en otra, al final de la fase reproductiva se elimina la generación anterior y se pasa a utilizar la nueva. Este modelo también es conocido como Algoritmo Genético Canónico.

Algoritmos Genéticos de estado Fijo.

Utilizan el esquema generacional de los mamíferos y otros animales de vida larga, donde coexisten padres y sus descendientes, permitiendo que los hijos sean educados por sus progenitores, pero también que a la larga se genere competencia entre ellos. En este modelo, no solo se deben seleccionar los dos individuos a ser padres, si no también cuales de la población anterior serán eliminados, para dar espacio a los descendientes. La diferencia esencial entre el reemplazo generacional y el modelo de estado fijo es que las estadísticas de la población son recalculadas luego de cada cruce y los nuevos descendientes están disponibles inmediatamente para la reproducción. Esto permite al modelo utilizar las características de un individuo prometedor tan pronto como es creado.

Algunos autores dicen que este modelo tiende a evolucionar mucho más rápido que el modelo generacional, sin embargo investigaciones de Goldberg y deb [GOLDBERG 93], encontraron que las ventajas parecen estar relacionadas con la alta tasa de crecimiento inicial, ellos dicen que los mismos efectos pueden ser obtenidos en rangos de adaptación exponencial o selección por competencia. No encontraron evidencia que este modelo sea mejor que el Generacional.

Algoritmos Genéticos Paralelos.

Parte de la metáfora biológica que motivo a utilizar la búsqueda genética consiste en que es inherentemente paralela, donde al evolucionar se recorren simultáneamente muchas soluciones, cada una representada por un individuo de la población. Sin embargo, es muy común en la naturaleza que no solo sea una población evolucionando, si no varias poblaciones, normalmente aisladas geográficamente, que originan respuestas diferentes a la presión evolutiva. Esto origina dos modelos que toman es cuenta esta variación, y utilizan no una población como los anteriores si4 no múltiples concurrentemente.

Modelos de Islas.

Si se tiene una población de individuos, esta se divide en subpoblaciones que evolucionan independientemente como un Algoritmo Genético normal. Ocasionalmente, se producen migraciones entre ellas, permitiéndoles intercambiar material genético. Con la utilización de la migración, este modelo puede explotar las diferencias en las subpoblaciones; esta variación representa una fuente de diversidad genética. Sin embargo, si un número de individuos emigran en cada generación, ocurre una mezcla global y se eliminan las diferencias locales, y si la migración es infrecuente, es probable que se produzca convergencia prematura en las subpoblaciones.

Modelo Celular

Coloca cada individuo en una matriz, donde cada uno sólo podrá buscar reproducirse con los individuos que tenga a su alrededor (mas cerca de casa) escogiendo al azar o al mejor adaptado. El descendiente pasara a ocupar una posición cercana. No hay islas en este modelo, pero hay efectos potenciales similares. Asumiendo que el cruce esta restringido a individuos adyacentes, dos individuos separados por 20 espacios están tan aislados como si estuvieran en dos islas, este tipo de separación es conocido como aislamiento por distancia.

Luego de la primera evaluación, los individuos están todavia distribuidos al azar sobre la matriz. Posteriormente, empiezan a emerger zonas como cromosomas y adaptaciones semejantes. La reproducción y selección local crea tendencias evolutivas aisladas, luego de varias generaciones, la competencia local resultara en grupos mas grandes de individuos semejantes.

Se ha observado de igual forma que los AG están indicados para resolver todo

tipo de problemas que se puedan expresar como un problema de optimización

donde se define una representación adecuada para las soluciones y para la función

a optimizar. Se busca una solución por aproximación de la población, en lugar de

una aproximación punto a punto.

Probablemente el punto más delicado de todo se encuentra en la definición de la

función objetivo, ya que de su eficiencia depende la obtención de un buen resultado. El resto del proceso es siempre el mismo para todos los casos.

La programación mediante AG supone un nuevo enfoque que permite abarcar todas aquellas áreas de aplicación donde no se sabe de ante mano como resolver el

problema.