Hay dos conceptos fascinantes para la gente de computación evolutiva, la exploración y la explotación: Carlos Coello Coello

En la cuarta sesión del curso Una introducción a la computación evolutiva: conceptos básicos y aplicaciones, Carlos Coello Coello, miembro de El Colegio Nacional describió los conceptos básicos de la biología que se utilizan en la computación evolutiva, habló de los componentes fundamentales de un algoritmo genético y se refirió a los algoritmos genéticos paralelos.

El informático mexicano recordó que los componentes fundamentales de un algoritmo genético son: la representación, que tradicionalmente es binaria, 0 y 1; la selección, que suele hacerse con un método probabilístico; los operadores, los principales son cruza y mutación; los parámetros, como el tamaño de población y el porcentaje de mutación, la parte más escabrosa de los algoritmos evolutivos.

Sostuvo que se llama epítasis a la interacción entre los diferentes genes de un cromosoma. Se refiere a la medida en que la contribución de aptitud de un gene depende de los valores de otros genes. En términos matemáticos, decimos que cuando hay epítasis es necesario correlacionarse entre sí, es decir, que el valor de una depende de otra de las variables.

“Epítasis es un concepto fundamental en computación evolutiva, porque si un problema tiene epítasis o su grado de epítasis es muy bajo, podemos hablar de variables independientes, entonces, no necesitamos de un algoritmo evolutivo”. Si la epítasis es elevada, ni siquiera un algoritmo evolutivo resolverá el problema. Existen técnicas especiales para “epítasis” elevadas, que normalmente tienen que hacer una transformación del cromosoma, pero no son muy comunes. Es una condición que puede ocurrir, pero en la práctica es muy poco probable que ocurra. La de poca epítasis también es un problema muy inusual, a menos que sea un problema artificial, es raro que se dé ese caso, enfatizó el colegiado.

Dijo que otro concepto un poco abstracto es el bloque constructor, que se refiere a un grupo pequeño y compacto de genes que han co-evolucionado, de tal forma que su introducción en cualquier cromosoma tiene una alta probabilidad de incrementar su valor de aptitud. Se trata de conjuntos de bits de 0 y 1 que van co-evolucionando junto con la población, de tal manera que son los responsables de que se llegue a una buena solución. También está el concepto de decepción, se le llama así a la condición donde la combinación de buenos bloques constructores lleva a una reducción de aptitud, en vez de un incremento, y fue sugerido para explicar el mal desempeño de los algoritmos genéticos en algunos problemas. La decepción se puede generar parcialmente en un error en la representación, es algo que ya no se estudia actualmente.

Luego están los operadores de reproducción, mecanismos que van a influenciar la forma en la que se pasa información de la población de padres a hijos, no es un proceso biológico, es una simulación y tiene tres amplias categorías: cruza, un operador que forma un nuevo cromosoma combinando partes de cada uno de los padres, “las cruzas más convencionales utilizan dos padres y generan dos hijos, ese es el caso del algoritmo genético”; mutación, es un operador que hace alteraciones aleatorias en los hijos, suele aplicarse en codificación binaria con probabilidades muy bajas; y reordenamiento, son operadores poco comunes que cambian el orden de los alelos de un cromosoma, facilitando la producción de buenos bloques constructores.

La inversión es un ejemplo de operador de ordenamiento en el que se invierte el orden de todos los genes comprendidos entre dos puntos seleccionados al azar en el cromosoma, es otro tipo de mutación en la búsqueda.

De acuerdo con el informático mexicano, en un algoritmo genético, cuando una población no tiene variedad de requisito, la cruza no es útil como operador de búsqueda, porque se perdió diversidad. Ya no hay material diverso para intercambiar. En los algoritmos genéticos, los operadores de reproducción actúan sobre los genotipos, sobre esta cadena binaria, y no sobre los fenotipos, no sobre el valor decodificado, son dos espacios diferentes.

Por eso el algoritmo genético es recomendable cuando el problema tiene variables mixtas, de tipos diferentes, algunas variables tienen números reales, otras enteros y discretas. El genético es el más adecuado para esos problemas, porque lo convierte todo a binario.

