Algoritmos Genéticos
Resumen
Uno de los grandes problemas es el cálculo de funciones no derivables o de difícil derivación, en su resolución son útiles los algoritmos genéticos, inspirados en la evolución biológica se pueden aplicar a una cantidad de problemas los cuales no se puedan descomponer en pasos o no se conozcan la cantidad de pasos necesarios para su resolución. El presente trabajo tiene la finalidad de explicar la teoría de los algoritmos genéticos y su funcionamiento, para que contribuya a la comprensión de está poderosa herramienta.
Introducción
En la actualidad los algoritmos genéticos son aplicados en múltiples áreas, desde aprendizaje de reglas de lógica difusa, análisis de expresión de genes, análisis lingüístico, predicción, optimización de producción y distribución de energía eléctrica, hasta aprendizaje de comportamiento de robots.
Proveniente de la inteligencia artificial se originó una de las ramas conocida como los algoritmos genéticos, creada por John Henry Holland en los años 1970. Estos se inspiran en la evolución biológica y la genética.
Estos algoritmos hacen evolucionar una población de individuos generados aleatoriamente y luego los hacen reproducirse, recombinarse y mutar, a cada generación se le aplica un criterio de selección inspirada en la selección natural.
Desarrollo
Los Algoritmos Genéticos son métodos adaptativos, generalmente usados
en problemas de búsqueda y optimización de parámetros, basados en la reproducción
sexual y en el principio de supervivencia del más apto (Fogel, 2000)
(Fogel, 2006).
Para alcanzar la solución a un problema se parte de un conjunto inicial
de individuos, llamado población, generado de manera aleatoria. Cada uno de
estos individuos representa una posible solución al problema. Estos individuos
evolucionarán tomando como base los esquemas propuestos por Darwin
sobre la selección natural, y se adaptarán en mayor medida tras el paso de cada
generación a la solución requerida (Darwin, 2007).
Bases biológicas
En la naturaleza, los individuos de una población compiten constantemente
con otros por recursos tales como comida, agua y refugio. Los individuos
que tienen más éxito en la lucha por los recursos tienen mayores probabilidades
de sobrevivir y generalmente una descendencia mayor.
Esto implica que los genes de los individuos mejor adaptados se propagarán a un número cada vez mayor de individuos de las sucesivas generaciones.
La combinación de características buenas de diferentes ancestros puede originar, en ocasiones, que la descendencia esté incluso mejor adaptada al medio que los padres. De esta manera, las especies evolucionan adaptándose más y más al entorno a medida que transcurren las generaciones (Beasley, Bull & Martin, 1993).
Codificación de problemas
Cualquier solución potencial a un problema puede ser presentada dando valores a una serie de parámetros. El conjunto de todos los parámetros (genes en la terminología de Algoritmos Genéticos) se codifica en una cadena de valores denominada cromosoma. El conjunto de los parámetros representado por un cromosoma particular recibe el nombre de genotipo. El genotipo contiene la información necesaria para la construcción del organismo, es decir, la solución real al problema, denominada fenotipo.
La codificación suele hacerse mediante valores binarios, aunque hay otras variantes, mediante valores reales, valores enteros o valores ascii. Se asigna un determinado número de bits a cada parámetro y se realiza una discretización de la variable representada por cada gen. El número de bits asignados dependerá del grado de ajuste que se desee alcanzar. Evidentemente no todos los parámetros tienen por qué estar codificados con el mismo número de bits. Cada uno de los bits pertenecientes a un gen suele recibir el nombre de alelo.
Algoritmo Principal
Los Algoritmos Genéticos trabajan sobre una población de individuos.
Cada uno de ellos representa una posible solución al problema que se desea resolver.
Todo individuo tiene asociado un ajuste de acuerdo a la bondad con respecto al problema de la solución que representa (en la naturaleza el equivalente sería una medida de la eficiencia del individuo en la lucha por los recursos).
Una generación se obtiene a partir de la anterior por medio de los operadores de reproducción. Existen 2 tipos:
Cruce. Se trata de una reproducción de tipo sexual. Se genera una descendencia a partir del mismo número de individuos (generalmente 2) de la generación anterior.
Copia. Se trata de una reproducción de tipo asexual. Un determinado número de individuos pasa sin sufrir ninguna variación directamente a la siguiente generación.
Operadores genéticos
Para el paso de una generación a la siguiente se aplican una serie de operadores
genéticos. Los más empleados son los operadores de selección, cruce, copia y mutación. En el caso de no trabajar con una población intermedia temporal también cobran relevancia los algoritmos de reemplazo.
Selección: Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.
Recombinación o cruzamiento: La recombinación es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
Mutación: Modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.
Reemplazo: Una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente.
Evaluación
Para el correcto funcionamiento de un Algoritmo Genético se debe de poseer un método que indique si los individuos de la población representan o no buenas soluciones al problema planteado. Por lo tanto, para cada tipo de problema que se desee resolver deberá derivarse un nuevo método, al igual que ocurrirá con la propia codificación de los individuos.
De esto se encarga la función de evaluación, que establece una medida numérica de la bondad de una solución. Esta medida recibe el nombre de ajuste. En la naturaleza el ajuste (o adecuación) de un individuo puede considerarse como la probabilidad de que ese individuo sobreviva hasta la edad de reproducción y se reproduzca. Esta probabilidad deberá estar ponderada con el número de individuos de la población genética.
Bibliografía:
Gestal, Marcos; Rivero, Daniel; Rabuñal, Juan Ramón; Dorado, Julián; Pazos, Alejandro (2010) Introducción a los Algoritmos Genéticos y la Programación Genética.
Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Genetic Programming - An Introduction. San Francisco, CA: Morgan Kaufmann.
Schmitt, Lothar M (2001), Theory of Genetic Algorithms, Theoretical Computer Science.
López, Manuel (2015), Jugando a ser Dios.
Autor:
Enmanuel J. Ramírez
(Optando por el título de T.S.U en Informática U.P.T.A “Federico Brito Figueroa”)