CHAPITRE 8.

NP-COMPLÉTUDE ET QUELQUES MÉTHODES HEURISTIQUES

D’OPTIMISATION

Chapitre 8
NP-COMPLÉTUDE ET QUELQUES
MÉTHODES HEURISTIQUES
D’OPTIMISATION

1. NP-Complétude

Définition 1.
Un problème est simple quand le nombre d‟étapes nécessaires à sa résolution peut-être
borné par un polynôme ; c‟est un problème polynomial, que l‟on notera avec P.
Sinon, il est difficile : il s‟agit d‟un problème non-polynomial, noté NP.

De petites variations d‟un problème peuvent être suffisantes pour passer d‟un problème
P à un problème NP :
- On veut partitionner un ensemble en deux sous-ensembles de même cardinalité, telle
que la différence des sommes de ces sous-ensembles soit maximale.
- On veut partitionner un ensemble en deux sous-ensembles de même cardinalité, telle
que la différence des sommes de ces sous-ensembles soit minimale.
Il est facile de couper un ensemble en deux de façon à avoir cette différence maximale.

Exemple :
On peut trier l‟ensemble, et prendre comme parties les éléments de la fin et les éléments du
début.
→ Obtenir une différence minimale est un problème de combinatoire.

64
CHAPITRE 8. NP-COMPLÉTUDE ET QUELQUES MÉTHODES HEURISTIQUES
D’OPTIMISATION

Il existe de nombreux problèmes NP, souvent en combinatoire (l‟algorithmique difficile) :

- Problème du voyageur de commerce (Travelling Salesman). Y a-t-il un cycle qui visite
tous les noeuds d‟un graphe, et dont le poids soit au plus K ? Minimiser le trajet pour
voir les clients
- Factorisation. On veut décomposer un grand nombre en nombres premiers.
- Coloration de graphes. On veut attribuer à chaque sommet une couleur sans que deux
sommets reliés soient de la même couleur ; le nombre minimal de couleurs requises est
dit „nombre chromatique‟ et noté γ(G). Déterminer γ(G) est NP-Complet dans le cas
général.

Le problème qui se pose maintenant est de voir lorsque deux problèmes sont du même
niveau de difficulté. L‟outil de base pour établir des relations entre les complexités de
différents problèmes est la Réduction.

2. Réduction d’un problème Q à un problème Π

Soit X une donnée d‟entrée pour le problème Q, dont on veut une réponse „oui‟ ou „non‟.
On transforme X en une donnée d‟entrée Y pour le problème Π avec un algorithme A.
La réponse donnée au problème Π avec la donnée Y doit être la même que celle donnée au
problème Q avec la donnée Y.
Même réponse

entrée entrée
x Q? 𝝅? y

Passage par algorithme A

Figure 12. Réduction d‟un problème Q à un problème Π

Si la donnée X peut être transformée en donnée Y par un algorithme polynomial,

alors il n‟est pas plus „difficile‟ de résoudre Π que Q. Avec un polynôme, on passe d‟un
problème à l‟autre.
Lorsque l‟algorithme A est polynomial, on note Q → pΠ.
Si Q → pΠ et Π → pQ alors Q = pΠ ; on dit que Q et Π sont des problèmes équivalents
en temps polynomial.

La plupart des problèmes d‟optimisation sont NP-difficiles, en raison de la croissance

de la complexité pour explorer un espace de recherche très grand, c'est-à-dire traiter des
données de taille énormément pour atteindre la solution de problème.
65
CHAPITRE 8. NP-COMPLÉTUDE ET QUELQUES MÉTHODES HEURISTIQUES
D’OPTIMISATION

3. Quelques méthodes d’optimisation

3.1. Problème d’optimisation

Définitions 2.

Problème d’optimisation
Un problème d‟optimisation est un problème pour lequel on veut trouver non
seulement une solution, mais la meilleurs solution.

Un problème d’optimisation discret

Est un problème dont les variables de décisions appartiennent à des domaines
discrets. On parle de programmation entière si les variables sont entières.

Un problème d’optimisation combinatoire

Est un problème de choix de la meilleure combinaison parmi toutes les combinaisons
possible.

La plupart des problèmes combinatoires sont formulés comme des programmes

entiers.

3.2. Méthode approchée : Algorithme Glouton

Pour les problèmes de grandes tailles, pas de temps de calculs raisonnables avec les
méthodes exactes. Il faut donc, rechercher de bonnes solutions approchées.

Définition 3.
Un algorithme Glouton ou avide (en anglais, Greedy) est parfois intéressant pour les
problèmes d‟optimisation.
Un algorithme Glouton se déroule selon les phases à chaque phase : on espère que
choisir un optimum local à chaque phase convergera vers une solution optimale globale
«une solution locale → une solution globale».

Un algorithme avide emploie de simples stratégies, faciles à implanter et qui

