08. Agente viajero: algoritmo genético

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!