1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
|
import networkx as nx
import random as rn
import numpy as np
from numpy.random import choice as np_choice
from collections import OrderedDict
class AntColony(object):
def __init__(self, distances, n_ants, n_best, n_iterations, decay, alpha=1, beta=1):
self.distances = distances
self.pheromone = np.ones(self.distances.shape) / len(distances)
self.all_inds = range(len(distances))
self.n_ants = n_ants
self.n_best = n_best
self.n_iterations = n_iterations
self.decay = decay
self.alpha = alpha
self.beta = beta
def run(self):
shortest_path = None
all_time_shortest_path = ("placeholder", np.inf)
for i in range(self.n_iterations):
all_paths = self.gen_all_paths()
self.spread_pheronome(all_paths, self.n_best, shortest_path=shortest_path)
shortest_path = min(all_paths, key=lambda x: x[1])
if shortest_path[1] < all_time_shortest_path[1]:
all_time_shortest_path = shortest_path
self.pheromone * self.decay
return all_time_shortest_path
def gen_all_paths(self):
all_paths = []
for i in range(self.n_ants):
path = self.gen_path(0)
all_paths.append((path, self.gen_path_dist(path))) # (path - distance)
return all_paths
def gen_path(self, start):
path = []
visited = set()
visited.add(start)
prev = start
for i in range(len(self.distances) - 1):
move = self.pick_move(self.pheromone[prev], self.distances[prev], visited)
path.append((prev, move))
prev = move
visited.add(move)
path.append((prev, start)) # going back to where we started
return path
def pick_move(self, pheromone, dist, visited):
pheromone = np.copy(pheromone)
pheromone[list(visited)] = 0
row = pheromone ** self.alpha * (( 1.0 / dist) ** self.beta)
norm_row = row / row.sum()
move = np_choice(self.all_inds, 1, p=norm_row)[0]
return move
def gen_path_dist(self, path):
total_dist = 0
for ele in path:
total_dist += self.distances[ele]
return total_dist
def spread_pheronome(self, all_paths, n_best, shortest_path):
sorted_paths = sorted(all_paths, key=lambda x: x[1])
for path, dist in sorted_paths[:n_best]:
for move in path:
self.pheromone[move] += 1.0 / self.distances[move]
G= nx.dorogovtsev_goltsev_mendes_graph(n=2)
m = nx.to_numpy_array(G)
#print(m)
for r in range(len(m)):
for c in range(len(m[r])):
if m[r][c] == 0: m[r][c] = float('inf')
distances = repr(m)
"""
distances = np.array([[np.inf, 1, 1, 1, 1, np.inf],
[1, np.inf, 1, 1, np.inf, 1],
[1, 1, np.inf, np.inf, 1, 1],
[1, 1, np.inf, np.inf, np.inf, np.inf],
[1, np.inf, 1, np.inf, np.inf, np.inf],
[np.inf, 1, 1, np.inf, np.inf, np.inf]])
"""
print(distances)
ant_colony = AntColony(distances, 1, 1, 100, 0.95, alpha=1, beta=1)
shortest_path = ant_colony.run()
print ("shortest_path: {}".format(shortest_path)) |
Partager