Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # -*- coding: utf-8 -*-
- ## Shaco ##
- import random
- def creaMatriz(n, limite_superior, seed):
- """ Crea una matriz de n x n con valores menores a limite_superior """
- random.seed(seed)
- m = []
- for row in range(n):
- cel = []
- m.append(cel)
- for col in range(n):
- cel.append(limite_superior * random.random())
- return m
- def imprimeMatriz(matriz):
- """ Imprime la matriz dada de manera ORDENADA """
- for fil in range(len(matriz)):
- print str(matriz[fil])
- def sumarPesosAdyacentes(ciudades, feromonas, usadas, ciudad_actual):
- """ Suma el peso de las ciudades adyacentes """
- suma_total = 0.0
- for ciudad in range(len(ciudades)):
- if not usadas.has_key(ciudad):
- suma_total =(suma_total + ciudades[ciudad_actual][ciudad] * (1.0 + feromonas[ciudad_actual][ciudad]))
- return suma_total
- def encuentraCiudad(ciudades, feromonas, usadas, ciudad_actual, porcentaje):
- """ Regresa la siguiente ciudad visitada en el recorrido """
- suma_total = 0.0
- siguiente = 0
- for ciudad in range(len(ciudades)):
- if suma_total >= porcentaje:
- break
- if not usadas.has_key(ciudad):
- suma_total =(suma_total + ciudades[ciudad_actual][ciudad] * (1.0 + feromonas[ciudad_actual][ciudad]))
- siguiente = ciudad
- return siguiente
- def crearCamino(ciudades, feromonas):
- """ Regresa el camino que recorre una hormiga como una lista """
- ciudad_actual = random.randint(0, len(ciudades)-1)
- camino = [ciudad_actual]
- usadas = {ciudad_actual:1}
- while len(usadas) < len(ciudades):
- suma_de_pesos = sumarPesosAdyacentes(ciudades, feromonas, usadas, ciudad_actual)
- porcentaje = random.random() * suma_de_pesos
- ciudad_actual = encuentraCiudad(ciudades, feromonas, usadas, ciudad_actual, porcentaje)
- camino.append(ciudad_actual)
- usadas[ciudad_actual] = 1
- return camino
- def caminoAdelantado(camino):
- """ Regresa una copia del camino pero adelantando todo un indice """
- return camino[1:4] + [camino[0]]
- def longitudCamino(ciudades, camino):
- """ Regresa la longitud del camino seguido por la hormiga """
- pares = zip(camino, caminoAdelantado(camino))
- return sum([ciudades[fil][col] for (fil,col) in pares])
- def actualizarFeromonas(feromonas, camino, boost):
- """ Actualiza las feromonas en la matriz de feromonas """
- pares = zip(camino, caminoAdelantado(camino))
- for (fil,col) in pares:
- feromonas[fil][col] = feromonas[fil][col] + boost
- def evaporarFeromonas(feromonas, hormigas, boost):
- """ Evapora las feromonas en la matriz de feromonas """
- decremento = boost / float(hormigas)
- for fil in range(len(feromonas)):
- for col in range(len(feromonas[fil])):
- if feromonas[fil][col] > decremento:
- feromonas[fil][col] = feromonas[fil][col] - decremento
- else:
- feromonas[fil][col] = 0.0
- def mejorCamino(ciudades, seed, hormigas, boost):
- """ Regresa el camino óptimo """
- feromonas = creaMatriz(len(ciudades), 0, 0)
- random.seed(seed)
- mejor_camino = []
- for i in range(hormigas):
- camino = crearCamino(ciudades, feromonas)
- longitud_camino = longitudCamino(ciudades, camino)
- if i == 0:
- longitud_mejor_camino = longitud_camino
- print "El camino que siguio la hormiga fue: ", camino
- print "Su recorrido fue: ", longitud_camino
- print "----------------------"
- if longitud_camino < longitud_mejor_camino:
- actualizarFeromonas(feromonas, camino, boost)
- longitud_mejor_camino = longitud_camino
- mejor_camino = camino
- evaporarFeromonas(feromonas, hormigas, boost)
- return mejor_camino
- seed = 2
- boost = 1000
- hormigas = 30
- num_de_ciudades = 6
- distancia_max = 100
- seed_de_distancias = 1
- ciudades = creaMatriz(num_de_ciudades, distancia_max, seed_de_distancias)
- mejor_camino = mejorCamino(ciudades, seed, hormigas, boost)
- print("El mejor camino fue este: \n")
- print(mejor_camino)
- print("Distancia recorrida: ", longitudCamino(ciudades, mejor_camino))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement