I. introduction








télécharger 296.05 Kb.
titreI. introduction
page4/4
date de publication31.03.2018
taille296.05 Kb.
typeRecherche
p.21-bal.com > documents > Recherche
1   2   3   4

Exemple :

On veut totaliser une somme d’argent S en utilisant un nombre minimal de pièces appartenant à un ensemble donné. A chaque étape on choisit la plus grande pièce <= S tout en mettant à jour la nouvelle somme (S – la pièce choisie):

Pour S = 257 DA et pièces = {100DA, 50DA, 20DA, 10DA, 5DA, 2DA, 1DA}

à l’étape 1 : S1 = 257 , on choisit 1 pièce de 100DA

à l’étape 2 : S2 = 157 , on choisit 1 pièce de 100DA

à l’étape 3 : S3 = 57 , on choisit 1 pièce de 50DA

à l’étape 4 : S4 = 7 , on choisit 1 pièce de 5DA

à l’étape 5 : S5 = 2 , on choisit 1 pièce de 2DA

La solution trouvée est donc 2x100 DA , 1x50 DA , 1x5 DA et 1x2 DA

On peut montrer que dans ce cas, l'algorithme glouton donne toujours une solution optimale. Mais dans le système de pièces (1, 3, 4), l'algorithme glouton n'est pas optimal, comme le montre l'exemple simple suivant. Il donne pour 6 : 4+1+1, alors que 3+3 est optimal.

III.2. Heuristiques développées et méta heuristiques
a) Algorithme de Descente

Une des idées les plus utilisées dans les méthodes d’optimisation est de procéder itérativement en examinant le voisinage de la solution courante, dans l’espoir d’y détecter des directions de recherche prometteuses. Pour cela, on doit disposer :

  • d’une notion de voisinage qui structure l’espace X des solutions ;

  • d’un moyen efficace pour trouver la meilleure (ou une bonne) solution dans le voisinage d’une solution quelconque.

Partant d’une solution initiale quelconque, on progresse alors de proche en proche, tant que l’on trouve une solution meilleure que la solution courante dans le voisinage de celle-ci. L’algorithme s’arrête lorsque la solution courante est meilleure que toutes les solutions appartenant à son voisinage – ce qui est bien la définition d’un optimum local.


  • Schéma général

On suppose que pour toute solution x  X, il est défini un ensemble V(x)  X de solutions voisines de x.
Initialisation : Soit x0, une solution initiale
Etape n : Soit xn  X, la solution courante

Sélectionner la meilleure (ou une bonne) solution x*  V(xn)

Si Z(x*)  Z(xn) alors xn+1 = x* et passer à l’étape suivante

Sinon xn est la meilleure solution trouvée ; Arrêt.
Il est évident que le choix du voisinage peut exercer une influence déterminante sur la qualité de solutions obtenues. Illustrons la diversité des voisinages sur le problème du voyageur de commerce. Si xi représente le nom d’une ville, une solution est décrite par un vecteur x=(x1, x2, …,xN), N étant le nombre de villes, voici quelques définitions usuelles de voisinages de x :

  • Le voisinage « 2-échange » : tous les tours qui peuvent être obtenus à partir du tour x en permutant deux villes quelconques dans la liste ordonnée (taille du voisinage : |V(x)| = N(N-1)/2).

  • Le voisinage « k-opt » : tous les tours qui peuvent s’obtenir en rejetant k arêtes du tour courant et en reconnectant de la meilleure manière possible les tronçons ainsi formés dans le tour. Les cas particuliers les plus usuels sont 2-opt et 3-opt. Avec 2-opt la taille du voisinage est O(N²).


L’inconvénient principal des algorithmes de descente est le fait que l’algorithme s’arrête, le plus souvent, dans un optimum local et non dans un optimum global. C’est précisément, pour faire face à ce problème qu’ont été proposées des méthodes qui autorisent une détérioration temporaire de l’objectif permettant ainsi de quitter des minimums locaux tout en maintenant en général une « pression » favorisant les solutions qui améliorent l’objectif. Ces méthodes sont souvent appelées méta-heuristiques ; contrairement aux heuristiques classiques conçus pour un problème particulier, les méta-heuristiques sont des méthodes approximatives générales, pouvant s'appliquer à différents problèmes. On peut citer par exemple : le recuit simulé, les algorithmes génétiques, la recherche tabou, …

Optimums

Locaux

Optimum global
b) Le Recuit Simulé (Simulated Annealing)



  • Principe

L’idée de base de cette heuristique [Kirkpatrick 1983] provient de l’opération de recuit (annealing), courante en sidérurgie et dans l’industrie du verre : après avoir fait subir des déformations au métal (par exemple après avoir mis en bobines des tôles d’acier laminées), on réchauffe celui-ci à une certaine température, de manière à faire disparaître les tensions internes causées par les déformations, puis on laisse refroidir lentement. L’énergie fournie par le réchauffement permet aux atomes de se déplacer légèrement et le refroidissement lent fige peu à peu le système dans une structure d’énergie minimale.
Cette idée se transpose assez naturellement en optimisation pour modifier l’heuristique de descente. Au lieu de ne permettre que des mouvements (des changements de solution courante) qui diminuent l’énergie (la fonction objectif), on autorise des augmentations, même importantes, de l’énergie au début de l’exécution de l’algorithme, puis, à mesure que le temps passe, on autorise ces augmentations de plus en plus rarement (la température baisse). Finalement, le système « gèle » dans un état d’énergie minimale.
Plus précisément, partant d’une solution xn, on tire au sort une solution voisine x*  V(xn). Si Z(x*)  Z(xn), alors x* devient la nouvelle solution courante xn+1 ; si Z(x*)>Z(xn), on calcule une probabilité qui va décider si x* devient la nouvelle solution courante ou si xn reste la solution courante. Dans ce dernier cas, on tirera au sort un autre voisin de xn. La probabilité p d’accepter x* décroît avec le temps de l’algorithme et est généralement une fonction p(T,Z) dépendant d’un paramètre T qui est appelé « température », et de la dégradation de l’objectif Z = Z(x*) – Z(xn).


  • Schéma général

Initialisation : Soit x0  X, une solution initiale ; = Z(x0)
Etape n : Soit xn  X, la solution courante ;

Tirer au sort une solution x*  V(xn) ;

Si Z(x*) < Z(xn), alors xn+1 = x* ;

Si Z(x*) < , alors = Z(x*) // Enregistrer la meilleure solution trouvée

Sinon, tirer un nombre r au hasard entre 0 et 1 ;

Si r  p, alors xn+1 = x* Sinon xn+1 = xn
Deux éléments restent à préciser : la manière dont p dépend de T et de Z et le critère d’arrêt. De nouveau, c’est l’analogie avec les systèmes physiques qui a guidé le choix d’une fonction p(T, Z) et l’expérimentation dans le champ de l’optimisation combinatoire a souvent confirmé la pertinence de ce choix. C’est la distribution de Boltzmann (appelé critère de Metropolis) décrite comme suit :

p(T,Z) =

Cette quantité est comprise entre 0 et 1 comme une probabilité. Le paramètre température T varie lui-même au cours de l’exécution de l’algorithme. Le profil le plus souvent adopté est une décroissance géométrique par paliers : Une température initiale T0 est maintenue cste pendant L itérations, après quoi on passe, pendant L itérations, à une température T1 =  T0 (0 <  < 1), que l’on réduit à T2 = ()² T0 pour L autres itérations, etc.
Les paramètres T0, L et doivent être déterminés expérimentalement en tenant compte de la taille du problème. Typiquement, T0 est choisi de sorte qu’au début de l’algorithme, des solutions moins bonnes que la solution courante soient aisément acceptées. La longueur L du palier de température doit être déterminée en tenant compte de la taille des voisinages ; elle devrait augmenter avec la taille du problème, puisqu’il faut laisser plus de temps pour explorer l’espace des solutions quand celui-ci est vaste. Enfin, le paramètre de décroissance géométrique de la température  est fixé le plus souvent entre 0,75 à 0,95. C’est lui qui gère la lenteur du refroidissement. Un refroidissement rapide conduit le plus souvent à des optimums locaux de mauvaise qualité (équivalent de la trempe dans la sidérurgie)
Le critère d’arrêt peut tout simplement être l’allocation d’un nombre maximal d’itérations. Le plus souvent, on lui préfère un critère dynamique déterminant le moment où le système est « gelé ». Par exemple, on dira que le système est gelé si la fonction Z a diminué seulement de 0.1% pendant 100 paliers consécutifs.

