Algorithmes Avancés et Optimisation

(AAO)

Chapitre 3 : Généralité sur les méthodes

d’optimisation

Master 1 Informatique
Dr Djerou Leila
Ldjerou@yahoo. fr
 Introduction
 Dans la vie courante et économique, on se confronte quotidiennement à des problèmes
de complexité grandissante, qui surgissent dans des secteurs très divers:
 une manufacture doit trouver les meilleurs plans de production et place pour les
machines dans l’atelier.
 minimiser la consommation de matières premières et d’énergie pour la fabrication
de produits
 Une famille en voyage doit choisir le chemin le plus court et le moins coûteux pour
atteindre sa destination.

 Le problème à résoudre peut souvent s’exprimer sous la forme générale d’un problème
d’optimisation, dans lequel on définit une ou plusieurs fonctions objectif que l’on
cherche à minimiser ou à maximiser par rapport à tous les paramètres concernés

 La résolution d’un problème d’optimisation a conduit les chercheurs à proposer des

méthodes de plus en plus performantes, parmi lesquelles on trouve les métaheuristiques.
 Les métaheuristiques sont des méthodes générales de recherche dédiées aux problèmes
d’optimisation difficile.
L.DJEROU Méthodes d'optimisation 2
 Problème d’optimisation (1)




 Problème d’optimisation
 un problème d’optimisation consiste à trouver, parmi un ensemble de
solution potentielles, une solution optimale au regard d’un critère donné.


3
L.DJEROU Méthodes d'optimisation
 Problème d’optimisation (2)
 Selon le problème, on veut maximiser ou minimiser l’objectif.

 Il est possible de passer d’un problème de maximisation à un problème de minimisation

L.DJEROU Méthodes d'optimisation 4

 Problème d’optimisation avec contraintes
 Un problème d’optimisation se modélise par une fonction objectif et des
contraintes
x ∈ IRd est le vecteur des variables de décision,
f : la fonction objectif,
h1, .., hm : les contraintes d’égalités
g1, .., gk: les contraintes d’inégalité
xL, xU : sont respectivement les bornes inférieures et
supérieures du domaine de recherche des variables.

 L’ensemble de points de l’espace des états possibles qui satisfait au mieux les
contraintes est donné par :

 Exemple : la tournée de véhicules.

 Un bus effectue le ramassage scolaire. Il doit respecter des contraintes sur les horaires.
Son objectif est de faire le trajet le plus court pour minimiser les coûts.
L.DJEROU Méthodes d'optimisation 5
 Optimisation multi-critères

Très souvent on veut optimiser plusieurs fonctions/critères de qualité en même temps :

problème multi-critères, multi-objectifs.

 La fonction objectif d’un problème multiobjectif est un vecteur de fonctions

mono-objectifs défini par :

 Chaque fonction fi(x) peut-être à maximiser ou à minimiser.

x est le vecteur représentant les n variables de décision :

Exemple
On veut le moteur le plus puissant, mais aussi le plus léger, qui consomme le moins
possible et qui coûte le moins cher à fabriquer…

L.DJEROU Méthodes d'optimisation 6

 Exemples de problèmes d’optimisation
Cas continu
Problème continu
Optimisation continue : les solutions sont des vecteurs de réels : on parle de
variables réelles, et l’espace de recherche est infini.

L.DJEROU Méthodes d'optimisation 7

 Exemples de problèmes d’optimisation
Cas discret
 Problème discret
 L’espace de recherche est fini, discret.
 Les problèmes discrets sont généralement combinatoires.
 Optimisation combinatoire
une solution est une combinaison d’éléments pris dans un ensemble discret : on parle
de variables discrètes.

8
L.DJEROU Méthodes d'optimisation
 Enumération exhaustive
1.

2.

3.

1:

L.DJEROU Méthodes d'optimisation 9

Puissance de calcul et Avancées algorithmiques

L.DJEROU Méthodes d'optimisation 10

 Optimisation = modélisation et résolution

1.
2.
3.
4.

L.DJEROU Méthodes d'optimisation 11

 Terminologie
Méthode complète:
Méthode optimale:
Méthode exacte (exhaustive):

Méthode approchée (approximative ):

Méthode déterministe :

Méthode stochastique:

L.DJEROU Méthodes d'optimisation 12

 Classification des méthodes d’optimisation
combinatoires

Méthodes à
base de population

Essaim de particules
Algorithmes
génétiques
Remarque Colonie de fourmis
Fourragement
Les méthodes exactes ne sont efficaces que pour les bactériens Abeilles
instances de problèmes de petite taille
artificielles
L.DJEROU Méthodes d'optimisation 13
 Heuristique



Heuristique ≠ algorithme exacte

Algorithme exacte: garantit une solution optimale
Heuristique : pas de garantie d’optimalité

L.DJEROU Méthodes d'optimisation 14

 Métaheuristique (ou méta-heuristique)





L.DJEROU Méthodes d'optimisation 15

 Metaheuristiques
Intensification et diversification
 Dans les metheuristiques ; les deux caractéristiques déterminant l’ exploration
