08. Agente viajero: algoritmo genético

Publicado por

Con esta nota concluiremos la implementación del algoritmo genético para dar solución al problema del agente viajero. Si eres nuevo en el sitio te recomiendo leer esta serie desde el inicio.

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

Los métodos que faltan por implementar son: el algoritmo genético, también crearemos un método para guardar las coordenadas que se generen como resultado y finalmente construiremos el método principal de nuestro programa.

Con este método implementamos el algoritmo genético para resolver el problema del agente viajero, siguiendo el pseudocodigo explicado previamente en aquí.

def genetico(ciudades, pobtam, pcruza, pmuta, iteraciones ):
	poblacion = generapob(ciudades, pobtam)
	print imprimepob(poblacion)
	mejores = list()
	poblacion.sort()
	print "Poblacion ordenada"
	print imprimepob(poblacion)
	mejor = poblacion[0]
	mejores.append(mejor.copy())
	selec = selecciont(poblacion, pobtam)
	continua = True
	i = 1
	while continua and i < iteraciones:
		print i, ") comenzando iteracion"
		i+=1
		print imprimepob(selec)
		hijos = cruzarpob(selec, pcruza)
		selec.extend(hijos)
		mutarpop(selec, pmuta)
		selec = selecciont(selec, pobtam)
		selec.sort()
		mejores.append(selec[0].copy())
		if(len(mejores)>1):
			aux=list(mejores)
			aux.sort()
			n=aux.count(aux[0])
			if(len(mejores)>=10 and n>len(aux)/2):
				continua= False
	mejores.sort()

	print "Los mejores individuos en todas las iteraciones:"
	print imprimepob(mejores)
	return mejores[0]

Método para guardar coordenadas

Con este método guardamos las coordenadas de las ciudades recorridas, en un archivo. Estas coordenadas serán guardadas de acuerdo al recorrido óptimo encontrado por el algoritmo genético.

def guardaCoordenadas( optimo, rutaArchivo ):
	archivo   = open( rutaArchivo, "w" )
	contenido = ""
	for ciudad in optimo.getciudades():
		contenido += "%f %f\n" % (ciudad.getx(), ciudad.gety())
	archivo.write(contenido)

	archivo.close()

Método principal

En este método podremos modificar los parámetros que le pasamos al algoritmo genético. Los cuales son los siguientes:

  • ciudades es una lista que contiene todas las ciudades obtenidas del archivo puntos-dj38.tsp, con el que iniciamos trabajando en la primera nota.
  • pobtam es el tamaño de la población con la que iniciaremos.
  • pcruza es la probabilidad de cruzamiento.
  • pmuta es la probabilidad de mutación.
  • iteraciones es el número de iteraciones para detener el programa.

def main():
	ciudades = parserCiudades("puntos-dj38.tsp")
	pobtam = 40
	pcruza = 0.9
	pmuta = 0.5
	iteraciones = 200
	optimo = genetico(ciudades, pobtam, pcruza, pmuta, iteraciones )
	print "Mejor solución encontrada:"
	print optimo, "-- Con un costo de", optimo.aptitud(), "unidades."

	guardaCoordenadas( optimo, "recorrido-optimo.data" )



if __name__ == "__main__":
	main()

Con esta implementación ustedes obtendrán un archivo llamado recorrido-optimo.data que contiene las coordenadas ordenadas de acuerdo al recorrido, solo faltaría que realicen la implementación de un método para graficarlos y así puedan visualizarlo.

El código completo lo pueden descargar del siguiente repositorio. Con esta nota concluimos la temporada 1 de la serie algoritmos genéticos. Agradezco su interés y paciencia para la conclusión de esta temporada. ¡Hasta la próxima!

6 comments

  1. Buenos días, gracias por compartir tu conocimiento, te quería consultar porque me muestra este error al querer correr tu proyecto en spyder (anaconda)

    File «C:\Users\selvi\OneDrive\Escritorio\algoritmogenetico-agenteviajero-master\agenteviajero.py», line 101, in distancia
    if distancias.has_key(key):
    AttributeError: ‘dict’ object has no attribute ‘has_key’

    Es extraño porque no hay ni una palabra con el nombre dict

    1. Hola Selvin, gracias por leernos.

      En el código que les ofrecemos como parte de la nota, la variable distancias es de tipo dict. El error se debe a la versión de Python con la que estás trabajando en tu caso debe ser Python3. El ejemplo que les ofrecemos en esta nota utiliza Python2, y en esta version del lenguaje la clase dict implementa el método has_key() para verficar si el diccionario contine un elemento bajo la llave en questión. Este método fue removido desde la versión 3.0 del lenguaje como puedes ver aquí.
      A partir de la versión Python3 en lugar de utilizar has_key() tienes que utilizar el operador in, pasando de esto:

      if distancias.has_key(key):
          # ...
      

      A esto:

      if key in distancias:
          # ...
      
    2. Hola Selvin

      Como menciona Diego en su comentarios, la razón es porque en esta solución estoy utilizando Python 2, ya lo agregué como nota en el cuerpo de la nota, espero que con el aporte de Diego puedas resolver tu problema.

      Gracias por leernos, saludos.

    1. Buen día Alex

      Te comparto el psedocódigo, es tal cula lo explico en esta nota http://codingornot.com/algoritmos-geneticos, espero te sirva.

      Comienza
      –población inicial
      –evaluación de los cromosomas de la población inicial
      –repite
      —-comienza
      ——selección de los cromosomas más aptos en la nueva población
      ——cruzamiento a los cromosomas de la población
      ——mutación a los cromosomas de la población
      ——evaluación a los cromosomas de la población
      —-termina
      –hasta que se cumpla la condición de terminación
      –regresa la mejor solución (la más apta) en la población
      termina

      ¡Saludos!
      Miriam

Responder a Diego Guzmán Cancelar respuesta

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