LES MÉTHODES APPROCHÉES

POUR L’OPTIMISATION
COMBINATOIRE

SEDDIK ILIAS INTTIC

 MÉTHODES APPROCHÉES
Résoudre un problème d’optimisation combinatoire nécessite l’étude des points suivants:
1. Définir l’ensemble des solutions « X »
2. Exprimer l’ensemble des contraintes du problème « C » afin de définir l’ensemble des
solutions réalisables « S »,
3. Exprimer la fonction objectif « f » à optimiser,
4. Choisir la méthode de résolution à utiliser,

 Les trois premiers points relèvent de la modélisation du problème, le dernier point de sa

résolution.
 MÉTHODES APPROCHÉES
Lorsque les problèmes d’optimisation deviennent complexes ou qu’ils occupent des espaces très
importants, les temps d’exécution de méthodes de résolution exacte deviennent trop importants.
 MÉTHODES APPROCHÉES
La majorité des problèmes d'optimisation combinatoire, sont des problèmes NP-difficiles et donc
ils ne possèdent pas à ce jour un algorithme efficace, i.e. de complexité polynomiale, capable de
trouver la solution optimale en un temps raisonnable.
Ceci a motivé les chercheurs à développer de nombreuses méthodes de résolution en recherche
opérationnelle et en intelligence artificielle:
 La recherche s’est d'abord orientée vers des heuristiques spécifiques aux problèmes,
 Elle s’est progressivement intéressée aux méthodes plus générales, c'est à dire les méta-
heuristiques.
MÉTHODES APPROCHÉES
 LES HEURISTIQUES
Les heuristiques sont des règles empiriques simples basées sur l'expérience, ne fournissant pas
nécessairement une solution optimale.
Généralement, une heuristique est conçue pour un problème particulier, en s'appuyant sur sa
structure propre, mais les approches peuvent contenir des principes plus généraux.
La qualité d’une heuristique dépende de:
 Qualité du résultat : on implémente l'heuristique et on évalue la qualité de ses solutions par
rapport aux solutions optimales (ou aux meilleures solutions connues), soit en termes de
distance, soit en termes de probabilité de réussite.
 Coût de l'heuristique : complexité (temps, espace) de l'heuristique.
 Remise en cause du contexte originel
 Étendue du domaine d'application (domaine d'optimalité et domaine d'admissibilité des
solutions).
 LES HEURISTIQUES
Exemples:
 Heuristiques de Choix de Variables du problème Max-Sat (affectation de valeurs booléennes
pour maximiser un nombre maximale de clauses)
 Certaines méthodes gloutonnes:
– Rendu de monnaie par division successives
– Méthode du plus proche voisin pour problème de TSP
 MÉTAHEURISTIQUES
Le mot Méta-Heuristique est dérivé de la composition de deux mots grecs:
 heuristique: qui vient du verbe heuriskein (ευρισκειν) et qui signifie ‘trouver’
 méta: qui est un suffixe signifiant « au-delà », « dans un niveau supérieur »

Une Méta-heuristique peut être définie comme une méthode algorithmique capable de guider et
d’orienter le processus de recherche dans un espace de solution (souvent très grand) à des régions
riches en solutions optimales dans le but de trouver des solutions, peut-être pas toujours
optimales, en tout cas très proches de l’optimum, en un temps raisonnable.
 MÉTAHEURISTIQUES
Propriétés fondamentales:
1. Les méta-heuristiques sont des stratégies qui permettent de guider la recherche d’une solution
optimale.
2. Le but visé par les méta-heuristiques est d’explorer l’espace de recherche efficacement afin de
déterminer des solutions (presque) optimales.
3. Les techniques qui constituent des algorithmes de type métaheuristique vont de la simple
procédure de recherche locale à des processus d’apprentissage complexes.
4. Les méta-heuristiques sont en général non-déterministes (aucune garantie d’optimalité)
5. Les méta-heuristiques peuvent contenir des mécanismes qui permettent d’éviter d’être bloqué
dans des régions de l’espace de recherche.
6. Les méta-heuristiques peuvent faire appel à des heuristiques qui tiennent compte de la spécificité
du problème traité, mais ces heuristiques sont contrôlées par une stratégie de niveau supérieur.
7. Les méta-heuristiques peuvent faire usage de l’expérience accumulée durant la recherche de
l’optimum, pour mieux guider la suite du processus de recherche.
 MÉTAHEURISTIQUES
