Algorithme de colonies de fourmis [Résolu]

Bonjour à tous,

Etant débutant en python, j'ai des incompréhensions au niveau d'un programme python sur l'algorithme de colonies de fourmis pour trouver le plus court chemin pour résoudre le problème du voyageur de commerce.

Je vous met d'abord ci-joint le code(il est assez commenté) et je vous mettrai juste un peu plus en bas mes questions.

import random as rn
import numpy as np
from numpy.random import choice as np_choice

class AntColony(object):

    def __init__(self, distances, n_ants, n_best, n_iterations, decay, alpha=1, beta=1):
        """
        Args:
            distances (2D numpy.array): Square matrix of distances. Diagonal is assumed to be np.inf.
            n_ants (int): Number of ants running per iteration
            n_best (int): Number of best ants who deposit pheromone
            n_iterations (int): Number of iterations
            decay (float): Rate it which pheromone decays. The pheromone value is multiplied by decay, so 0.95 will lead to decay, 0.5 to much faster decay.
            alpha (int or float): exponenet on pheromone, higher alpha gives pheromone more weight. Default=1
            beta (int or float): exponent on distance, higher beta give distance more weight. Default=1

        Example:
            ant_colony = AntColony(german_distances, 100, 20, 2000, 0.95, alpha=1, beta=2)          
        """
        self.distances  = distances
        self.pheromone = np.ones(self.distances.shape) / len(distances) # au départ chaque arc est marqué de la même quantité de phéromones
        self.all_inds = range(len(distances)) # on génère une liste des noeuds à visiter
        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) # au départ pas de chemin le plus court, la plus courte longueur pour passer par tous les noeuds est +infini
        for i in range(self.n_iterations):
            all_paths = self.gen_all_paths() # on génère les chemins de chaque fourmi
            self.spread_pheronome(all_paths, self.n_best, shortest_path=shortest_path) # on modifie la matrice phéromone : les fourmis déposent les phéromones là où elles sont passées
            shortest_path = min(all_paths, key=lambda x: x[1]) # on selectionne le plus court chemin : selon la longueur du chemin (le deuxième élément du tuple)
            print (shortest_path)
            if shortest_path[1] < all_time_shortest_path[1]: # si on a trouvé un chemin plus court que all_time_shortest_path, on modifie all_time_shortest_path
                all_time_shortest_path = shortest_path            
            self.pheromone * self.decay            # on fait s'évaporer les phéromones
        return all_time_shortest_path

    def spread_pheronome(self, all_paths, n_best, shortest_path):
        sorted_paths = sorted(all_paths, key=lambda x: x[1]) # on trie les chemins selon leur longueur (distance totale, le deuxième élément du tuple)
        for path, dist in sorted_paths[:n_best]: # on va déposer des phéromones sur les n_best plus courts chemins
            for move in path:
                self.pheromone[move] += 1.0 / self.distances[move] # on ajoute des phéromones sur chacun des arcs où les meilleures fourmis sont passées

    def gen_path_dist(self, path):
        total_dist = 0
        for ele in path: # la distance totale parcourue par la fourmi est la somme des distances parcourues sur chacun des déplacements
            total_dist += self.distances[ele]
        return total_dist

    def gen_all_paths(self):
        all_paths = []
        for i in range(self.n_ants): # pour chacune des n_ants fourmis, on ajoute à la liste all_paths le chamin suivi par la fourmi i
            path = self.gen_path(0) # on génère un chemin qui part du premier noeuds (0) et passe par tous les noeuds
            all_paths.append((path, self.gen_path_dist(path))) # le chemin suivi par une fourmi a pour forme un tuple : le premier élément est la liste des noeuds visités, le deuxième est élément est la distance totale parcourue par la fourmi sur ce chemin
        return all_paths

    def gen_path(self, start):
        path = [] # la liste des déplacements d'un noeud à l'autre, qu'on va remplir au fur et à mesure que la fourmi se déplace
        visited = set() # un set est une liste non-ordonnée, ici on crée un set vide qui correspond à tous les noeuds que la fourmi a déjà visité. Cela sert à éviter que la fourmi visite 2 fois le même noeud
        visited.add(start) # on ajoute le noeud de départ à l'ensemble des noeuds visités
        prev = start # prev est une variable qui stocke, à chaque déplacement de la fourmi, le noeud dont elle part
        for i in range(len(self.distances) - 1): # pour visiter tous les noeuds du graphe une et une seule fois, la fourmi va devoir faire autant de déplacements qu'il y a de noeuds -1
            move = self.pick_move(self.pheromone[prev], self.distances[prev], visited) # on selectionne la destination du déplacement effectué par la fourmi à cette étape de la boucle, qu'on stocke dans la variable move
            path.append((prev, move)) # on ajoute le déplacement de prev à move à la liste path
            prev = move # le noeud move est maintenant le noeud où se trouve la fourmi, donc le point de départ du prochain déplacement
            visited.add(move) # on ajoute le noeud où est la fourmi à l'ensemble des noeuds visités
        path.append((prev, start)) # going back to where we started : le dernier déplacement va du dernier noeud au premier, pour effectuer une boucle
        return path

    def pick_move(self, pheromone, dist, visited): # on prend en argument la ligne de la matrice self.pheromone correspondant au noeud de départ, la ligne de la matrice self.distances correspondant à ce noeud, et l'ensemble des noeuds déjà visités
        pheromone = np.copy(pheromone) # on copie la liste pheromone pour agir dessus dans la fonction, sans modifier la ligne de la matrice self.pheromone qui est un attribut de l'objet
        pheromone[list(visited)] = 0 # pour empêcher la fourmi de choisir un noeud déjà visité, on fait comme si il n'y avait pas de phéromones sur les arcs qui mènent du noeud de départ aux noeuds qui sont dans l'ensemble visited

        row = pheromone ** self.alpha * (( 1.0 / dist) ** self.beta) # row est une liste dont chaque élément est le produit de l'intensité (quantité de phéromones) de l'arc et de sa visibilité (inverse de sa distance), pondérés par alpha et beta

        norm_row = row / row.sum() # norm_row est la liste où on divise les coefficients obtenus précédement par la somme de tous ces coefficients, pour obtenir la probabilité que la fourmi choisisse le noeud considéré
        move = np_choice(self.all_inds, 1, p=norm_row)[0] # choix du noeud selon la loi qu'on a construite
        return move