Cruces en los Algoritmos Geneticos

El Algoritmo Genético Canónico descrito anteriormente utiliza el cruce basado en un punto, en el cual los dos individuos seleccionados para jugar el papel de padres, son recombinados por medio de la selección de un punto de corte, para posteriormente intercambiar las secciones que se encuentran a la derecha de dicho punto.

Se han investigado otros operadores de cruce, habitualmente teniendo en cuenta más de un punto de cruce. De Jong investigó el comportamiento del operador de cruce basado en múltiples puntos, concluyendo que el cruce basado en dos puntos, representaba una mejora mientras que añadir más puntos de cruce no beneficiaba el comportamiento del algoritmo. La ventaja de tener más de un punto de cruce radica en que el espacio de búsqueda puede ser explorado más fácilmente, siendo la principal desventaja el hecho de aumentar la probabilidad de ruptura de buenos esquemas.

En el operador de cruce basado en dos puntos, los cromosomas (individuos) pueden contemplarse como un circuito en el cual se efectúa la selección aleatoria de dos puntos, tal y como se indica en la Figura 8.

Figura 8

Desde este punto de vista, el cruce basado en un punto, puede verse como un caso particular del cruce basado en dos puntos, en el cual uno de los puntos de corte se encuentra fijo al comienzo de la ristra que representa al individuo. Véase Figura,9.

En el denominado operador de cruce uniforme (Syswerda) cada gen, en la descendencia se crea copiando el correspondiente gen de uno de los dos padres, escogido de acuerdo ' a una "máscara de cruce" generada aleatoriamente. Cuando existe un l en la "máscara de cruce", el gen es copiado del primer padre, mientras que cuando exista un 0 en la

Figura 9

"máscara de cruce", el gen se copia del segundo padre, tal y como se muestra en la Figura 10. En la literatura, el término operador de cruce uniforme se relaciona con la obtención

Figura 10

de la "máscara de cruce" uniforme, en el sentido de que cualquiera de los elementos del alfabeto tenga asociada la misma probabilidad. Hablando en términos de la teoría de la probabilidad la máscara de cruce está compuesta por una muestra aleatoria de tamaño A extraída de una distribución de probabilidad de Bernouilli de parámetro l/2.

Si tuviésemos en cuenta el valor de la función de adaptación de cada padre en el momento de generar la "máscara de cruce", de tal manera que cuanto mayor sea la función de adaptación de un individuo, más probable sea heredar sus características, podríamos definir, véase Larrañaga y Poza [26], un operador de cruce basado en la función objetivo, en el cual la "máscara de cruce" se interpreta como una muestra aleatoria de tamaño l proveniente de una distribución de Bernouilli de parámetro

Función

donde (I super j sub t) y I(super i sub t) denotan los padres seleccionados para ser cruzados.

El concepto de "máscara de cruce" puede también servir para representar los cruces basados en un punto y basados en múltiples puntos, tal y como se muestra en Figura 11.

Sirag y Weiser, modifican el operador de cruce en el sentido del Simulated Annealing. De esta manera el operador de cruce se modifica definiendo un umbral de energía H. y una temperatura T, las cuales influencian la manera en la que se escogen los bits individuales. Según el operador propuesto el bit (i + 1)-ésimo se tomará del padre opuesto al que se ha tomado el bit i-ésimo, con probabilidad exp( . (tetha sub c)/T), donde T es el parámetro "temperatura" el cual, al igual que en Simulated Annealing, decrecerá lentamente por medio de un programa de enfriamiento. Con altas temperaturas el comportamiento se asemeja al del operador de cruce uniforme, es decir con probabilidad cercana a la unidad los bits se van escogiendo alternativamente de cada padre. Por otra parte cuando el valor

Figura 11

del parámetro temperatura se acerca a cero el hijo "resultante coincide prácticamente con uno de los padres.

Existen otros operadores de cruce específicos para un determinado problema como son, por ejemplo, los definidos para el problema del agente de comercio.

Por otra parte, la idea de que el cruce debería de ser más probable en algunas posiciones ha sido descrita por varios autores (Schaffer y Morishima, Holland, Davis, Levenick).