Définitions:
 Un mouvement: est une opération élémentaire permettant de passer d’une solution `a une
solution voisine (exemple : changer la valeur d’une variable, échanger deux variables).

 Le voisinage d’une solution est l’ensemble des solutions voisines, c’est `a dire l’ensemble des
solutions accessibles par un mouvement (et un seul).

 Un essai est une succession de mouvements.

 Une recherche locale est une succession d’essais.

 MÉTAHEURISTIQUES
Définitions:
On peut classer les métaheuristiques selon plusieurs critères, mais 2 principales familles apparaissent
en général:
 MÉTHODES DE RECHERCHE LOCALE
Hill climbing:
Entrées :
– nœud initial
– fonction objectif à optimiser (notée F(n) dans les
algorithmes)
– fonction générant des nœuds successeurs (voisins)
Méthode :
– Le nœud courant est initialisé au nœud initial u
– Itérativement, le nœud courant est comparé à ses
successeurs (voisins) immédiats:
• le meilleur voisin n’ ayant la plus grande valeur F(n’) et tel
que F(n’) > F(n) devient le nœud courant
• si un tel voisin n’existe pas, on arrête et on retourne le
nœud courant comme solution.
MÉTHODES DE RECHERCHE LOCALE
 MÉTHODES DE RECHERCHE LOCALE
Hill climbing:
Exemple: Soit la fonction objectif suivante:

Quelle valeur de n trouverait la méthode hill‐climbing si la valeur initiale de n était 6

et que les successeurs (voisins) utilisés étaient n‐1 (seulement si n>1) et n+1
(seulement si n<16)?
 MÉTHODES DE RECHERCHE LOCALE
Hill climbing:
Exemple:

 suite des valeurs de n parcourues: 6 → 7→ 8→ 9→ 10→ 11→ 12

 hill-­‐climbing termine et retourne n=12
 MÉTHODES DE RECHERCHE LOCALE
Hill climbing:
Exemple de dimension plus complexe (N-Queens):
 n : configuration de l’échiquier avec N reines
 F(n): nombre de paires de reines qui s’attaquent
mutuellement directement ou indirectement dans la
configuration n
 On veut le minimiser
 MÉTHODES DE RECHERCHE LOCALE
Hill climbing:
Exemple de dimension plus complexe (N-Queens):
 Un minimum local avec f(n)=1
 MÉTHODES DE RECHERCHE LOCALE
Recuit simulé:
La méthode du recuit simulé (« Simulated Annealing », Kirkpatrick et co 1983) s’inspire
de la thermodynamique d’un système de particules.
 Le recuit est un processus utilisé en métallurgie pour obtenir un alliage sans défaut. A très haute
température, le métal est à l’état liquide et les atomes se déplacent librement.
– On procède à un refroidissement pour revenir à l’état solide.

 Si le refroidissement est rapide (trempe), les atomes se figent dans un état désordonné. L’alliage
obtenu a une structure irrégulière et présente des défauts (énergie élevée).
 Si le refroidissement est lent (recuit), les atomes se réorganisent de façon régulière. L’alliage
obtenu a une structure cristalline sans défaut (énergie minimale).
 MÉTHODES DE RECHERCHE LOCALE
Recuit simulé:
C’est une amélioration de l’algorithme hill-climbing pour minimiser le risque d’être piégé dans des
maxima/minima locaux.
 au lieu de regarder le meilleur voisin immédiat du nœud courant, avec une certaine probabilité on
va regarder un moins bon voisin immédiat » on espère ainsi s’échapper des optima locaux
 au début de la recherche, la probabilité de prendre un moins bon voisin est plus élevée et diminue
graduellement.
 Le nombre d’itérations et la diminution des probabilités sont définis à l’aide d’un schéma
(schedule) de « températures », en ordre décroissant
– ex.: schéma de 100 itérations [ 2-0, 2-1, 2-2, ... , 2-99]
– la meilleure définition du schéma va varier d’un problème à l’autre
 MÉTHODES DE RECHERCHE LOCALE
