El algoritmo genético es una técnica de búsqueda basada en la teoría de la evolución de Darwin, que ha cobrado tremenda popularidad alrededor del mundo durante los últimos años.
¿Cómo saber si es posible usar el Algoritmo Genético?
La aplicación más común de los algoritmos genéticos 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:
Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora.
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 preferentemente cuando exista un rango de soluciones relativamente pequeño.
La función de aptitud no es más que la función objetivo de nuestro problema de optimización. El algoritmo genético únicamente maximiza, pero la minimización puede realizarse fácilmente utilizando el recíproco de la función maximizante (debe cuidarse, por supuesto, que el recíproco de la función no genere una división por cero). Una característica que debe tener esta función es que debe ser capaz de "castigar" a las malas soluciones, y de "premiar" a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez.
La codificación más común de las respuestas es a través de cadenas binarias, aunque se han utilizado también números reales y letras. El primero de estos esquemas ha gozado de mucha popularidad debido a que es el que propuso originalmente Holland, y además porque resulta muy sencillo de implementar.
Funcionamiento de un Algoritmo Genético Simple
La operación de un algoritmo genético simple puede ilustrarse con el siguiente segmento de pseudo-código:
Primero, se genera aleatoriamente la población inicial, que estará constituida por un conjunto de cromosomas, o cadenas de caracteres que representan las soluciones posibles del problema. A cada uno de los cromosomas de esta población se le aplicará la función de aptitud a fin de saber qué tan buena es la solución que está codificando.
Sabiendo la aptitud de cada cromosoma, se procede a la selección de los que se cruzarán en la siguiente generación (presumiblemente, se escogerá a los "mejores"). Dos son los métodos de selección más comunes:
1) La Ruleta : Este método es muy simple, y consiste en crear una ruleta en la que cada cromosoma tiene asignada una fracción proporcional a su aptitud. Sin que nos refiramos a una función de aptitud en particular, supongamos que se tiene una población de 5 cromosomas cuyas aptitudes están dadas por los valores mostrados en la Tabla 1.
Tabla 1 : Valores de ejemplo para ilustrar la selección mediante ruleta
Con los porcentajes mostrados en la cuarta columna de la Tabla 1 podemos elaborar la ruleta de la Figura 1. Esta ruleta se gira 5 veces para determinar qué individuos se seleccionarán. Debido a que a los individuos más aptos se les asignó un área mayor de la ruleta, se espera que sean seleccionados más veces que los menos aptos.
Figura 1 : Ruleta que representa los valores de aptitud de la Tabla 1
2) El torneo : La idea de este método es muy simple. Se baraja la población y después se
hace competir a los cromosomas que la integran en grupos de tamaño predefinido (normalmente compiten en parejas) en un torneo del que resultarán ganadores aquéllos que tengan valores de aptitud más altos. Si se efectúa un torneo binario (i.e., competencia por parejas), entonces la población se debe barajar 2 veces. Nótese que esta técnica garantiza la obtención de múltiples copias del mejor individuo entre los progenitores de la siguiente generación (si se efectúa un torneo binario, el mejor individuo será seleccionado 2 veces).
Una vez realizada la selección, se procede a la reproducción sexual o cruza de los individuos seleccionados. En esta etapa, los sobrevivientes intercambiarán material cromosómico y sus descendientes formarán la población de la siguiente generación. Las 2 formas más comunes de reproducción sexual son: uso de un punto único de cruza y uso de 2 puntos de cruza. Cuando se usa un solo punto de cruza, éste se escoge de forma aleatoria sobre la longitud de la cadena que representa el cromosoma, y a partir de él se realiza el intercambio de material de los 2 individuos, tal y como se muestra en la Figura 2.
Cuando se usan 2 puntos de cruza, se procede de manera similar, pero en este caso el intercambio se realiza en la forma mostrada en la Figura 3. Normalmente la cruza se maneja dentro de la implementación del algoritmo genético como un porcentaje que indica con qué frecuencia se efectuará. Esto significa que no todas las parejas de cromosomas se cruzarán, sino que habrán algunas que pasarán intactas a la siguiente generación. De hecho existe una técnica desarrollada hace algunos años en la que el individuo más apto a lo largo de las distintas generaciones no se cruza con nadie, y se mantiene intacto hasta que surge otro individuo mejor que él, que lo desplazará. Dicha técnica es llamada elitismo, y no debe sorprendernos el hecho de que haya sido desarrollada en Alemania.
Figura 2 : Uso de un solo punto de cruza entre 2 individuos. Observe que cada pareja de cromosomas da origen a 2 descendientes para la siguiente generación. El punto de cruza puede ser cualquiera de los 2 extremos de la cadena, en cuyo caso no se realiza la cruza.
Figura 3: Uso de 2 puntos de cruza entre 2 individuos. Note como en este caso se mantienen los genes de los extremos, y se intercambian los del centro. También aquí existe la posibilidad de que uno o ambos puntos de cruza se encuentren en los extremos de la cadena, en cuyo caso se hará una cruza usando un solo punto, o ninguna cruza, según corresponda.
Además de la selección y la cruza, existe otro operador llamado mutación, el cual realiza un cambio a uno de los genes de un cromosoma elegido aleatoriamente. Cuando se usa una representación binaria, el gene seleccionado se sustituye por su complemento (un cero cambia en uno y viceversa). Este operador permite la introducción de nuevo material cromosómico en la población, tal y como sucede con sus equivalentes biológicos.
Al igual que la cruza, la mutación se maneja como un porcentaje que indica con qué frecuencia se efectuará, aunque se distingue de la primera por ocurrir mucho más esporádicamente (el porcentaje de cruza normalmente es de más del 60%, mientras que el de mutación normalmente nunca supera el 5%).
Si supiéramos la respuesta a la que debemos llegar de antemano, entonces detener el algoritmo genético sería algo trivial. Sin embargo, eso casi nunca es posible, por lo que normalmente se usan 2 criterios principales de detención : correr el algoritmo genético durante un número máximo de generaciones o detenerlo cuando la población se haya estabilizado (i.e., cuando todos o la mayoría de los individuos tengan la misma aptitud).
¿Qué Ventajas y Desventajas tienen con respecto a otras técnicas de búsqueda?
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 masivas en paralelo. 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.
Un Ejemplo de Uso
Un grupo de financieros mexicanos ha resuelto invertir 10 millones de pesos en la nueva marca de vino "Carta Nueva".
Así pues, en 4 ciudades de las principales de México se decide iniciar una vigorosa campaña comercial:
México en el centro, Monterrey en el noroeste, Guadalajara en el occidente y Veracruz en el oriente. A esas 4 ciudades van a corresponder las zonas comerciales I, II, III y IV. Un estudio de mercado ha sido realizado en cada una de las zonas citadas y han sido establecidas curvas de ganancias medias en función de las inversiones totales (almacenes, tiendas de venta, representantes, publicidad, etc.) Estos datos se ilustran en la Tabla 2 y en la Figura 5.
Para simplificar los cálculos, supondremos que las asignaciones de créditos o de inversiones deben hacerse por unidades de 1 millón de pesos. La pregunta es: ¿en dónde se deben de asignar los 10 millones de pesos de los que se dispone para que la ganancia total sea máxima?
Representación: Lo primero que necesitamos determinar para poder aplicar el algoritmo genético, es cuál será el esquema a utilizarse para representar las posibles soluciones del problema. En este caso necesitamos 4 bits (24 = 16) para representar cada solución, porque cada una admite 11 valores posibles (de 0 a 10). Como existen 4 valores independientes (uno por cada zona de estudio), se requieren entonces 16 bits (4 x 4) por cada cromosoma. De tal forma, una cadena representativa de un cromosoma será como se muestra en la Figura 4. Es importante hacer notar que se requiere una función de codificación (i.e., que transforme el valor de la inversión a binario) y una de decodificación (i.e., que realice el proceso inverso). Debido a que en este caso los 4 bits utilizados para representar una solución pueden producir más valores de los que se necesitan, se usará una función de ajuste que haga que los resultados producidos siempre se encuentren en el rango válido.
Tabla 2 : Datos obtenidos con la investigación de mercado en cada una de las regiones en estudio.
2) Función de Aptitud: Dado que el objetivo es obtener las inversiones que sumen 10, y que tengan un beneficio máximo, podemos usar la siguiente función de aptitud penalizada:
donde
c1, c2, c3 y c4 son las ganancias por zona, que se calculan de acuerdo a los valores de la Tabla 2, y v es el valor absoluto de la diferencia entre la suma obtenida y 10.
Nótese que cuando no se viole ninguna restricción (i.e., cuando la suma de inversiones sea exactamente
10) la función de aptitud no será "castigada".
Figura 4 : Cadena representativa de un cromosoma de los utilizados en nuestro ejemplo de optimización. Las cadenas 1, 2, 3 y 4 corresponden a las cantidades invertidas en las zonas económicas respectivas.
3) Operadores: Se usará una cruza de 2 puntos, la cual se efectúa de la forma que se indica en la Figura 3. La probabilidad que se dará a la misma será del 80%. En cuanto a la mutación, se le asignará una probabilidad baja, por lo que será del orden del 1%.
El tamaño de población manejado para este ejemplo será de 50 cromosomas, y se correrá el algoritmo genético durante 20 generaciones.
4) Resultados: El resultado obtenido en una corrida típica es de $1.81 (en millones de pesos), correspondiente a los valores de C1=4 millones, C2=3 millones, C3=1 millón y C4=2 millones. Esta es la solución óptima, la cual se obtuvo originalmente mediante programación dinámica.
El tiempo que le tomó al algoritmo genético encontrar este valor fue de sólo 13 segundos.
Ambientes de Programación
En la actualidad existe un gran número de ambientes de programación disponibles en el mercado para experimentar con los algoritmos genéticos. De acuerdo a la taxonomía, pueden distinguirse 3 clases de ambientes de programación:
Sistemas Orientados a las aplicaciones: Son esencialmente "cajas negras" para el usuario, pues ocultan todos los detalles de implementación. Sus usuarios -normalmente neófitos en el área- los utilizan para un cierto rango de aplicaciones diversas, pero no se interesan en conocer la forma en qué éstos operan. Ejemplos de este tipo de sistemas son: Evolver (Axcelis, Inc.) y XpertRule GenAsys (Attar Software).
Sistemas Orientados a los algoritmos: Soportan algoritmos genéticos específicos, y suelen subdividirse en:
Sistemas de uso específico : Contienen un solo algoritmo genético, y se dirigen a una aplicación en particular. Algunos ejemplos son: Escapade (Frank Hoffmeister), GAGA (Jon Crowcroft) y Genesis (John Grefenstette).
Cajas de Herramientas : Proporcionan muchas herramientas de programación, algoritmos y operadores genéticos que pueden aplicarse en una enorme gama de problemas. Normalmente se subdividen en:
Sistemas Educativos : Ayudan a los usuarios novatos a introducirse de forma amigable a los conceptos de los algoritmos genéticos. GA Workbench (Mark Hughes) es un buen ejemplo de este tipo de ambiente.
Sistemas de Propósito General : Proporcionan un conjunto de herramientas para programar cualquier algoritmo genético y desarrollar cualquier aplicación. Tal vez el sistema más conocido de este tipo es Splicer (NASA).
Aplicación de algoritmos genéticos
· Aplicación de técnicas basadas en lógica difusa para la mejora del comportamiento de los algoritmos genéticos: diseño de operadores, control de parámetros,...
· Algoritmos genéticos en problemas de optimización con información imprecisa.
· Aplicación de los algoritmos genéticos al diseño e identificación de sistemas difusos: ajuste y aprendizaje de bases de reglas difusas.
Referencia
http://cursos.itam.mx/akuri/PUBLICA.CNS/2000/Algoritmos%20Gen%E9ticos%20y%20sus%20Aplicaciones.pdf
http://delta.cs.cinvestav.mx/~ccoello/revistas/genetico.pdf.gz
La ciencia de la esteganografia, en el caso general y no centrándonos necesariamente en ocultación de información en sistemas operativos (procesos, etc), ha sabido recoger con el tiempo todas y cada una de las ingeniosas técnicas que han ido surgiendo.
