Bonjour,

Le code suivant fonctionne correctement avec la matrice en commentaire "distances", cependant, je veux utiliser la matrice du graphe généré G

Code : Sélectionner tout - Visualiser dans une fenêtre à part
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))
Comment je pourrai résoudre ce probleme ?

Merci