Recuit simulé:
1. Engendrer une configuration initiale S0 de S : SS0

2. Initialiser la température T en fonction du schéma de refroidissement

3. Répéter
4. Engendrer un voisin aléatoire S` de S
5. Calculer ΔE = f (S`) - f(S)
6. Si Δ E ≤ 0 alors S  S`
7. Sinon S` est la nouvelle solution avec la probabilité P(E, T) = exp (- ΔE/T)
8. Mettre T à jour en fonction du schéma de refroidissement (réduire la température)
9. Jusqu’à la condition d’arrêt
 MÉTHODES DE RECHERCHE LOCALE
Recuit simulé:
Convergence:
 L’acceptation de solutions moins bonnes permet d’explorer l’espace des solutions.
 Le système peut s’extraire d’un minimum local si le nombre d’essais est suffisant.
 La convergence vers un minimum global nécessite :
– une température initiale élevée → pour autoriser l’accès à tous les états
– une décroissance de température lente → pour échapper au minima locaux
– un nombre d’essais élevé
 MÉTHODES DE RECHERCHE LOCALE
Recuit simulé:
Comment définir les voisins ?

Insertion:

Échange:

Permutation:
 MÉTHODES DE RECHERCHE LOCALE
Recuit simulé:
Exécution sur un problème de plus court chemin pour 250 villes fictives (Defi250):
 MÉTHODES DE RECHERCHE LOCALE
Recherche Taboue (Tabou search):
 L’algorithme Simulated annealing minimise le risque d’être piégé dans des optima locaux
– par contre, il n’élimine pas la possibilité d’osciller indéfiniment en revenant à un nœud
antérieurement visité
 Idée: on pourrait enregistrer les nœuds visités on revient à A* et approches similaires
mais c’est impraticable si l’espace d’états est trop grand.

 L’algorithme de recherche taboue enregistre seulement les k derniers nœuds visités :

– l’ensemble tabou est l’ensemble contenant les k nœuds
– le paramètre k est choisi empiriquement
– cela n’élimine pas les oscillations, mais les réduit
– il existe en fait plusieurs autres façon de construire l’ensemble taboue...
 MÉTHODES DE RECHERCHE LOCALE
Recherche Taboue (Tabou search):
 La méthode de recherche avec tabou (« Tabu Search », Glover 1986) est une méthode locale avec
une mémoire des solutions visitées.
 On cherche une amélioration dans un voisinage (à définir) de la solution courante
en excluant les solutions précédentes pour forcer la sortie d’un minimum local.
– La taille de la liste est généralement à peu près de l’ordre de p=10 → mémoire à court terme

 On cherche donc une amélioration dans le voisinage, en excluant les K solutions précédentes
 MÉTHODES DE RECHERCHE LOCALE
Recherche Taboue (Tabou search):
 La liste tabou interdit temporairement le retour à des solutions visitées
 La taille et la durée de la liste Taboue sont à définir parle programmeur.
– Une liste trop grande peut déconnecter la solution courante de la solution optimale
Sur la figure, la solution en vert ne peut être atteinte sans enlever des restrictions  blocage
 MÉTHODES DE RECHERCHE LOCALE
•Inconvénients des recherches locales

 manque de modélisation mathématiques (chaque cas est différent : il faut

adapter la recherche à chaque problème particulier)
 difficiles à paramétrer

 aucune évaluation de la distance à l’optimum (pas une approximation, trouve

au pire un optimum local qui n’a rien à voir avec l’optimum global)
 MÉTHODES ÉVOLUTIVES
Méthodes basées sur les populations:
Les méthodes basées sur des populations de solutions, aussi appelées méthodes évolutives, font
évoluer une population d’individus selon des règles bien précises. Ces méthodes alternent entre des
périodes d’adaptation individuelle et des périodes de coopération durant lesquelles les individus
échangent de l’information.
Une méthode évolutive peut être décrite comme suit.
 Générer une population initiale d’individus ;
 Tant que aucun critère d’arrêt n’est satisfait faire
– Exécuter une procédure de coopération ;
– Exécuter une procédure d’adaptation individuelle ;
 Fin du tant que
 MÉTHODES ÉVOLUTIVES
