Heuristiques, métaheuristiques et systèmes de voisinage Application à des problèmes théoriques et industriels de type TSP et ordonnancement. Présenté par

Heuristiques, métaheuristiquesHeuristiques, métaheuristiques et systèmes de voisinage et systèmes de voisinage

Application à des problèmes théoriques etApplication à des problèmes théoriques etindustriels de type TSP et ordonnancement.industriels de type TSP et ordonnancement.

Présenté par Laurent DeroussiLIMOS CNRS UMR 6158

Equipe Modélisation et Aide à la Décision

- META-Bermudes - Lille - 07/02/2003 -

22

PréambulePréambule[Lin & Kernighan, 1973]

"An Effective Heuristic Algorithmfor the Traveling Salesman Problem"

Améliorer la performancedes métaheuristiques

Méthodes derésolution

Systèmes devoisinage

33

SommaireSommaire

II INTRODUCTION INTRODUCTION IIII OPTIMISATION COMBINATOIRE OPTIMISATION COMBINATOIRE III SYSTEMES DE VOISINAGEIII SYSTEMES DE VOISINAGE IVIV VOYAGEUR DE COMMERCE VOYAGEUR DE COMMERCE VV SYSTEMES FLEXIBLES DE SYSTEMES FLEXIBLES DE

PRODUCTIONPRODUCTION VI CONCLUSION ET PERSPECTIVESVI CONCLUSION ET PERSPECTIVES

44

II INTRODUCTION INTRODUCTION IIII OPTIMISATION COMBINATOIRE OPTIMISATION COMBINATOIRE IIIIII SYSTEMES DE VOISINAGE SYSTEMES DE VOISINAGE IVIV VOYAGEUR DE COMMERCE (TSP) VOYAGEUR DE COMMERCE (TSP) VV SYSTEMES FLEXIBLES DE SYSTEMES FLEXIBLES DE

PRODUCTIONPRODUCTION VI CONCLUSION ET PERSPECTIVESVI CONCLUSION ET PERSPECTIVES

55

INTRODUCTIONINTRODUCTION

Performance des systèmes de voisinage ?

Construction de systèmes de voisinage efficaces ?

Robustesse ?

Systèmes de voisinageSystèmes de voisinage

66

INTRODUCTIONINTRODUCTION

Avantage : efficacité.

Inconvénients :lenteur,paramétrage.

Algorithmes stochastiquesAlgorithmes stochastiques

Méthodes délaissées par la littérature

77


PRODUCTIONPRODUCTION VIVI CONCLUSION ET PERSPECTIVES CONCLUSION ET PERSPECTIVES

88

