Algorithme de colonies de fourmis [Résolu]

Signaler
Messages postés
31
Date d'inscription
samedi 21 novembre 2020
Statut
Membre
Dernière intervention
29 novembre 2020
-
Messages postés
13948
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
19 janvier 2021
-
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







Configuration: Windows / Chrome 87.0.4280.66

3 réponses

Messages postés
31
Date d'inscription
samedi 21 novembre 2020
Statut
Membre
Dernière intervention
29 novembre 2020

J'ai de nombreuses questions si vous voulez bien m'aider svp. Je les poserait au fur et à mesure et je vous remercie d'avance.

Déjà je ne comprend pas pourquoi dans la run() on a shortest_path = None dans une fonction (normalement on écrit pas cela que quand on définit une procédure?

Et puis je ne comprend pas non plus dans cette même fonction ce que veut dire all_time_shortest_path = ("placeholder", np.inf)

Après dans la boucle for de la même fonction je suis encore perdu, je ne comprend pas ces lignes dans la boucle, je n'arrive pas à visualiser?

self.spread_pheronome(all_paths, self.n_best, shortest_path=shortest_path)
shortest_path = min(all_paths, key=lambda x: x[1])

En gros j'ai donc du mal avec la fonction run().

Je vous remercie d'avance,

Jerry
Messages postés
13948
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
19 janvier 2021
785
bonjour,
ce programme n'est pas tout-à-fait à la portée des débutants?
comment te retrouves-tu face à ce programme? pourquoi fais-tu cela?
je pense à deux options:
- d'abord te former pour être moins débutant
- exécuter le programme, analyser son comportement, pour le comprendre
Messages postés
31
Date d'inscription
samedi 21 novembre 2020
Statut
Membre
Dernière intervention
29 novembre 2020

Bonjour,

Je me suis retrouvé face à ce programme parce que je dois faire une présentation mathématique et aussi le code python dans le cadre d'une présentation qui sera évaluée. En effet, je suis en école d'ingénieur et je n'avais jamais de python avant et comme on ne peut pas voir en 1 semestre en même ce qu'on a pas vu avant et suivre les algorithmes qui ceux qui sont déjà avancés font, on est évalué ainsi.

Alors cher yg_be, si tu ne peux pas m'aider je l'apprécierai beaucoup mais sinon tu n'est pas obligé d'empêcher une autre personne qui pourrait m'aider de le faire. En effet, ce n'est pas la première fois que vous intervenez sur mes posts toujours sans apporter votre aide mais j'ai l'impression que cela vous gène. N'est ce pas un site d'entraide pour ceux qui le peuvent et qui le font bénévolement?
Jerry
Messages postés
13948
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
19 janvier 2021
785
ne sont-ce pas deux suggestions constructives?
- te former pour être moins débutant
- exécuter le programme, analyser son comportement, pour le comprendre

je n'ai aucune raison ni aucun moyen d'empêcher d'autres de t'aider.
je n'ai pas répondu à tes questions parce que je pense que les réponses ne vont pas t'aider à progresser.
https://www.commentcamarche.net/faq/10925-demander-de-l-aide-pour-vos-exercices-sur-ccm
Messages postés
13948
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
19 janvier 2021
785 >
Messages postés
13948
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
19 janvier 2021

peux-tu donner suite, ou marquer cette discussion comme résolue?
Messages postés
853
Date d'inscription
lundi 23 mars 2020
Statut
Membre
Dernière intervention
17 janvier 2021
96
Bonjour Jerry,

Ok, mais tu ne nous dis toujours pas d'ou sort ce code ...

De plus, ce n'est pas un programme complet mais juste la définition d'une classe