fork download
copy 
  1. # -*- coding: utf-8 -*-
  2.  
  3. import random
  4. import math
  5. import matplotlib.pyplot as plt
  6. from time import clock
  7. import multiprocessing as mp
  8.  
  9.  
  10.  
  11. class Ant:
  12.  
  13.     def __init__(self, map_):
  14.         self.map = map_
  15.         self.path = []
  16.         self.path_length = math.inf
  17.  
  18.  
  19.     def run(self):
  20.         self.path = []
  21.         pheromone_map = [self.map.pheromones[row][:] for row in range(len(self.map.pheromones))]
  22.         current_node = random.choice(range(len(self.map.nodes)))
  23.         self.path.append(current_node)
  24.         for row in range(len(pheromone_map)):
  25.             pheromone_map[row][current_node] = 0
  26.         for i in range(len(self.map.nodes) - 1):
  27.             current_node = random.choices(range(len(self.map.nodes)), weights = pheromone_map[self.path[-1]])[0]
  28.             self.path.append(current_node)
  29.             for row in range(len(pheromone_map)):
  30.                 pheromone_map[row][current_node] = 0
  31.         self.path_length = distance([self.map.nodes[i] for i in self.path])
  32.  
  33.  
  34.  
  35.  
  36.     def get_path_length(self):
  37.         return self.path_length
  38.  
  39.  
  40.     def get_path(self):
  41.         return self.path
  42.  
  43.  
  44.  
  45. class TSPMap:
  46.  
  47.     def __init__(self, num_of_ants = 1, size = 10, auto_generate = True, source = "", evaporating_rate = 0):
  48.         self.ants = [Ant(self) for i in range(num_of_ants)]
  49.         if auto_generate:
  50.             self.nodes = TSPMap.generate_nodes(size)
  51.         else:
  52.             self.nodes = self.read_nodes(source)
  53.         self.pheromones = [[1 for i in range(len(self.nodes))] for j in range(len(self.nodes))]
  54.         for i in range(len(self.pheromones)):
  55.             self.pheromones[i][i] = 0
  56.         self.evaporating_rate = evaporating_rate
  57.         self.optimal_path = []
  58.         self.optimal_length = math.inf
  59.         self.optimal_history = []
  60.  
  61.  
  62.     def generate_nodes(size):
  63.         nodes = [(random.uniform(0, size), random.uniform(0, size)) for i in range(size)]
  64.         return nodes
  65.  
  66.  
  67.     def read_nodes(self, source):
  68.         with open(source, 'r') as file:
  69.             lines = file.readlines()
  70.             path = [(float(line.split()[0]), float(line.split()[1])) for line in lines]
  71.             return path
  72.  
  73.  
  74.     def run(self, trials):
  75.         for trial in range(trials):
  76. #            for ant in self.ants:
  77. #                ant.run()
  78.             pool = mp.Pool(processes=4)
  79.             pool.map(Ant.run, self.ants)
  80.             optimal_ant = min(self.ants, key = Ant.get_path_length)
  81.             self.update_pheromones(optimal_ant)
  82.             self.optimal_path = optimal_ant.get_path()
  83.             self.optimal_length = optimal_ant.get_path_length()
  84.             self.optimal_history.append(self.optimal_length)
  85.  
  86.  
  87.  
  88.  
  89.     def update_pheromones(self, optimal_ant):
  90.         self.pheromones = [[self.pheromones[i][j] * (1 - self.evaporating_rate) 
  91.                             for j in range(len(self.pheromones))] for i in range(len(self.pheromones))]
  92.         path = optimal_ant.get_path()
  93.         for i in range(len(path) - 1):
  94.             self.pheromones[path[i]][path[i + 1]] += 1 / optimal_ant.get_path_length()
  95.             self.pheromones[path[i + 1]][path[i]] += 1 / optimal_ant.get_path_length()
  96.         if len(path) > 0 and path[0] != path[-1]:
  97.             self.pheromones[path[0]][path[-1]] += 1 / optimal_ant.get_path_length()
  98.             self.pheromones[path[-1]][path[0]] += 1 / optimal_ant.get_path_length()
  99.  
  100.  
  101.     def get_optimal_history(self):
  102.         return self.optimal_history
  103.  
  104.     def get_optimal_path(self):
  105.         return [self.nodes[i] for i in self.optimal_path]
  106.  
  107.     def get_optimal_distance(self):
  108.         return self.optimal_distance
  109.  
  110.  
  111.  
  112. def distance(path):
  113.     dist = 0
  114.     for i in range(len(path) - 1):
  115.         dist += math.sqrt(math.pow(path[i][0] - path[i + 1][0], 2) + math.pow(path[i][1] - path[i + 1][1], 2))
  116.     dist += math.sqrt(math.pow(path[0][0] - path[-1][0], 2) + math.pow(path[0][1] - path[-1][1], 2))
  117.     return dist
  118.  
  119.  
  120.  
  121. if __name__ == "__main__":
  122.     NUM_OF_ANTS = 10
  123.     SIZE = 20
  124.     NUM_OF_TRIALS = 10
  125.     EVAPORATING_RATE = 0.06
  126.     SOURCE = 'map.txt'
  127.     random.seed(1)
  128.     start = clock()
  129.     map_ = TSPMap(num_of_ants=NUM_OF_ANTS, size=SIZE, evaporating_rate=EVAPORATING_RATE)
  130. #    map_ = TSPMap(num_of_ants=NUM_OF_ANTS, evaporating_rate=EVAPORATING_RATE, auto_generate=False, source=SOURCE)
  131.     random.seed()
  132.     map_.run(NUM_OF_TRIALS)
  133.     end = clock()
  134.     print(f'Total time: {end - start}')
  135.     history = map_.get_optimal_history()
  136.     print(history[-1])
  137.     path = map_.get_optimal_path()
  138.     path.append(path[0])
  139.     X = [path[i][0] for i in range(len(path))]
  140.     Y = [path[i][1] for i in range(len(path))]
  141.  
  142.     plt.figure(1, figsize=(6, 10))
  143.     plt.subplot(211)
  144.     plt.title('Learning curve\n'
  145.               f'Number of ants: {NUM_OF_ANTS}\n'
  146.               f'Number of trials: {NUM_OF_TRIALS}\n'
  147.               f'Evaporating rate: {EVAPORATING_RATE}\n'
  148.               f'Found solution: {history[-1]}\n'
  149.               f'Working time: {end - start}')
  150.     plt.xlabel('trials')
  151.     plt.ylabel('optimal path length')
  152.     plt.plot(history)
  153.     plt.subplot(212)
  154.     plt.title('Optimal path')
  155.     plt.plot(X, Y)
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Traceback (most recent call last):
  File "/usr/lib/python3.5/py_compile.py", line 125, in compile
    _optimize=optimize)
  File "<frozen importlib._bootstrap_external>", line 735, in source_to_code
  File "<frozen importlib._bootstrap>", line 222, in _call_with_frames_removed
  File "./prog.py", line 134
    print(f'Total time: {end - start}')
                                     ^
SyntaxError: invalid syntax

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python3.5/py_compile.py", line 129, in compile
    raise py_exc
py_compile.PyCompileError:   File "./prog.py", line 134
    print(f'Total time: {end - start}')
                                     ^
SyntaxError: invalid syntax
stdout
copy 
Standard output is empty
https://ideone.com/bLo3yZ
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!