07. Agente viajero: población inicial

Publicado por

Bienvenido otra vez a esta serie de notas sobre algoritmos genéticos, en esta temporada estamos abordando el problema del agente viajero, si eres nuevo en el sitio te recomiendo leer esta serie desde el inicio.

En esta nota construiremos la población inicial que alimentará a nuestro algoritmo genético.

A continuación te menciono los métodos que utilizaremos para poder generar y manipular la población inicial.

Método para generar la población inicial

En este método se genera la población inicial, seleccionando fin-ini permutaciones aleatorias del espacio de solucuiones.

def generapob( ciudades, pob):
	s     = list()
	perms = permutaciones(ciudades)
	fin   = aleatorio( pob, fact( len(ciudades) ) )
	ini   = fin - pob

	Sigma = list(rango(perms, pob))

	for sigma in Sigma:
		k = list(sigma)
		s.append(cromosoma(k))

	for k in range(2):
		mutarpop(s,1.0)

	return s

Método para imprimir una población

Con este método se genera una representación como cadena de caracteres de un conjunto de soluciones.

def imprimepob( pob ):
	n      = int( log( len(pob),10) + 1 )
	s      = " | %" + str(n) + "d | %s | %f\n"
	edge= " +" + (n + 2) * "-" + "+" + (len(str(pob[0])) + 2) * "-" + "+\n"
	strpob = edge
	for i, p in enumerate(pob):
		strpob += s % (i+1,str(p), p.aptitud() )

	return strpob + edge

Como puedes ver estas funciones son muy sencillas pero indispensables para poder implementar la solución. En la siguiente nota construiremos la implementación del algoritmo genético completo. ¡Hasta entonces!

One comment

  1. En la función «generapob», la variable ‘ini’ no se usa. Por tanto, la variable ‘fin’ tampoco. ¿Cómo sería la selección aleatoria de las permutaciones? ¿Porqué es necesario que sea aleatoria?

Deja una respuesta

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