Problème d’optimisation Problème d’optimisation combinatoirecombinatoire

)(min

cc *

Rechercher une solution ω* de Ω telle que :

Ω : espace des solutions (fini)c : Ω R

II. OPTIMISATION COMBINATOIRE

99

Méthodes de résolutionMéthodes de résolution


Principales méthodes de résolutionPrincipales méthodes de résolution

Méthodesexactes

Méthodesapprochées

Séparation / évaluation Méthodes de coupe …

Heuristiques de construction Méthodes de recherche locale Métaheuristiques Méthodes hybrides …

1010



Méthodes à voisinageMéthodes à voisinage

• méthodes de recherches locales itérées,• recuit simulé,• méthode tabou,• …

Méthodes de recherche locale

Métaheuristiques

Méthodes hybrides

• métaheuristiques / recherche locale,• métaheuristiques / métaheuristiques,• …

1111



1212

GénéralitésGénéralités

III. SYSTEMES DE VOISINAGE

Quelques définitionsQuelques définitions

Système de voisinage (SdV) (Hao et al., 1999)

Minimum global

cc,

Minimum V-local

cc,V VVVV

P:V

1313

GénéralitésGénéralités


Notion de performanceNotion de performance

Un SdV est performant s’il permet d’obtenirrapidement des minima locaux de bonne qualité.

Deux notions antagonistes :

Rapidité Qualité

1414

Opérateurs internes aux SdVOpérateurs internes aux SdV


GuidageGuidage

Restriction du SdV aux voisins les "plus prometteurs"

ω

V

V

1515

Opérateurs internes aux SdVOpérateurs internes aux SdV


CouplageCouplage

Réunion de plusieurs SdV

ω

2V 1V

1616

Construction de SdV Construction de SdV performantsperformants


Proposition d’une méthodologieProposition d’une méthodologie

Méthodologie en trois étapes :

recensement des mouvements de base "pertinents",

guidage des mouvements de base,

couplage des mouvements guidés.

1717

Construction de SdV Construction de SdV performantsperformants


Avantages de la méthodologie Avantages de la méthodologie proposéeproposéeRecensement des mouvements de base "pertinents"

Guidage des mouvements de base

Couplage des mouvements guidés

s’appuyer sur les propriétés propresà chacun des mouvements

améliorer le temps d’exécution avec une pertede qualité raisonnable pour les minima locaux

obtenir des minima locaux de meilleure qualitéavec une perte raisonnable en temps d’exécution

1818

Justification théorique du Justification théorique du couplagecouplage


Théorème de caractérisationThéorème de caractérisationdes minima globauxdes minima globaux

V

V(finie)

Soit V le couplage de V1 et V2 ,alors, on a :

21 VVV

1V

2V

1919

Evaluation des SdVEvaluation des SdV


Existant : étude des paysagesExistant : étude des paysages

Platlisse

Valléelisse

Platrugueux

Valléerugueuse

2020




Evaluation de nombreux critères :

la distribution de la fonction coût, la rugosité du paysage, le nombre de minima locaux, la distribution des minima locaux dans l’espace de recherche, la structure des bassins d’attraction des minima locaux, …

2121




+ Connaissance très pointue de l’espace de recherche

+ Très utile pour l’étude d’un problème particulier

- Mise en œuvre délicate

- Difficilement applicable pour vérifier le caractère générique de la méthodologie proposée

2222



Combinatoire et profondeur des SdVCombinatoire et profondeur des SdV

Deux notions antagonistes :

Rapidité Qualité

Combinatoire :taille des Sdv

Profondeur :Proximité

entre et V

2323



Combinatoire des SdVCombinatoire des SdV

Combinatoire : nombre moyen de solutions voisines

VV1

Cas particulier des SdV "homogènes"

VV

2424



Profondeur des SdVProfondeur des SdV

Méthode de recherche locale associée à V

VVV :H

Domaine d’attraction d’un minimum local ωV

VVH/ V

1

VH

2 3

2525




Profondeur (première définition) :qualité moyenne des minima locaux

VV

VV

cVp

1

MAIS

est inconnu, minima locaux plus ou moins accessibles.

V

2626




Profondeur : qualité moyenne des minima locaux,pondérée par la taille de leur domaine d’attraction

VV

VVV cHVp

11

On montre que :

VHcVp1

2727




Evaluation absolue

Evaluation relative

minimum global, meilleure borne inférieure, meilleure borne supérieure.

2828



Combinatoire et profondeur du Combinatoire et profondeur du couplagecouplageSoit

k

iiVV

1

, le couplage de k SdV Vi , alors

ik..i

VpminVp1

k

iiVV

1

Combinatoire :

Profondeur :

Vrai

Faux en général

2929



profondeur du couplageprofondeur du couplage

ik..i

VpminVp1

• en théorie

L’inégalité n’est vérifiée que

si la méthode de recherche locale HV vérifie certainespropriétés concernant la politique d’exploration(i.e. l’ordre dans lequel les voisins sont explorés)

• en pratique

Vérifier expérimentalement que le couplage a un effetpositif sur la profondeur

3030



Politique d’explorationPolitique d’exploration

ω

2V 1V

1

234

56

7

89

1011

12

13

3131

Etude expérimentaleEtude expérimentale


Voyageur de commerce à 9 villesVoyageur de commerce à 9 villes

SdVSdV combcomb profprof tempstemps

2-opt2-opt 2727 0.77%0.77% 39 s39 s

EPEP11 insertioninsertion 6363 2.62%2.62% 49 s49 s

couplagecouplage 9090 0.45%0.45% 45 s45 s

2-opt2-opt 2727 1.78%1.78% 39 s39 s

EPEP22 insertioninsertion 6363 1.90%1.90% 49 s49 s

couplagecouplage 9090 0.07%0.07% 45 s45 s

3232

Etude expérimentaleEtude expérimentale


Voyageur de commerce à 9 villesVoyageur de commerce à 9 villes

+ Amélioration significative de la profondeur

+ Hausse modérée du temps d’exécution

- Influence de la politique d’exploration

- Caractère imprévisible de la politique d’exploration

3333



3434

Conception du système de voisinageConception du système de voisinage

IV. VOYAGEUR DE COMMERCE

Mouvements de baseMouvements de base

Mouvement 2-opt Mouvement de Or (insertion généralisée) Mouvement LK

Mouvements retenus

Mouvements non retenus

Mouvement de permutation

3535



Guidage des mouvementsGuidage des mouvements

Basé sur l’ensemble des "meilleurs" voisins de chaque ville

TSP symétrique euclidien TSP asymétrique

Propriétés du plan euclidien

Distance

Distance

3636




Méthode existante :

algorithme du kangourou (KA)

Nouvelle métaheuristique :

variante du kangourou (ISKA)"Improved Solution Kangaroo Algorithm"

Algorithmes stochastiques Comportement moyen

3737

RESULTATS POUR LE TSP RESULTATS POUR LE TSP SYMETRIQUESYMETRIQUE


Comparaison KA / ISKAComparaison KA / ISKA

00,10,20,30,40,50,60,70,80,9

Ecart

KA

ISKA

3838

RESULTATS POUR LE TSP RESULTATS POUR LE TSP SYMETRIQUESYMETRIQUE


SynthèseSynthèse

est plus performant que KA, trouve une solution optimale pour 10 des 12 instances testées, concurrence les méthodes de la littérature

ILK (Johnson, 1997)GLS (Merz, 1997)GLS + FLS (Voudouris, 1999)

ISKA :

3939

LE TSP ASYMETRIQUELE TSP ASYMETRIQUE


Approches possiblesApproches possibles

Heuristiques dédiées au ATSP,

Heuristiques adaptées du STSP au ATSP,

Transformation du ATSP en STSP.

4040



Espace de rechercheEspace de recherche

La transformation du ATSP en STSPdouble le nombre de villes ! ΩS

ΩA

Pour n=5 villes ΩS=181440 ΩA=24

4141



Espace de rechercheEspace de recherche

Transformation pénalisation de certaines arêtes.

Subdivision de ΩS en trois sous-espaces.

Optimisation multi-critères hiérarchisés.

4242



Système de voisinage multipleSystème de voisinage multiple

La réutilisation de ISKA fournit des résultats corrects.

MAIS

Problèmes de comportement dans ISKA

4343




Certains mouvements sont parfois inefficaces

Exemple :

Solutionadmissible

Solutionnon

admissible

2-opt

4444




Solutions :

Adaptation du système de voisinage selon le sous-espace exploré

Conception du mouvement "zéro-insertion"

4545



RésultatsRésultats

27 instances de la TSPLIB (17 – 443 villes)

25 solutions optimales

Robustesse ?

RBG443 0% entre 1 et 14 minutes

RBG323 entre 1.2% et 1.8% en 25 minutes

4646

LE TSPLE TSP


ConclusionConclusion

Apport de la méthodologie ?

+ Très bons résultats obtenus

- Domination du mouvement LK

4747

LE TSPLE TSP


PerspectivesPerspectives

Utiliser LKH avec d’autres métaheuristiques

Améliorer le calcul des bornes inférieures du ATSP

Adapter LKH pour la ATSP

TSP symétrique

TSP asymétrique

4848



4949

LE PROBLEMELE PROBLEME

V. SYSTEMES FLEXIBLES DE PRODUCTION

DéfinitionDéfinition

Job Shop avec transport

Pièces

Véhicule

MachineStation

L/U

5050



ComplexitéComplexité

Résolution conjointe de deux problèmes NP-complets :

Job Shop Problem,

Vehicle Scheduling Problem.

5151



Couplage heuristique / simulationCouplage heuristique / simulation

Méthode derésolution

Solution

Simulation àévénements discretsSystème de

voisinage

évaluer

Makespan

5252

Conception du système de voisinageConception du système de voisinageMouvements de baseMouvements de base

Mouvement d’insertion Mouvement de permutation

Mouvements retenus


5353

Conception du système de voisinageConception du système de voisinageGuidageGuidage


Permutation :

Insertion :

temps de calcul divisé par 3,aucune perte de qualité.

temps de calcul divisé par 5,perte sensible de qualité (1%).

5454

ETUDE EXPERIMENTALEETUDE EXPERIMENTALEJeux d’essaiJeux d’essai


40 instances :

[Ulusoy & Bilge, 1993]

4 machines, 2 véhicules

10 jeux de données :

5 à 8 pièces, 13 à 23 opérations

4 topologies

5555

ETUDE EXPERIMENTALEETUDE EXPERIMENTALEJeux d’essaiJeux d’essai


M1 M2 M3 M4

LU

Exemple d’une topologie

5656

ETUDE EXPERIMENTALEETUDE EXPERIMENTALEMéthodes de résolutionMéthodes de résolution


méthode de recherche locale itérée,

recuit simulé,

méthode hybride.

5757

ETUDE EXPERIMENTALEETUDE EXPERIMENTALERésultats : comparaison avec la Résultats : comparaison avec la littératurelittérature


Les trois méthodes sont toujours au moins aussibonnes que le meilleur résultat de la littérature.

23 nouvelles bornes supérieures (sur 40 instances)

InstancInstancee

LittératLittérat..

Résult.Résult. InstancInstancee

LittératLittérat..

Résult.Résult.

Ex24Ex24 113113 108108 Ex71Ex71 118118 111111

Ex31Ex31 105105 9999 Ex72Ex72 8585 7979

Ex44Ex44 126126 121121 Ex104Ex104 164164 159159

5858

ETUDE EXPERIMENTALEETUDE EXPERIMENTALERésultats : comparaison des méthodesRésultats : comparaison des méthodes


Méthode hybride

retrouve 100% des meilleures bornes supérieures, temps d’une réplication : de 19 à 46 secondes, robustesse.

MinimumMinimum MoyenneMoyenne MaximumMaximum

Résultats moyensRésultats moyens

pour les 40 pour les 40 instancesinstances

108,48108,48

(0 %)(0 %)108,85108,85

(0.34 %)(0.34 %)109,73109,73

(0.93 %)(0.93 %)

5959



6060

CONCLUSIONCONCLUSION

Déterminer un bon paramétrage a priori,

Concevoir un système de voisinage performant,

Pratique3 problèmes : TSP, ATSP, SFP

4 méthodes : KA, ILS, SA, SALS

Théorique

Proposition d’outils mathématiques

6161

PERSPECTIVESPERSPECTIVES

Etudier l’effet du couplage sur le paysage.

Application de la méthodologie :à d’autres problèmes,avec d’autres méthodes.

Méthodes à individus vs. méthodes à population ?

Méthodes stochastiques vs. méthodes déterministes ?

6262

FINFIN

"When designing a metaheuristic, it is preferable that it besimple, both conceptually and in practice. Naturally, it alsomust be effective, and if possible general purpose. …… The ideal case is when the metaheuristic can be usedwithout any problem-specific knowledge. …… Problem-specific knowledge must now be incorporatedinto metaheuristics in order to reach the state of the art level. … … We run the risk of loosing both simplicity and generality."

(Lourenzo, Martin & Stützle, 2001)(Lourenzo, Martin & Stützle, 2001)

"Iterated Local Search"

Documents

Heuristiques, métaheuristiques et systèmes de voisinage Application à des problèmes théoriques et industriels de type TSP et ordonnancement. Présenté par