c) La Recherche Tabou (Tabu Search)

Cette approche emprunte certains de ses concepts de l’intelligence artificielle [Glover 1986], en particulier la notion et l’utilisation de mémoire. Comme le recuit simulé, il s’agit, au moins dans sa version de base, d’une variante de la recherche locale. Partant de la solution courante xn, on calcule la meilleure solution x* dans un sousvoisinage V* de V(xn), sousvoisinage déterminé en fonction de l’histoire de recherche aux étapes précédentes. Cette solution devient la nouvelle solution courante xn+1, qu’elle soit meilleure ou moins bonne que la précédente. Ceci est indispensable si l’on veut éviter de rester coincé dans des minimums locaux. Il faut cependant mettre en place un mécanisme qui évite le cyclage. Ceci est obtenu grâce à une liste appelée liste tabou (ou restrictions tabou), qui garde en mémoire les dernières solutions rencontrées ou des caractéristiques de celles-ci. Ainsi, on exclut de V* les solutions récemment rencontrées.
Exemple : On considère le voisinage « 2-échange » pour le TSP composé de 5 villes A, B, C, D, et E. Supposons que la solution courante xn soit le tour (A,B,C,D,E) et que xn+1 soit le tour (A,D,C,B,E), obtenu en permutant les positions des 2ème et 4ème villes du tour. Au lieu d’enregistrer, dans la liste tabou, la description complète des tours rencontrés durant les dernières étapes, seule la transformation appliquée (appelée souvent mouvement) est généralement enregistrée. Dans notre cas, le mouvement peut être représenté par la paire (2,4) et pendant un nombre défini d’étapes, on interdira l’exécution de l’inverse de ce mouvement (pour éviter de retourner à la même solution). Cependant la liste tabou peut écarter des solutions non rencontrées, on peut envisager de négliger le statut tabou de certaines solutions si un avantage suffisant en résulte. Ceci est implémenté à l’aide du « critère d’aspiration ». Par exemple, on acceptera pour xn+1 une solution x* tabou si celle-ci donne à la fonction objectif Z une valeur meilleure que toutes celles obtenues jusqu’à présent.


  • Schéma général

Initialisation : Soit x0  X, une solution initiale

= Z(x0)

k = longueur de la liste tabou ou degré de récence (prohibition period)
Etape n : Soit xn  X, la solution courante ;

Chercher dans un sous-voisinage V* de V(xn) (appelé aussi liste des mouvements candidats) la meilleure solution x* qui soit : - non tabou ou bien

- tabou, mais satisfait le critère d’aspiration

Faire xn+1 = x*

Si Z(x*) < alors =Z(x*)

Mettre à jour la liste tabou


  • Intensification et Diversification

De manière générale, il est indiqué d’implémenter une recherche tabou comme une succession de phases d’intensification et de phases de diversification de la recherche.

  • Au cours des phases d’intensification, on explore plus en profondeur le voisinage de la solution courante, par exemple en augmentant la taille de V*.

  • Lors des phases de diversification, au contraire, on s’attache à constituer V* de solutions très différentes les unes des autres et très différentes de xn ; ceci peut être obtenu, par exemple, via des listes tabou qui excluent les solutions ressemblant à celles rencontrées récemment.


d) Algorithmes Génétiques (Genetic Algorithms)

Les algorithmes génétiques [Holland 1975] ont été conçus comme un modèle de système adaptatif complexe capable de simuler l’évolution des espèces. Du point de vue algorithmique, les algorithmes génétiques se distinguent aussi bien du recuit simulé que de la recherche tabou par le fait qu’ils traitent et font évoluer une population de solutions, et non une seule solution. De plus, au cours d’une itération, les solutions de la population courante n’évoluent pas indépendamment les unes des autres, mais interagissent pour fournir la génération suivante.


  • Description d’un algorithme génétique de base