Méthodes basées sur les populations:

Un algorithme évolutif typique est composé de trois éléments essentiels :

1. une population constituée de plusieurs individus représentant des solutions potentielles
(configurations) du problème donné.
2. un mécanisme d'évaluation de l'adaptation de chaque individu de la population à l'égard de son
environnement extérieur
3. un mécanisme d'évolution composé d'opérateurs permettant d'éliminer certains individus et de
produire de nouveaux individus à partir des individus sélectionnés.
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):

Une population d’individus évolue de génération en génération.

Chaque individu est plus ou moins « performant » selon ses caractéristiques. L’évolution naturelle
favorise les caractéristiques qui rendent un individu performant.
Le renouvellement d’une génération (parents) se déroule en 4 étapes :
1. sélection d’une partie des parents pour la reproduction
2. croisement des parents sélectionnés pour engendrer des enfants
3. mutation (variation) éventuelle d’une partie des enfants
4. sélection entre parents et enfants pour constituer la génération suivante
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):
Une variante possible de l’algorithme:
 Générer une population initiale P0 de p ≥ 2 individus et poser i ← 0 ;
 Tant que aucun critère d’arrêt n’est satisfait faire
– Poser i ← i + 1 et Pi ← ∅;
– Répéter p fois les 2 lignes suivantes
– Créer une enfant E en croisant 2 individus I1 et I2 de Pi−1 ;
– Appliquer une opérateur de mutation à E et rajouter l’enfant ainsi modifié à Pi;
 Fin du tant que
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):
 MÉTHODES ÉVOLUTIVES
Exemple (algorithme génétique):
 On veut trouver le maximum de la fonction :

2  x 2 ( y 1) 2 3 3  x2  y2
f ( x, y )  (1  x) e  (x  x  y ) e
où x et y varient entre 3 et 3.

 La première étape consiste à représenter les variables du problème sous forme de

chromosomes : x et y sont écrit sous forme de deux chaînes binaire concaténées de m bits
chacune (m=8 dans l’exemple) :

1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1

x y
 MÉTHODES ÉVOLUTIVES
Exemple (algorithme génétique):
 Ensuite, on fixe la taille de la population de chromosomes (e.g. N=6) et on génère
une population initiale.
 L’adaptation de chaque chromosome est alors calculée en plusieurs étapes :
1. La chaîne de 16 bits est séparée en deux mots de 8 bits :
1 0 0 0 1 0 1 0 et 0 0 1 1 1 0 1 1
2. Les deux mots sont convertis en décimal :
(10001010) 2  1  2 7  0  2 6  0  2 5  0  2 4  1  2 3  0  2 2  1  21  0  2 0  (138)10
and
(00111011) 2  0  2 7  0  2 6  1  2 5  1  2 4  1  2 3  0  2 2  1  21  1  2 0  (59)10

3. Les résultats sont convertis de l’intervalle [0,255] à [-3,3]

6 6
138 *  3  0.247 59 *  3  1.611
255 255
4. L’adaptation du chromosome est alors donnée par
f (0.247,-1.611)
 MÉTHODES ÉVOLUTIVES
Exemple (algorithme génétique):

 On répète l’étape précédente pour chaque chromosome avant de passer aux

transformations génétiques.
 Pour trouver le maximum de la fonction, on utilisera une probabilité de croisement de 0.7
et une probabilité de mutation de 0.001. Le nombre de générations est fixé à 100
(l’algorithme génétique créera au plus, 100 générations de chromosomes avant de s’arrêter).
 MÉTHODES ÉVOLUTIVES
Initiale 1ère génération

Maximum local Maximum global

 MÉTHODES ÉVOLUTIVES
Maximum local Maximum global
pc = 0.7, pm = 0.001 pc = 0.7, pm = 0.01
0.7 1.8

0.6 1.6

0.5 1.4

0.4 1.2
Fitness

Fitness
0.3 1.0

0.2 0.8

0.1 0.6

Best Best
0 Average 0.4 Average

-0.1 0.2
0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100
Generations Generations

pc=prob. Croisement ; pm=prob. mutation

 MÉTHODES ÉVOLUTIVES

pc = 0.7, pm = 0.001
1.8

1.6

1.4

