Métaheuristiques : Recherches Locales Et Algorithmes .
Métaheuristiques :Recherches locales etAlgorithmes evolutionnairesMaster 1 informatique RIF IFI - Systèmes Arti ciels ComplexesSébastien Verelverel@i3s.unice.frwww.i3s.unice.fr/ verelUniversité Nice Sophia AntipolisLaboratoire I3SEquipe DOLPHIN - INRIA Lille Nord Europe12 octobre 2012
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifPlan1Problèmes d'optimisation2Métaheuristiques standards3Paysage AdaptatifSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifModélisation de ProblèmesRésolution d'un problème :Problème modélisation solution(s)Modélisation :simpli cation de la réalité (nombrede paramètres, bruit , défauts.)Conception d'un (bon) modèle :"petit" sudoko (n 3)Connaissance experte du domaineConnaissance des méthodes derésolution (informatique)Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifProblèmes d'optimisation combinatoireMAX - SATColoration de grapheVoyageur de commerce (TSP)Quadratic Assignment Problem (QAP)Schedulingpaysages NKSudoku (coloration de graphe)Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifProblème SATPremier problème NP-di cileN variables booléennes : {x , x , ., xN },m clauses : {C , C , ., Cm }.kj littérals par clause Cj : {l ,j , l ,j , ., lkj ,j },11221Vm2j Cjoù1Cj Wki j li ,j et li xn ou x n1Existe-t-il une valeur des variables qui véri e la formule logique ?Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifSAT / MAX - SATMaximiser le nombre de clausesCj véri éesf (s ) #{Cj true }s est une solution de SAT ssi f (s ) mSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifSATTransition de phase suivantα mNApplications : véri cation decircuits, logique, informatique.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifColoration de grapheGrapheG (S , A), S ens. des sommetsA ens. des arcsColoration α : S C telle que si(s , t ) A alors α(s ) 6 α(t )etApplications : a ection de fréquence en téléphonie mobile, emploidu temps, coloration des cartes.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifSodoku : coloration de graphe ?G (S , A),S {xi ,j (i , j ) {1, . . . , 3n} }A {(xi ,j , xi ,j ) . . .(xi ,j , xi ,j ) . . .(xi ,j , xi ,j ) . . .}Ensemble des couleurs {1, . . . , n }Graphe200002Remarque : "petit" problème puisqueseulement 81 noeudsSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifVoyageur de commerce (TSP)Pni 1Pnj d xi xj1avec :Trouver le parcours le pluscourt passant par toutesn : nombre de villesdrs : distance entre les villes r et s .x une permutation :xi est la i eme ville traversée.les villes.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifQuadratic Assignment Problem (QAP)Minimiser le ot total :n objets, nemplacementsfij : ot entre objectsi et j ,drs : distance entreemplacement r et sn XnXi j 1fij dpi pj1p une permutation :pi emplacement l'objet i .avecApplications : répartition de batiments ou de servives, a ectationdes portes d'aéroport, placement de modules logiques, claviers.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifQuadratic Assignment Problem (QAP)Exemple d'aprés Taillard.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifVehicule Routing Problem (VRP)But : transporter des biens à des clientsVéhicule à capacité limitée, fenêtre de temps, etc.Problème : Déterminer pour chaque véhicule leur trajet.Application : logistique du dernier kilomètre, etc.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifJob Scheduling ProblemEnsemble de tachesJ {j , j , j , . . . , jp }temps d'execution p (ji )Réalisés sur m machinesM {M , . . . , M m }1231Applications : ordonnancement, emploidu temps,.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifPaysages NKf (x ) N1NXi fi (xi ; xi , . . . , xiK )11N nombre d'acides animésK N 1 nombres d'intéraction entre ac. animésdeux types d'ac. animé 0 ou 1xk le k eme ac. animé d'une chaine x{i1 , . . . , iK } {1, . . . , i 1, i 1, . . . , N }fi : {0, 1}K 1 [0, 1]Application : modélisation de protéinesSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsexempleN 4KPaysage Adaptatif 2x 0110x1 x2 x4000001010011.f (x ) f1x1 x2 x30.90.60.10.2.1414((f2000001010011.f (010)10.1x2 x3 x40.40.80.30.2000.101110111. f (011)20.2 f30.2.0.90.10.5f (110)30.10.3Sébastien VerelMétaheuristiquesx1 x2 x4000001010011. f40.10.20.80.0.f (010)40.8))
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifOptimizationInputsSearch space : Set of all feasible solutions,XObjective function : Quality criteriumf: X IRGoalFind the best solution according to the criteriumx ? argmax fSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifOptimizationInputsSearch space : Set of all feasible solutions,XObjective function : Quality criteriumf: X IRGoalFind the best solution according to the criteriumx ? argmax fBut, sometime, the set of all best solutions, good approximation ofthe best solution, good 'robust' solution.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifContexteBlack box ScenarioWe have onlyx fxx fx{( 0 , ( 0 )), ( 1 , ( 1 )), .}given by an "oracle"No information is either not available or needed on the de nition ofobjective functionObjective function given by a computation, or a simulationObjective function can be irregular, non di erentiable, noncontinous, etc.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifContexteBlack box ScenarioWe have onlyx fxx fx{( 0 , ( 0 )), ( 1 , ( 1 )), .}given by an "oracle"No information is either not available or needed on the de nition ofobjective functionObjective function given by a computation, or a simulationObjective function can be irregular, non di erentiable, noncontinous, etc.(Very) large search space for discrete case (combinatorialoptimization),i.e. NP-complete problemsSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifSearch algorithmsPrincipleEnumeration of the search spaceA lot of ways to enumerate the search spaceUsing random sampling : Monte Carlo technicsLocal search technics :Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifSearch algorithmsPrincipleEnumeration of the search spaceA lot of ways to enumerate the search spaceUsing random sampling : Monte Carlo technicsLocal search technics :Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifSearch algorithmsPrincipleEnumeration of the search spaceA lot of ways to enumerate the search spaceUsing random sampling : Monte Carlo technicsLocal search technics :If objective functionIf not.fhas no propertie : random searchSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRetour à MAX-SATComment résoudre ce genre de problèmes ?x x ) (x x ) (x x )(x x x12x x x23x x x13x x xx x x( 4 2 3 ) ( 2 4 5 ) ( 2 1 5 ) ( 2 5 4 ) ( 1 3 4 )Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRetour à MAX-SATmathématiquement ou .Exhaustivementn 20, n 100, .AléatoirementConstruction de solution (pas dans ce cours)Méthodes exactes (pas dans ce cours)ou .Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifHeuristiquesHeuristique : algorithme de résolution basé sur l 'expérience nefournissant pas nécessairement une solution optimaleOn désire toutefois :Le plus souvent possible une solution proche de l'optimalitéLe moins souvent possible un mauvaise solution (di érent !)Une complexité raisonnable De la simplicité d'implémentation (code light en version debase.)Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifMetaheuristiquesMétaheuristique : ensemble d'heuristiquesPeu probable qu'un algorithme puisse résoudre tout problèmeMétaheuristique :regroupe des heuristiques dépendant de paramètresdécrit une méthode de conception d'heuristiquedeun aveu d'impuissanceàdes techniques performantes d'optimisation di cileSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifMetaheuristisques de recherche localeAlgorithmes à population de solutionsAlgorithmes Evolutionnaires (EA) : Holland 1975 et mêmeavantAlgorithmes d'essaims particulaires (PSO) : R. Ebenhart et J.Kennedy 1995.Algorithmes de fourmis (ACO) : Bonabeau 1999Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifMetaheuristisques de recherche localeAlgorithmes à solution unique(Recherches aléatoire),Algorithmes de descente : Hill-Climber (HC),première-descenteRecuit Simulé (SA) : Kirkpatricket al 1983,Recherche Tabou (TS) : Glover 1986 - 89 -90,Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifStochatic algorithms with unique solution (Local Search)Sfset of solutions (search space): S IRV(s )objective functionset of neighbor's solutions ofSébastien VerelsMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRecherche Locale (LS)3 ingrédients indispensables :Sensemble des solutions (espace de recherche),f : S IR fonction objectif à maximiser (ou coût à minimiser)V(s ) ensemble des solutions voisines de sAlgorithme d'une Recherche LocaleChoisir solution initiale s Srépéterchoisirs s0s0s V( )jusqu'à critère d'arrêt non veri éSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simplef (x ) PNi xi où x chaine binaire de taille N .Une solution pour N 6 :x 01101 et f (x ) 3Maximiser1Taille de l'espace de rechercheSébastien VerelS:Métaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simplef (x ) PNi xi où x chaine binaire de taille N .Une solution pour N 6 :x 01101 et f (x ) 3Maximiser1Taille de l'espace de rechercheSébastien VerelS: 2NMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simplef (x ) PNi xi où x chaine binaire de taille N .Une solution pour N 6 :x 01101 et f (x ) 3Maximiser1Taille de l'espace de rechercheS: 2NExerciceCoder, dans le langage que vous voulez, la fonctiond'évaluation.Tester en a chant une solution et la valeur de la fonctionCoder la recherche aléatoire qui consiste à générer dessolutions aléatoirement (uniformément)Evaluer les performances de la recherche aléatoireSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRecherche Locale AléatoireHeuristique d'exploration maximaleRecherche locale aléatoireChoisir solution initiale s Srépéterchoisirs s0s0s V( )Algorithme inutilisableen pratiqueAlgorithme decomparaisonaléatoirementOpérateur local debase de nombreusesjusqu'à Nbr d'éval. maxNbEvalSébastien VerelmétaheuristiquesMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simpleVoisinage dex {0, 1}N :Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simpleVoisinage dexV( )x {0, 1}N :: ensemble des chaînes binaires à une distance (deHamming) 1.Pourx 01101, V(x ) {Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simpleVoisinage dexV( )x {0, 1}N :: ensemble des chaînes binaires à une distance (deHamming) 1.Pourx 01101, V(x ) {011000111101001001010010111101}Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simpleVoisinage dexV( )x {0, 1}N :: ensemble des chaînes binaires à une distance (deHamming) 1.Pourx 01101, V(x ) {011000111101001001010010111101}Taille du voisinage de chaque solutionSébastien Verelx:Métaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simpleVoisinage dexV( )x {0, 1}N :: ensemble des chaînes binaires à une distance (deHamming) 1.Pourx 01101, V(x ) {011000111101001001010010111101}Taille du voisinage de chaque solutionSébastien Verelx:NMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simpleExerciceCoder la recherche locale aléatoireA cher le graphique du parcours de la recherche (nbd'évaluationsvs. valeur fonction)Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifHill-Climbing (HC) (ou steepest-descent)Heuristique d'exploitation maximale.Hill ClimbingChoisir solution initiale s SrépéterChoisirs0s V( )telle queAlgorithme decomparaisonf (s ) est0maximales sbase demétaheuristique0jusqu'à sOpérateur local deoptimum localSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUne variante : rst-improvementPremière améliorationChoisir solution initiale s Srépéters0s V( ) aléatoirement0si ( ) ( ) alors0 Choisirfs fss sn sijusqu'à soptimum local OU nbr d'éval.Sébastien Verel maxNbEvalMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simpleExerciceCoder la recherche rst-improvementEvaluer les performances de la recherche rst-improvementSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifHill-Climbing (HC) (ou steepest-descent)Quel est l'inconvénient majeur du Hill-Climbing ?Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifHill-Climbing (HC) (ou steepest-descent)Peut-on imaginer des situations où ce n'est qu'un faibleinconvénient ?Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifUn exemple très simpleExerciceChanger la fonction d'évaluation (UBQP) :f (x ) N XNXi j ( i j )mod21avecqij ( 1) i j3 7qij xi xj116Evaluer les performances de la recherche rst-improvment.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifPoints critiques dans la conception d'une recherche localeReprésentation des solutions :codage plus ou moins redondant,introduction dans le codage de connaissances au problème,complexité du codage, de l'évaluation (évaluationincrémentale),etc.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifPoints critiques dans la conception d'une recherche localereprésentation des solutions : redondance, introductionconnaissance du problème, complexité.voisinage : taille, continuité :sfs fss s s op sfonction f guide vers l'optimalité0s0 V( ), δ( ( ), ( )) 00V( ) { ( )} choisir un voisinAutres : générateur aléatoire ( !), choix d'implémentation(évaluation incrémentale), critère d'arrêt.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifPoints critiques dans la conception d'une recherche localeVoisinage :taille :V(s ) {s 0continuité :s0 op (s )}s S et s V(s ),P (δ(f (s ), f (s )) ) est grande0Pour tout0une idée pour bon voisinage :prob. trouver meilleure solution dans le voisinagetrouver meilleure solution à l'extérieurSébastien VerelMétaheuristiques prob.
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifPoints critiques dans la conception d'une recherche localef guide vers l'optimalité :f (x ) est grand, plus x est proche de l'optimum.fonctionplus choisir un voisin :Choisir un voisin tel que la probabilité de trouver une bonnesolution depuis ce voisin est grande.Autres : générateur aléatoire ( !), choix d'implémentation(évaluation incrémentale), critère d'arrêt.Sébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifMetaheuristicsRandom search / Hill ClimbingAlgorithme 1 Random walkChoose randomly initial solutions SrépéterChooses s0s0s V( )Algorithme 2 Hill-climbingChoose randomly initial solutions Srépéterrandomly V(s ) suchf (s ) is maximals sjusqu'à s local optimumChoose00jusqu'à .Sébastien VerelMétaheuristiquess0as
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifMetaheuristicsRandom search / Hill ClimbingHill-climbingRandom walkObjective functionObjective functionlocal optimumlocal optimumsearch spacesearch spacemaximal exploration ,maximal exploitation ,diversi cationintensi cationMain issue : exploration / exploitation tradeo escape from local optima, etc. simulated annealing, tabu searchSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRecuit Simulé (Simulated Annealing)Utilisé depuis les années 80,Metropolis (1953) simulation du refroidissement de matériaux(Thermodynamique)Kirkpatricket al (IBM 1983) utilisation pour la résolution deproblème d'optimisation.But : échapper aux optima locauxPrincipe : probabilité non nulle de sélection d'une solution voisinedégradéeSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRecuit Simulé : analogieSystème physiqueProblème d'optimisationEnergiefonction objectifEtats du systèmesolutionÉtats de basse énergiebonne solutionTempératureparamètre de contrôlePerformanceOptimum localSolutionsSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRecuit Simulés S et temperature initiale TChoisir solution initialerépéterchoisir aléatoirementsi 0 alorss ss0sfs00sinonu nombre aléatoire de [0, 1]si u e T alorss s 0n sin siupdate temperaturefs V( ), ( ) ( )Tjusqu'à Critère d'arrêt véri éSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRecuit Simulé : remarquesSi 0alors la probabilité exp(la di érencefs0T ) est proche de 0 lorsque : fs ( ) ( ) est grandela temperature est petiteConséquences :lorsque température grande (début de la recherche) : recherche aléatoirelorsque température petite ( n de la recherche) : Hill-ClimbingSébastien VerelMétaheuristiques
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRecuit Simulé : température initialeEvaluerfsfs0 0 ( 0 ) ( 0 )Choisir:n (grand si possible) solutions aléatoires initiales ssune solution voisine0calculer la moyenne deTempérature initialeT000 0telle quequalité médiocre (τ0qualité bonne sur l'échantillone 0τ0 T0désiré : 0.50) : démarrage à haute température(τ0 0.20) : démarrage à basse températureSébastien VerelMétaheuristiqueset
Problèmes d'optimisationMétaheuristiques standardsPaysage AdaptatifRecuit Simulé : décroissance de température décroissance suivant une loi géométriquesouvent 0.8 α 1.0Tk 1 αTkChangement par pallier de température suivant l'une des deuxconditions :N perturbations acceptées (mouvements de solution)100.N perturbations tentées (mouvement ou non mouvement)où N est un paramètre qui décrit la taille du problème (nombre de12.villes, de variables.)Sébastien VerelMétaheuristiques
Metaheuristisques de recherche locale Algorithmes à population de solutions Algorithmes Evolutionnaires (EA) : Holland 1975 et même avant Algorithmes d'essaims particulaires (PSO) : R. Ebenhart et J. Kenned
qu'empoisonnent encore les hypocrisies de la Cabale. Ce que nous savons vraiment sur Molière et sur sa famille repose essentiellement sur les recherches d'Eudore Soulié. Ces recherches datent d'un siècle et se sont accrues, pendant ces dernières cent années, des découvertes de chercheurs nombreux qu'aidèrent parfois la chance et le hasard.
loi n 47-06 relative a la fiscalite des collectivites locales dahir n 1-07-195 du 19 kaada 1428 (30 novembre 2007) d.g.i. 26-12-2007 2 premiere partie regles d’assiette, de recouvrement et de sanctions titre i - regles d’assiette chapitre i des taxes des collectivites locales
Partie 2. Étude de l’impact financie global de la c ise du ovid-19 sur les collectivités locales 29 1. Malgé la stabilité des impôts ménages et des concou s financie s de l’Etat, les ecettes de fonctionnement des collectivités locales seront fortement affectées en 2020 avant un rebond partiel en 2021 et 2022 29
Conciliación y Arbitraje, tanto en el ámbito federal como local. Siendo así que los conflictos de naturaleza laboral pasan a ser competencia del Poder Judicial Federal y de los poderes judiciales locales, por lo que se crearán tribunales laborales federales y locales para tal fin. 10. Centro Federal de Conciliación y Registro Laboral .
y las personas. Consciente de que fallar a las generaciones futuras no es una opción, el movimiento municipal se reunirá bajo el lema "Los gobiernos locales y regionales avanzan con un mismo latido". La Cumbre Mundial reunirá a los líderes locales y a los actores internacionales para afrontar un escenario de avance.
latif des travaux exécutés au cours de l'année écoulée en matière de recherches sur le charbon ainsi que des résultats les plus importants obtenus dans ce domaine. d'une bifurcation ou des dégâts matériels ont plus d'une fois nécessité des interruptions. Lors des travaux de creusement, l'attention s'est
Vol. 4 of Recherches au pays d’Aštata, Emar VI. Synthèse 28. Paris: Éditions Recherches sur les Civilisations, 1987 EncJud Encyclopedia Judaica. Edited by Fred Skolnik and Michael Berenbaum. 2nd ed. 22 vols. Detroit : Macmillan Reference USA, 2007 HACL History, Archaeology, and Culture of the Levant HCCT Tsukimoto, Akio.
2 EMMANUEL PEYRE [5] Hauteurs et mesures de Tamagawa sur les variétés de Fano, Duke Math. J. 79 (1995), no 1, 101–218. [6] Terme principal de la fonction zêta des hauteurs et torseurs universels, Prépubli cation (1996), 1–36. 2. Travaux de recherches L’ensemble de mes travaux et projets de recherches est axé sur deux thèmes principaux