de l’espace de solutions sont intensification et diversification .


 L’intensification conduit à la convergence

 La convergence donne le moyen à l’algorithme ( meta-heuristique) d’obtenir
rapidement de bonnes solutions.

 La diversification permet à l’algorithme d’éviter les minimums locaux.

L.DJEROU Méthodes d'optimisation 16
 Paradigmes de méthodes approchées (heuristiques et
métaheuristiques)

 Construction :
 Recherche locale (ou voisinage):

 Evolution :

 Hybridation :

L.DJEROU Méthodes d'optimisation 17

Principes des heuristiques constructives

n
Op (n )   (3  opc (i , n ))
i 1

L.DJEROU Méthodes d'optimisation 18

 Heuristiques constructives gloutonnes
Définition
Un algorithme glouton (greedy) est un algorithme qui construit sa solution pas à pas
-
-

Exemple

L.DJEROU Méthodes d'optimisation 19

 Problème du sac à dos (Knapsack Problem «KP»




L.DJEROU Méthodes d'optimisation 20

Heuristique constructive gloutonne pour le KP

Poids maximal autorisé

dans le sac =15

Solutions possibles sont:

ou

L.DJEROU Méthodes d'optimisation 21

 Approche constructive Heuristique
le plus proche voisin
Plus proche voisin (nearest neighbour)
1.

2.

3.

L.DJEROU Méthodes d'optimisation 22

 Approche constructive
Heuristique le plus proche voisin et le problème TSP(1)
 Problème du voyageur de commerce (travelling salesman problem)
Trouver un cycle hamiltonien dans un graphe de longueur minimale : chaque
sommet du graphe est visité une et une seule fois

L.DJEROU Méthodes d'optimisation 23

 Approche constructive
Heuristique le plus proche voisin et le problème
TSP(2)
Exemple La solution est construite selon
le schéma suivante:
V1

V1 – V3
V1 – V3 –V4
V1 – V3 –V4-V2
V1 – V3 –V4-V2-V5
V1–V3–V4-V2-V5-V6
V1–V3–V4-V2-V5-V6-V7
V1–V3–V4-V2-V5-V6-V7-V10
V1–V3–V4-V2-V5-V6-V7-V10-V8
V1–V3–V4-V2-V5-V6-V7-V10-V8-V9
V1–V3–V4-V2-V5-V6-V7-V10-V8-V9-V1
L.DJEROU Méthodes d'optimisation 24
 Approche constructive
Heuristique l’ insertion et le problème TSP (1)
Principe
1.
2.

L.DJEROU Méthodes d'optimisation 25

 Approche constructive
Heuristique l’ insertion et le problème TSP (2)
Exemple
La solution est construite selon le
schéma suivante:
V1
V1-V3-V1
V1-V3-V4-V1
V1-V3-V4- V2-V1
V1-V5-V3-V4-V2-V1

V1-V5-V6-V3-V4-V2-V1

V1-V5-V6-V7-V3-V4-V2-V1

V1-V5-V6-V10-V7-V3-V4-V2-V1

V1-V5-V6-V10-V8-V7-V3-V4-V2-V1

V1-V5-V6-V10-V8-V9-V7-V3-V4-V2-V1
L.DJEROU Méthodes d'optimisation 26
 Approche constructive gloutonnes

 En O(n) (ou polynomial)

 Une succession de choix localement optimaux ne garantit pas une solution optimale

L.DJEROU Méthodes d'optimisation 27

 Principe de la recherche locale




Voisinage
 Fonction   2 : x  (x )  
 Traduit la notion de solutions proches, semblables, voisines
 Suite de solutions: une trajectoire dan l’espace de recherche

L.DJEROU Méthodes d'optimisation 28

Structure générale d’une recherche locale

L.DJEROU Méthodes d'optimisation 29

 Méthodes de descente du gradient (1)




L.DJEROU Méthodes d'optimisation 30

Descente du gradient

L.DJEROU Méthodes d'optimisation 31

 Recherche Locale

Idée d’amélioration
 Autoriser, de temps en temps, une dégradation de la solution courante

 Contrôler la dégradation pour éviter la divergence de l’algorithme

L.DJEROU Méthodes d'optimisation 32

 Recuit simulé (simulated annealing), 1983 (1)


1.
2.




L.DJEROU Méthodes d'optimisation 33

 Recuit simulé (simulated annealing), 1983 (2)
Principe

Retourner
Fin

L.DJEROU Méthodes d'optimisation 34

 Recuit simulé (simulated annealing), 1983 (3)

Remarques





L.DJEROU Méthodes d'optimisation 35

 Recherche Tabou (Tabu Search), 1989(Glover)
Principe

 Mémoire à courte terme: on mémorise les dernières configurations

visitées(liste tabou)
 Choisir un des meilleurs voisins qui n’appartient pas à la liste tabou
même s’il dégrade f
 Pas de tirages aléatoires

Paramètres




L.DJEROU Méthodes d'optimisation 36

 Références

1. S. Ben Imail, Introduction à l’optimisation combinatoire, Majeure Informatique –

INF413-C5, 2012.TELECON Bretagne

2. Laurent Péridy, Techniques d’optimisation combinatoire

L.DJEROU Méthodes d'optimisation 37