1.2
Fitness

1.0

0.8

0.6

Best
0.4 Average

0.2
0 2 4 6 8 10 12 14 16 18 20
Generations
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):
Exemple: Minimiser f(x,y)=x2
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):
Exemple: 8-Queens
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):
Exemple: 8-Queens

Fonction d'adaptation : nombre de paires de reines qui ne s' attaquent pas (min=0,max=8×7/2=28)
Probabilité de sélection du premier chromosome : proportionnelle à l'adaptation
24/(24+23+20+11)=31%
23/(24+23+20+11)=29%
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):
Les algorithmes génétiques ont certaines limites, s’ils sont utilisés de façon brute:
 Le temps de calcul long. Les algorithmes génétiques requiert de nombreuses itérations, ainsi que
l’utilisation excessive de la fonction d’évaluation : d’autres métaheuristiques peuvent être plus
intéressante.
 Ils sont complexes à utiliser, des paramètres comme la taille de la population ou le taux de mutation
sont parfois difficiles à déterminer.
 Les résultats sont incertains: malgré un nombre important de génération, il est impossible d’être
assuré que la solution obtenue est la meilleure. On est sûr de s’être approché de la solution optimale,
sans la certitude de l'avoir atteinte.
 Il y a le risque des optimaux locaux qui est résultat d’une convergence prématurée qui écarte les
autres solutions potentielles.
 Ces algorithmes nécessitent une grande allocation mémoire par l’utilisation d’une grande population
et de nombreuses variables lors du processus de génération. L’utilisation du Design Pattern
Flyweight.
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):
Voici une liste d'exemples utilisant les algorithmes génétiques :
 Cryptanalyse : Bruteforce pour obtenir la clef privée sur des clés asymétriques.
 Finance : Prédiction de l'évolution d'une action.
 Résolution des Sudokus : Obtenir la solution à un sudoku.
 Planning : Obtenir le meilleur planning en fonction de dispositions.
 Plan de table : Effectuer la meilleure disposition de table en fonction des affinités de chacun.
 Robotique : Comportement intuitif et apprentissage.
 Data Mining : Création et utilisation de règles pour obtenir de nouvelles informations.
 MÉTHODES ÉVOLUTIVES
Algorithmes génétiques (Holland 1975):
Voici une liste d'exemples utilisant les algorithmes génétiques :
 Cryptanalyse : Bruteforce pour obtenir la clef privée sur des clés asymétriques.
 Finance : Prédiction de l'évolution d'une action.
 Résolution des Sudokus : Obtenir la solution à un sudoku.
 Planning : Obtenir le meilleur planning en fonction de dispositions.
 Plan de table : Effectuer la meilleure disposition de table en fonction des affinités de chacun.
 Robotique : Comportement intuitif et apprentissage.
 Data Mining : Création et utilisation de règles pour obtenir de nouvelles informations.
 MÉTHODES ÉVOLUTIVES
Essaims particuliers
La méthode des essaims particulaires s’inspire du comportement social des animaux (nuée d’oiseaux,
banc de poissons, essaim d’abeilles).
Un essaim est composé d’individus ou particules en mouvement.
Le mouvement de chaque particule est influencé par :
- sa vitesse actuelle → tendance «aventureuse»
- son expérience personnelle → tendance « conservatrice » à revenir à sa meilleure position
- l’expérience sociale → tendance « panurgienne » à suivre un groupe de voisins
 MÉTHODES ÉVOLUTIVES
Essaims particuliers
Lien avec les techniques de calcul évolutionnaires (e.g., algorithmes génétiques, AG)
 Comme un AG, le PSO exploite aussi des populations de solutions pour chercher l’optima.
 PSO ne suit aucun concept de «survie des plus forts», même s’il exploite le concept de fitness.
 PSO n’utilise pas d’opérateurs évolutionnaires comme celles de mutation et de croisement.
 Chaque particule évolue selon son expérience antérieure, et selon ses relations avec les autres
particules de l’essaim.
 MÉTHODES ÉVOLUTIVES
Algorithme Essaims particuliers
• Randomly initialize particle positions and velocities
• While not terminated
– For each particle :
• Evaluate fitness at current position
• If is better than pbest then update pbest and
• If is better than best then update best and
– For each particle
• Update velocity and position using:
 MÉTHODES ÉVOLUTIVES
