Algoritmos Geneticos

Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A Lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acuerdo a los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin (1859). Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real.

Para hablar de algoritmos debemos saber qué significado tiene esta palabra, es la serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico, bien algo importante que se rescata de la definición es que da solución a un problema, así entonces podemos hablar de algoritmos genéticos, son algoritmos matemáticos altamente paralelos que se transforman en un conjunto de objetos matemáticos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta función matemática que refleja su aptitud.

Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor o puntuación, relacionado con la bondad de dicha solución. En la naturaleza esto equivaldría al grado de efectividad de un organismo para competir por unos determinados recursos. 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.

De esta manera se produce una nueva población de posibles soluciones, la cual reemplaza a la anterior y verifica la interesante propiedad de que contiene una mayor proporción de buenas características en comparación con la población anterior. Así a lo largo de las generaciones las buenas características se propagan a través de la población. Favoreciendo el cruce de los individuos mejor adaptados.

Por otro lado el poder de los algoritmos Genéticos proviene del hecho de que se trata de una técnica robusta, y se pueden tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el Algoritmo Genético encuentre la solución óptima del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria. En el caso de que existan técnicas especializadas para resolver un determinado problema, lo más probable es que superen al Algoritmo Genético, tanto en rapidez como en eficacia. El gran campo de aplicación de los Algoritmos Genéticos se relaciona con aquellos problemas para los cuales no existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibridándolas con los Algoritmos Genéticos.

Por otro lado una de sus características principales es la de ir perfeccionando su propia heurística en el proceso de ejecución, por lo que no requiere largos períodos de entrenamiento especializado por parte del ser humano, principal defecto de otros métodos para solucionar problemas, como los Sistemas Expertos.

Además no necesitan conocimientos específicos sobre el problema que intentan resolver y tienen las siguientes características.

• Operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales.

• Cuando se usan para problemas de optimización, maximizar una función objetivo resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales.

• Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivamente paralelas.

• Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas.

• Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen tamaño de la población, número de generaciones, etc.-.

• Pueden converger prematuramente debido a una serie de problemas de diversa índole.

También tienen las siguientes ventajas

• los algoritmos genéticos son paralelos. La mayoría de los otros algoritmos son en serie y sólo pueden explorar el espacio de soluciones hacia una solución en una dirección al mismo tiempo. Sin embargo los AG tienen descendencia múltiple, pueden explorar el espacio de soluciones en múltiples direcciones a la vez. Si un camino resulta ser un callejón sin salida, pueden eliminarlo fácilmente y continuar el trabajo en avenidas más prometedoras, dándoles una mayor probabilidad en cada ejecución de encontrar la solución

• Los algoritmos genéticos funcionan particularmente bien resolviendo problemas cuyo espacio de soluciones potenciales es realmente grande y demasiado bastó para hacer una búsqueda exhaustiva en un tiempo razonable. La mayoría de los problemas que caen en esta categoría se conocen como ``no lineales''. En un problema lineal

• La mayoría de los problemas prácticos tienen un espacio de soluciones enorme, imposible de explorar exhaustivamente.

• Aunque puede parecer un desastre, resulta ser una de sus ventajas a saber, los AG no saben nada de los problemas que deben resolver. En lugar de utilizar información específica conocida a prioridad para guiar cada pasó y realizar cambios con un ojo puesto en el mejoramiento

Y las siguientes desventajas

• La primera y más importante consideración al crear un algoritmo genético es definir una representación del problema. El lenguaje utilizado para especificar soluciones candidatas debe ser robusto; es decir, debe ser capaz de tolerar cambios aleatorios que no produzcan constantemente errores fatales o resultados sin sentido

• El problema de cómo escribir la función de aptitud debe considerarse cuidadosamente para que se pueda alcanzar una mayor aptitud y verdaderamente signifique una solución mejor para el problema dado

• Además de elegir bien la función de aptitud, también deben elegirse cuidadosamente los otros parámetros de un AG -el tamaño de la población, el ritmo de mutación y cruzamiento, el tipo y fuerza de la selección

En el contexto de los algoritmos genéticos se manejan algoritmos como:

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 T amañ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 Algoritmo Genético Simple, también denominado Canónico, necesita una codificación o representación del problema, que resulte adecuada al mismo. Además se requiere una función de ajuste o adaptación al problema, la cual asigna un número real a cada posible solución codificada. Durante la ejecución del algoritmo, los padres deben ser seleccionados para la reproducción, a continuación dichos padres seleccionados se cruzaran generando dos hijos, sobre cada uno de los cuales actuara un operador de mutación. El resultado de la combinación de las anteriores funciones será un conjunto de individuos (posibles soluciones al problema), los cuales en la evolución del Algoritmo Genético formaran parte de la siguiente población.

La codificación supone que los individuos (posibles soluciones del problema), pueden representarse como un conjunto de parámetros, los cuales agrupados forman una ristra de valores (a menudo referida como cromosoma). Si bien el alfabeto utilizado para representar los individuos no debe necesariamente estar constituido

...