requièrent un minimum de ressources.
Construction d‟une solution réalisable en se ramenant à une suite de décisions qu‟on
prend à chaque fois au mieux en fonction d‟un critère local sans remettre en question les
décisions déjà prises, la solution obtenue est approchée.

Avantage : algorithmes simples à implémenter.

Inconvénients : solutions approchées obtenues plus ou moins bonnes, critère local.
66
CHAPITRE 8. NP-COMPLÉTUDE ET QUELQUES MÉTHODES HEURISTIQUES
D’OPTIMISATION

Exemple 1 : Placement optimal de pièces 2D (Bin Packing).

On dispose de plaques rectangulaires toutes identiques dans lesquelles on veut placer
des pièces rectangulaires sans chevauchement. Les pièces à placer ont des dimensions
différentes.
- On veut trouver le placement pour minimiser le nombre de plaques utilisées.

Figure 13. Exemple d‟un placement optimal de pièces 2D (Bin Packing)

Algorithme glouton : trier les pièces en fonction de leur taille et placer d‟abord les
pièces les plus grandes.

3.3. Quelques Méthodes heuristiques

3.3.1. Définitions

Heuristiques
Une heuristique est une technique qui améliore l'efficacité d'un processus de recherche,
en sacrifiant éventuellement l‟exactitude ou l‟optimalité de la solution.

Pour des problèmes d'optimisation (NP-complets) où la recherche d'une solution exacte

(optimale) est difficile (coût exponentiel), on peut se contenter sur :
- une solution satisfaisante donnée par une heuristique avec un coût plus faible.

Règles empiriques simples qui ne sont pas basées sur l‟analyse scientifique différents
de l‟algorithmes, Elles sont basées sur :
- L‟expérience et les résultats déjà obtenus et
- L‟analogie pour optimiser les recherches suivantes.
 La solution non optimale mais une solution approchée.

67
CHAPITRE 8. NP-COMPLÉTUDE ET QUELQUES MÉTHODES HEURISTIQUES
D’OPTIMISATION

Méta-heuristiques
Algorithmes d‟optimisation généralement de type stochastique combinant plusieurs
approches heuristiques.

L‟intérêt et domaines d‟applications des méthodes heuristiques Algorithme A∗,

Recuit simulé et Algorithmes génétiques est dans les problèmes d‟optimisation de la
forme :

Figure 14. La fonction d‟optimisation

La fonction f peut être optimisation multi-objectifs et la fonction objectif f et les

contraintes g sont non linéaires.

Figure 15. Exemple de fonction d‟optimisation

Problème : Plusieurs minima locaux possibles ⇒ les méthodes classiques d‟optimisation

non-linéaire couteuses et incapables de capturer la solution globale.
Solution : Méthodes méta-heuristiques, capacité à s‟extraire d‟un minimum local pour
aller vers un minimum global.

3.3.2. Algorithme A*

Proposé par Hart, Nilsson, Raphael (1968). Il s‟agit d‟un algorithme heuristique de
programmation dynamique qui fournit généralement une solution approchée.

Algorithme très utilisé pour sa rapidité (jeux vidéo, ...). C‟est un algorithme de
recherche d‟un plus court chemin dans un graphe allant de x0 à xF. Il est basé sur une
évaluation heuristique à chaque sommet pour estimer le meilleur chemin qui y passe.
Les sommets sont parcourus en fonction de cette évaluation heuristique : on retient le
sommet où l‟évaluation est la plus petite.
68
CHAPITRE 8. NP-COMPLÉTUDE ET QUELQUES MÉTHODES HEURISTIQUES
D’OPTIMISATION

On construit deux listes :

S liste ouverte : contient les sommets (successeurs) à examiner.
S liste fermée : contient tous les sommets déjà examinés, qui appartiennent au chemin
solution.
On commence par le sommet x=x0
1. On regarde tous les successeurs (voisins) x‟ de x
2. Si un sommet x‟ n‟est pas dans la liste ouverte S ni dans la liste fermée S, alors on
l‟ajoute dans S.
3. Si un sommet x‟ est déjà dans S ou bien dans S et si x‟ a un nouveau coût ∅ plus
petit, alors on met à jour le coût.
1. De plus, si x‟ ∈ S alors on l‟enlève de S et on l‟ajoute à S.
2. On détermine le meilleur sommet x de toute la liste ouverte S (si
S=∅ alors arret, pas de solution).
3. On met x dans la liste fermée S et on le supprime de la liste S.
4. On itère avec le sommet courant x (retour à 1).

3.3.3. Algorithme génétique

Les AGs forment une famille très intéressante d'algorithmes d'optimisation. Ils ont été
développés en première par John Holland à l'université de Michigan ("Adaptation in
Natural and Artificial Systems", 1975).

