Segunda parte Operadores en algoritmos genéticos

En la obra citada de Goldberg, se menciona que el operador de apareamiento es el encargado de combinar la información de los cromosomas, planteando la búsqueda en otros puntos del espacio de diseño. Los descendientes obtenidos con el operador se componen íntegramente a partir del material genético de sus progenitores. Muchos son los métodos que pueden ser utilizados para escoger la localización, y la longitud del material genético a intercambiar. La recombinación se implementa por medio de un operador que es el encargado de transferir el material genético de una generación a la siguiente. Según Falkenauer, en el libro escrito el año 1999 titulado “Algoritmos evolucionarios: Aplicación de algoritmos genéticos a problemas del mundo real”, este operador confiere a la búsqueda de soluciones mediante algoritmos genéticos su característica más distintiva. A diferencia de otros métodos de optimización, los algoritmos genéticos no solamente exploran el entorno de las buenas soluciones, sino que recombinan sus partes para formar nuevas soluciones. El objetivo de los operadores de recombinación es, partiendo de dos cromosomas padres, generar uno o más cromosomas hijos que hereden características de ambos padres.

Algunas formas de selección del punto de apareamiento son: (1) Apareamiento monopunto. Este operador consiste en separar a los padres en dos partes para formar dos hijos intercambiando las partes de cada padre. Si los cromosomas se componen de “ene” bloques, se elige un número “c” al azar, tal que dicho numero sea mayor a uno y menor o igual que “ene”, y luego se asigna al primer hijo los primeros “c” bloques del primer padre y los últimos “ene menos c” bloques del segundo padre; se procede en forma inversa para formar al segundo hijo. (2) Apareamiento multipunto. En el operador de apareamiento monopunto, el primer y último bloque de uno de los padres no puede pasar juntos al hijo en ningún caso. En el operador de apareamiento multipunto se avanza un paso más, quitando esta restricción. En la cruza multipunto, se eligen “eme” puntos de corte al azar, y las secciones de cada padre se pasan a los hijos en forma alternada. (3) Apareamiento uniforme. Este operador permite el intercambio de los bloques, tal que es independiente del orden que la codificación impuso a cada uno dentro del cromosoma. Para cada posición de los cromosomas hijos, se elige al azar cuál de los dos bloques de los cromosomas padres se copia en cada uno. Esta es una generalización del esquema de cruza multipunto donde la cantidad de puntos de corte “eme” se elige al azar.

El operador de mutación altera arbitrariamente uno o más genes del cromosoma seleccionado, con el propósito de aumentar la diversidad de la población. Todos los genes de los cromosomas existentes están sujetos a la posibilidad de mutar de acuerdo a una probabilidad de mutación. El operador de mutación clásicamente empleado en los algoritmos genéticos con codificación binaria se basa en cambiar el valor del bit seleccionado para mutar por su complementario en el alfabeto binario. Este fenómeno, poco frecuente en la naturaleza, se puede modelar de la siguiente manera: Cuando se produce un gen hijo se examinan sus bits uno a uno, y se genera un coeficiente aleatorio para cada uno. En el caso de que alguno de los coeficientes supere un cierto umbral se altera el alelo de dicho bit. Mediante la modificación de este umbral es posible variar la probabilidad de la mutación. La mutación es un mecanismo muy interesante, con el cual se pueden generar nuevos individuos con características distintas a las de sus progenitores. Los tipos de mutación más conocidos, son: (1) Mutación de bit. Existe una única posibilidad de que se produzca la mutación de algún bit. De producirse, el algoritmo elige aleatoriamente un bit y lo invierte. (2) Mutación multi-bit. Cada bit tiene una probabilidad de mutarse o no, la cual se recalcula para cada una de las generaciones. (3) Mutación de gen. Similar a la mutación de bit, solo que, en vez de cambiar un bit, cambia un gen completo, añadiendo un valor aleatorio, constante, o introduciendo un gen aleatorio nuevo. (4) Mutación multi-gen. Similar al procedimiento multi-bit, solo que, en vez de cambiar un conjunto de bits, cambia un conjunto de genes, añadiendo un valor aleatorio, constante, o introduciendo un nuevo conjunto de genes aleatorios. (5) Mutación de intercambio. Se intercambia el contenido de dos bits o genes de forma aleatoria. (6) Mutación de barajado. Existe una probabilidad de que se produzca una mutación. De producirse, toma dos bits o dos genes aleatoriamente, y baraja de forma aleatoria los bits ó genes comprendidos entre los dos. (7) Creep. Este operador aumenta, o disminuye, en una unidad el valor de un gen; sirviendo para modificar sus valores de forma más controlada.