Advertisement
Sax

SHACO - The jokes on you!

Sax
Mar 25th, 2012
348
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.08 KB | None | 0 0
  1. # -*- coding: utf-8 -*-
  2. ## Shaco ##
  3.  
  4. import random
  5.  
  6. def creaMatriz(n, limite_superior, seed):
  7.     """ Crea una matriz de n x n con valores menores a limite_superior """
  8.     random.seed(seed)
  9.     m = []
  10.     for row in range(n):
  11.         cel = []
  12.         m.append(cel)
  13.         for col in range(n):
  14.              cel.append(limite_superior * random.random())
  15.     return m
  16.  
  17. def imprimeMatriz(matriz):
  18.     """ Imprime la matriz dada de manera ORDENADA """
  19.     for fil in range(len(matriz)):
  20.             print str(matriz[fil])
  21.  
  22. def sumarPesosAdyacentes(ciudades, feromonas, usadas, ciudad_actual):
  23.     """ Suma el peso de las ciudades adyacentes """
  24.  
  25.     suma_total = 0.0
  26.  
  27.     for ciudad in range(len(ciudades)):
  28.         if not usadas.has_key(ciudad):
  29.             suma_total =(suma_total + ciudades[ciudad_actual][ciudad] * (1.0 + feromonas[ciudad_actual][ciudad]))
  30.  
  31.     return suma_total
  32.  
  33. def encuentraCiudad(ciudades, feromonas, usadas, ciudad_actual, porcentaje):
  34.     """ Regresa la siguiente ciudad visitada en el recorrido """
  35.  
  36.     suma_total = 0.0
  37.     siguiente = 0
  38.  
  39.     for ciudad in range(len(ciudades)):
  40.         if suma_total >= porcentaje:
  41.             break
  42.         if not usadas.has_key(ciudad):
  43.              suma_total =(suma_total + ciudades[ciudad_actual][ciudad] * (1.0 + feromonas[ciudad_actual][ciudad]))
  44.              siguiente = ciudad
  45.     return siguiente
  46.  
  47. def crearCamino(ciudades, feromonas):
  48.     """ Regresa el camino que recorre una hormiga como una lista """
  49.  
  50.     ciudad_actual = random.randint(0, len(ciudades)-1)
  51.     camino = [ciudad_actual]
  52.     usadas = {ciudad_actual:1}
  53.  
  54.     while len(usadas) < len(ciudades):
  55.         suma_de_pesos = sumarPesosAdyacentes(ciudades, feromonas, usadas, ciudad_actual)
  56.         porcentaje = random.random() * suma_de_pesos
  57.         ciudad_actual = encuentraCiudad(ciudades, feromonas, usadas, ciudad_actual, porcentaje)
  58.         camino.append(ciudad_actual)
  59.         usadas[ciudad_actual] = 1
  60.  
  61.     return camino
  62.  
  63. def caminoAdelantado(camino):
  64.     """ Regresa una copia del camino pero adelantando todo un indice """
  65.     return camino[1:4] + [camino[0]]
  66.    
  67.  
  68. def longitudCamino(ciudades, camino):
  69.     """ Regresa la longitud del camino seguido por la hormiga """
  70.     pares = zip(camino, caminoAdelantado(camino))
  71.     return sum([ciudades[fil][col] for (fil,col) in pares])
  72.  
  73. def actualizarFeromonas(feromonas, camino, boost):
  74.     """ Actualiza las feromonas en la matriz de feromonas """
  75.  
  76.     pares = zip(camino, caminoAdelantado(camino))
  77.     for (fil,col) in pares:
  78.         feromonas[fil][col] = feromonas[fil][col] + boost
  79.  
  80. def evaporarFeromonas(feromonas, hormigas, boost):
  81.     """ Evapora las feromonas en la matriz de feromonas """
  82.  
  83.     decremento = boost / float(hormigas)
  84.     for fil in range(len(feromonas)):
  85.         for col in range(len(feromonas[fil])):
  86.             if feromonas[fil][col] > decremento:
  87.                 feromonas[fil][col] = feromonas[fil][col] - decremento
  88.             else:
  89.                 feromonas[fil][col] = 0.0
  90.  
  91. def mejorCamino(ciudades, seed, hormigas, boost):
  92.     """ Regresa el camino óptimo """
  93.  
  94.     feromonas = creaMatriz(len(ciudades), 0, 0)
  95.     random.seed(seed)
  96.     mejor_camino = []
  97.  
  98.     for i in range(hormigas):
  99.         camino = crearCamino(ciudades, feromonas)
  100.         longitud_camino = longitudCamino(ciudades, camino)
  101.         if i == 0:
  102.             longitud_mejor_camino = longitud_camino
  103.         print "El camino que siguio la hormiga fue: ", camino
  104.         print "Su recorrido fue: ", longitud_camino
  105.         print "----------------------"
  106.         if longitud_camino < longitud_mejor_camino:
  107.            actualizarFeromonas(feromonas, camino, boost)
  108.            longitud_mejor_camino = longitud_camino
  109.            mejor_camino = camino
  110.         evaporarFeromonas(feromonas, hormigas, boost)
  111.     return mejor_camino
  112.  
  113. seed = 2
  114. boost = 1000
  115. hormigas = 30
  116. num_de_ciudades = 6
  117. distancia_max = 100
  118. seed_de_distancias = 1
  119.  
  120. ciudades = creaMatriz(num_de_ciudades, distancia_max, seed_de_distancias)
  121.  
  122. mejor_camino = mejorCamino(ciudades, seed, hormigas, boost)
  123.  
  124. print("El mejor camino fue este: \n")
  125. print(mejor_camino)
  126. print("Distancia recorrida: ", longitudCamino(ciudades, mejor_camino))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement