Recherche tabou








télécharger 107.64 Kb.
titreRecherche tabou
page1/6
date de publication19.12.2016
taille107.64 Kb.
typeRecherche
l.21-bal.com > loi > Recherche
  1   2   3   4   5   6

  1. Introduction :

L'optimisation combinatoire occupe une place très importante en recherche opérationnelle, en mathématiques discrètes et en informatique en générale. Son importance se Justifie d'une part par la grande difficulté des problèmes d'optimisation [1].Et d'autre part par de nombreuses applications pratiques pouvant être formulées sous la forme d'un problème d'optimisation combinatoire[2] .Bien que les problèmes d'optimisation combinatoire soient souvent faciles à définir, ils sont généralement difficiles à résoudre En effet, la plupart de ces problèmes appartiennent à la classe des problèmes NP-difficiles et ne possèdent donc pas à ce jour de solution algorithmique efficace valable pour toutes les données[3].

Étant donnée l'importance de ces problèmes, de nombreuses méthodes de résolution ont été développées en recherche opérationnelle (RO).

Ces méthodes peuvent être classées sommairement en deux grandes catégories :

  • les méthodes exactes (complètes) : qui garantissent la complétude de la résolution ;

  • les méthodes approchées (incomplètes):qui perdent la complétude pour gagner en efficacité.

Le principe essentiel d'une méthode exacte consiste à effectuer une énumération explicite de toutes les solutions (c'est-à-dire de les tester une à une, méthode envisageable pour tous les problèmes à variables à valeurs bornées). Cette méthode montre très vite ses limites dès que le nombre de variables augmente puisque sa complexité est en kn où k représente le nombre de valeurs que peut prendre une variable et n le nombre de variables du problème [4].

Parmi les méthodes exactes, on trouve La programmation dynamique et le Branch & Bound etc.

Par contre Les méthodes approchées qui a pour but de trouver une solution de bonne qualité (C’est-à-dire assez proche de l'optimale) en un temps de calcul raisonnable sans garantir l'optimalité de la solution obtenue. Elles sont fondées principalement sur diverses heuristiques, souvent spécifiques à un type de problème.

Les méta-heuristiques constituent une autre partie importante des méthodes approchées et ouvrent des voies très intéressantes en matière de conception de méthodes heuristiques pour l’optimisation combinatoire.est pour cela on constaté deux approches ont clairement démontré leur utilité dans de nombreux domaines.

La première de ces approches, appelée Recherche Locale ou bien (voisinage), est couramment utilisée de puis plus de 20 ans et comprend, entre autres :

  1. la méthode de descente ;

  2. Le recuit simulé ;

  3. Recherche tabou ;

  4. Méthode du bruitage ;

  5. Les algorithmes d’acceptation avec seuil.

La deuxième approche, appelée Méthode Évolutive, est plus récente puisqu’elle date du début des années 90. Elle s’est particulièrement fait connaître par :

  • les algorithmes génétiques ;

  • les algorithmes de colonies de fourmis etc.

A cet exposé nous intéressons sur la première approche qui est ‘les méthodes de recherche locale’.


  1. notions de base :


2.1) Quelques définitions :

  • Une solution : est une affectation de toutes les variables du problème.

  • Une solution optimale : est une solution de coût minimal (ou maximal).

  • Un mouvement : est une opération élémentaire permettant de passer d'une solution a une solution voisine (exemple : changer la valeur d'une variable, échanger deux variables).

  • Le voisinage : d'une solution est l'ensemble des solutions voisines, c'est a dire l'ensemble des solutions accessibles par un mouvement (et un seul).

  • Un essai : est une succession de mouvements.

  • Une recherche locale : est une succession d’essais. [5]

2.2) optimisation combinatoire :

On peut trouver de nombreuses définitions de problèmes d’optimisation combinatoire.

En mathématiques, l'optimisation recouvre toutes les méthodes qui permettent de déterminer l'optimum d'une fonction, avec ou sans contraintes.

Dans le cas d’une minimisation, un problème d’optimisation se représentera de la forme suivant :

Minimiser f(s) (f : fonction à optimiser) ;

Avec g(s)<=0 (m contraintes d’inégalités) ;

Et h(s)=0 (p contrainte d’égalités). [6]

En théorie, un problème d'optimisation combinatoire se définit par l’ensemble de ses instances, souvent infiniment nombreuses. Dans la pratique, le problème se ramène à résoudre numériquement l’une de ces instances, par un procédé algorithmique.

A chaque instance du problème est associé un ensemble discret de solutions S, un Sous-ensemble X de S représentant les solutions admissibles (réalisables), ainsi qu’une Fonction de coût f (appelée aussi fonction objectif).

f assigne à chaque solution s X le nombre f (s).

Résoudre un problème d’optimisation combinatoire consiste alors à trouver une solution

sX optimisant la valeur de la fonction de coût f.

Formellement, on cherche donc s* X tel que f(s*) ≤ f(s) pour tout s X.

Une telle solution s* s'appelle une solution optimale, ou un optimum global.

Il existe une seconde formalisation du problème d’optimisation combinatoire, plus générale, qui inclue la notion de contraintes et d’affectation de valeurs à des variables. En voici la définition. Soit :

  • un ensemble de variables

  • un ensemble de domaines de définitions

  • un ensemble de contraintes C sur les variables (par exemple, des inéquations, ou bien l’obligation que toutes les variables prennent des valeurs différentes)

  • une fonction objective f que l’on cherche à minimiser :


L’ensemble S des solutions possibles peut alors se définir comme :

