Cours Objectifs du Cours

Algorithmes avancés ■ Présentation de techniques générales, appelées

(Méta-heuristiques) méta-heuristiques pour résoudre des problèmes
d'optimisation combinatoire difficiles

Master BIG DATA & Cloud ■ Application sur des exemples

Computing
Faculté des sciences
Université Ibn Tofail
Kénitra ■ Implémentation en langage C ou Java
Par
H. ETTAZI

2020-2021
2

Contenu du Cours Pré-requis

■ Introduction générale

■ Problèmes d'optimisation combinatoire

■ Généralités, Complexité des algorithmes, Complexité des problèmes ■ Notions de base d’algorithmique et de
■ Introduction aux méta-heuristiques
structures de données
■ Définitions, Domaines d'application, …

■ Méthodes de voisinage ■ Notions de la théorie des graphes

■ Recuit simulé, Recherche tabou, …

■ Méthodes évolutives
■ Programmation en langage C ou Java
■ Algorithmes génétiques, …

■ Approches hybrides

3 4

Introduction générale

1
 Optimisation Combinatoire ? Méta-heuristiques ?
■ Beaucoup de méthodes de résolution développées en recherche opérationnelle et en
intelligence artificielle :
■ De nombreux problèmes d'optimisation : ■ Les méthodes exactes : garantissent l'optimalité
■ Dans des domaines variés : transport, robotique, télécommunications, ■ Les méthodes approchées : donnent une solution de "bonne qualité" en un temps raisonnable
bourse, planification, biologie, reconnaissance d'image, …
■ Les méthodes exactes inapplicables aux applications de taille importante :
■ souvent très difficiles à résoudre ■ Temps de calcul nécessaire pour trouver une solution augmente exponentiellement avec la
taille du problème à résoudre

■ Plusieurs applications réelles peuvent être formulées sous la ■ Les méthodes approchées (ou heuristiques) constituent une alternative très intéressante
forme d'un problème d'optimisation combinatoire pour les problèmes d'optimisation de grande taille

■ On s'intéresse aux heuristiques :

