View
16
Download
0
Category
Preview:
DESCRIPTION
Francoro III. Challenge ROADEF: Combinaison de Propagation de Contraintes et de Méta-Heuristiques. Yves Caseau & all Bouygues – e-lab. Introduction. Objectif: Instancier un patron de conception Auto-adaptabilité, économie de développement Application précédente: VRPTW CP’99, CP-AI-OR’01 - PowerPoint PPT Presentation
Citation preview
Y. Caseau 19/04/23 1
Challenge ROADEF: Combinaison de Propagation de Contraintes et de
Méta-Heuristiques
Yves Caseau & all
Bouygues – e-lab
Francoro III
Y. Caseau 19/04/23 2
Introduction Objectif: Instancier un patron de conception
• Auto-adaptabilité, économie de développement Application précédente: VRPTW
• CP’99, CP-AI-OR’01
• TSPTW + (LDS,LNS,Ejection)
PPCheuristiques
Push
Pull
Méta-heuristiques
Domain-dependent Domain-independent Learning Tool
LNS
LDS
E.Tree
CombinaisonDe
Méta-heuristiques
AlgorithmeHybride
Y. Caseau 19/04/23 3
Etat d’Avancement Utilisation de la PPC pour trouver une solution
• Modèle tiré de l’ordonnancement• Propagation de contraintes Ad Hoc
Application de trois méta-heuristiques• « Shaving » (consistance forte)• « Shuffling » = Large Neighborhood Search• « Limited Discrepency Search » = Introduction controlée du
Branch&Bound.
Travail en cours sur l’auto-réglage• Confirmation: le réglage représente 80% du travail• Limites de temps sur l’apprentissage• Besoin d’enrichir le modèle courant
Y. Caseau 19/04/23 4
Modèle d’Ordonnancement Le problème d’attribution de fréquence est considéré
comme un problème d’ordonnancement• (chemin, fréquence) => (tache, date)
Possibilité de réutiliser différentes techniques• Propagation (distance => contrainte classique disjonctive de
partage de ressource)• Branchement (ordre chronologique)
La notion d’intervalles de taches se retrouve avec les cliques de chemins• Possibilité d’utiliser des techniques d’edge-finding (consistance,
propagation, branchement)• Résultats décevants
Y. Caseau 19/04/23 5
Règles de Propagation Contraintes:
• Ordonnancement avec distance• Contraintes d’égalité, de différence• Sous-problème 2-SAT induit par la polarité• La distance varie suivant la polarité:
couplage dynamique 2-SAT & ORDO
Modèle classique de PPC• Fenêtre de temps + domaines exacts pour la polarité• Ordonnancement des contraintes disjonctives
Propagation des contraintes• Propagation classique (2SAT + Ordo)• Couplage 2SAT/ Ordo• Implémentation Ad Hoc vs. Choco
Y. Caseau 19/04/23 6
Consistance sur la Polarité Choix stratégique
• Contraintes globales• Consistance globale
Consistance globale (« shaving », « singleton consistency »)• Essayer chaque valeur d’un domaine individuellement, propager et
rejeter les valeurs qui provoquent une contradiction
• Technique de choix en ordonnancement (Carlier&Pinson, Martin & Shmoys)
Utilisation systématique pour la polarité• Appelé après chaque décision d’insertion d’une tâche dans la solution
courante
• À chaque changement de la date d’insertion
• Remplace un algorithme spécialisé (marquage)
• Couplage avec le sous-problème d’ordonnancement
Y. Caseau 19/04/23 7
Consistance sur l’ordonnancement
Shaving sur un domaine intervalle• Exclusion des valeurs extrèmes• Recherche d’un point fixe• Très couteux => testé mais pas utilisé
Shaving sur un ordre• Pour chaque disjonction, on teste les deux branches de
l’alternative et on élimine les branches impossibles• Forme simplifiée de la disjonction constructive• Appliqué à chaque insertion sur les disjonctions concernées• Appliqué à chaque changement de la date d’insertion de façon
globale
L’utilisation du « shaving » est un élément clé de notre approche
Y. Caseau 19/04/23 8
Algorithme Glouton
Ordonnancement chronologique classique• Recherche d’une suite d’évènements• Pour chaque date, on calcule un ensemble de candidats• Sélection des candidats retenus en « look-ahead »
– Propagation du choix et minimisation d’une fonction globale• Résultat = solution partielle + tâches rejettées
Obtention de bornes inférieures• Pour chaque valeur de K, la propagation est appliqué au
problème initial• Lorsqu’une contradiction survient, on en déduit une borne
inférieure (cf. résultats en ordonnancement)• Sur le challenge, la borne inférieure est exacte pour tous les
problèmes => puissance de la propagation.
Y. Caseau 19/04/23 9
Algorithme de branchement LDS
L’algorithme de branchement classique consiste à énumérer les sous-ensembles de tâches affectées à une date T.
Le « Limited Discrepency Search » consiste à ne remettre en cause l’algorithme glouton que dans certains cas• Le nombre de remise en cause (discrepencies) est bornée et
faible• Excellents résultats sur de nombreux problèmes
Application:• Décider de retarder une tâche qui pourrait être affectée à T• Aucun branchement sur la polarité !
Y. Caseau 19/04/23 10
Heuristiques de LDS
Fondé sur le graphe d’exclusion local à l’intérieur de l’ensemble candidat• Branche (t reporté) => t est en conflit avec au moins 3 autres
tâches• (t reporté) => une autre tâche est placée (cut)
Poids prédominant des premiers choix• Focalise l’effort LDS sur les premiers moments
Priorité donnés aux taches les plus importantes dans l’ensemble candidat
Résultats probants (amélioration) mais décevants
Y. Caseau 19/04/23 11
Application du LNS
Large Neighborhood Search• Voisinage obtenu par reconstruction d’une solution• On enleve un fragment de la solution• On le ré-insère (par Branch&Bound = LDS)• Très bons résultats en Jobshop
Application • Variable: de la réparation jusqu’à la re-construction à partir d’un
noyau • Bien adapté à l’optimisation de solutions partielles, on essayer
de re-injecter un fragment plus grand que celui qu’on enlève• Importance de l’heuristique de sélection du « fragment »
(exemple: [Shaw98])• Meta-meta-heuristique: hill climbing
Y. Caseau 19/04/23 12
Heuristiques de LNS
Analyse des conflits entre une tâche à insérer et une solution partielle• Chaque domaine (vide) est décomposé en sous-intervalles
avec leurs causes (autres tâches)• On en déduit une liste ordonnée de voisins en conflits
Chaque fragment est construit récursivement autour d’une tâche externe (à insérer dans la solution partielle)• Les fragments font de 10 à 85% de la solution initiale• Les choix sont randomisés
Un poids est affecté aux tâches externe de façon à éviter les cycles d’éjections • Possibilité de stratégie taboue
Y. Caseau 19/04/23 13
Optimisation des Contraintes Molles
La valorisation utilisée dans l’algorithme Glouton et le LDS fait intervenir faiblement les contraintes molles
Les résultats obtenus ne sont pas bons! Nous utilisons une phase de post-optimisation avec le
LNS:• En utilisant comme source du fragment les taches impliquées
dans des contraintes molles violées• En renforçant aléatoirement le statut de certaines de ces
contraintes violées (deviennent dures)• Ce schéma donne des résultats corrects
Y. Caseau 19/04/23 14
Stratégie de Contrôle
(1) K = 0
(2) Augmenter K => la propagation ne déclenche pas de contradiction
(3) Trouver une solution avec un LDS
(4) Si le nombre de tâches externes est trop grand (> 80)augmenter K => aller à (3)
(5) Sinon appliquer LNS avec des fragments de tailles variables jusqu’à 80% du temps, ou jusqu’à l’obtention d’une solution faisable
(6) Si la solution est faisable, post-optimiser (contraintes molles), sinon relacher K (=> K + 1) et répeter (5)
Y. Caseau 19/04/23 15
Outils de développement
Utilisation de CLAIRE• Langage conçu pour le développement d’algorithmes hybrides
d’optimisation combinatoire• 500 lignes pour chaque module (propagation + greedy) et (LNS
+ LDS)• Vers la mise au point d’une librairie de classe pour les méta-
heuristiques
Mise au point = 80% de l’effort dans le réglage des paramètres
Apprentissage• L’approche utilisée pour le VRPTW nécessite 10000 fois le
temps de calcul de l’algorithme !
Y. Caseau 19/04/23 16
Conclusion Un problème très intéressant et difficile du point de vue
de la PPC. Un bon exemple d’application de notre patron de
conception• Temps de développement réduit• Résultats compétitifs
La question de l’auto-réglage reste ouverte pour des algorithmes dont le temps de calcul est long.
Recommended