ALGORITMOS GENÉTICOS
1. DEFINICIÓN
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 acorde con los principios de la
selección natural y la supervivencia de los más fuertes, postulados por Darwin.
Por imitación de este proceso, los Algoritmos Genéticos 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.
Un algoritmo genético consiste en una función matemática o una rutina de
software que toma como entradas a los ejemplares y retorna como salidas
cuales 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.
2. PROBLEMÁTICA
Los principios básicos de los Algoritmos Genéticos fueron establecidos por
Holland, y se encuentran bien descritos en varios textos . Goldberg, Davis,
Michalewicz, Reeves.
En la naturaleza los individuos de una población compiten entre sí en la
búsqueda de recursos tales como comida, agua y refugio. Incluso los miembros
de una misma especie compiten a menudo en la búsqueda de un compañero.
Aquellos individuos que tienen más éxito en sobrevivir y en atraer compañeros
tienen mayor probabilidad de generar un gran número de descendientes. Por el
contrario individuos poco dotados producirán un menor número de
descendientes. Esto significa que los genes de los individuos mejor adaptados
se propagarán en sucesivas generaciones hacia un número de individuos
creciente. La combinación de buenas características provenientes de diferentes
ancestros, puede a veces producir descendientes "superindividuos", cuya
adaptación es mucho mayor que la de cualquiera de sus ancestros. De esta
manera, las especies evolucionan logrando unas
características cada vez mejor adaptadas al entorno en el que viven.
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 ó 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, van siendo exploradas las áreas más prometedoras del
espacio de búsqueda. Si el Algoritmo Genético ha sido bien diseñado, la,
población convergerá hacia una solución óptima del problema.
3. VENTAJAS Y DESVENTAJAS
No necesitan conocimientos específicos sobre el problema que intentan
resolver.
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.
4. LIMITACIONES
El poder de los Algoritmos Genéticos proviene del hecho de que se trata de una
técnica robusta, y 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.
5. FUNCIONAMIENTO DE UN ALGORITMO GENETICO
Vamos a partir de una función f(x) muy sencilla:
f(x) =x2
(es decir, x al cuadrado).
Imagina que deseas encontrar el valor de x que hace que la función f(x)
alcance su valor máximo, pero restringiendo a la variable x a tomar valores
comprendidos entre 0 y 31. Aún más, a x sólo le vamos a permitir tomar
valores enteros, es decir: 0,1, 2, 3,..., 30, 31. Obviamente el máximo se tiene
para x = 31, donde f vale 961. No necesitamos saber algoritmos genéticos para
resolver este problema, pero su sencillez hace que el algoritmo sea más fácil
de comprender.
Lo primero que debemos hacer es encontrar una manera de codificar las
posibles soluciones (posible valores de x). Una manera de hacerlo es con la
codificación binaria. Con esta codificación un posible valor de x es
(0, 1, 0, 1, 1).
¿Cómo se interpreta esto? Muy sencillo: multiplica la última componente (un 1)
por 1, la penúltima (un 1) por 2, la anterior (un 0) por 4, la segunda (un 1) por 8
y la primera (un 0) por 16 y a continuación haz la suma: 11. Observa que (0, 0,
0, 0, 0) equivale a x = 0 y que (1, 1, 1, 1, 1) equivale a x = 31.
A cada posible valor de la variable x en representación binaria le vamos a
llamar individuo. Una colección de individuos constituye lo que se denomina
población y el número de individuos que la componen es el tamaño de la
población.
Una vez que tenemos codificada la solución, debemos escoger un tamaño de
población. Para este ejemplo ilustrativo vamos a escoger 6 individuos.
Debemos partir de una población inicial. Una manera de generarla es
aleatoriamente: coge una moneda y lánzala al aire; si sale cara, la primera
componente del primer individuo es un 0 y en caso contrario un 1. Repite el
lanzamiento de la moneda y tendremos la segunda componente del primer
individuo (un 0 si sale cara y un 1 si sale cruz). Así hasta 5 veces y obtendrás
el primer individuo. Repite ahora la secuencia anterior para generar los
individuos de la población restantes. En total tienes que lanzar 5 * 6 = 30 veces
la moneda.
Nuestro siguiente paso es hacer competir a los individuos entre sí. Este
proceso se conoce como selección. La tabla 1 resume el proceso.
Tabla 1.- SELECCION
(1) (2) (3) (4) (5)
1 (0,1,1,0,0) 12 144 6
2 (1,0,0,1,0) 18 324 3
3 (0,1,1,1,1) 15 225 2
4 (1,1,0,0,0) 24 576 5
5 (1,1,0,1,0) 26 676 4
6 (0,0,0,0,1) 1 1 1
Cada fila en la tabla 1 está asociada a un individuo de la población inicial. El
significado de cada columna de la tabla es el siguiente:
(1) = Número que le asignamos al individuo.
(2) = Individuo en codificación binaria.
(3) = Valor de x.
(4) = Valor de f(x).
Observa que el mejor individuo es el 5 con f = 676. Calcula la media de f y
obtendrás fmed =324.3.
En cuanto a la columna (5) ahora te lo explico. Una manera de realizar el
proceso de selección es mediante un torneo entre dos. A cada individuo de la
población se le asigna una pareja y entre ellos se establece un torneo: el mejor
genera dos copias y el peor se desecha. La columna (5) indica la pareja
asignada a cada individuo, lo cual se ha realizado aleatoriamente. Existen
muchas variantes de este proceso de selección, aunque este método nos vale
para ilustrar el ejemplo.
Después de realizar el proceso de selección, la población que tenemos es la
mostrada en la columna (2) de la tabla 2. Observa, por ejemplo, que en el
torneo entre el individuo 1 y el 6 de la población inicial, el primero de ellos ha
recibido dos copias, mientras que el segundo cae en el olvido.
Tabla 2.- CRUCE
(1) (2) (3) (4)
1 (0,1,1,0,0) 5 1
2 (0,1,1,0,0) 3 3
3 (1,0,0,1,0) 2 3
4 (1,0,0,1,0) 6 1
5 (1,1,0,1,0) 1 1
6 (1,1,0,1,0) 4 1
Tras realizar la selección, se realiza el cruce. Una manera de hacerlo es
mediante el cruce 1X: se forman parejas entre los individuos aleatoriamente de
forma similar a la selección. Dados dos individuos pareja se establece un punto
de cruce aleatorio, que no es más que un número aleatorio entre 1 y 4 (la
longitud del individuo menos 1). Por ejemplo, en la pareja 2-3 el punto de cruce
es 3, lo que significa que un hijo de la pareja conserva los tres primeros bits del
padre y hereda los dos últimos de la madre, mientras que el otro hijo de la
pareja conserva los tres primeros bits de la madre y hereda los dos últimos del
padre. La población resultante se muestra en la columna (2) de la tabla 3.
Tabla 3.- POBLACION TRAS EL CRUCE
(1) (2) (3) (4)
1 (0,1,0,1,0) 10 100
2 (1,1,1,0,0) 28 784
3 (0,1,1,1,0) 14 196
4 (1,0,0,0,0) 16 256
5 (1,1,0,1,0) 26 676
6 (1,0,0,1,0) 18 324
En la columna (3) tienes el valor de x; en la siguiente tienes el valor de f
correspondiente.
Fíjate en que ahora el valor máximo de f es 784 (para el individuo 2), mientras
que antes de la selección y el cruce era de 676. Además fmed ha subido de
324.3 a 389.3. ¿Qué quiere decir esto? Simplemente que los individuos
después de la selección y el cruce son mejores que antes de estas
transformaciones.
El siguiente paso es volver a realizar la selección y el cruce tomando como
población inicial la de la tabla 3. Esta manera de proceder se repite tantas
veces como número de iteraciones tú fijes. Y ¿cuál es el óptimo? En realidad
un algoritmo genético no te garantiza la obtención del óptimo pero, si está bien
construido, te proporcionará una solución razonablemente buena. Puede que
obtengas el óptimo, pero el algoritmo no te confirma que lo sea. Así que
quédate con la mejor solución de la última iteración. También es buena idea ir
guardando la mejor solución de todas las iteraciones anteriores y al final
quedarte con la mejor solución de las exploradas.
CONSIDERACIONES ADICIONALES
En problemas reales en los que se aplican los algoritmos genéticos, existe la
tendencia a la homogeinización de la población, es decir a que todos los
individuos de la misma sean idénticos. Esto impide que el algoritmo siga
explorando nuevas soluciones, con lo que podemos quedar estancados en un
mínimo local no muy bueno.
Existen técnicas para contrarrestar esta "deriva genética". El mecanismo más
elemental, aunque no siempre suficientemente eficaz, es introducir una
mutación tras la selección y el cruce. Una vez que has realizado la selección y
el cruce escoges un número determinado de bits de la población y los alteras
aleatoriamente. En nuestro ejemplo consiste simplemente en cambiar
algunos(s) bit(s) de 1 a 0 ó de 0 a 1.
BIBLIOGRAFÍA
- DAVIS, L. (1991): Handbook of Genetic Algorithms. Van Nostrand Reinhold.
- DIAZ, A. y GLOVER, F. (1996): Optimización Heurística y Redes
Neuronales en Dirección de Operaciones e Ingeniería. Paraninfo.
- Eddy Alfaro. (2008). ALGORITMOS GENETICOS. 2017, de Eddy Alfaro
Sitio web: [Link]