Algorithme Essaims particuliers
Pour chaque particule :
• : un vecteur donnant sa position
• : le vecteur donnant sa vitesse
• : fonction de fitness de
• : sa meilleure position trouvée jusqu’à maintenant
• : la fitness de
• : la meilleure position trouvée jusqu’ici dans son voisinage
• : la fitness de
• : un vecteur aléatoire distribué uniformément sur [ 0, ϕi ] régénéré à chaque
génération pour chaque particule
 MÉTHODES ÉVOLUTIVES
Colonies de fourmis
La méthode des colonies de fourmis (« Ant Colony », Dorigo et co 1990) est inspirée du comportement
des fourmis à la recherche de nourriture.
Les fourmis déposent sur leur passage des substances volatiles appelées phéromones.
Plus un chemin est concentré en phéromones, plus il est attractif. Ce mode de communication indirecte
par modification de l’environnement est la stigmergie.
 MÉTHODES ÉVOLUTIVES
Colonies de fourmis
• Si l'on considère un problème de voyageur de commerce à villes, chaque fourmi parcourt le graphe
et construit un trajet de longueur . Pour chaque fourmi, le trajet d'une ville à une ville dépend de :
• La liste des déplacements possibles , quand la fourmi est sur la ville ;
• L'inverse de la distance entre les villes , appelée visibilité. Cette information est utilisée pour diriger
les fourmis vers des villes proches et, ainsi, éviter de trop longs déplacements ;
• La quantité de phéromones déposée sur l'arête reliant deux villes , appelée tensité de la piste. Cette
quantité définit l'attractivité d'une piste et est modifiée après le passage d'une fourmi. C'est en
quelque sorte la mémoire du système.
 MÉTHODES ÉVOLUTIVES
Colonies de fourmis
La règle de déplacement est la suivante :

• où et sont deux paramètres contrôlant l'importance relative de l'intensité de la piste et de la

visibilité.
• Après un tour complet, chaque fourmi dépose une quantité de phéromones sur l'ensemble de son
parcours. Cette quantité dépend de la qualité de la solution trouvée et est définie par :
 MÉTHODES ÉVOLUTIVES
Colonies de fourmis
où est le trajet effectué par la fourmi à l'itération est la longueur de et est un paramètre de réglage.
• Enfin, il est nécessaire d'introduire un processus d'évaporation des phéromones. En effet, pour éviter
de rester piégé dans des optima locaux, il est nécessaire qu'une fourmi " oublie» les mauvaises
solutions. La règle de mise à jour est la suivante :

où est le nombre de fourmis et est un paramètre de réglage.

 MÉTHODES ÉVOLUTIVES
Colonies de fourmis
 CONCLUSION
 Les problèmes d’optimisation discrète posent des difficultés différents de ceux rencontrés dans les
problèmes continus.
 Les techniques de résolution exacte permettront de trouver un optimum global en faisant des
explorations systématiques de l’espace de recherche, mais elles font parfois face à l’explosion
combinatoire (espace de solution très importants), et leur temps de résolutions devient beaucoup
trop important.
 Dans ce cas, des méthodes approchées pourront nous donner des solutions de bonne qualité (sans
forcément trouver l’optimum global) dans un temps raisonnable.
 Ces méthodes regroupent les heuristiques, spécialisées dans des problèmes très précis, et les
métaheuristiques qui sont des méthodes modélisables sur de nombreux problèmes.
 Ces métaheuristiques sont nombreuses, et plusieurs logiciels les exploitent, et doivent être
choisies selon le problème à optimiser, La difficulté est le plus souvent de modéliser le problème
pour qu’il s’adapte à celle choisie.
 SUPPORTS COMPLÉMENTAIRES
 Méthodes approchées en optimisation combinatoire
 Hill climbing (Université de Sherbrook)
 Recuit simulé (Université de Sherbrook)
 Démo recuit simulé pour traitement d’image
 Algorithmes génétiques (Université de Sherbrook)
 Toolbox python pour les métaheuristiques
 Formation Coursera complète de l’université de Melbourne (Australie) en optimisation combinatoi
re (En anglais)