AE: Operadores de cruzamiento y mutación en estructuras "complejas"

Tengo una duda sobre cómo deberíamos implementar los operadores de cruzamiento y mutación cuando utilizamos estructuras "complejas".

Estoy utilizando dos listas para representar a los individuos, dónde una es una permutación y la otra no. Ambas del mismo largo, y están relacionadas posicionalmente. De hecho, podría verse como una sola lista de pares.

1) Cruzamiento: Al momento de cruzar dos padres, estoy cruzando cada lista independientemente, y después juntando los resultados para obtener los descendientes. Entonces, por ejemplo, si utilizo cruzamiento de dos puntos, los dos puntos para la primer lista serán distintos de los seleccionados para el cruzamiento de la segunda. Me queda la duda de si esto no es demasiado "destructivo" de la información de los padres, ¿debería corregir esto para que los puntos sean los mismos?

2) Mutación: De forma similar, ¿está bien que el parámetro de probabilidad de mutación de entrada se utilice por separado para mutar ambas listas, y luego a partir de ambas mutaciones se cree el individuo mutado que devuelve el operador? ¿o debería mutar el individuo como si esas estructuras fueran indivisibles? ¿O capaz ambas son correctas, y es una decisión que debemos tomar?

Muchas gracias. Saludos,

Benjamín.-

Re: Operadores de cruzamiento y mutación en estructuras "complejas"

de Renzo Massobrio - lunes, 28 de septiembre de 2020, 13:50

Buenas,

1) Creo que tu intuición es correcta y es posible que ese cruzamiento sea "demasiado destructivo". Podés hacer lo que planteas de utilizar los mismo puntos de corte, que sería equivalente a permitir solamente puntos de corte en las posiciones pares si usaras la representación contínua que comentas (de una única lista). En cualquier caso, no se puede saber de antemano si un cruzamiento "es mejor que otro". Para compararlos sería necesario hacer una evaluación experimental del AE con cada cruzamiento y ver los resultados.

2) De nuevo, de antemano no se puede saber qué opción dará mejores resultados, por lo que, como bien decis, es una decisión que deben tomar ustedes. La primer opción que mencionas se puede ver como tener dos operadores de mutación independientes: una "mutación que cambia recorridos" y una "mutación que cambia vehículos" o similar, cada una con su probabilidad de ser aplicada. Creo que esta primera opción que mencionas tiene la ventaja de poder hacer un cambio en uno de los aspectos que codifica la solución sin afectar el otro: por ejemplo cambiar un tipo de vehículo sin afectar la ruta que está codificada en la solución. Esto tal vez resulte útil en algún caso, pero como dije no lo sabemos sin una evaluación experimental.

Cualquier duda nos escriben.

Saludos,
Renzo