Diseño de un operador de cruce para el QAP

Diseño de un operador de cruce para el QAP

Algunos aspectos importantes a tener en cuenta son:

• Los hijos deberían heredar algunas características de cada padre. Si éste no es el caso,entonces estamos ante un operador de mutación.

• Se debe diseñar de acuerdo a la representación.

• La recombinación debe producir cromosomas válidos.

• Se utiliza con una probabilidad alta deactuación sobre cada pareja de padres a cruzar, si no actúan los padres son los descendientes del proceso de recombinación de la pareja.


Cruce de mapeamiento parcial (PMX)

Toma una subsecuencia delgenoma del padre y procura preservar el orden absoluto de los fenotipos -es decir, orden y posición en el genoma- del resto del genoma lo más parecido posible de la madre.

• Se elige una subcadenacentral y se establece una correspondencia por posición entre las asignaciones contenidas en ellas

• Cada hijo contiene la subcadena central de uno de los padres y el mayor número posible deasignaciones en las posiciones definidas por el otro padre. Cuando se forma un ciclo, se sigue la correspondencia fijada para incluir una asignación nueva.

Padre1 = (1 2 3 | 4 5 6 7 | 8 9)
Padre2 = (45 3 | 1 8 7 6 | 9 2)
Hijo1 = (* * * | 1 8 7 6 | * *)
Hijo2 = (* * * | 4 5 6 7 | * *)

Correspondencias: (1-4, 8-5, 7-6, 6-7)

Hijo1 = (1-42 3 | 1 8 7 6 | 8-59) = (4 2 3 | 1 8 7 6 | 5 9)
Hijo2 =(4-15-83 | 4 5 6 7 | 9 2) = (1 8 3 | 4 5 6 7 | 9 2)




Cruce de ciclo (CX)

Tomamos el primer gen del genoma del padre, poniéndolo en la primera posición del hijo, y el primer gen del genomade la madre, poniéndolo dentro del genoma del hijo en la posición que ocupe en el genoma del padre. El fenotipo que está en la posición que ocupa el gen del genoma del padre igual al primer gen delgenoma de la madre se va a colocar en la posición que ocupe en el genoma del padre, y así hasta rellenar el genoma del hijo.

• Partiendo de la asignación i del primer padre, CX toma la siguiente...