02. Agente viajero: cromosoma

En esta nota explicaré como construir un cromosoma que represente una solución al problema del agente viajero, para que a partir de él se cree la población inicial. Como lo mencioné en la nota sobre algoritmos genéticos, es indispensable partir de un conjunto de soluciones del problema para poder implementar el algoritmo. 

Nota: recuerda que durante esta temporada la solución será implementada en el lenguaje de programación Python 2.

Un cromosoma es comúnmente construido como una cadena de bits, sin embargo, para este problema en particular conviene más representarlo como una cadena de números enteros.

Si tenemos que recorrer 8 ciudades y a cada ciudad le asignamos un identificador, entonces nuestro cromosoma será una cadena de 8 números enteros. Por lo que para un recorrido con N ciudades tendremos un cadena de N enteros.

Una posible solución al problema se ve de la siguiente forma:

[1,2,3,4,5,6,7,8]

O bien

[1,2,3,4,5,...,N]

Nótese que las ciudades no deben ser repetidas a excepción de la primera que es el punto de partida y punto de llegada, por lo que solo bastará con agregarla al final de la lista.

Para lograr estos cromosomas es necesario generar el archivo de las ciudades con sus coordenadas x y y. Este archivo lo construí a partir de los datos de Djibouti el cual les muestro a continuación.

42102.500000 11003.611100
42373.888900 11108.611100
42885.833300 11133.333300
42712.500000 11155.833300
42933.333300 11183.333300
42853.333300 11297.500000
42929.444400 11310.277800
42983.333300 11416.666700
43000.277800 11423.888900
42057.222200 11438.333300
43252.777800 11461.111100
43187.222200 11485.555600
42855.277800 11503.055600
42106.388900 11511.388900
42841.944400 11522.222200
43136.666700 11569.444400
43150.000000 11583.333300
43148.055600 11595.000000
43150.000000 11600.000000
42686.666700 11690.555600
41836.111100 11715.833300
42814.444400 11751.111100
42651.944400 11770.277800
42884.444400 11785.277800
42673.611100 11822.777800
42660.555600 11846.944400
43290.555600 11963.055600
43026.111100 11973.055600
42195.555600 12058.333300
42477.500000 12149.444400
43355.555600 12286.944400
42433.333300 12300.000000
43156.388900 12355.833300
43189.166700 12363.333300
42711.388900 12372.777800
43334.722200 12386.666700
42895.555600 12421.666700
42973.333300 12645.000000

#Método que crea las ciudades a partir de un archivo
def parserCiudades(archivo):
    fcd = open(archivo,"r")
    lineas = fcd.readlines()
    fcd.close()
    ciudades = [] #Se crea una lista de ciudades
    for i, linea in enumerate (lineas):
        #La función split parte la línea utilizando el espacio como separador
        nums = linea.split(" ")
        #Agrega una ciudad a la lista
        ciudades.append( ciudad(i, float(nums[0]), float(nums[1])) )
    return ciudades

Las ciudades quedarán de la forma (id, x, y).

(1, 42102.500000, 11003.611100)

Después construimos la clase ciudad que permitirá manipular cada una de ellas.

#Clase ciudad cuyas instancias representan las ciudades que forman parte del
#territorio
class ciudad:
    #constructor de la clase
    def __init__(self, id, x, y):
        self.__id = id
        self.__x = x
        self.__y = y

    #representación de una ciudad como cadena de caracteres
    def __str__(self):
        return "%d" % (self.__id)

    #destructor de la clase ciudad
    def __del__(self):
        del self.__id
        del self.__x
        del self.__y

    #devuelve el valor del id de la ciudad
    def getid(self):
        return self.__id

    #devuelve el valor de x de la ciudad
    def getx(self):
        return self.__x

    #devuelve el valor de y de la ciudad
    def gety(self):
        return self.__y

Ahora construimos la clase cromosoma, de momento con la siguiente implementación es suficiente. Conforme avance esta temporada será necesario agregar más métodos a la clase.

#cromosoma clase cuyas instancias representan posibles soluciones al problema
#de optimización
class cromosoma:
    #constructor de la clase
    def __init__(self, ciudades = []):
        self.__ciudades = list(ciudades)

    #copia un cromosoma
    def copy(self):
        return cromosoma( self.getciudades())

    #destructor de la clase cromosoma
    def __del__(self):
        while self.__ciudades:
        ciudad = self.__ciudades.pop()
        del ciudad

    #devuelve la lista de ciudades
    def getciudades(self):
        return self.__ciudades

    #representación como cadena de caracteres del cromosoma
    def __str__(self):
        s  = "["
        for ciudad in self.getciudades() :
            s += " %s," % (str(ciudad))
        s +=" %2s ]" % (self.getciudades()[0])
        #Se agrega al final la primera ciudad de la solución para expresar
        #que es un recorrido circular
        return s

Con la clase ciudad y la clase cromosoma se tiene la base para construir los demás componentes necesarios para obtener las soluciones del problema. No olvides dejar tus sugerencias, dudas y comentarios. ¡Hasta la próxima!