ALGORITMOS GENÉTICOS (AGS)
Los algoritmos genéticos caen dentro de los métodos evolutivos debido a que estos están basados en poblaciones de soluciones a diferencia de los métodos basados en el seguimiento de trayectorias. Esta técnica de algoritmo evolutivo se puede clasificar en tres categorías principales: Algoritmo Genéticos (AG), Estrategias Evolutivas (EE) y la programación Evolutiva (PE). Todas estas estrategias se basan en un en un esquema común que es la generación de un conjunto de elementos llamados población inicial (conjunto de soluciones), esta población inicial es sometida a una serie de transformaciones que da lugar a una nueva población de soluciones, de esto se valora la adaptabilidad al medio de cada una de estas soluciones, de esto se desprende que la elección de los mejores individuos o soluciones para conformar la siguiente generación, este proceso se repite un número determinado de veces (ciclos) esperando que los individuos de la población haya evolucionado hacia una mejor adaptación al medio.
Las diferencias fundamentales entre cada una de las técnicas antes mencionadas radica en los tipo de alteraciones que se realizan en las soluciones para obtener nuevos individuos y en los métodos empleados para la selección de la nueva generación.
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 (AG), 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. También este algoritmo es denominado “algoritmo evolutivo” e incluye las estrategias de evolución, la programación evolutiva y la programación genética.
Los Algoritmos genéticos ocupan un lugar determinante dentro de la Programación Evolutiva debido a:
► Son flexibles y adaptables a una gran cantidad de problemas diferentes y distintas áreas, este algoritmo permite ser combinado con otros técnicas diferentes aunque no sean evolutivas.
► Los algoritmos genéticos tienen una mejor base teórica.
► Poseen una gran versatilidad ya que no necesitan mayor conocimientos específicos del problema para su resolución.
Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Un algoritmo genético consiste en una función matemática o una rutina de software que toma como entradas una población de ejemplares y retorna como salidas cuáles de ellos deben generar descendencia para la nueva generación. Versiones más complejas de algoritmos genéticos generan un ciclo iterativo que directamente toma a la especie (el total de los ejemplares) y crea una nueva generación que reemplaza a la antigua una cantidad de veces determinada por su propio diseño. 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.
Los Algoritmos Genéticos 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 ó 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. Si el Algoritmo Genético ha sido bien diseñado, la población convergerá hacia una solución óptima del problema.
El poder del Algoritmo Genético proviene del hecho de una técnica robusta y pueden tratar una gran variedad de problemas provenientes de diferentes áreas, sin embargo esto no garantiza una solución óptima del problema, si existe evidencia empírica de que se encuentran soluciones aceptables en un tiempo competitivo con el resto de los algoritmos de optimización combinatoria.
Los componentes básicos de un algoritmo genético son:
► Operadores genéticos (mutación y cruzamiento).
► Una representación apropiada del problema a resolver.
► Una función de oportunidad o bien llamada de Aptitud.
► Un procedimiento de inicialización.
El Algoritmo Genético en su versión más básica, 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.
A continuacion se muestra codigo algoritmico genetico basico:
En la codificación del algoritmo genético supone que los individuos (posibles soluciones al problema) pueden representarse como un conjunto de parámetros utilizando una codificación binaria de 0 y 1 los cuales agrupados forman una lista de valores. Si bien el alfabeto utilizado para representar los individuos no debe necesariamente estar constituido por el (0; 1), buena parte de la teoría en la que se fundamentan los Algoritmos Genéticos utiliza dicho alfabeto.
Un punto importante dentro del Algoritmo genético es la adaptación de un individuo el cuál dependerá de su genotipo, la cual puede inferirse a partir del fenotipo, es decir, puede ser computada usando una función de evaluación. La función de adaptación debe ser diseñada para cada problema de manera específica asignando un número real, que se supone refleja el nivel de adaptación al problema del individuo.
En la siguiente figura se ve reflejado un esquema general del algoritmo genético, donde en la fase reproductiva se seleccionan los individuos de la población para cruzarse y producir descendientes, que constituirán, una vez mutados, la siguiente generación de individuos.
La selección de padres se efectúa al azar usando un procedimiento que favorezca a los individuos mejor adaptados, ya que a cada individuo se le asigna una probabilidad de ser seleccionado que es proporcional a su función de adaptación. Este procedimiento se dice que está basado en la ruleta sesgada. Según dicho esquema, los individuos bien adaptados se escogerán probablemente varias veces por generación, mientras que los pobremente adaptados al problema, no se escogerán más que de vez en cuando.
Una vez seleccionados dos padres, sus cromosomas se combinan, utilizando habitualmente los operadores de cruce y mutación. Las formas básicas de dichos operadores se describen a continuación.
El operador de cruce, coge dos padres seleccionados y corta sus conjuntos de cromosomas en una posición escogida al azar, para producir dos subconjuntos iniciales. Después se intercambian las subconjunto iniciales, produciéndose dos nuevos cromosomas completos. Ambos descendientes heredan genes de cada uno de los padres. Este operador se conoce como operador de cruce basado en un punto. Habitualmente el operador de cruce no se aplica a todos los pares de individuos que han sido seleccionados para emparejarse, sino que se aplica de manera aleatoria, normalmente con una probabilidad comprendida entre 0.5 y 1.0.