S = { tels que , et tels que s satisfasse toutes les contraintes C}
Les problèmes d'affectation sous contraintes possèdent de nombreuses applications pratiques, comme l'affectation de ressources, le groupement, la classification, la planification, l'emploi du temps et l'ordonnancement, dans des domaines très variés… [7]

2.3) Les heuristiques :

Les méthodes heuristiques sont particulièrement utiles pour les problèmes qui nécessitent une solution en temps réel (ou très court) ou pour résoudre des problèmes difficiles sur des instances numériques de grande taille. Certaines sont ciblées sur un problème particulier (heuristiques spécifique). [4]

2.4) Les méta-heuristiques :

2.4.1) Étymologie :

Ce mot vient de la combinaison de deux mots grecs:

-Le verbe heuriskein : « trouver » ;

- le suffixe méta : « au-delà », « dans un niveau supérieur ». [4]

2.4.2) Définition :

Une méta-heuristique1 est constituée d'un ensemble de concepts fondamentaux.qui permettent d'aider à la conception de méthodes heuristiques pour un problème d'optimisation. [4]

2.4.3) Propriétés fondamentales et fonctionnement :

Elles sont :

  • Efficaces : elles permettent d’explorer efficacement l’espace de recherche.

  • Non déterministe : puisqu’elles ne donnent aucune garantie d’optimalité

Elles possèdent deux autres propriétés intéressantes :

  • Elles peuvent des mécanismes qui permettent d’éviter d’être bloqué dans des régions de

L’espace de recherche. C’est leur capacité à s’échapper d’un minimum local

  • Les méta-heuristiques peuvent faire usage de l’expérience accumulée durant la recherche de l’optimum.

L'exécution des méta-heuristiques se déroule en trois phases :

Diversification – Intensification – Mémoire

  • La diversification regroupe les actions ayant pour but de récolter des informations sur le problème dans Un ensemble défini (ou espace local) lors de l'intensification.

  • L'intensification vise à utiliser les informations de la mémoire et celles récoltées lors de la phase de Diversification afin de définir les meilleurs espaces de recherche locaux futurs. Et de les faire parcourir de Façon optimale par les fonctions objectifs.

  • La mémoire est le support de l'apprentissage permettant à l'algorithme de ne tenir compte que des zones où l'optimum est susceptible de se trouver et de garder en mémoire les résultats passés.

Les méta-heuristiques progressent itérativement et alternativement entre les phases de

Diversification, d'intensification et d’apprentissage [4].
2.4.4) classement :

Pour classer l’ensemble ces meta-heuristiques, il existe en realite plusieurs possibilites (ce qui est notamment ce qui du au fait qu’elles sont le fruit de travaux en recherche operationnelle et en intelligence artificielle). Le classement depend donc du point de vue. Ci-apres, une classification possible de ces algorithmes. On distingue :

  • Constructives (algorithmes glouton, methode Pilote, GRASP)

  • Recherche locale (algorithmes de descente appeles aussi methodes d’ameliorations iteratives, recuit simule, algorithme a seuil, recherche Tabou, methode de bruitage)

  • Evolutionnistes (algorithmes genetiques, algorithmes d'evolution, recherche dispersee, methode des chemins, systemes de fourmis)

  • Reseaux de neurones (Modele de Hopfield-Tank, machine de Boltzmann, reseau auto-adaptatif, reseau elastique)

  1. La recherche locale :

3.1) le principe de recherche locale :

Une méthode de recherche locale est basée sur l’évolution itérative d’une solution unique. Le passage d’une solution vers une autre se fait grâce à la définition de structure de voisinage qui est un élément très important dans la définition de ce type de méthode.

Nous résumons le principe dans les points suivants :

  1. partir d'une solution sinon approchée du moins potentiellement bonne et d'essayer de l'améliorer itérativement.

Pour améliorer une solution on ne fait que de légers changements (on parle de changement local, ou de solution voisine).

  1. relancer la méthode plusieurs fois en changeant le point de départ pour avoir plus de Couverture.

  2. tout problème est considérée comme un problème d'optimisation (même les problèmes de satisfaction : le coût à optimiser est alors le nombre de contraintes insatisfaites).
  1   2   3   4   5   6

similaire:

Recherche tabou iconMichel Marian «condamne le terrorisme arménien (1975-1985)»
«tabou arménien», et sur la compétence supposée de «deux anciens militants d’extrême gauche», dont aucun n’est historien et n’a mené...

Recherche tabou iconÈme Le corps est tabou, toilette corporelle sèche En 1790

Recherche tabou iconRecherche L’alphabet français semble mieux convenir à la fonction...

Recherche tabou iconLa Recherche Scientifique
...

Recherche tabou iconRecherche en santé mentale
«corps et psyche» est une association de recherche «Loi 1901»; déclarée au Journal Officiel de la République en décembre 2007

Recherche tabou icon3-Objet de recherche : 2 grandes orientations 4-1er axe : concerne...

Recherche tabou iconRecherche juridique htm >recherche juridique
«ne fait pas obstacle à ce que celui-ci puisse être saisi en vue d'assortir d'une astreinte la décision qu'il a rendue» (Cass civ.,...

Recherche tabou iconContenu de recherche : Les Partenaires s’engagent vis-à-vis du contenu...

Recherche tabou iconAncien directeur de recherche au cnrs
«Recherche et Développement» déboucher sur des générateur nucléaire d’électricité utilisant l’énergie dégagée par la fusion de deux...

Recherche tabou icon2. Recherche de partenaires 15
«Quelles informations pour aider les pme à faire de l‘innovation technologique ?». Pour ce faire, nous avons dû mettre en place une...








Tous droits réservés. Copyright © 2016
contacts
l.21-bal.com