■ L'optimisation combinatoire est l'étude mathématique qui ■ Les heuristiques classiques (de base) :
■ Les méthodes constructives (souvent spécifiques au problème)
conduit à un arrangement, un groupement, une sélection ou un ■ Les méthodes de recherche locale (ou d'amélioration itérative)
classement optimal d'objets discrets (Lawler [1975])
■ Les heuristiques modernes, ou méta-heuristiques (plus générales) :
■ Les méthodes à solution unique
■ Les méthodes à population de solutions

7 8

Problèmes d'optimisation combinatoire ?

■ Un problème d’optimisation combinatoire (POC) est défini à partir :
■ d'un ensemble fini (ou discret) X , et

Problèmes d'optimisation ■

■
d'une application f, qui renvoie le plus souvent une valeur réelle (ou entière).
Il s'agit de déterminer s* ∈X tel que : f(s*) = min {f(s) tel que s ∈ X }

X : ensemble des solutions réalisables, ou admissibles (feasible solutions), de l'espace

combinatoire ■
de recherche Ω (lui-même un ensemble discret).
■ X fini mais compte un très grand nombre d'éléments,
■ X décrit de manière implicite, par une liste de contraintes que doivent satisfaire les solutions
réalisables.
Généralités, Complexité des ■ f : fonction objectif, ou fonction économique (objective function, or cost function).
algorithmes & des problèmes s* : solution optimale (optimal solution) ; une solution réalisable, s* ∈ X, de valeur ■
f(s*) minimum (i.e. il n'existe pas de solution s ∈ X tel que f(s) < f(s*)).

■ Problème consistant à chercher un élément maximum au lieu d'un élément

minimum de même nature, puisque : max{f(s) tq s ∈ X } = -min {-f(s) tq s ∈ X
}

10

Exemple de POCs (1) Exemple de POCs (2)

■ Problème du chemin de coût minimal (min-cost path problem) :
■ On se donne un graphe orienté valué G = (X,U,C), et deux sommets
■ Problème du voyageur de commerce (travelling
distincts s et t de X salesman problem) :
■ consiste à trouver un circuit ou cycle hamiltonien, de
■ X est l'ensemble des sommets, U est l'ensemble des arcs et C est une coût minimal, dans un graphe valué quelconque
application qui associe à chaque arc de U un coût ou un poids (un réel)

■ Il s'agit de chercher un chemin élémentaire (ne passant pas deux fois par ■ modélise un représentant qui doit partir de chez lui en
un même sommet) de coût minimal, allant de s à t minimisant la distance parcourue

■ Problème apparaissant dans les transports, et en sous-problème ■ L'un des problèmes les plus étudiés. Ces applications
de nombreux problèmes de graphes sont nombreuses :
■ transport, industrie, fabrication de cartes électroniques,
…

11 12

2
 Exemple de POCs (3)
■ Problème du sac à dos (knapsack problem) : Introduction à la
■ On dispose de n objets ayant chacun un poids aj et une
valeur cj (j = 1, 2, …, n) complexité des
■ Il s'agit d'effectuer une sélection (déterminer un sous-ensemble algorithmes
decesobjets) dont le poids total soit inférieur ou égal à un
nombre donné et dont la valeur, somme des valeurs des
objets sélectionnés, soit maximum

■ Problème avec de nombreuses applications

13

Motivation Analyse de Complexité Algorithmique

■ Pour un problème donné, il peut exister
■ Consiste à évaluer les ressources nécessaires à l’exécution
plusieurs algorithmes pour le résoudre. Par d’un algorithme
exemple :
■ Problème de tri € algorithmes possibles (tri par ■ Deux ressources critiques :
sélection, tri par insertion, tri à bulles, tri rapide, tri par ■ le temps d’exécution
fusion, …) ■ la place mémoire
■ Problème de recherche € algorithmes possibles
(rechercheséquentielle,recherchedichotomique,…) ■ Le but est de choisir (dans des conditionsderéalisation égales)
l’algorithme, le mieux adapté et le plus efficace (le moins coûteux)
pour résoudre un problème.
■ Il faut donc une analyse de la complexité
des algorithmes ! ■ On s’intéresse à l’évaluation du temps d’exécution d’un
algorithme : la complexité temporelle
15 16

Comment Evaluer ? (1) Comment Evaluer ? (2)

■ De façon empirique (expérimentale) : ■ De façon formelle (théorique) : on compte le
■
■
on programme l’algorithme
on exécute le programme sur des ensembles de données variés
nombre d’opérations caractéristiques de l’algorithme
■ on mesure le temps d’exécution

■ Ceci dépend de plusieurs facteurs :

■ On se base sur un modèle de machine abstraite sur
■ la machine utilisée laquelle l’algorithme sera implémenté (sous formede
■ le langage de programmation programme)
■ le compilateur
■ les données
■ … ■ On prendra comme référence un modèle de machine
à accès aléatoire (RAM), munie d’une mémoire et
■ On veut pouvoir dire :
■ Sur toute machine, quel que soit le langage de programmation,
d’un processeur unique, où les instructions sont
l’algorithme A1 est meilleur que l’algorithme A2 pour les données de exécutées l’une après l’autre, sans opérations
grande taille simultanées

17 18

3
 Notion de Taille de Données Représenter le Temps d’Exécution
■ Le temps d’exécution d’un algorithme doit être ■ Le temps d’exécution (ou complexité
défini comme une fonction de la taille des données algorithmique) désigne le nombre d’opérations
■ Exemples : le nombre d’éléments à trier, le nombre de élémentaires effectuées par un algorithme
chiffres dans l’écriture des nombres à multiplier, la dimension
des matrices à multiplier, …
■ Il s’exprime en fonction de la taille n des données
■ Le temps d’exécution ne pourra pas être exprimé On note : T(n)
en unités de temps « standard » comme les
secondes. L’analyse d’algorithme a pour but
principal de fournir des résultats indépendants de ■ T(n) donne une évaluation du nombre d’opérations
la machine utilisée élémentaires à exécuter pour des données de taille n
19 20

Notion d’Opération Elémentaire Différentes Complexités (1)

■ Une opération est élémentaire lorsque son temps ■ Dans la pratique, le temps d’exécution d’un
d’exécution est constant, c’est-à-dire ne dépend algorithme dépend non seulement de la taille des
pas de la taille des données données, mais aussi de leurs valeurs précises

■ Exemples : ■ Exemple :
■ Les opérations suivantes sont élémentaires : Appel et retour ■ Pour la recherche séquentielled’un élément dans une liste den éléments, le
d’unefonction,Effectuer uneopérationarithmétique, Comparer deux temps d’exécution varie selon que l’élément se trouve en
nombres, etc. première position, ou que l’élément n’est pas présent dans la
■ Le test d’appartenance d’un élément à un ensemble n’est pas liste
une opération élémentaire parce que son temps d’exécution ■ Pour le tri d’une liste, le temps d’exécution varie selon que la
dépend de la taille de l’ensemble liste est déjà triée ou non

21 22

Différentes Complexités (2) Complexité dans le Pire Cas ?

■ Complexité dans le pire cas (Tmax (n)) : temps ■ Donne idée de borne supérieure du temps d’exécution pour une entrée
quelconque
d’exécution maximal d’un algorithme pour des données
de taille n ■ De nombreux algorithmes fonctionnent assez souvent dans le pire cas. Par
exemple, la recherche d’une information dans une base de données

■ Complexité moyenne (Tmoy(n)) : temps moyen ■ Le pire cas est d’importance cruciale pour certaines applications (par exemple,
contrôle aérien, chirurgie, gestion de réseaux)
d’exécution d’un algorithme sur tous les jeux de
données de taille n ■ Le meilleur cas apporte peu d’informations car beaucoup d’algorithmes font
exactement la même chose dans une telle situation

■ Complexité dans le meilleur cas (Tmin(n)) : temps ■ La complexité en moyenne est en général plus difficile à calculer, car il faut
d’exécution minimal d’un algorithme pour des données que soit précisée une distribution de probabilité pour les données de taille n

de taille n
23 24

4
 Règles de Calcul de Complexité Complexité Asymptotique
■ Les opérations élémentaires ont un temps d’exécution constant
■ On s’intéresse à une "estimation asymptotique" (i.e. pour n
■ La complexité d’une séquence d’instructions est la somme des complexités grand) du temps d’exécution des algorithmes
des instructions qui la composent

■ La complexité d’une instruction conditionnelle est égale à la somme de la

■ On évalue l’efficacité d’un algorithme en donnant un "ordre de
complexité du test et du maximum des complexités des deux alternatives grandeur" du nombre d’opérations T(n) qu’il effectue lorsque la
taille n du problème qu’il résout augmente
■ La complexité d’une instruction répétitive est la somme sur toutes les
répétitions, de la somme de la complexité du corps de la boucle et de la ■ On ne calcule ni le temps réel d’exécution sur une machine
complexité de la condition de boucle
précise, ni le nombre exact d’instructions exécutées
■ La complexité d’une fonction est déterminée par celle de son corps :
■ pour une fonction récursive, elle est exprimée comme une équation de ■ Pour exprimer cet ordre de grandeur, on utilise les notations de
récurrence ; Landau. La plus fréquente, la notation O (grand O) introduite
■ pour une fonction itérative, elle se calcule en sachant que l’appel à une par la suite, donne une majoration de l’ordre de grandeur
fonction prend un temps constant.

25 26

Notation O (grand O) Exemples

■ Soient T(n) et f(n), deux fonctions réelles positives du ■ T(n) = (n+1)2 est en O(n2). Pour le démontrer, prendre
paramètre entier n nO= 1 et c = 4

■ On dit que T(n) est en O(f(n)) (en grand O de f(n)) ■ T(n)=3(n3)+2(n2) est en O(n3). Pour le démontrer,
si et seulement si il existe un entier nO et une constante
c > 0 tels que: T(n) ≤ c f(n), pour tout n ≥ nO prendre nO= 0 et c = 5

■ On dit aussi que T(n) est de l’ordre de f(n). Par abus ■ Si T(n) est le temps d’exécution d'un algorithme A, A est
de notation, on écrit : T(n) = O(f(n)) donc O(n3). On pourrait aussi dire que A est O(n4), mais, ce
serait un énoncé plus faible
■ Soit maintenant A un algorithme de temps d’exécution
T(n). On dira que A est de complexité O(f(n)) ■ T(n) = 3n n’est pas en O(2n)

27 28

Illustration du grand O Grandes Classes de Complexité

Grand O Complexité Exemples d’algorithmes

O(1) Constante Renvoidu premier élémentd’une

liste delongueur n
O(log(n)) Logarithmique Recherche dichotomique dans un
tableau trié de taillen
O(n) Linéaire Recherche séquentielle dans un
tableau detaille n
O(n log(n)) n log n Tri rapide, tri par tas d’une liste
delongueur n
O(n 2 ) Quadratique Tris « naïfs » d’une liste de
longueur n
O(n 3 ) Cubique Multiplication dedeux matrices
carrées d’ordre n
O(2n) Exponentielle Tours deHanoi avec n disques
29 30

5
 Ordres de Grandeur (exemples) Quelques Règles de Simplification
1, log n, n, n log n, n2, n3, 2n ■ Si T(n) = O(k f(n)) où k > 0, alors T(n) = O(f(n))
■ Exemple : 2n+10 est O(n), par contre n2 n’est pas O(n)

2n n2 ■ Dans un polynôme, seul le terme de plus haut degré compte

n
■ Exemple : 3(n3)+20(n2)+5 est O(n3)
T(n)
■ Une exponentielle "l'emporte" sur une puissance, et cette dernière
sur un log
■ Exemple : (2n)+(n100) est O(2n) et 100log(n)+n est O(n)
Log n
■ Si T 1 (n) = O(f(n)) et T 2 (n) = O(g(n)) alors
1 T 1 (n)+T 2 (n) = O(Max(f(n),g(n)))
■ Exemple : T1(n) = n et T2(n) = n2 décrivent deux tâches qui s’exécutent l’une
à la suite de l’autre

■ Si T 1 (n) = O(f(n)) et T 2 (n) = O(g(n)) alors T 1 (n).T 2 (n) = O(f(n).g(n))

■ Exemple : une tâche provoque l’exécution d’une autre plusieurs fois dans
n chacune de ses itérations (bouclesimbriquées)

31 32

Exemples (1) Exemples (2)

■ Boucles logarithmiques
■ Boucles simples ■ i=1;
■ for (i=O; i<n; i++) { s; } while (i<=n){
s;
i = 2 * i;
où s est en O(1) }
■ i prend les valeurs 1, 2, 4, …, jusqu’à ce qu’elle dépasse n
■ la complexité en temps est en O(n) ■ il y a 1 + log2n itérations
■ la complexité est en O(log n)

L’indice de la boucle interne dépend de l’indice de la boucle externe

■ Boucles imbriquées ■
■ for (j=1; j<=n; j++)
■ for(i=O; i<n; i++) for (k=1; k<=j; k++)
s;
for (j=O; j<n; j++) { s; } ■ la boucle interne s’exécute : 1, 2, 3, …., n fois. En sommant sur j, pour j allant
de 1 à n, on a : n (n+1)/2
■ la complexité est en O(n2) ■ la complexité est en O(n2)

33 34

Notion d'algorithme efficace Problème facile vs difficile

■ Algorithme polynomial : complexité en O(np), c'est-à-dire
de l'ordre d'un polynôme, pour un certain entier p
■ De manière informelle :
■ Exemple : Multiplication de deux matrices (n x n)

■ Un problème disposant d ’un algorithme

■ Algorithme exponentiel : complexité en O(rn) pour un
polynomial pour le résoudre est un problème
certain réel r facile
■ Exemple : Enumération des parties d'un ensemble de n éléments
■ Un problème pour lequel il n'existe pas, à ce
■ Les algorithmes polynomiaux sont dits "efficaces" jour, d'algorithme efficace qui puisse le
résoudre est un problème difficile

35 36

6
 Evolution du temps d'exécution en Taille maximale des problèmes
fonction de la complexité résolubles en une heure avec divers
Complexité
Taille de n types d'ordinateurs et de complexités
temporelle
10 20 30 40 50 60

n [Link] [Link] O.OOOO3s O.OOOO4s O.OOOO5 O.OOOO6s Complexité Avec un ordinateur Avec un ordinateur Avec un ordinateur
actuel 100 fois plus rapide 1000 fois plus rapide
2s s
n2 [Link] O.OOO4 O.OOO9s O.OOl6s O.OO25s O.OO36s n N1 100 N1 1000 N1
s
n2 N2 10 N2 31.6 N2
n3 [Link] O.OO8s O.O27s O.O64s O.l25s O.2l6s
n3 N3 4.64 N3 10 N3
n5 ls 3.2s 24.3s l.7mn 5.2mn l3.O mn
n5 N4 2.5 N4 3.98 N4
2n 35.7
[Link] [Link] l7.9mn l2.7jours années 366 Siècles
2n N5 N5+6.64 N5+9.97
n 6.5 3855 2xlO8 l.3xlOl3
3 O.O59s 58mn Siècles
années siècles siècles 3n N6 N6+4.19 N6+6.29

On suppose une machine exécutant 106 opérations par seconde

37 38

Problème de décision
Introduction à la ■ Problème qui consiste à apporter une réponse "oui" ou "non"
à une question.

Complexité des ■ A chaque problème d’optimisation combinatoire, on peut

associer un problème de décision :
problèmes ■ Soit un problème d’optimisation combinatoire :
Trouver s*CS tel que f(s*) = min {f(s) | s C S}
■ Soit k un nombre, on définit le problème de décision associé :
Existe-t-il s*C S tel que f(s*) S k ?

■ Exemple : Le Problème de décision associé au problème du

voyageur de commerce consiste chercher une solution de
valeur au plus égale à une valeur k donnée
40

Classes de complexité Classe P

■ La théorie de la complexité permet de classer les problèmes de ■ Regroupe l'ensemble des problèmes de décision
décision en fonction de la complexité des algorithmes qui
existent pour les résoudre
pouvant être résolus en un temps polynomial

■ On distingue les problèmes décidables pour lesquels il existe au ■ Classe des problèmes dits "faciles"
moins un algorithme pour les résoudre, de ceux indécidables

■ Exemple :
■ Il existe plusieurs classes de complexité, mais les plus connues
sont : ■ Le problème de décision associé au problème du plus court
■ Classe P (Polynomial time) chemin ;
■ Classe N P (Non deterministic Polynomial time) ■ On dispose de plusieurs algorithmes polynomiaux pour
■ Classe NP-complet résoudre ce problème (algorithmes de Bellman, de Dijkstra,
…)

41 42

7
 Classe N P Exemple de problème de N P
Problème de décision associé au voyageur de commerce
■ Classe des problèmes de décision pour lesquels la
réponse Oui peut être décidée par un algorithme non- Un voyageur de commerce désire faire sa tournée, existe-t-il une
déterministe en un temps polynomial tournée de moins de 50 km ?

10
■ Le terme non déterministe désigne un pouvoir qu’on a
b
a-b-e-c-d-a 50km
incorpore à un algorithme pour qu’il puisse deviner la 10
bonne solution
20 40 10
10 d
■ Classe des problèmes de décision pour lesquels une 10
proposition de solution Oui est vérifiable par un 10
algorithme déterministe en temps polynomial c
12
10

■ Conjecture : P ≠ NP e

MasterIA : Méta-heuristiques (2010-2011) 43 44

Classe NP-complet Résolution des problèmes

■ Un problème P1 se réduit polynomialement en P2 s'il existe un algorithme
NP-difficiles
polynomial A transformant toute donnée pour P1 en une pour P2, en conservant la
réponse Oui ou Non. ■ Méthodes exactes :
■ Algorithmes exponentiels qui permettent d’atteindre l’optimum
■ Exemple : Le problème de recherche du circuit hamiltonien dans un graphe G(X,U) peut se ■ Seuls des problèmes de taille réduite traités
réduire polynomialement en le problème de décision associé au voyageur de commerce ■ Exemples : branch & bound, programmation dynamique, …

■ La classe NP-complet contient les problèmes de NP tels que n’importe quel problème ■ Méthodes approchées :
de NP leur est polynomialement réductible ■ Algorithmes polynomiaux qui permettent de donner une solution approchée au problème
■ Il existe des algorithmes rapides qui n'offrent aucune garantie théorique dans le cas
■ Aucun problème NP-complet n’a pu être résolu à l’aide d’un algorithme efficace général, mais qui sont réputés, sur base expérimentale, donner en moyenne de bons
résultats. Ce sont les heuristiques et les méta-heuristiques
■ S’il existe un algorithme efficace pour un problème NP-complet quelconque alors il existe
un algorithme efficace pour tout problème NP-complet ■ Le principal problème est l'évaluation de la qualité des résultats obtenus

■ La suite du cours sera consacrée aux heuristiques et aux méta-heuristiques pour

■ Un problème d’optimisation combinatoire est NP-difficle si le problème de décision résoudre des problèmes d'optimisation combinatoire NP-difficles :
associé est NP-complet ■ Méthodes constructives
■ Recherche locale
■ Méta-heuristiques
■ Exemple : Le problème du voyageur de commerce est NP-difficile

45 46