Les solutions sont codées de manière appropriée. Un codage élémentaire pour un PLNE0/1 est un vecteur x de 0 et de 1. Pour le TSP, un codage approprié sera une liste ordonnée des noms des N villes. Un vecteur codant une solution est souvent appelé « chromosome » et ses coordonnées (noms des villes) sont appelées « gènes ». Le choix d’un codage approprié est très important pour l’efficacité des opérateurs appliqués pour faire évoluer les solutions.
Une population initiale de solutions X(0) est constituée. Une fonction d’évaluation des solutions est également choisie. Traditionnellement, cette fonction notée F est croissante avec la qualité de la solution (on parle de fitness function, mesurant la « santé » de l’individu solution), ce peut être l’opposé de la fonction objectif (ou la fonction objectif en cas de max), mais pour des raisons d’efficacité, on est amené souvent à choisir une fonction fitness plus sophistiquée que la fonction objectif.
Sur la base de la fonction fitness, une génération suivante est créée en appliquant des opérateurs de « sélection », de « croisement » et de « mutation ».


  • Schéma de base

Initialisation : Soit X(0)  X, une population initiale
Etape n : Soit X(n)  X, la population courante

- sélectionner dans X(n) un ensemble de paires de solutions de haute qualité
- appliquer à chacune des paires de solutions sélectionnées un opérateur de « croisement » qui produit une ou plusieurs solutions « enfants ».
- remplacer une partie de X(n) formée de solutions de basse qualité par des solutions « enfants » de haute qualité.
- appliquer un opérateur de mutation aux solutions ainsi obtenues ; les solutions éventuellement mutées constituent la population X(n+1).


  • Opérateurs utilisés

  1. Sélection

La sélection – aussi bien celle des individus de haute qualité que celle des individus de basse qualité – comporte généralement un aspect aléatoire. Chaque individu xi de la population parmi laquelle se fait la sélection se voit attribuer une probabilité pi d’être choisi d’autant plus grande que son évaluation est hausse (basse dans le cas d’une sélection de mauvais individus). On tire au sort un nombre r au hasard entre 0 et 1. L’individu k est choisi tel que :

La probabilité que xk soit choisi est ainsi bien égale à pk.


  1. Croisement

Soit deux solutions x et y sélectionnées parmi les solutions de haute qualité. Un opérateur de croisement (crossover) fabrique une ou deux nouvelles solutions x’, y’ en combinant x et y. Par exemple, si x et y sont deux vecteurs de 0 et 1, un opérateur de croisement classique consiste à sélectionner aléatoirement deux positions dans les vecteurs et à permuter les séquences de 0 et de 1 figurant entre ces deux positions dans les deux vecteurs. A titre d’exemple, pour des vecteurs à huit composantes :

x = 0 1 1 0 1 1 0 0

y = 1 1 0 0 1 0 1 0

si les positions « après 2 » et « après 5 » sont choisies, on obtient, après croisement :

x’ = 0 1 0 0 1 1 0 0

y’ = 1 1 1 0 1 0 1 0

L’opérateur de croisement est utilisé pour favoriser la transmission des « bonnes sous-structures » des solutions parents aux enfants.


  1. Mutation

Une mutation est une perturbation introduite pour modifier une solution individuelle, par exemple la transformation d’un 0 en un 1 ou inversement dans un vecteur binaire. Dans le TSP, une mutation peut être une permutation arbitraire de deux villes. En général, cet opérateur est appliqué avec une probabilité assez faible. Un but possible de la mutation est d’introduire un élément de diversification, d’innovation comme dans la théorie de l’évolution des espèces.

1   2   3   4

similaire:

I. introduction iconChapitre 1 : Introduction à l'optique géométrique I introduction

I. introduction iconI. Introduction

I. introduction iconI introduction

I. introduction iconA. Introduction

I. introduction iconI introduction

I. introduction iconBibliographie Introduction

I. introduction iconBibliographie introduction

I. introduction iconLeçon 1 introduction

I. introduction icon1. astrometrie introduction

I. introduction iconRésumé Introduction








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