[PDF] [PDF] Métaheuristiques - TEL archives ouvertes

[PDF] Métaheuristiques - GERAD

Une métaheuristique est un algorithme d'optimisation visant à résoudre des problèmes d'opti- misation On peut modifier les poids wi au cours de l' algorithme

[PDF] Introduction aux métaheuristiques - GERAD

▻ Les matheuristiques sont l'objet du cours du 13 mars MTH6311: Introduction aux métaheuristiques 9/25 Page 10 1/2

[PDF] LES METAHEURISTIQUES€:

RESUME : Durant ces dernières années, plusieurs métaheuristiques ont prouvé leur efficacité pour la résolution de cours de ces vingt dernières années

[PDF] Metaheuristiques et optimisation combinatoire - eCursus - Université

13 fév 2019 · Métaheuris- tiques Problèmes d'optimisation Heuristiques Métaheuristiques Algorithmes évolution- naires Optimisation multi- Objectifs 3/33

[PDF] Métaheuristiques - TEL archives ouvertes

Métaheuristiques : stratégies pour l'optimisation de la production de biens et de services Activités pédagogiques Encadrements et supports de cours

[PDF] Métaheuristiques pour loptimisation combinatoire Plan du cours

– mimétisme – heuristique – méta heuristique – minimum local / global – méthodes (in)complètes – codage solution – landscape – structure de voisinage – 

[PDF] Métaheuristiques - LISIC

12 oct 2012 · Aléatoirement Construction de solution (pas dans ce cours) Méthodes exactes ( pas dans ce cours) ou Sébastien Verel Métaheuristiques 

[PDF] Les méthodes de résolution approchées pour le - Cedric-Cnam

La métaheuristique Variable Neihborhood Descent (VND) La métaheuristique Variable Neihborhood Search (VNS) La métaheuristique Tabou Amélie Lambert  

Métaheuristiques hybrides pour la résolution du - Archipel UQAM

Les métaheuristiques représentent alors une alternative intéressante pour trouver une solution de qualité acceptable dans des délais très courts Toutefois, il est 

[PDF] module de exp(ix)

[PDF] méthodes métaheuristiques

[PDF] algorithme heuristique pdf

[PDF] généralités sur les systèmes automatisés de production

[PDF] différence entre heuristique et métaheuristique

[PDF] structure fonctionnelle d'un système automatisé

[PDF] méthodes heuristiques d'optimisation

[PDF] définition d'un système automatisé de production

[PDF] méthodes heuristiques et métaheuristique d'optimisation

[PDF] méthode heuristique optimisation

[PDF] système automatisé de production sap

[PDF] les métaheuristiques en optimisation combinatoire

[PDF] système automatisé de production pdf

[PDF] système automatisé de production ppt

[PDF] cours aide soignante module 1 pdf

M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

M´etaheuristiques

strat´egies pour l"optimisation de la production de biens et de services

Marc Sevaux

Universit´e de Valenciennes et du Hainaut-Cambr´esis Laboratoire d"Automatique de M´ecanique, d"Informatique

Industrielles et Humaines du CNRS (UMR CNRS 8530)

Le Mont Houy - Bat Jonas 2

F-59313 Valenciennes cedex 9 - France

Marc.Sevaux@univ-valenciennes.fr

Habilitation `a Diriger des Recherches

1erjuillet 2004, Valenciennes

1 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Contenu de la pr´esentation

Contenu de la pr´esentation

Curriculum Vitae

?Activit´es p´edagogiques ?Activit´es de recherche ?Synth`ese scientifique ?Perspectives 2 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Curriculum Vitae

Curriculum vitae

Informations personnelles

?35 ans ?Mari´e, 3 enfants

Depuis septembre 1999

?Maˆıtre de conf´erences ?61esection ?IUT de Valenciennes - Dept. OGP Cambrai ?LAMIH - Equipe Syst`emes de Production 3 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Curriculum Vitae

Parcours et Formation

DEUG, Licence et Maˆıtrise, IMA (1992-1994)

?DEA Informatique et Recherche Op´erationnelle, Paris 6(1994-1995) ?Doctorat, Universit´e de Paris 6 / EMN (1996-1998)

?Etude de deux probl`emes d"optimisation en planification etordonnancement- Direction : S. Dauz`ere-P´er`es- Pr´esident : Ph. Chr´etienne- Rapporteurs : Y. Crama et J.-B. Lasserre- Examinateurs : M.-C. Portmann et Ch. Prins

?Ing´enieur de recherche, EMN (1998-1999) ?Maˆıtre de conf´erences, UVHC (depuis 1999) 4 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es p´edagogiques

Activit´es p´edagogiques

Enseignements

?Encadrements et supports de cours ?Administration de l"enseignement 5 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es p´edagogiques

Enseignements

Enseignements

Avant l"UVHC

?IMA - Informatique - (1992-1993) 60h ?ITEC - Maths, Physique, Chimie - (1993-1994) 240h ?EMN - PL, Gest. Prod. - (1997-1999) 90h

A l"UVHC

?Qualit´e, IUT 1, 1999-2000, 75h/an ?Programmation lin´eaire, EIGIP (2000-2002) 20h/an ?Math´ematiques de la d´ecision, Master 1 (2002-2003) 20h/an ?Informatique, IUT 1 (depuis 1999) 60h/an ?Recherche op´erationnelle, IUT 2 (depuis 1999) 110h/an 6 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es p´edagogiques

Encadrements et supports de cours

Encadrements et supports de cours

Encadrements d"´etudiants

?Stages industriels (2 `a 3 par an) ?Projets internes ou industriels (2 par an) ?Lancement du jeu d"entreprise

Supports de cours

?Supports de cours ´electronique (RO, MD) ?Passage des cours en ligne (Info) ?Deux livres 7 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es p´edagogiques

Administration de l"enseignement

Administration de l"enseignement

Elu au conseil restreint de l"IUT - depuis 2003

Supervision de l"attribution des postes, Enseignants /

Chercheurs, Enseignants, ATER, Vacataires

?Responsable des relations internationnales - depuis 2003Stagiaires `a l"´etranger, invitations d"enseignants

?Responsable de l"organisation des projets - 2001-2003Projets en entreprise, concours national OGP, jeu d"entreprise

?Responsable des visites en entreprise - 1999-20014 `a 5 visites par an

Responsable p´edagogique

Modules 9 (Informatique) et 17 (Recherche Op´erationnelle). 8 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Activit´es de recherche

Animation de la recherche

?Organisation de manifestations ?Visibilit´e et rayonnement ?Evaluation de la recherche ?Contrats, projets et financements ?Encadrement de 3ecycle 9 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Evolution des activit´es

1997
2003

20041996

1998
1999
2000

20022001

Linear and integer programmingReactive PlanningProduction Planning

Control Policies

Robust scheduling

1-Machine # Late Jobs //-Machine Weighted # Late Jobs

1-Machine Weighted # Late Jobs 1-Machine TWT

Bi-objective CARP

CARP

Robust VRP

Heuristics

Metaheuristics

Multi-objective optimisation

10 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Animation de la recherche

Le groupe EU/ME

EU/ME on metaheuristicsEuropean chapter

EU/ME, European chapter on Metaheuristics

Th`eme: m´etaheuristiques, cr´eation 2000, 750 membres ?Coordination avec K. S¨orensen ?Administration/Animation ?Gestion du site web ?Relations avec EURO ?Mailing list, Forum, Workingpapers, Annonces, Annuaire www.euro-online.org/eume/ 11 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Animation de la recherche

Activit´es du groupe EU/ME

EU/ME on metaheuristicsEuropean chapterEU/ME, European chapter on Metaheuristics ?EU/MEetings : 1 manifestationinternationale par an depuis 2001 ?Un livre ´edit´e LNEMS ?Un num´ero sp´ecial EJOR ?Une session MIC 2001 ?Deux "creative sessions"MIC 2001, MIC 2003 12 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Animation de la recherche

Activit´es futures du groupe EU/ME

EU/ME on metaheuristicsEuropean chapterEU/ME, European chapter on Metaheuristics ?Un cluster "M´etaheuristiques", INFORMS Denver 2004 ?EU/MEeting : University of Nottingham 3-4 Novembre 2004 ?libOR : une nouvelle version de la OR-Library ?On-line BibTeX : r´ef´erences en ligne ?EURO mini-conference, VNS (Mladenovic & Moreno-P´erez) ?MIC 2005 : EU/ME creative session 13 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Organisation de manifestations

Organisation de manifestations

A Valenciennes

?Pentom 2003, IFIP FEATS 2001 ?R´eunion Bermudes 2001, Journ´ees GRP 2000

En dehors de Valenciennes

?EU/ME on metaheuristicsEuropean chapterEU/MEetings : en association avec un groupe local Londres 2001, Paris 2002, Anvers 2003, Nottingham 2004

Sessions / Cluster de sessions

?EU/ME on metaheuristicsEuropean chapterMIC, Porto 2001

Th`eme m´etaheuristiques et ordonnancement

?EU/ME on metaheuristicsEuropean chapterINFORMS, Denver 2004

Th`eme m´etaheuristiques : 4 sessions

14 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Visibilit´e et rayonnement

Visibilit´e et rayonnement

Collaborations

?EU/ME on metaheuristicsEuropean chapterUniversit´e d"Anvers ?EU/ME on metaheuristicsEuropean chapterUniversit´e Polytechnique de Hong-Kong ?Massachusetts Institute of Technology ?UTT, EMN, UBP, IMA

Soci´et´es et groupes de recherche

?INFORMS, SOGESCI-BVWB, ROAD´eF, EU/ME on metaheuristicsEuropean chapterEU/ME ?GDR-MACS/STP, Club EEA, PM2O, GOThA

Comit´es scientifiques

?EU/ME on metaheuristicsEuropean chapterMIC"05, PENTOM"05, FRANCORO"04, EU/ME on metaheuristicsEuropean chapterEURO XX ?ISS"04, EU/ME on metaheuristicsEuropean chapterMIC"03, EU/ME on metaheuristicsEuropean chapterESI XXI, PENTOM"03, EU/ME on metaheuristicsEuropean chapterMIC"01 15 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Evaluation de la recherche

Evaluation de la recherche

Editeur associ´e et fonction d"´edition

?EA : Int. J. of Computational Intelligence (IJCM) ?EA : Int. J. of Signal Processing (IJSP) ?EU/ME on metaheuristicsEuropean chapterEdition d"un num´ero sp´ecial EJOR ?EU/ME on metaheuristicsEuropean chapterEdition d"un livre (LNEMS)

Rapporteur de revues scientifiques

?EJOR, JOH, AOR, IEEE-SMC, EAAI, Kluwer ?4OR, IJMS, IEEE-TRA, INFOR, RCIM, IIE Trans, DSS,Rairo, JESA, Hermes

Commission de sp´ecialistes

61esection - Suppl´eant en 2003, Titulaire depuis 2004

16 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Contrats, projets et financements

Contrats, projets et financements

Alcatel - 12 mois - 2003-2004

Algorithmes d"optimisation du trafic

?SNCF - 24.2ke- 3 ans - 2000-2003

Th`ese CIFRE - Yann Le Qu´er´e

?Centre Hospitalier - 48ke- 3 ans - 2000-2003

Optimisation des flux logistiques

?SART - 42.7ke- 18 mois - 2003-2004 ?MOST - 27.4ke- 18 mois - 2001-2002 ?MAE - MIC 2003 (850e) et IEPM 1999 (530e) ?EU/ME on metaheuristicsEuropean chapterPAI - Univ. Polytech. Hong-Kong - 8ke- 2003-2004 17 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Activit´es de recherche

Encadrements de 3ecycle

Encadrements de 3ecycle

Th`ese de doctorat

?F. Beugnies - 2003-2006 ?K. Bouamrane - 2003-2006 ?Y. Le Qu´er´e - 2000-2004 (8 septembre 2004) DEA ?C. Bian - 2003-2004 ?Y. Qiu - 2003-2004 ?J. Saint-Mars - 2002-2003 ?C. Tilleul - 2000-2001

Jury de th`ese

?Comit´e d"accompagnement : N. Soua¨ı (2006) ?EU/ME on metaheuristicsEuropean chapterRapporteur : K. S¨orensen (13 juin 2004) ?Examinateur : W. Ramdane-Ch´erif (12 d´ecembre 2003) 18 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Synth`ese scientifique

M´etaheuristiques

Strat´egies pour l"optimisation

de la production de biens et de services ?Intensification et diversification ?Algorithme m´em´etique ?Scatter search ?GA|PM ?Probl´ematiques ?Conclusion 19 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Synth`ese scientifique

Pourquoi les m´etaheuristiques

Probl`emesNP-difficiles

?Alternative efficace ?aux heuristiques ?aux m´ethodes exactes ?Besoin de rapidit´e (d´eveloppement et r´esolution)

Un outil formidable

?Cadre g´en´eral "facile" ?`a appliquer ?`a adapter ?Outil de r´esolution pratique 20 M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Synth`ese scientifique

Intensification et diversification

M´etaheuristique : concepts de base

Intensification

?Am´eliorer la qualit´e d"une ou plusieurs solutions

Diversification

?Explorer un espace de solutions plus large

Equilibre

?Trop d"intensification→optima locaux ?Trop de diversification→exploration trop longue 21
M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Synth`ese scientifique

Algorithme m´em´etique

Algorithme m´em´etique (MA) [Moscato 1989]

El´ements de base

?Population: plusieurs solutions sont contruites et manipul´ees en parall`ele ?S´election: favoriser les individus de la population les mieux adapt´es (meilleurfitness) ?Croisement: combiner deux solutions parents pour produire un ou deux enfants ?Recherche locale: am´eliorer les solutions enfants produites

Technique

?Remplacer la mutation par une recherche locale syst´ematique 22
M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Synth`ese scientifique

Algorithme m´em´etique

Algorithme MA

(version incr´ementale) 1: initialise: generate an initial populationPof solutions

2:repeat

3: selection: choose 2 solutionsxandx? 4: crossover: combinexandx?to form a child solutiony 5: local search: apply a local search operator ony

6:choose an individualy?to be replaced in the population

7:replacey?byyin the population

8:untilstopping criterion satisfied

23
M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Synth`ese scientifique

Algorithme m´em´etique

Analyse de l"algorithme

Algorithme extensible

?Taux de recherche locale ?Ajout d"un op´erateur de mutation ?Taux de mutation ?Combinaisons infinies

Intensification

?S´election ?Recherche locale

Diversification

?Remplacement ?Croisement? ?Mutation 24
M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Synth`ese scientifique

Scatter search

Scatter search (SS) [Glover 1994]

El´ements de base

?Populationimportante ?Ensemble de r´ef´erencede taille r´eduite ?Mesure dediversit´e ?Recherche locale

Technique

?G´en´eration de nouvelles solutions par combinaison jusqu"`a

´epuisement de l"ensemble de r´ef´erence

?Remplacement d"une partie de l"ensemble de r´ef´erence 25
M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Synth`ese scientifique

Scatter search

Algorithme SS

1:initialise: generate an initial improved population

2:

Selecta diverse subsetR(Reference set)

3:whilestopping criterion is not satisfieddo

4:A←R

5:whileA?=∅do

6: combinesolutions (B←R×A) 7: improvesolutions ofB 8: updateR(keep best solutions fromR?B)

9:A←B-R

10:end while

11:

Removehalf of the worst solutions inR

12:

Addnew diverse solutions inR

13:end while

26
M´etaheuristiques : strat´egies pour l"optimisation de laproduction de biens et de services

Synth`ese scientifique

Scatter search

Intensification et diversification

quotesdbs_dbs16.pdfusesText_22