Université des Sciences et de la Technologie Oran, Mohamed Boudiaf

Université des Sciences et de la Technologie Oran, Mohamed Boudiaf.

Faculté de Sciences / Département d’Informatique

Recherche à voisinages variables

MOUEDDEN Abdelkader – M2 RFIA

Module : Optimisation Avancée

Enseigné Par : Mr. BENYETTOU.M

2012-2013

PLANIntroductionHistoriqueStructure de voisinage et minimum localDéfinitionAlgorithmeExempleAvantages/InconvénientsConclusion

PLANIntroductionHistoriqueStructure de voisinage et minimum localDéfinitionAlgorithmeExempleAvantages/InconvénientsConclusion

IntroductionRésoudre un problème d’optimisation

combinatoire , c’est trouver l’optimum d’une fonction (Max/Min)

Espace de solution très largeApplications(production industrielle,

transports, économies)Métaheuristique (temps de calcul)Recherche à voisinages variables

PLANIntroductionHistoriqueStructure de voisinage et minimum localDéfinitionAlgorithmeExempleAvantages/InconvénientsConclusion

HistoriqueMladenovic(1995): Algorithme de voisinage

variable (une nouvelle métaheuristique pour l’optimisation combinatoire)

Mladenovic et Hansen en 1997: ont proposé la Recherche à Voisinages Variables

Université de Brunel - London UK

PLANIntroductionHistoriqueStructure de voisinage et minimum localDéfinitionAlgorithmeExempleAvantages/InconvénientsConclusion

Structure de voisinage et minimum localS un ensemble de solutions à un problème

d’optimisationf la fonction objectifUne structure de voisinage est une fonction

N qui associe un sous-ensemble de S à toute solution s ϵ S

Une solution s’ ϵ N(s) est dite voisine de s

Une solution s ϵ S est un minimum local relativement à la structure de voisinage N si :

Une solution s ϵ S est un minimum global si :

Structure de voisinage et minimum local

PLANIntroductionHistoriqueStructure de voisinage et minimum localDéfinitionAlgorithmeExempleAvantages/InconvénientsConclusion

DéfinitionRVV est une métaheuristique récente pour la résolution

de problèmes d’optimisation combinatoirele changement de voisinage au sein d’une recherche

localeRVV utilise les constats suivants :I. Un minimum local par rapport à un voisinage n’est pas

nécessairement un minimum par rapport à un autreII. Un minimum global est un minimum local par rapport à

tous les voisinages possiblesIII. Pour de nombreux problèmes, les minimaux locaux par

rapport à un ou à plusieurs voisinages sont relativement proches les uns des autres.

PLANIntroductionHistoriqueStructure de voisinage et minimum localDéfinitionAlgorithmeExempleAvantages/InconvénientsConclusion

Algorithme Entrée: Structures de voisinage Nk ,k = 1..kmax

Choisir une solution s* Répéter: K = 1 Répéter Générer aléatoires une solution s’ de Nk(s*) s’’ = Recherche_Locale(s’) Si f(s’’) < f(s*) alors: s* s’’ k 1 Si non k k+1 fin Si Jusqu’à ‘’ k > kmax ‘’ Jusqu’à ‘’la condition d’arrêt est vraie’’

PLANIntroductionHistoriqueStructure de voisinage et minimum localDéfinitionAlgorithmeExempleAvantages/InconvénientsConclusion

Exemple

N1 consiste à changer la couleur d’un sommet en conflitN2 consiste à choisir un sommet W voisin du sommet V en conflit, à condition que W soit libre et de permuter les couleur de V et WOn a F(x) = 2:(A,B) et (F,G)

Exemple

F(x) = 1:(F,G)

Exemple

F(x) = 1:(F,E)

Exemple

Solution précédente

Exemple

F(x) = 0: Pas de conflit

PLANIntroductionHistoriqueStructure de voisinage et minimum localDéfinitionAlgorithmeExempleAvantages/InconvénientsConclusion

Avantages et InconvénientsAvantagesElle est simple à utilisée puisqu’elle est basée

sur un principe simple qui nous permet de changer le voisinage lorsqu’on se retrouve bloqué dans un minimum local

Etant très généraliste, elle s’applique à un grand nombre de problèmes d’optimisation combinatoire

Elle est efficace : les meilleures solutions sont obtenues en un temps de calcul modéré

Avantages et InconvénientsInconvénientsElle est souvent moins puissante que des

méthodes exactes sur certains types de problèmes

Elle ne garantie pas non plus la découverte d’un optimum global en un temps fini

Explore un nombre grand de voisinages

PLANIntroductionHistoriqueStructure de voisinage et minimum localDéfinitionAlgorithmeExempleAvantages/InconvénientsConclusion

ConclusionLes métaheuristiques étant très généralistes,

elles peuvent être adaptées à tout type de problème d’optimisation

Elles sont souvent moins puissantes que des méthodes exactes sur certains types de problèmes

Elles ne garantissent pas non plus la découverte de l’optimum global en un temps fini

Bibliographie1. P.Hansen and N.Mladenovic. An introduction to variable

neighbourhood search. In S. Voss, S. Martello, I. H. Osman, and C. Roucairol, editors, Meta-heuristics, Advances and trends in local search paradigms for optimization, pages 433-458. Kluwer Academic Publishers.1999.

2. P. Hansen and N. Mladenovic. variable neighbourhood search. In F . Glover and G. A. Kochenberger , editors , Handbook of Metaheuristics ,chapter 6. Kluwer, 2003.

3. C. Helmberg and F . Rendl. Solving quadratic (0,1)- problems by semidefinite programs and cutting plantes .Mathematical Programming , 82 :291-315, 1998.

4. N.Mladenovic and P.Hansen. variable neighbourhood search. Comput. Oper . Res .; 4(11) :1097-1100,1997

5 : http://fr.wikipedia.org/wiki/M%C3%A9taheuristique