Heuristiques, métaheuristiques et systèmes de voisinage Application à des problèmes théoriques...

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 -

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

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

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

INTRODUCTIONINTRODUCTION

Performance des systèmes de voisinage ?

Construction de systèmes de voisinage efficaces ?

Robustesse ?

Systèmes de voisinageSystèmes de voisinage

INTRODUCTIONINTRODUCTION

Avantage : efficacité.

Inconvénients :lenteur,paramétrage.

Algorithmes stochastiquesAlgorithmes stochastiques

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

PRODUCTIONPRODUCTION VIVI CONCLUSION ET PERSPECTIVES CONCLUSION ET PERSPECTIVES

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

Rechercher une solution ω* de Ω telle que :

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

II. OPTIMISATION COMBINATOIRE

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 …

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,• …

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

Minimum V-local

cc,V VVVV

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é

Opérateurs internes aux SdVOpérateurs internes aux SdV

GuidageGuidage

Restriction du SdV aux voisins les "plus prometteurs"

Opérateurs internes aux SdVOpérateurs internes aux SdV

CouplageCouplage

Réunion de plusieurs SdV

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.

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

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(finie)

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

21 VVV

Evaluation des SdVEvaluation des SdV

Existant : étude des paysagesExistant : étude des paysages

Platlisse

Valléelisse

Platrugueux

Valléerugueuse

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, …

+ 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

Combinatoire et profondeur des SdVCombinatoire et profondeur des SdV

Deux notions antagonistes :

Rapidité Qualité

Combinatoire :taille des Sdv

Profondeur :Proximité

entre et V

Combinatoire des SdVCombinatoire des SdV

Combinatoire : nombre moyen de solutions voisines

Cas particulier des SdV "homogènes"

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

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

est inconnu, minima locaux plus ou moins accessibles.

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

VVV cHVp

On montre que :

VHcVp1

Evaluation absolue

Evaluation relative

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

Combinatoire et profondeur du Combinatoire et profondeur du couplagecouplageSoit

, le couplage de k SdV Vi , alors

VpminVp1

Combinatoire :

Profondeur :

Faux en général

profondeur du couplageprofondeur du couplage

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

Politique d’explorationPolitique d’exploration

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

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

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

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

Méthode existante :

algorithme du kangourou (KA)

Nouvelle métaheuristique :

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

Algorithmes stochastiques Comportement moyen

RESULTATS POUR LE TSP RESULTATS POUR LE TSP SYMETRIQUESYMETRIQUE

Comparaison KA / ISKAComparaison KA / ISKA

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

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 :

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.

Espace de rechercheEspace de recherche

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

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

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.

Système de voisinage multipleSystème de voisinage multiple

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

Problèmes de comportement dans ISKA

Certains mouvements sont parfois inefficaces

Exemple :

Solutionadmissible

Solutionnon

admissible

Solutions :

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

Conception du mouvement "zéro-insertion"

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

LE TSPLE TSP

ConclusionConclusion

Apport de la méthodologie ?

+ Très bons résultats obtenus

- Domination du mouvement LK

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

LE PROBLEMELE PROBLEME

V. SYSTEMES FLEXIBLES DE PRODUCTION

DéfinitionDéfinition

Job Shop avec transport

Pièces

Véhicule

MachineStation

ComplexitéComplexité

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

Job Shop Problem,

Vehicle Scheduling Problem.

Couplage heuristique / simulationCouplage heuristique / simulation

Méthode derésolution

Solution

Simulation àévénements discretsSystème de

voisinage

évaluer

Makespan

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

Mouvement d’insertion Mouvement de permutation

Mouvements retenus

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%).

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

ETUDE EXPERIMENTALEETUDE EXPERIMENTALEJeux d’essaiJeux d’essai

M1 M2 M3 M4

Exemple d’une topologie

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

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

recuit simulé,

méthode hybride.

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

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 %)

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

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 ?

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"

Heuristiques, métaheuristiques et systèmes de voisinage Application à des problèmes théoriques...

Documents

Utilisations pédagogiques des cartes heuristiques en sciences

Algorithmes d’approximation Heuristiques Gloutonnes les

R echerche heuristiques

La sécurité du poste de travail Stephane Saunier TSP Sécurité Microsoft France

Cartes heuristiques Atelier Gullivergulliver.eu.org/_media/atelier_cartes_heuristiques_18-4... · 2012. 4. 19. · Cartes heuristiques Atelier Gulliver mercredi 18 avril à 20h

Les Heuristiques de Bastien et Scapin

LES CARTES HEURISTIQUES - Le goût du françaislegoutdufrancais.org/.../2016/05/Les-cartes-heuristiques-_extrait.pdf · Une unité d’information du cerveau. ... Les lois heuristiques

Les cartes heuristiques numériques

Cartes heuristiques

Cartes Heuristiques - Usages en Contextes Universitaires

DES RENDUS SOUS FORME DE CARTES HEURISTIQUES…

Présentation Aurélien Schuller SP-TSP 27052013

Heuristiques, Méta-heuristiques

Les Cartes Heuristiques Cycles 2 Et 3

Les atouts des cartes heuristiques

Cartes heuristiques et hétérogénéité

Analyse cryptographique par les méthodes heuristiques

Parallélisation des métaheuristiques

Optimisation des paramètres de fonctionnement d’un sécheur de Triple Super Phosphate (TSP)

Méthaheuristiques pour l’optimisation combinatoire et l ... · 3 heuristiques pour un problème d'optimisation1. Ainsi les métaheuristiques sont adaptables et applicables à une