05. Agente viajero: cruzamiento

Publicado por

En esta nota construiremos el método que se encargará de realizar el cruzamiento de dos cromosomas. Existen varias técnicas para implementar la cruza, uno de ellos es el cruzamiento por ciclos, este método es el que utilizaré.

Cruzamiento por ciclos

Se tienen que elegir dos cromosomas, que se denominarán padres, ya que de ellos se formarán dos nuevos cromosomas a partir de su combinación, los cromosomas que se generen se denominarán como hijos.

Supongamos que los cromosomas padres son los siguientes:

padre1 = [3 1 2 6 4 5 7 9 8]
padre2 = [4 5 2 1 8 7 6 9 3]

El cruzamiento por ciclos consiste en tomar el primer elemento de cada padre, en este ejemplo son el 3 y 4.

Después se busca el valor obtenido de padre2 4 en padre1 y se toma el valor de esa posición de padre2, en este caso es 8.

De esa manera se obtiene un ciclo formado por: 3-4-8.

Estos nuevos valores se colocan en el primer cromosoma hijo de la siguiente forma:

hijo1 = [3 X X X 4 X X X 8]

A las posiciones vacías se le asigna un valor X.

Después se colocan los valores restantes, utilizando el cromosoma padre2. Sustituyendo las X por los valores de padre2 que correspondan a cada una de las posiciones.

hijo1= [3 5 2 1 4 7 6 9 8]

Para obtener hijo2 se repite el proceso:

padre2 = [4 5 2 1 8 7 6 9 3]
padre1 = [3 1 2 6 4 5 7 9 8]

Pero ahora se toma primero al padre2, y se obtienen los elementos de la primera posición, es decir, 4 y 3.

Después se busca el valor obtenido de padre1 3 en padre2 y se toma el valor de esa posición de padre1, en este caso es 8.

De esta manera se obtiene el ciclo formado por: 4-8-3.

Estos nuevos valores se colocan en el segundo cromosoma hijo de la siguiente forma:

hijo2 = [4 X X X 8 X X X 3]

Se rellenan los demás valores con los valores de padre1 de esas posiciones.

hijo2 = [4 1 2 6 8 5 7 9 3]

Como se puede notar los dos cromosomas hijos son válidos, ya que no repiten ninguno de sus valores.

Método para agregar en la clase cromosoma

#Método que implementa la cruza de dos cromosomas.
#Cruzamiento por ciclos
def cruzar(self, otro):
    p1, p2 = self.getciudades(), otro.getciudades()
    h1, h2 = list(p2), list(p1)
    idx = [0]
    i = 0
    cont = True
    while cont:
        ciudad = p2[i]
        i = p1.index(ciudad)
        idx.append(i)
        cont = not p1[0] is p2[i]

    for i in idx:
        h1[i], h2[i] = h2[i], h1[i]

return cromosoma(h1), cromosoma(h2)

Función para cruzar una población

También es necesario agregar la siguiente función al código que utilizamos en notas anteriores, para la creación de la población de las siguientes generaciones.

#Cruza los individuos de la población para obtener cromosomas nuevos que
#posteriormente se integrarán a la población en la siguiente generación.
def cruzarpob( pob, pcruza ):
    padres = list( pob )
    hijos = list()

    if len(padres) % 2:
        if random() > 0.5:
            padres.pop( aleatorio(0, len(padres)))
    else:
        padres.append( padres[aleatorio(0, len(padres))] )

    while padres:
        a = padres.pop(aleatorio(0,len(padres)))
        b = padres.pop(aleatorio(0,len(padres)))

    if pcruza > random() :
        hijos.extend( a.cruzar(b) )

return hijos

Espero que este contenido haya sido claro, en caso de que tengas dudas puedes expresarlas en los comentarios y con gusto las atenderé. ¡Hasta la próxima!

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *