Rapport de Projet [PDF]

Zitiervorschau

RECHERCHE OPÉRATIONNELLE

RAPPORT DE PROJET LA RÉSOLUTION DU PROBLÈME DE VOYAGEUR DE COMMERCE PAR UN ALGORITHME DE COLONIES DE FOURMIS CALIBRÉ ET OPTIMISÉ PAR UN ALGORITHME GÉNÉTIQUE

DATE

30 MARS 2018

ELABORÉ PAR :

SLIMANE RABII BELLAHIRECH FAROUK SUPERVISÉ PAR :

HACHAICHI YASSINE

TABLE DES MATIERES 1. INTRODUCTION :………………………………………………………………………………………………………..2 2. POURQUOI LES FOURMIS :………………………………………………………………………………..…………2 3. PROBLEME DU PLUS COURT CHEMIN ENTRE DEUX POINTS :………………………………..……..2 4. PROBLEME DE VOYAGEUR DE COMMERCE :……………………………………………………..…………3 5. MODELISATION DU COMPORTEMENT DES FOURMIS :……………………………………….………..4 5.1. REGLE DE TRANSITION :………………………………………………………………………..………4 5.2. QUANTITES DE PHEROMONES……………………………………………..……..………..………..5 6. IMPLEMENTATION DE L’ALGORITHME ET TEST AVEC PYTHON 3 :…………………………..….6 6.1. IMPLEMENTATION DE L’ALGORITHME :…………………………………………..…..….…….6 6.2. TEST DE L’ALGORITHME :………………………………………………………..……..……….....….6 7. CHOIX DES PARAMETRES : PERFORMANCE ET OPTIMISATION : ……………..……………..……6 7.1. INFLUENCE DU NBR_FOURMI SUR LE TEMPS DE CALCUL : …………...…………...…. 7 7.2. INFLUENCE DE Q SUR LE TEMPS DE CALCUL : ………………………………...…………..…8 7.3. INFLUENCE DE C SUR LE TEMPS DE CALCUL :…………………………………..…......……..9 7.4. INFLUENCE DE ALPHA SUR LE TEMPS DE CALCUL :……………………………………..10 7.5. INFLUENCE DE BETA SUR LE TEMPS DE CALCUL :………………………………………..11 7.6. INFLUENCE DE STAGNATION_MAX SUR LE TEMPS DE CALCUL :……………..…….11 7.7. INFLUENCE DE CYCLE_MAX SUR LE TEMPS DE CALCUL :………………………….…..12 7.8. INFLUENCE DE ROU SUR LE TEMPS DE CALCUL :…………………………………………13 8. CALIBRATION ET L’OPTIMISATION PAR UN ALGORITHME GENETIQUE :…………..………13 8.1. INTRODUCTION :………………………………………………..………………………………………..13 8.2. IMPLEMENTATION :………………………………………………………………….…………….…..14 8.3. RESUME DES RESULTATS :……………………………………………………………...……….…..14 9. CONCLUSION :…………………………………………………………………………………………………….…….15 1

1. INTRODUCTION : Calibration et optimisation de l'algorithme de colonie de fourmis Ce projet de recherche opérationnelle porte sur la résolution du problème de voyageur de commerce par l’algorithme de colonies de fourmis calibré et optimisé par un algorithme génétique. Pour commencer, le problème de voyageur de commerce est un problème d'optimisation qui, étant donné une liste de ville et des distances entre toutes les paires de villes, détermine un plus court chemin qui visite chaque ville une et une seule fois et qui termine dans la ville de départ. Malgré la simplicité de son énoncé, il s'agit d'un problème NP-complet et du fait de sa NP-complétude, de nombreuses métaheuristique ont été proposées. Alors une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (pour lequel on ne connaît pas de méthode classique plus efficace) comme par exemple l’algorithme de colonies de fourmis qui est un algorithme inspiré du comportement des fourmis.

2. POURQUOI LES FOURMIS : Les fourmis ont un comportement collectif qui les aide à résoudre des problèmes complexes tels que celui de la recherche du plus court chemin. Et pour la résolution de ces problèmes, les fourmis communiquent entre eux en déposant au passage sur le sol une substance odorante appelée phéromone et en la suivant pour se déplacer.

3. PROBLEME DU PLUS COURT CHEMIN ENTRE DEUX POINTS:

Figure 1 : recherche du plus court chemin entre deux points.

2

Au départ le déplacement des fourmis est assez aléatoire mais les premières fourmis qui reviennent au nid avec de la nourriture (en rouge sur la figure 1) sont celles qui ont emprunté un chemin plus court et donc leur chemin sera plus marqué par les phéromones (plus attirant). Et grâce à l’aspect aléatoire dans le déplacement des fourmis le choix du chemin plus court s’améliora au fur du temps et attirera au final toutes les fourmis. Il faut noter que la phéromone est une substance volatile ce qui joue un rôle très important, en effet cela favorise la découverte de nouveaux chemins, qui malgré leur concentration faible en phéromone ont quand même une chance d’être choisi.

4. PROBLEME DE VOYAGEUR DE COMMERCE : A partir d’un ensemble de nœuds, et des distances dij entre toutes les paires de nœuds (i,j), le problème de voyageur de commerce consiste à déterminer un plus court chemin qui visite chaque nœud une et une seule fois et qui termine dans le nœud de départ. C’est-à-dire à partir d’un graphe complet d’ordre n (nombre des nœuds) on va déterminer le cycle hamiltonien minimal en terme de longueur. Pour cela on va utiliser la méthode de colonie de fourmis qui est basé principalement sur les étapes suivantes : 1-Distribuer f fourmis sur les n nœuds. 2-remplir les arrêtes avec une quantité de phéromone initiale. 3-Répéter : 3-1-Chaqu'une des f fourmi effectue un cycle hamiltonien en respectant quelques règles de transition. (Le traitement de cette étape est similaire au traitement du « Problème du plus court chemin entre deux points » sauf que cette fois chaque fourmi, pour effectuer un cycle hamiltonien, elle doit mémoriser les nœuds déjà visité). 3-2-Calculer la longueur du cycle effectué par chaque fourmi. 3-3-Mettre à jour le meilleur cycle trouvé. 3-4-Mettre à jour les quantités de phéromones des arrêtes (déposer de nouvelle quantité et tenir compte de l’évaporation). 3-5-Vider les mémoires des fourmis pour recommencer à partir du nœud initial. Jusqu’à (stagnation) ou (nitération> nitération_max) 3

5. MODELISATION DU COMPORTEMENT DES FOURMIS : 5.1. REGLE DE TRANSITION : Soit une fourmi k placée sur un nœud i. Pour effectuer un seul cycle hamiltonien cette fourmi va visiter tout les nœuds en passant par chaque nœud une seule fois. C’est-àdire elle est amenée à se déplacer d’un nœud à un autre n fois (elle doit prendre n décision).

Figure 2 : Règle de transition.

Pour chaque décision la fourmi choisit une arrête non encore visité tout en préférant les arrêtes courtes et les arrêtes qui contiennent plus de phéromones. La probabilité du passage de la fourmi k placée sur le nœud i vers un nœud j se calcule par la formule suivante.

𝟏 𝒕𝒊𝒋𝜶 . ( )𝜷 𝒅𝒊𝒋 , 𝒌 𝒑𝒊𝒋 = 𝟏 𝜷 𝜶 ∑𝒍𝝐𝑵𝒌 𝒕𝒊𝒍 . ( ) 𝒅𝒊𝒍 𝒊 { 𝟎,

𝒔𝒊 𝒋𝝐𝑵𝒌𝒊

(𝟏)

𝒔𝒊𝒏𝒐𝒏

Avec : -𝒕𝒊𝒋 : Variable qui indique la quantité des phéromones entre le nœud i et le nœud j. 𝟏

- : Variable qui caractérise la visibilité du nœud j à partir du nœud i (𝒅𝒊𝒋 est la distance qui 𝒅𝒊𝒋

sépare le nœud i du nœud j) 4

-𝜶 : Paramètre qui caractérise l’importance de la quantité de phéromones. -𝜷 : Paramètre qui caractérise l’importance du facteur visibilité. -𝑵𝒌𝒊 : L’ensemble des nœuds que la fourmi k, placée sur la ville i, n’a pas encore visité dans le cycle courant.

5.2. QUANTITES DE PHEROMONES Soit Q la quantité de phéromone distribué par une seule fourmi lors d’un seul cycle. Et soit 𝑳 𝒌 la distance parcourue par une fourmi k lors d’un cycle bien déterminé. Lors de son passage entre le nœud i et le nœud j la fourmi k va déposer une quantité 𝑸⁄ de phéromone sur l’arrête ij. Par conséquence, pour calculer la quantité de 𝑳𝒌 phéromone déposée sur cette arrête par toute les fourmis ∆𝒕𝒊𝒋 , on utilise la formule suivante :

∆𝒕𝒊𝒋 = ∑ 𝒌𝝐𝑬

𝑸 𝑳𝒌

(𝟐)

Avec : -E : l’ensemble des fourmis qui ont passé par l’arrête ij.

Une fois les ∆𝒕𝒊𝒋 sont calculés, on passe au calcul des 𝒕𝒊𝒋 au biais de la formule suivante :

𝒕𝒊𝒋 ← 𝝆. 𝒕𝒊𝒋 + ∆𝒕𝒊𝒋 (𝟑) Avec : 𝝆 : Coefficient qui définie la vitesse d’évaporation des phéromones sur les arrêtes.

5

6. IMPLEMENTATION DE L’ALGORITHME ET TEST AVEC PYTHON 3 : (Voir annexe 1) 6.1. IMPLEMENTATION : 6.2. Test: from from from from

numpy.core.multiarray import array main import voy_comm_colo_fourmi random import * matplotlib import pyplot as PLT

#entrer les données du graphe tab_distance=array([[0,5,7,4,11,2,5], [5,0,9,8,14,1,6], [7,9,0,4,7,12,7], [4,8,4,0,7,17,7], [11,14,7,7,0,4,1], [2,1,12,17,4,0,3], [5,6,7,7,1,3,0]]) voy_comm_colo_fourmi(tab_distance=tab_distance, nbr_fourmi=7, c=0.5, alpha=1, beta=1, q=100, rou=0.01, cycle_max=100, stagnation_max=2,nbr_noeud=7);

Résultat de l’exécution : C:\Users\firas\AppData\Local\Programs\Python\Python36-32\python.exe "D:/Rabii/2 année/PRO/test3.py" nbr cycle: 42 nbr stagnation: 2 meilleur circuit trouvé: [1, 5, 6, 4, 2, 3, 0, 1] distance: 25 ******************************************* Process finished with exit code 0

7. Etude de l’influence des paramètres sur la PERFORMANCE ET la convergence de l’algorithme : Après avoir effectué plusieurs tests, ce qu’on a pu constater c’est que le temps de calcul et la convergence même de l’algorithme dépendent fortement du choix des 8 paramètres suivantes (nbr_fourmi, c, alpha, beta, q, rou, cycle_max, stagnation_max). Dans cette partie notre objectif est de visualiser l’influence de chaque paramètre sur le temps de calcul et la convergence de l’algorithme et cela pour 5 graphes de tailles différentes.

6

Remarques : 1-Pour la visualisation on va considérer les variables non étudiées comme constantes selon le tableau ci dessous, en effet D’après « Optimisation par colonies de fourmisCOSTANZO Andrea -LUONG Thé Van -MARILL Guillaume -19 mai 2006 » les résultats suivants donnent en pratique les meilleurs résultats pour un problème à 30 villes : nbr_fourmi nbr_noeud

c 0.5

Alpha 1

beta 1

q 100

rou 0.5

cycle_max 5000

stagnation_max 1

2-En ce qui concerne le temps de calcul, les calculs ont été effectués avec un Pc Portable Asus K555LD i5-4210U 4é Génération Up To 2.7 GHz, Mémoire 8 Go DDR3 1600 MHz.

7.1. INFLUENCE DU NBR_FOURMI SUR LE TEMPS DE CALCUL :

Figure 3 : étude de l’influence du nombre de fourmis sur le temps de calcul et la convergence de l’algorithme 𝑐𝑜𝑒𝑓𝑓𝑐𝑜𝑟𝑟 (𝑞, 𝑡𝑒𝑚𝑝𝑠𝑐𝑎𝑙𝑐𝑢𝑙 ) = 0.79296

7

La figure 3 représente l’influence du nombre de fourmis sur le temps de calcul et la convergence de l’algorithme et ceci pour 5 graphe de différent nombre de nœud. En effet chaque figure englobe 1000 point et Chaque point de cette figure indique le temps de calcul en (ms) et la longueur du meilleur resultat trouvé en exécutant l’algorithme pour un nombre de nœud entre 6 et 10 et pour un nombre aléatoire de fourmis entre 1 et 20. Comme le coefficient de corrélation le confirme, le temps de calcul est proportionnel au nombre de fourmis utilisé et proportionnel au carré du nombre de nœud (on pourra démontrer par une étude de complexité que le nombre d’itération et un O(cycle_max · nbr_noeud2 · nbr_fourmi)).

7.2. INFLUENCE DE Q SUR LE TEMPS DE CALCUL :

Figure 4 : étude de l’influence du facteur q sur le temps de calcul et la convergence de l’algorithme

Remarque : 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑝𝑜𝑖𝑛𝑡 𝑝𝑎𝑟 𝑡𝑦𝑝𝑒 𝑑𝑒 𝑔𝑟𝑎𝑝ℎ𝑒 = 1000 𝑐𝑜𝑒𝑓𝑓𝑐𝑜𝑟𝑟 (𝑞, 𝑡𝑒𝑚𝑝𝑠𝑐𝑎𝑙𝑐𝑢𝑙 ) = 0.00297

D’après la figure ci dessus les deux variables q et temps de calcul sont du moins linéairement indépendantes, d’ailleurs le coefficient de corrélation est assez faible.

8

7.3. INFLUENCE DE C SUR LE TEMPS DE CALCUL :

Figure 5 : étude de l’influence du facteur c sur le temps de calcul et la convergence de l’algorithme

Remarque : 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑝𝑜𝑖𝑛𝑡 𝑝𝑎𝑟 𝑡𝑦𝑝𝑒 𝑑𝑒 𝑔𝑟𝑎𝑝ℎ𝑒 = 250 𝑐𝑜𝑒𝑓𝑓𝑐𝑜𝑟𝑟 (𝑐, 𝑡𝑒𝑚𝑝𝑠𝑐𝑎𝑙𝑐𝑢𝑙 ) = −0.88878

La figure 5 et le coefficient de corrélation confirment la présence d’une relation (fonction constante par palier) entre le temps de calcul et le facteur c dans l’intervalle [0,2]. Au-delà de cet intervalle le coefficient de corrélation est de l’ordre de 0.00128 c’est-àdire pas de relation. Vu que quand on augmente c le temps de calcul diminue, on pense directement à prendre max(c) mais malheureusement quand c augmente, le risque de divergence de l’algorithme augmente aussi.

9

7.4. Influence d’alpha sur le temps de calcul :

Figure 6 : étude de l’influence du facteur rou sur le temps de calcul et la convergence de l’algorithme

Remarque : 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑝𝑜𝑖𝑛𝑡 𝑝𝑎𝑟 𝑡𝑦𝑝𝑒 𝑑𝑒 𝑔𝑟𝑎𝑝ℎ𝑒 = 500 𝑐𝑜𝑒𝑓𝑓𝑐𝑜𝑟𝑟 (𝑎𝑙𝑝ℎ𝑎, 𝑡𝑒𝑚𝑝𝑠𝑐𝑎𝑙𝑐𝑢𝑙 ) = −0.86137

La figure 6 et le coefficient de corrélation confirment la présence d’une relation (fonction constante par palier) entre le temps de calcul et le facteur alpha dans l’intervalle [0,2]. Au-delà de cet intervalle le coefficient de corrélation est de l’ordre de 0.00302 c’est-à-dire pas de relation. Vu que quand on augmente alpha le temps de calcul diminue, on pense directement à prendre max (alpha) mais malheureusement quand alpha augmente, le risque de divergence de l’algorithme augmente aussi.

10

7.5. INFLUENCE DE BETA SUR LE TEMPS DE CALCUL :

Figure 7 : étude de l’influence du facteur beta sur le temps de calcul et la convergence de l’algorithme

Remarque : 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑝𝑜𝑖𝑛𝑡 𝑝𝑎𝑟 𝑡𝑦𝑝𝑒 𝑑𝑒 𝑔𝑟𝑎𝑝ℎ𝑒 = 500 𝑐𝑜𝑒𝑓𝑓𝑐𝑜𝑟𝑟 (𝑏𝑒𝑡𝑎, 𝑡𝑒𝑚𝑝𝑠𝑐𝑎𝑙𝑐𝑢𝑙 ) = 0.06491

D’après la figure ci dessus les deux variables beta et temps de calcul sont du moins linéairement indépendantes, d’ailleurs le coefficient de corrélation est assez faible. 7.6. INFLUENCE DE STAGNATION_MAX SUR LE TEMPS DE CALCUL :

Figure 8 : étude de l’influence de stagnation_max sur le temps de calcul et la convergence de l’algorithme

11

Remarque : 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑝𝑜𝑖𝑛𝑡 𝑝𝑎𝑟 𝑡𝑦𝑝𝑒 𝑑𝑒 𝑔𝑟𝑎𝑝ℎ𝑒 = 1000 𝑐𝑜𝑒𝑓𝑓𝑐𝑜𝑟𝑟 (𝑎𝑙𝑝ℎ𝑎, 𝑡𝑒𝑚𝑝𝑠𝑐𝑎𝑙𝑐𝑢𝑙 ) = 0.46906

D’après la figure ci dessus et le coefficient de corrélation les deux variables stagnation_max et temps de calcul présentent une faible dépendance linaire.

7.7. INFLUENCE DE CYCLE_MAX SUR LE TEMPS DE CALCUL :

Figure 9 : étude de l’influence du facteur cycle_max sur le temps de calcul et la convergence de l’algorithme

Remarque : 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑝𝑜𝑖𝑛𝑡 𝑝𝑎𝑟 𝑡𝑦𝑝𝑒 𝑑𝑒 𝑔𝑟𝑎𝑝ℎ𝑒 = 250 𝑐𝑜𝑒𝑓𝑓𝑐𝑜𝑟𝑟 (𝑎𝑙𝑝ℎ𝑎, 𝑡𝑒𝑚𝑝𝑠𝑐𝑎𝑙𝑐𝑢𝑙 ) = 0.94697

Comme le coefficient de corrélation le confirme, le temps de calcul est proportionnel au facteur cycle_max (nombre d’itération et un O(cycle_max · nbr_noeud2 · nbr_fourmi)).

12

7.8. INFLUENCE DE ROU SUR LE TEMPS DE CALCUL :

Figure 10 : étude de l’influence du facteur rou sur le temps de calcul et la convergence de l’algorithme

Remarque : 𝑛𝑜𝑚𝑏𝑟𝑒 𝑑𝑒 𝑝𝑜𝑖𝑛𝑡 𝑝𝑎𝑟 𝑡𝑦𝑝𝑒 𝑑𝑒 𝑔𝑟𝑎𝑝ℎ𝑒 = 500 𝑐𝑜𝑒𝑓𝑓𝑐𝑜𝑟𝑟 (𝑟𝑜𝑢, 𝑡𝑒𝑚𝑝𝑠𝑐𝑎𝑙𝑐𝑢𝑙 ) = 0.06491

D’après la figure précédente les deux variables rou et temps de calcul sont du moins linéairement indépendantes, d’ailleurs le coefficient de corrélation est assez faible.

8. CALIBRATION ET L’OPTIMISATION PAR UN ALGORITHME GENETIQUE : 8.1. INTRODUCTION :

Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en un temps raisonnable. Les algorithmes génétiques utilisent la notion de sélection naturelle et l'appliquent à une population de solutions potentielles au problème donné.

13

Le déroulement d'un algorithme génétique peut être découpé en cinq parties : 1. 2. 3. 4. 5.

La création de la population initiale L'évaluation des individus La création de nouveaux individus L'insertion des nouveaux individus dans la population Réitération du processus

Figure 11: déroulement d'un algorithme génétique

8.2. IMPLEMENTATION : (Voir annexe 2) 8.3. RESUME DES RESULTATS : La figure ci dessous représente les meilleurs résultats trouvés par l’algorithme génétique. La distribution des points de cette figure nous montre que plus on minimise l’erreur plus le temps de calcul augmente et vice vers ça et ceci est tout à fait attendue. Pour plus de détails des points trouvés voir annexe 3.

14

Figure 12 : représentation des meilleurs résultats trouvés par l’algorithme génétique.

9. CONCLUSION : Le problème du voyageur de commerce se prête très bien à l'utilisation de la métaheuristiques colonies de fourmis. Cette méthode a ses points forts et ses inconvénients. Grâce au partage des données entre les fourmis cette méthode fourni des très bons résultats. Le choix des paramètres reste le point le plus délicat de cette méthode.

15

ANNEXE 1 from random import * from numpy import * import copy #Def la class fourmi class Fourmi(): id=0 trajet=[] def __init__(self,id,nbr_noeud): self.id=id self.trajet=[randint(0, nbr_noeud-1)] def deplacer (self,x): self.trajet.append(x) def __repr__(self): return (str(self.id)+str(self.trajet)) #passage: retourne le noeud suivant de f en utilisant la formule (1) def passage(f,tab_distance,nbr_noeud,tab_pheromone,alpha,beta): noeud_act=f.trajet[-1] liste=copy.copy(tab_distance[noeud_act]) #effacer les noeud deja visités for i in f.trajet: liste[i]=0 #calculer les probabilité s=0 for i in range(0,nbr_noeud): liste = liste.astype(float32) if liste[i]!=0: liste[i]=(tab_pheromone[noeud_act,i]**alpha)*\ ((1/tab_distance[noeud_act,i])**beta) s+=liste[i] for i in range(0,nbr_noeud): if s!=.0: liste[i]=(liste[i])/s liste1=[] #eliminer les proba null for i in range(0,nbr_noeud): if liste[i]!=.0: liste1.append([i,liste[i]]) #linst1:intervalle for i in range(1,len(liste1)): liste1[i][1]+=liste1[i-1][1] #selection du noeud suivant r=uniform(0, 0.99) for i in range(0,len(liste1)): if rdistance(f.trajet,tab_distance): meilleur=copy.copy(f.trajet) #Remise à zero des mémoires des fourmis for f in tab_fourmi: f.trajet=[f.trajet[0]] #verifier le condition d'arret if cycle>=cycle_max or stag>=stagnation_max: break #affichage des resultats print('nbr cycle:',cycle) print('nbr stagnation:',stag) print('meilleur circuit trouvé:',meilleur) print('distance:',distance(meilleur,tab_distance)) print('*******************************************') return()

3

ANNEXE 2 from main import voy_comm_colo_fourmi from random import * import operator from numpy.core.multiarray import array from math import inf def fitness (indiv): tab_distance = array([[0, 5, 7, 4, 11, 2, 5, 6, 3, 2], [5, 0, 9, 8, 13, 1, 6, 2, 7, 6], [7, 9, 0, 4, 7, 12, 7, 4, 2, 1], [4, 8, 4, 0, 7, 17, 7, 8, 4, 1], [11, 14, 7, 7, 0, 4, 1, 5, 10, 8], [2, 1, 12, 17, 4, 0, 3, 5, 3, 5], [5, 6, 7, 7, 1, 3, 0, 3, 4, 6], [6, 2, 4, 8, 5, 5, 3, 0, 8, 1], [3, 7, 2, 4, 10, 3, 4, 8, 0, 2], [2, 6, 1, 1, 8, 5, 6, 1, 2, 0]]) meilleur_sol=23 nbr_fourmi=indiv[0] c=indiv[1] alpha=indiv[2] beta=indiv[3] q=indiv[4] rou=indiv[5] cycle_max=indiv[6] stag_max=indiv[7] nbr_noeud = len(tab_distance) res=voy_comm_colo_fourmi(tab_distance=tab_distance, nbr_fourmi=nbr_fourmi, c=c, alpha=alpha, beta=beta, q=q,rou=rou, cycle_max=cycle_max, stagnation_max=stag_max, nbr_noeud=nbr_noeud) if res[1]>meilleur_sol: return 0.0000001 else: return (1/(res[0]+0.0000001)) def generate_indiv (): # ( nbr_fourmi, c, alpha, beta, q, rou, cycle_max, stagnation_max ) indiv=[randint(10,20),uniform(0.1,2.0),uniform(0.1,2.0),uniform(0.1,2.0),rand int(0,100),uniform(0.1,2.0),randint(1,50),randint(1,10)] return indiv def generateFirstPopulation(sizePopulation): population = [] for i in range(0,sizePopulation): population.append(generate_indiv()) return population def computePerfPopulation(population): populationPerf = {} for i in range(0,len(population)): populationPerf[i] = fitness(population[i]) # for j in range(0,len(populationPerf)): # print(str(populationPerf[j])+":"+str(population[j])) # print(populationPerf) return sorted(populationPerf.items(), key = operator.itemgetter(1), reverse=True)

4

def selectFromPopulation(populationSorted,population, best_sample, lucky_few): nextGeneration = [] for i in range(best_sample): nextGeneration.append(population[populationSorted[i][0]]) for i in range(lucky_few): nextGeneration.append(population[choice(populationSorted)[0]]) shuffle(nextGeneration) return nextGeneration def createChild(individual1, individual2): child = [] for i in range(len(individual1)): if (randint(0,100) < 50): child.append(individual1[i]) else: child.append(individual2[i]) return child def createChildren(breeders, number_of_child): nextPopulation = [] for i in range(int(len(breeders)/2)+1): for j in range(number_of_child): nextPopulation.append(createChild(breeders[i], breeders[len(breeders) -1 -i])) return nextPopulation def mutation (population,mutationRate): for indiv in population: for j in range(0,len(indiv)): if uniform(0,1)