El elitismo es otro mecanismo importante utilizado en los algoritmos genéticos para asegurar que los cromosomas de los miembros más aptos de una población se pasen a la siguiente generación sin ser alterados por ningún operador genético. Se requiere para garantizar convergencia matemáticamente. Es importante acotar, que el usar elitismos no necesariamente significa que el algoritmo genético va a encontrar una mejor solución ni tampoco que va a aumentar su probabilidad de llegar a lo óptimo.

Cuando se atraviesa un espacio de búsqueda hay dos conceptos fascinantes para la gente de computación evolutiva que tienen que ver con cuestiones probabilísticas, aseguró Coello Coello. El de exploración, que permite buscar en varias regiones del espacio de búsqueda para encontrar las mejores soluciones, esta acción la realiza la cruza e involucra grandes saltos hacia lo desconocido; y explotación, que se refiere al uso de la información obtenida de los puntos visitados previamente para determinar qué lugares resultan más convenientes de visitar a continuación, esta labor se hace gracias a la mutación e involucra movimientos finos. Dos mecanismos complementarios e importantes.

Por otra parte, se denomina esquema a un patrón de valores de genes de un cromosoma, que puede incluir estados *. Usando un alfabeto binario, los esquemas se forman del alfabeto (0, 1, *), por ejemplo, el cromosoma 0110 es una instancia del esquema *10, donde asterisco significa “no importa”.

Funcionamiento básico de un Algoritmo Genético

En relación al funcionamiento básico de un algoritmo genético, el científico nivel III del Sistema Nacional de Investigadoras e Investigadores, explicó que, primero, se genera aleatoriamente la población inicial, después se calcula la aptitud de cada individuo, se hace una selección probabilísticamente con base en la aptitud, se aplican operadores genéticos de cruza y mutación para generar la siguiente población, y se repiten los pasos del dos al cuatro hasta que cierta condición de paro se satisfaga. “Para el tamaño de población se sugiere un mínimo de 50 y tiene que ser un número par por el tema de las cruzas”.

Para tener una idea de cómo funcionan las técnicas de solución en la computación evolutiva, el colegiado explicó la técnica de selección de la ruleta, “una vez que cada individuo tiene un valor de aptitud, se saca la suma de aptitudes y posteriormente se divide cada aptitud entre la suma total. Imaginen que tienen una ruleta en la que los pedazos grandes corresponden a las zonas de mayor probabilidad, ahí están los individuos más aptos, se da una vuelta aleatoria a la ruleta y donde se detenga ese es el individuo que selecciona, ese es el primer padre”.

Existen también la cruza de un punto, que se refiere al uso de un solo punto de cruza entre dos individuos, en la que cada pareja de cromosoma da origen a dos descendientes para la siguiente generación. La cruza uniforme, que no se utiliza mucho y en la que los dos padres dan un porcentaje de cruza del 50%, es decir la mitad de los genes de cada hijo proviene de cada uno de sus padres, la idea de este algoritmo es ir eligiendo posición por posición, detalló el colegiado.

Algoritmos genéticos paralelos

Según el colegiado, en algoritmos genéticos paralelos existen tres esquemas principales usados desde que se inventaron en los años 80. El primero se llama paralelización global, es el más sencillo y en este caso, sólo hay una población, como en el algoritmo genético poblacional, pero la evaluación de los individuos y los operadores genéticos se paralelizan de forma explícita. Como solo hay una población, la selección considera a todos los individuos y cada uno puede aparearse con cualquier otro, es decir, hay apareamiento aleatorio. Por lo tanto, el comportamiento del algoritmo genético simple, permanece sin cambios.

El segundo, el esquema de islas, es que cada procesador tendrá una población que evolucionará aislada y se puede tener 32 islas. Se puede migrar de una isla a otra y se requieren parámetros adicionales como el porcentaje de migración. Se trata del modelo más popular, porque es una extensión relativamente sencilla del genético convencional.

El tercer esquema es el modelo de difusión o grado fino, en este caso, la población de un algoritmo genético se divide en un gran número de subpoblaciones muy pequeñas. Actualmente casi no se usa y le llegaron a llamar celular, porque las islas debían tener un individuo, una célula. El problema es que el costo de la migración afecta el desempeño del modelo.

Fuente: Agencia ID.