Définitions 4.
 Individu : une solution potentielle du problème (un élément de l‟espace de
recherche).
 Génotype ou chromosome : c‟est une autre façon de dire “individu”.
 Gène : un chromosome est composé de gènes. Dans le codage binaire, un gène
vaut soit 0 soit 1.
 Phénotype : chaque génotype représente une solution potentielle à un problème
d‟optimisation. La valeur de cette solution potentielle est appelée le phénotype.

Le principe des AGs est de coder chaque solution potentielle d'un problème par un
"chromosome". L'ensemble des chromosomes ou "individus" forme alors la "population"
qui va être amenée à évoluer au cours du temps. Une "génération" est l'état de la
population à un instant t. La population évolue au cours des générations en suivant des
lois de sélection, de croisement et de mutation. En informatique, nous parlons
d'opérateur génétique.

69
CHAPITRE 8. NP-COMPLÉTUDE ET QUELQUES MÉTHODES HEURISTIQUES
D’OPTIMISATION

Dans AG de base, il existe trois opérateurs qui sont la sélection, le croisement et la

mutation.

[Link]. Les opérateurs génétiques

A. La sélection : l'opérateur de sélection donne plus de chance aux "bons" individus de

participer à la génération suivante en fonction d'un certain critère, la fitness.
B. Le croisement : l'objectif de croisement est de combiner des chromosomes à partir
de parents présentant des qualités pour obtenir de meilleurs individus. Le
croisement consiste à mélanger, au niveau du génome, des gènes de deux individus
parents pour générer deux enfants. La taille de la population reste constante.

- Le croisement par coupure : le génome des deux parents est sectionné en un

même endroit, choisi le plus souvent aléatoirement. Le nombre de points de
coupure est un paramètre de l'opérateur. Les fragments sont recombinés pour
constituer les enfants comme l'illustre la figure 16.

- Le croisement uniforme : dans le cas du croisement uniforme, un masque binaire

aléatoire de même longueur que le génome d'un chromosome utilisé. Si le bit i
du masque est à 1, alors l'enfant 1 prend le bit i du parent 1, et l'enfant 2 prend le
bit i du parent 2. Si par contre c'est un 0, c'est l'inverse qui est effectué.

Figure 16. L'opérateur de croisement.

C. La mutation : elle effectue une modification des gènes des chromosomes des
enfants. En fonction du problème à résoudre, à chaque individu est associé un
'degré d'adaptation à son environnement', appelé fitness. Après croisement et
mutation, une nouvelle génération est construite en conservant les individus de la
population précédente ayant une propriété de fitness particulière, jusqu'à. la
convergence vers une solution optimale.

70
CHAPITRE 8. NP-COMPLÉTUDE ET QUELQUES MÉTHODES HEURISTIQUES
D’OPTIMISATION

Figure 17. L'opérateur de mutation.

[Link]. Le processus d'optimisation

1. Initialisation : générer un ensemble de solutions initiales.

2. Phase de mise à jour.
A. Evolution :
- Sélection : choisir avec une probabilité proportionnelle à leur qualité une liste
d'individus.
- Reproduction : générer à partir de cette liste de nouveaux individus à l'aide
des opérateurs génétiques.
- Remplacement : éliminer avec une probabilité inversement proportionnelle à
leur qualité certains individus.
B. réactualisation de la meilleure solution.
C. allez en A tant que Nombre de Générations ≤ Valeur pré-déterminée.

Figure 18. Principe de base d'un AG.

- La fonction objectif f peut être non-linéaire.

- Temps de calculs souvent importants.
- Difficultés de mise en oeuvre.
- Fournit généralement une solution approchée.
- Problèmes d‟extréma locaux.
71
CHAPITRE 8. NP-COMPLÉTUDE ET QUELQUES MÉTHODES HEURISTIQUES
D’OPTIMISATION

4. Exercices de TD

Exercice 1 – les AG pour les n reines

On a n reines qu‟il faut placer dans un échiquier (matrice n x n) sans qu'aucune d'entres
elles ne soit en prise par une autre. Deux reines sont en prise si elles se trouvent sur une
même ligne, une même colonne ou une même diagonale.
Donc une reine placée dans la case d‟indice (i, j) condamnera la ligne i, la colonne j et
les deux diagonales passant par la case (i, j). Les états solutions sont ceux représentant
des échiquiers avec n reines déjà placées sans qu‟aucune ne soit en prise.

- Montrer comment peut-on appliquer les algorithmes génétiques pour la résolution

de ce problème.

Exercice 2 – Algorithme glouton pour les pièces de monnaie

On dispose de pièces en nombre illimité de valeurs.
Pièces={100DA, 50DA, 20DA, 10DA, 5DA, 2DA, 1DA}

- Montrer comment peut-on appliquer l‟algorithme glouton pour rendre une somme
S=257 DA avec un nombre minimum de pièces.

72