Métaheuristiques - Freedevezeb.free.fr/downloads/projets/metaheuristique.pdf · 3.2 Les essaims particulaires L’optimisation par essaims particulaires1 (OEP) est une technique

EPITA SCIA PROMO 200514-16 rue Voltaire94270 Kremlin-Bicêtre

MÉTAHEURISTIQUESTravaux Pratiques sur les Métaheuristiquespour l’optimisation difficile

Octobre 2004

par:ALEXANDRE BARGETONCLAIRE CALMEJANEBENJAMIN DEVÈZE

responsable: PATRICK SIARRY

TABLE DES MATIERES

1 Introduction 1

2 Cas discret 22.1 Rappel du sujet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2 Le recuit simule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.3 Realisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3.1 Choix techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3.3 Resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4.1 Choix des parametres . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Cas continu 93.1 Rappel du sujet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.2 Les essaims particulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.3 Realisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3.1 Choix techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3.3 Resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.4.1 Choix des parametres . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Conclusion generale 19

Annexes

A Code du recuit simule I

B Code des essaims particulaires V

Bibliographie XVI

Table des Figures XVI

Liste des Algorithmes XVII

Index XIX

i

CHAPITRE 1

INTRODUCTION

Lors du cours de tronc commun nous avons étudié différentes métaheuristiquespour l’optimisation difficile :

– méthode du recuit simulé– méthode de recherche tabou– algorithmes génétiques / évolutionnaires– algorithmes de colonies de fourmis– méthode des essaims particulaires

Suite à ce cours, nous devons mettre en pratique deux de ces méthodes dans lecadre d’exercices pratiques, l’un traitant le cas discret et l’autre le cas continu. Ce rap-port fait donc office de compte rendu du travail qui a été effectué dans cette perspective.

Pour chacun des exercices nous ferons un bref rappel du sujet, nous présenteronsbrièvement la méthode utilisée, nous exposerons ce qui a été réalisé et comment.Nous traiterons enfin de l’analyse des résultats et des méthodes permettant de fixerles paramètres de ces algorithmes.

1

CHAPITRE 2

CAS DISCRET

Sommaire

2.1 Rappel du sujet . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2 Le recuit simule . . . . . . . . . . . . . . . . . . . . . . . . . . 22.3 Realisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3.1 Choix techniques . . . . . . . . . . . . . . . . . . . . . 32.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . 42.3.3 Resultats . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4.1 Choix des parametres . . . . . . . . . . . . . . . . . . 7

2.1 Rappel du sujet

Nous allons tout d’abord rappelé le sujet de l’exercice à résoudre, en ce qui concernele cas discret.

Il s’agissait de résoudre un problème de placement de composants électroniquesen des sites prédéterminés. Il faut placer 25 blocs. Le seul mouvement autorisé estla permutation de deux blocs. La fonction objectif, qu’il convient de minimiser, estévaluée en sommant les longueurs en L (dites aussi « longueurs de Manhattan ») desconnexions. La distance entre deux blocs est égale à 5. Nous savons que pour lesconfigurations optimales, la fonction objectif est égale à 200, ce qui nous permettrad’évaluer l’efficacité de notre méthode. Notons que les composants voisins sont dé-finis dès le départ. Ainsi le composant numéro 8 doit être relié avec les composantsnuméro 13, 3, 7 et 9. Les captures d’écran de notre application sont, à ce sujet, sansdoute plus claires qu’un long discours ; le lecteur perdu est donc invité à s’y référer.

Nous avons choisi d’implémenter la méthode du recuit simulé qui semblait bienadaptée pour résoudre ce problème.

2.2 Le recuit simule

Nous n’allons pas détailler tous les aspects de cette méthode, car ce n’est pas lepropos de ce rapport. Nous allons, toutefois, récapituler très brièvement, les grands

2

2 Cas discret Metaheuristiques

traits caractéristiques du recuit simulé.

Cette méthode est inspirée de la physique. L’idée vient du fait que la nature par-vient à passer d’un état désordonné à un état ordonné, d’énergie globale minimum.Le forgeron travaille en utilisant des palliers de température. La méthode utilise unerègle d’acceptation qui est souvent la règle de Métropolis.

L’idée est de partir d’un état quelconque en fixant une température T assez élevée.On perturbe cet état par une transformation légère, ce qui entraîne une variation ∆Edu système, si ∆E ≤ 0 on accepte le nouvel état (meilleur), sinon on l’accepte avec uneprobabilité de exp −∆E

T . Ce procédé permet de ne pas rester pris dans un minimumlocal, en effet on peut accepter des configurations dégradantes dans certaines condi-tions. Si l’équilibre thermodynamique est atteint on baisse la température (on utilisesouvent en pratique T = 0.9T). On remarque donc que plus l’algorithme évolue, plusla température baisse et donc moins on aura tendance à accepter de configurationsdégradantes. Ceci permettra de tendre vers une stabilisation dans un optimum global.

Algorithme 2.1 Algorithme du recuit simulé

1: On se donne une configuration initiale quelconque2: On se donne une température initiale T3: while Le système n’est pas figé do4: On fait une modification élémentaire du système qui nous donne une variation

d’énergie ∆E5: if ∆E ≤ 0 then6: Modification acceptée7: else8: Modification acceptée avec la probabilité exp −∆E

T9: end if

10: if Equilibre thermodynamique then11: Diminution lente de T12: end if13: end while

Voyons comment cela se traduit concrètement, en pratique, sur notre problème.

2.3 Realisation

2.3.1 Choix techniques

Nous avons choisi d’implémenter l’algorithme en C++, notamment dans un soucide performance d’execution. On cherche en effet à obtenir la meilleure solution pos-sible dans un délai de temps le plus court possible. Pour le rendu graphique dessolutions nous utilisons la XLib.

3


2.3.2 Implementation

Nous avons choisi de mettre le code de la routine principale en annexe. Nous allonsbrièvement aborder ici quelques points de l’algorithmes qui peuvent poser problèmes.

Il nous a fallu développer une fonction qui calcule le coût d’une solution, puisquel’on cherche à minimiser ce coût qui représente notre fonction objectif, une fonctionqui échange 2 pièces puisque c’est la transformation élémentaire qui nous a été pro-posée.

Une fois que l’on a ces briques, on se fixe une température, on tire une configura-tion initiale aléatoirement et on applique l’algorithme. On abaisse la température tousles 25 tours de boucle. Pour ce qui est de la règle d’acceptation de Métropolis, le codesuivant fait l’affaire :i f (exp(−(delta/T)) > (((random())%1001)/1000.))

Comme nous voulions soigner l’aspect visualisation du déroulement de l’algo-rithme, nous avons développer des routines d’affichage, il est possible de lancer l’al-gorithme et de le voir évoluer peu à peu jusqu’au bout, ou bien de le faire évoluer pasà pas en avançant à chaque fois de 10 tours de boucle.

2.3.3 Resultats

Les résultats obtenus sont très satisfaisants. L’algorithme trouve toujours la meilleuresolution de 200. Il tombe d’ailleurs sur cette solution de nombreuses fois au cours del’exécution. Il est plaisant de partir d’un état désordonné et de voir peu à peu lesystème tendre vers l’organisation, comme l’illustrent ces captures d’écran de notreprogramme :

4


F. 2.1: État initial

F. 2.2: État 1

5


F. 2.3: État 2

F. 2.4: État 3

6


F. 2.5: Solution trouvée

2.4 Discussion

2.4.1 Choix des parametres

La résolution d’un tel « problème modèle » (c’est-à-dire un problème dont la so-lution est connue à l’avance) nous permet de mettre au point et de régler la méthoded’optimisation elle-même : cela permet d’étudier la sensibilité du recuit simulé parrapport au réglage de ses principaux paramètres.

Il convient d’abord d’identifier les différents paramètres du recuit simulé, à savoir :– la température initiale– la décrémentation de température– le critère correspondant à un équilibre thermodynamique– le critère d’acceptation de configurations dégradantes– la condition d’arrêt

Pour ce qui est du critère d’acceptation de configurations dégradantes nous avonsadopté la règle de Métropolis, nous ne reviendrons pas dessus. Nous décrémentonsla température toutes les 25 itérations (nombre de composants).

En ce qui concerne la température : nous initialisons la température à 6666666,nous la décrémentons en la multipliant par 0.999. Il convient de prendre une tempé-rature initiale assez élevée afin d’autoriser au début beaucoup de choix dégradants(ce qui évite de s’emprisonner dans un minimum local). Toujours dans cette optiquela température ne doit pas être décrémentée trop brusquement, mais tout de mêmesuffisament pour tendre vers une stabilisation douce du système sur le minimum

7


global.

En ce qui concerne la condition d’arrêt, nous stoppons l’algorithme lorsque latempérature est inférieure à 1. Nous pourrions arrêter le recuit lorsque par exemple lesystème ne change pas pendant 100 itérations.

Les paramètres que nous avons choisis, nous permettent ainsi de trouver à coupsûr la solution du problème et même de la rencontrer plusieurs fois. Nous pourrionsassouplir les paramètres choisis afin de faire moins d’itérations mais en pratique l’al-gorithme fonctionne très vite et de façon satisfaisante.

Nous ne discuterons pas plus ici du choix des paramètres car nous développeronsplus cette question dans le cadre de l’exercice suivant, qui, bien que traitant d’un autrealgorithme, permet de poser des bases de réflexion sur la méthodologie à suivre pourétudier l’influence des paramètres sur des algorithmes non déterministes.

8

CHAPITRE 3

CAS CONTINU

Sommaire

3.1 Rappel du sujet . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.2 Les essaims particulaires . . . . . . . . . . . . . . . . . . . . . 9

3.3 Realisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3.1 Choix techniques . . . . . . . . . . . . . . . . . . . . . 113.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . 113.3.3 Resultats . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.4.1 Choix des parametres . . . . . . . . . . . . . . . . . . 13

3.1 Rappel du sujet

Le but est d’implémenter les essaims particulaires afin de trouver le minimumglobal de fonctions. Nous allons d’abord brièvement présenter les grands principes decette méthode, nous verrons ensuite en pratique comment nous l’avons implémentéeet les résultats obtenus. Pour valider le programme d’optimisation continue, nousexploiterons quelques fonctions analytiques de test, dont les minima globaux et locauxsont connus. Nous discuterons alors du point crucial de cet algorithme : le choix desparamètres, et nous verrons comment il est possible d’améliorer les résultats obtenus.

3.2 Les essaims particulaires

L’optimisation par essaims particulaires1 (OEP) est une technique relativementrécente, qui date de 1995. Il s’agit d’une méthode faisant appel à une populationd’agents, appelés ici particules. Ici la notion d’efficacitée est due à la collaborationplutôt qu’à la compétition, ce qui fait la force de la méthode.

Si l’on souhaite explorer un espace de recherche, il est vain d’utiliser un seul agentpeu « intelligent ». En revanche si l’on utilise plusieurs agents aux capacités limitées, ilest possible d’envisager différentes stratégies pour qu’ensemble ils se comportent de

1Particle Swarm Optimization (en anglais)

9

3 Cas continu Metaheuristiques

manière astucieuse. Notons que cette méthode montre son efficacité dans les espacesde recherche continus ou mixtes.

Il s’agit d’une sorte d’algorithme évolutionnaire, avec une population d’individus(les particules), dans laquelle, à chaque pas de temps, les « meilleurs » (selon un critèreprédéfini) sont plus ou moins imités par les autres.

On place les particules aléatoirements dans l’espace de recherche. A partir desquelques informations dont elle dispose, une particule doit décider de son prochainmouvement, c’est-à-dire décider de sa nouvelle vitesse. Pour ce faire, elle combinelinéairement trois informations : sa vitesse actuelle, sa meilleure performance, lameilleure performance de ses voisines qui sont ses informatrices. Ceci se fait à l’aide detrois paramètres appelés coefficients de confiance, qui pondèrent trois tendances : ten-dance à suivre sa propre voie, tendance conservatrice, tendance panurgienne (suivrele meilleur voisin). Il existe différentes variantes de l’algorithmes selon la notion devoisinage que l’on considère, les initialisations de l’essaim, sa taille... Voici ce que celadonne en terme algorithmique, pour l’algorithme de base :

Algorithme 3.1 Algorithme des essaims particulaires

1: for chaque particule do2: Initialisation aléatoire de la particule3: end for4: while nombre maximal d’itérations non atteint et critère de précision non atteint

do5: for chaque particule do6: Calculer la valeur de la fonction (fitness)7: if fitness < pbest (meilleure valeur rencontrée pour la particule) then8: pbest = fitness9: end if

10: end for11: gbest =meilleur pbest de toutes les particules12: for chaque particule do13: calcul de la vitesse de la particule - équation (3.1)14: mise à jour de la position de la particule - équation (3.2)15: end for16: end while

avec : v(t + 1)=c1v(t) + c2(pi − x(t)) + c3(pg − x(t))

c2 = alea(0,Φ1)c3 = alea(0,Φ2)

(3.1)

x(t + 1) = x(t) + v(t + 1) (3.2)

L’efficacité de la méthode tient en particulier au caractère aléatoire des deux der-niers coefficients.

10


3.3 Realisation

3.3.1 Choix techniques

Là encore nous avons choisi d’utiliser le C++ pour ses performances ainsi quepour son aspect objet qui nous a permis d’adopter une architecture claire et saine pournotre application.

3.3.2 Implementation

Choix algorithmiques

L’implémentation en elle-même de l’algorithme ne pose aucun problème particu-lier. Nous avons choisi de mettre en place la méthode « historique » qui semble obtenirde bons résultats. Nous considérons comme voisinage l’ensemble des particules dusystème.

Modelisation

Nous avons conçu notre code afin qu’il puisse être réutilisé très facilement parn’importe quel utilisateur pour optimiser ses propres fonctions.

Nous avons donc tout d’abord une classe abstraite « OptiFunc », qui regroupeun nom, une dimension et les deux bornes de l’espace de recherche. Nous avons uneclasse « Swarm » qui prend une fonction (objet « OptiFunc ») à optimiser et les différentsparamètres de l’algorithme des essaims (nombre d’itérations, nombre de particules,précision, ...). Cette classe contient un ensemble d’éléments de type « Particle ». Une« particle » contient principalement, une vitesse courante, une position courante, lameilleure valeur rencontrée et la meilleure position associée.

Nous offrons ainsi une sorte d’outil générique pour permettre à l’utilisateur d’uti-liser les essaims particulaires de la façon la plus simple possible sur les fonctions deson choix. Il lui suffit concrètement de procéder comme suit. Tout d’abord l’utilisateurfait dériver une classe de OptiFunc dans laquelle il définit l’expression de la fonctionobjectif, le nom de cette fonction, la dimension et les ensembles de recherche. Puis ilpeut procéder comme suit s’il ne veut s’occuper d’aucun paramètre :

#include <swarm.hh>MyFunction function

Swarm S(function);

S.resolve();

Comme on le voit l’utilisation est très simple et nous avons tenter de relier aumieux les éléments et ce qui devait rentrer logiquement dans leur contenu.

3.3.3 Resultats

Nous avons testé la méthode sur quelques fonctions analytiques classiques de test,dont les minima globaux et locaux sont connus. Voici les résultats que nous obtenons

11


de base avec les paramètres suivants : 2000 itérations, 50 agents, 1, 2 et 2 pour lescoefficients. Nous lançons ici une fois l’algorithme pour avoir un résultat indicatif, ilest évident qu’en pratique on ne peut évaluer la qualité de l’algorithme de la sorte.Nous aborderons ce point dans la discussion qui suit. Notons également que cesrésultats sont obtenus instantanément sur un ordinateur bas de gamme.

Michalewicz

Michalewicz(2.199, 1.566) = -1.8Le résultat en dimension 2 est déjà correct, nous ne reviendrons donc pas dessus parla suite.

Michalewicz(2.101, 1.665, 1.321, 1.059, 1.026) = -3.696Michalewicz(2.233, 3.135, 1.305, 3.142, 1.747, 0.4522, 3.129, 3.142, 2.209, 1.212) = -4.075En dimension 5 (résultat attendu : -4.687) et 10 (-9.68) les résultats ne sont pas opti-maux, nous en reparlerons par la suite ainsi que de toutes les fonctions qui sont dansle même cas.

De Jong F1

DeJongF1(0.3997, 0.04119, 0.5908, 0.8978, -0.04683, 0.01011) = 1.319Résultat non optimal (0).

De Jong F2

DeJongF2(1.00, 1.00) = 0.00Le résultat est bon, nous ne reviendrons pas dessus.

De Jong F3

DeJongF3(-5.12, -5.12, -5.12, -5.12, -5.12) = -30En dimension 5, nous trouvons instantanément le résultat.

Goldstein and Price

GoldPrice(-0.001116, -0.9982) = 3.002Là encore le résultat est bon, modulo la précision que l’on se fixe évidemment.

Rosenbrock

Rosenbrock(-1.009, 1.027, 1.2, 1.451, 2.048) = 6.741Solution non optimale (0).

Zakharov

Zakharov(0.8027, 0.334, -1.017, 1.715, -0.5973, -0.2335) = 5.381Solution non optimale (0).

12


Conclusion preliminaire

Nous voyons donc que déjà avec des paramètres de base, un nombre d’itérationstrès faible et peu d’agents on obtient déjà instantanément des résultats corrects pourla plupart des fonctions et même le minimum global pour certaines fonctions. Il estévidemment plus facile de trouver ce minimum quand la dimension est faible, maispar exemple on remarque que le système se comporte très bien sur De Jong F3 qui estde dimension 5 (ce qui s’explique d’ailleurs par l’aspect général de la courbe de cettefonction, nous reviendrons sur ce point).

3.4 Discussion

3.4.1 Choix des parametres

Le choix des paramètres est là encore fondamental pour cette métaheuristiqued’optimisation. Les paramètres principaux sur lesquels ont peut jouer sont le nombred’itérations, le nombre d’agents et les coefficients de confiance qui déterminent lecomportement des particules. Existe-t-il des paramètres qui donneront le meilleurrésultat pour toutes les fonctions étudiés ? On peut penser à priori que non car selonles caractéristiques de la fonction, l’on peut penser qu’il sera parfois préférable pourune particule de suivre sa voie ou bien de suivre d’avantage la meilleure particule, etc.Nous allons tenter de trouver de meilleurs paramètres pour les fonctions qu’il nousreste à optimiser.

Notre methodologie d’analyse

Lorsque l’on tente d’analyser un algorithme non déterminisme comme celui-ci,dans lequel l’aléa intervient, il est évident que l’on ne peut pas se baser sur une seuleexécution de la méthode. Il faut la lancer plusieurs fois avec une initialisation diffé-rente du générateur de nombres aléatoires et faire une moyenne du résultat obtenupour avoir une estimation de la valeure de la méthode.

Pour tenter de trouver les meilleurs paramètres nous avons procédé comme suit :nous appelons une routine analysis de la classe Swarm, cette routine va effectuer 101fois l’algorithme des essaims sur une fonction donnée, elle renvoie la moyenne etla médiane des résultats trouvés ainsi que le nombre moyen d’itérations nécessairespour trouver ce résultat.

Nous utilisons alors cette méthode en fixant tous les paramètres sauf un seul quel’on fait varier. On s’intéresse ainsi successivement à tous les paramètres. Voici lesrésultats que l’on obtient.

Resultats

Nous allons détailler avec des graphiques les résultats obtenus sur Michalewiczen dimension 5. Nous expliquerons ensuite comment choisir les paramètres pour cettefonction et nous verrons que cette méthode est efficace. Nous donnerons ensuite lesparamètres et résultats obtenus pour les autres fonctions. Nous ne redévelopperons

13


cependant pas tout, puisque la méthode est exactement similaire pour les autres fonc-tions.

Voici les graphes que l’on obtient pour la moyenne et la médiane des résultats enfonction du nombre d’itérations, du nombre d’agents et des coefficients.

F. 3.1: Influence du nombre d’itérations

14


F. 3.2: Influence du nombre d’agents

F. 3.3: Influence de c1

15




16


On déduit de ces courbes qu’il semble judicieux de prendre 8500 itérations, 310agents et respectivement 0.9, 1.2, 0.2 pour c1, c2 et c3. Nous testons donc l’algorithmeavec ces paramètres ; on obtient le bon résultat qui est bien meilleur que celui quenous avions trouvé au départ :

En procédant de même on obtient :

Michalewicz en dimension 10 (9000 itérations, 460 agents, 0.9, 0.7, 0.2) :Michalewicz(2.203, 1.571, 1.285, 1.923, 1.72) = -4.688

De Jong F1 (8000 itérations, 410 agents, 0.5, 1.1, 0.1)DeJongF1(-0.0002007, 1.742e-06, 0.0007196, -0.000112, -0.0002583, 0.0003304) = 7.465e-07

Rosenbrock (8000 itérations, 460 agents, 0.9, 1.1, 0.1)Rosenbrock(1, 1, 1, 1, 1) = 0

Zakharov (8000 itérations, 460 agents, 0.8, 0.8, 0.1)Zakharov(-9.321e-24, 2.823e-24, 1.275e-23, 2.803e-24, -2.212e-24, 9.947e-25) = 0

Nous parvenons donc à renvoyer, quasi instantanément, le résultat de toutes lesfonctions étudiées avec une très bonne précision.

Analyse des resultats

Les résultats précédents nous montrent tout d’abord l’importance des paramètres,puisqu’avec des paramètres bien choisis on obtient la solution ce qui n’était pas le casavant. On peut voir que ces paramètres sont très sensibles, par exemple on peut avoirun mauvais résultat avec 1 pour c1 et un excellent résultat avec 0.9.

Dans la plupart des cas, augmenter le nombre de particules dans l’essaim dimi-nue logiquement le nombre d’itérations nécessaires pour atteindre l’objectif. Plus departicules échantillonnent évidemment mieux l’espace de recherche. Toutefois il fauttrouver le bon compromis entre nombre d’évaluations et nombre d’agents, car plus ily a d’agents plus il y a de valeurs de la fonction objectif à calculer.

Il est tout de même intéressant de constater qu’une fois un certain seuil atteintaugmenter le nombre d’itérations ou d’agents n’améliore pas les résultats.

Ces résultats nous permettent, également, de constater que majoritairement (saufquelques exceptions pour certaines fonctions) les paramètres intéressants sont prochesd’une fonction à l’autre : entre 8000 et 9000 pour le nombre d’itérations, environ 400pour le nombre d’agents, 0.9 pour c1, 1 pour c2 et 0.2 pour c3. Avec un nombre assezimportant d’agents on voit donc qu’il vaut mieux inciter l’agent à suivre sa voie plutôtque systématiquement le conduire vers la meilleure solution globale rencontrée. Nous

17


favorisons l’exploitation par rapport à l’exploration de l’espace.

Notons enfin que la tâche est plus difficile lorsque l’on a à faire à des fonctionsprésentant plusieurs optima locaux. Dans ce cas un nombre trop faible d’agents etd’itérations conduit immanquablement vers ces optima locaux et nous éloigne del’objectif.

18

CHAPITRE 4

CONCLUSION GENERALE

Nous avons implémenté avec succès deux métaheuristiques pour l’optimisationdifficile à savoir le recuit simulé pour répondre à un problème discret et les essaimsparticulaires pour répondre à un problème continu. Les deux méthodes se sont mon-trées très efficaces. Nous avons aussi pu réaliser l’importance des paramètres dansces méthodes et la difficulté pratique de trouver les meilleurs paramètres selon lesvariations des problèmes qui se posent. On pourrait sans doute proposer des « meta-metaheuristiques » qui seraient capables d’utiliser une métaheuristique et de trouverles meilleurs paramètres de cette métaheurisitque selon le problème posé. Pourquoine pas imaginer par exemple une application utilisant un essaim particulaire dont lesmeilleurs paramètres pour une fonction donnée seraient trouvés par recuit simulé ?

19

Annexes

ANNEXE A

CODE DU RECUIT SIMULE

#include <stdlib.h>#include <math.h>#include "map.hh"#include "XLIB/interfaceX.hh"

#define T INIT 6666666#define T STEP 0.999#define T STOP 0.00001

10#define I STEP 10

#define IC(x) (20 + ((x) + (x) * 2) * 20)

static InterfaceX * inter = NULL ;static Map * map = NULL ;static double T = T INIT ;

static void compute coord(int *x, int *xx, int *y, int *yy) 20{

*y += 10 ;*yy += 10 ;if (*x < *xx)

*x += 20 ;else

*xx += 20 ;}

30static void link(int id, int x, int y, int xx, int yy){

x = IC(x) ;y = IC(y) ;xx = IC(xx) ;yy = IC(yy) ;if (y == yy) //same line

compute coord(&x, &xx, &y, &yy) ;else if (x == xx) //same column

compute coord(&y, &yy, &x, &xx) ; 40else

if (abs(y−yy) > abs(x−xx))compute coord(&y, &yy, &x, &xx) ;

I

A Code du recuit simule Metaheuristiques

elsecompute coord(&x, &xx, &y, &yy) ;

inter−>draw line(id, x, y, xx, yy) ;}

static void link 0(t piece p1, t piece p2, int *res) 50{

link(*res, p1.x, p1.y, p2.x, p2.y) ;}

static bool event expose(InterfaceX *inter, int id){

int i, j ;char str[255] ;

60if (id == 0)

{inter−>change color(id, USHRT MAX, USHRT MAX, USHRT MAX) ;inter−>draw rectangle(id, 0, 0, (WIDTH + WIDTH*2) * 20, (HEIGHT + HEIGHT*2) * 20, true) ;inter−>change color(id, 0, 0, 0) ;for (i = 0 ; i < WIDTH ; i++)

for (j = 0 ; j < HEIGHT ; j++)inter−>draw rectangle(id, IC(i), IC(j), 20, 20, true) ;

inter−>change color(id, 0, 0, USHRT MAX) ;map−>compute(&link 0, &id) ; 70

inter−>change color(id, USHRT MAX, USHRT MAX, USHRT MAX) ;for (i = 0 ; i < WIDTH ; i++)

for (j = 0 ; j < HEIGHT ; j++)inter−>draw rectangle(id, IC(i)+1, IC(j)+1, 18, 18, true) ;

inter−>change color(id, 0, 0, 0) ;for (i = 0 ; i < WIDTH ; i++)

for (j = 0 ; j < HEIGHT ; j++){

sprintf(str, "%i", map−>map[j][i] + 1) ;inter−>write text(id, str, IC(i)+5, IC(j)+15) ; 80

}sprintf(str, "Température : %5f Coût : %5i", T, map−> cost) ;inter−>write text(id, str, 5, 12) ;

}else

{sprintf(str, "Fin du recuit !") ;inter−>write text(id, str, 5, 12) ;

}return false ; 90

}

static void recuit(bool step){

static const unsigned int nbpieces = WIDTH * HEIGHT ;unsigned int t = 0, nbiter = 0 ;unsigned int cost i, cost j, best cost ;int delta ;unsigned int i, j, k ; 100

k = 0 ;best cost = map−>cost() ;

II


while (T > T STOP){

t++ ;nbiter++ ;//Compute inititial costcost i = map−>cost() ;//Pick up two aleatory pieces 110i = (random()) % nbpieces ;do

{j = (random()) % nbpieces ;

}while (i == j) ;map−>swap(i, j) ;//Compute new costcost j = map−>cost() ;// Back up best solution 120if (cost j < best cost)

{map−>backup best( map−>map) ;

best cost = cost j ;}

if (cost j == 200)printf("Solution trouve, iteration : %u !\n", nbiter) ;

//Take the differencedelta = cost j − cost i ; 130if (delta < 0)

; //Accept the swapelse if (delta > 0)

{if (exp(−(delta / T)) > (((random())% 1001) / 1000.))

; //Accept the swapelse

map−>swap(j, i) ; //Refuse the swap, so we reput the last configuration}//Decrease temperature 140if ((t % nbpieces) == 0)

{T *= T STEP ;t = 0 ;k++ ;if (k == I STEP)

{k = 0 ;if (step)

break ; 150else

{event expose( inter, 0) ;usleep(1000) ;

}}

}}

map−>update endmap() ; 160event expose( inter, 0) ;

if (T <= T STOP)

III


{k = inter−>create window("Finish", 100, 25) ;inter−>open window(k) ;

}}

170

static bool event keypress(InterfaceX *inter, int id, char c){

if (c == ’q’){

inter−>close window(id) ;return true ;

}else if ((c == ’a’) && (id == 0)) //auto mode

{ 180recuit(false) ;

}else if ((c == ’s’) && (id == 0)) //step mode

{recuit(true) ;

}return false ;

}

190

int main(int argc, char **argv){

int window ;

argc = argc ;argv = argv ;srandom(time(NULL)) ;map = new Map() ;inter = new InterfaceX(&event expose, &event keypress, NULL, NULL, NULL) ; 200

window = inter−>create window("Recuit Simulé", (WIDTH + WIDTH*2) * 20, (HEIGHT + HEIGHT*2) * 20) ;inter−>open window(window) ;inter−>run() ;

delete inter ;delete map ;return 0 ;

}

IV

ANNEXE B

CODE DES ESSAIMS PARTICULAIRES

//// optifunc.hh for OEP in /home/paikan/work/Programming/metaheuristiques/continu//// Made by PaiKan// Login <paikan//// Started on Thu Oct 28 01 :41 :16 2004 PaiKan// Last update Sun Oct 31 16 :21 :57 2004 PaiKan//

10#ifndef OPTIFUNC HH# define OPTIFUNC HH

/*——–.| Defines |‘——–*/# define MIN R 0# define MAX R 1

/*———. 20| Includes |‘———*/# include <iostream># include <vector>

using namespace std ;

typedef vector<float> VecFloat ;

/*———. 30| OptiFunc |‘———*/class OptiFunc{public :

// ctors & dtorsOptiFunc(string name, int dimension, float min range, float max range){

name = name ; 40dimension = dimension ;

// make sure min range < max range or swap

V

B Code des essaims particulaires Metaheuristiques

if (min range > max range){

float t = min range ;min range = max range ;max range = t ;

}50

range[MIN R] = min range ;range[MAX R] = max range ;

}

virtual ˜OptiFunc() {}

// Accessorsinline string getName() const{ 60

return name ;}

inline void setName(string name){

name = name ;}

inline unsigned int getDimension() const{ 70

return dimension ;}

inline void setDimension(unsigned int dimension){

dimension = dimension ;}

inline float getRange(int i) const{ 80

return range[i] ;}

inline void setRange(float min range, float max range){// make sure min range < max range or swapif (min range > max range)

{float t = min range ;min range = max range ; 90max range = t ;

}

range[MIN R] = min range ;range[MAX R] = max range ;

}

// The expression of the function to compute (abstract)virtual float compute(VecFloat x) = 0 ;

100private :

// Name of the function

VI


string name ;

// Dimensionunsigned int dimension ;

// Range to search infloat range[2] ; 110

} ;

// Stream Operatorostream& operator<< (ostream& out, const OptiFunc& f){

unsigned int i ;

out << f.getName() + "(" ;

for (i = 0 ; i < f.getDimension() − 1 ; i++) 120{

out << "x" << i << ", " ;}

out << "x" << i << ")" ;

out << " on [" << f.getRange(MIN R) << " ; " << f.getRange(MAX R) << "]" ;

return out ;} 130

#endif /* !OPTIFUNC HH */

//// particle.hh for OEP in /home/paikan/work/Programming/metaheuristiques/continu//// Made by PaiKan// Login <paikan//// Started on Wed Oct 27 18 :32 :10 2004 PaiKan// Last update Mon Nov 1 00 :27 :56 2004 PaiKan//

10#ifndef PARTICLE HH# define PARTICLE HH

/*———.| Includes |‘———*/# include <vector># include <cassert># include <values.h># include <stdlib.h> 20

# include "optifunc.hh"


typedef vector<float> VecFloat ;

class Particle

VII


{public : 30

// ctors & dtorsParticle(OptiFunc* func, float c1, float c2, float c3){

float Down = func−>getRange(0) ;float Up = func−>getRange(1) ;

function = func ;

c1 = c1 ; 40c2 = c2 ;c3 = c3 ;

Vmax = Up − Down ;

// Initialize with random valuesfor (unsigned int i = 0 ; i < func−>getDimension() ; i++)

{curPosition.push back(getRand(Down, Up)) ;// curSpeed.push back(Vmax * getRand(0.0, 1.0)) ; 50curSpeed.push back(0) ;

}

bestValue = MAXFLOAT ;}

˜Particle(){}

float compute(){ 60

float res ;

res = function−>compute(curPosition) ;if (res < bestValue)

{bestValue = res ;bestPosition = curPosition ;

}

return res ; 70}

void update(const VecFloat gbest){

VecFloat newSpeed ;

assert(gbest.size() >= function−>getDimension()) ;

// update current speed and current positionfor (unsigned int i = 0 ; i < function−>getDimension() ; i++) 80

{// update speednewSpeed.push back( c1 * curSpeed[i] + getRand(0.0, c2) * (bestPosition[i] − curPosition[i])

+ getRand(0.0, c3) * (gbest[i] − curPosition[i])) ;

// update positioncurPosition[i] += newSpeed[i] ;

VIII


// Make sure position is in search intervalif (curPosition[i] > function−>getRange(1)) 90

curPosition[i] = function−>getRange(1) ;

if (curPosition[i] < function−>getRange(0))curPosition[i] = function−>getRange(0) ;

}

curSpeed = newSpeed ;}

inline VecFloat getPBest() const 100{

return bestPosition ;}

private :

// Return a random value between min and maxfloat getRand(float min, float max){

return (float) ((max − min)*(rand()/(float)RAND MAX) + min) ; 110}

private :

// Current positionVecFloat curPosition ;

// Current speed for each dimensionVecFloat curSpeed ;

120// Best position seen by the particleVecFloat bestPosition ;

// Best value seen by the particlefloat bestValue ;

// Function to optimizeOptiFunc* function ;

// Maximum velocity 130float Vmax ;

// The factors in equation that compute new velocity of a particlefloat c1 ;float c2 ;float c3 ;

} ;

#endif /* !PARTICLE HH */

//// swarm.hh for OEP in /home/paikan/work/Programming/metaheuristiques/continu//// Made by PaiKan// Login <paikan//

IX


// Started on Wed Oct 27 18 :32 :32 2004 PaiKan// Last update Mon Nov 1 00 :42 :44 2004 PaiKan//

10#ifndef SWARM HH# define SWARM HH

/*———.| Includes |‘———*/# include <vector># include <stdlib.h># include <list># include <iomanip> 20

# include "optifunc.hh"# include "particle.hh"


typedef vector<float> VecFloat ;typedef vector<Particle> VecParticle ;typedef list<float> ListFloat ;

30/*——–.| Defines |‘——–*/# define NB ITER 2000# define NB RUN 101# define NB PARTICLES 40# define C1 1.0# define C2 2.0# define C3 2.0

40class Swarm{public :

// ctors & dtorsSwarm(OptiFunc* f, unsigned int iter, unsigned int nbrun, unsigned int nbparticles, float c1, float c2, float c3){

function = f ;nbIter = iter ;if ((nbrun % 2) == 0) 50

nbRun = nbrun + 1 ;else

nbRun = nbrun ;nbParticles = nbparticles ;c1 = c1 ;c2 = c2 ;c3 = c3 ;

srandom(time(NULL)) ;}

60Swarm(OptiFunc* f, unsigned int iter, unsigned int nbrun, unsigned int nbparticles){

function = f ;nbIter = iter ;if ((nbrun % 2) == 0)

nbRun = nbrun + 1 ;

X


elsenbRun = nbrun ;

nbParticles = nbparticles ;c1 = C1 ; 70c2 = C2 ;c3 = C3 ;

srandom(1) ;}

Swarm(OptiFunc* f){

function = f ;nbIter = NB ITER ;nbRun = NB RUN ; 80nbParticles = NB PARTICLES ;srandom(time(NULL)) ;

}

Swarm(){

nbIter = NB ITER ;nbRun = NB RUN ;nbParticles = NB PARTICLES ;srandom(time(NULL)) ; 90

}

˜Swarm(){}

// function to find the global minimum of “function”void resolve(int precision = 4){// The best value seen by all particlesint gbest idx = −1 ;

100cout << "Trying to minimize :" << endl ;cout << "\t" << *function << endl << endl ;

initializeSwarm() ;

for (unsigned int iter = 0 ; iter < nbIter ; iter++){

for (unsigned int i = 0 ; i < nbParticles ; i++){

float res ; 110

res = particles[i].compute() ;if (res < gbest)

{gbest = res ;gbest idx = i ;Solution = particles[gbest idx].getPBest() ;

}}

120for (unsigned int i = 0 ; i < nbParticles ; i++)

{particles[i].update(particles[gbest idx].getPBest()) ;

}}

XI


printSolution(precision) ;}

// function to analysis the influence of some parameters on the algorithm efficiency 130// It does a few runs and display some useful average valuesvoid analysis(int precision = 6){

float average = 0 ;float average iter = 0 ;ListFloat l ;

for (unsigned int run = 0 ; run < nbRun ; run++){// The best value seen by all particles 140int gbest idx = −1 ;unsigned int nbiter = 0 ;

initializeSwarm() ;

for (unsigned int iter = 0 ; iter < nbIter ; iter++){


float res ; 150

res = particles[i].compute() ;if (res < gbest)

{gbest = res ;gbest idx = i ;nbiter = iter ;Solution = particles[gbest idx].getPBest() ;

}} 160


particles[i].update(particles[gbest idx].getPBest()) ;}

}l.push back(gbest) ;average += gbest ;average iter += nbiter ;printSolution(precision) ; 170cout << "found iteration number " << nbiter << endl << endl ;

}

cout << " ------------------- " << endl ;cout << " Average value : " << average / nbRun << endl ;cout << " Median value : " << getMediane(l) << endl ;cout << " Average iterations number : " << average iter / nbRun << endl ;

}

180// Accessorsinline OptiFunc* getFunction() const{

return function ;}

XII


inline void setFunction(OptiFunc* f){

function = f ;} 190

inline unsigned int getNbParticles() const{

return nbParticles ;}

inline void setNbParticles(unsigned int nb){

nbParticles = nb ;} 200

inline unsigned int getNbIter() const{

return nbIter ;}

inline void setNbIter(unsigned int iter){

nbIter = iter ;} 210

// Display Solutioninline void printSolution(int precision){

unsigned int i ;

cout << function−>getName() + "(" ;

for (i = 0 ; i < function−>getDimension() − 1 ; i++)cout << setprecision(precision) << Solution[i] << ", " ; 220

cout << setprecision(precision) << Solution[i] << ")" ;

cout << " = " << setprecision(precision) << gbest << endl << endl ;}

private :

// Initialize the particlesvoid initializeSwarm() 230{

gbest = MAXFLOAT ;

particles.clear() ;

for (unsigned int i = 0 ; i < nbParticles ; i++)particles.push back(Particle(function, c1, c2, c3)) ;

}

float getMediane(ListFloat l) 240{

l.sort() ;

list<float> : :iterator iter ;unsigned int i ;

XIII


for (iter = l.begin(), i = 0 ; i < l.size() / 2 ; iter++, i++);

return *iter ; 250}

private :

// Number of particlesunsigned int nbParticles ;

// Maximum number of iterationsunsigned int nbIter ;

260// Maximum number of iterationsunsigned int nbRun ;

// Function to minimizeOptiFunc* function ;

// Swarm of particlesVecParticle particles ;

// Final solution 270VecFloat Solution ;

// Value of solutionfloat gbest ;

// The factors in equation that compute new velocity of a particlefloat c1 ;float c2 ;float c3 ;

} ; 280

#endif /* !SWARM HH */

//// main.cc for OEP in /home/paikan/work/Programming/metaheuristiques/continu//// Made by PaiKan// Login <paikan//// Started on Wed Oct 27 18 :37 :34 2004 PaiKan// Last update Mon Nov 1 01 :21 :23 2004 PaiKan//

10#include <iostream>


#include "swarm.hh"#include "functions.hh"

int main(int argc, char **argv){// Avoid Warnings 20argc = argc ;

XIV


argv = argv ;

// Functions to optimizeMicha 2 a ;Micha 5 b ;Micha 10 c ;

DeJongF1<6> d ;DeJongF2 e ; 30DeJongF3<5> f ;

GoldPrice g ;

Rosenbrock<5> h ;

Zakharov<6> i ;

Schwefel<4> j ;40

Swarm S(&a, 2000, 11, 200, 1.0, 2.0, 2.0) ;

S.resolve() ;

return(0) ;}

XV

BIBLIOGRAPHIE

[Cle] Maurice Clerc. Math stuff about pso. http://clerc.maurice.free.fr/pso/.

[Cle03a] Maurice Clerc. L’optimisation par essaim particulaire, 2003.

[Cle03b] Maurice Clerc. Tribes, ou la coopération de tribus, 2003.

[Gac] L. Gacôgne. Comparaison entre pso et autres heuristiques d’optimisationavec opérateurs implicites.

[GB01] Patrick Siarry Gérard Berthiau. Etat de l’art des méthodes d’optimisationglobale. Rairo, 2001.

[JD03] Patrick Siarry Éric Taillard Johann Dréo, Alain Pétrowski. Métaheuristiquespour l’optimisation difficile. 2003.

[OEPa] Particle swarm central. http://www.particleswarm.info.

[OEPb] Particle swarm optimization. http://www.swarmintelligence.org/.

[Sia95] Patrick Siarry. La méthode du recuit simulé : théorie et applications. APII,29(4-5), 1995.

[Tre03] Ioan Cristian Trelea. L’essaim de particules vu comme un système dyna-mique : convergence et choix des paramètres, 2003.

XVI

http://clerc.maurice.free.fr/pso/

http://clerc.maurice.free.fr/pso/

http://www.particleswarm.info

http://www.swarmintelligence.org/

TABLE DES FIGURES

2.1 Etat initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Etat 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Etat 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4 Etat 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.5 Solution trouvee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.1 Influence du nombre d’iterations . . . . . . . . . . . . . . . . . . . . 143.2 Influence du nombre d’agents . . . . . . . . . . . . . . . . . . . . . . 153.3 Influence de c1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.4 Influence de c2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.5 Influence de c3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

XVII

LISTE DES ALGORITHMES

2.1 Algorithme du recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . 33.1 Algorithme des essaims particulaires . . . . . . . . . . . . . . . . . . . . 10

XVIII

INDEX

SYMBOLS˜OptiFunc, VI˜Particle, VIII˜Swarm, XI

Aanalysis, XII

Ccompute, VI, VIIIcompute_coord, I

Eevent_expose, IIevent_keypress, IV

GgetDimension, VIgetFunction, XIIgetMediane, XIIIgetName, VI, VIIgetNbIter, XIIIgetNbParticles, XIIIgetPBest, IXgetRand, IXgetRange, VI, VII

IinitializeSwarm, XIII

Llink, Ilink_0, II

Mmain, IV, XIV

OOptiFunc, V

PParticle, VIIIprintSolution, XIII

Rrecuit, IIresolve, XI

SsetDimension, VIsetFunction, XIIsetName, VIsetNbIter, XIIIsetNbParticles, XIIIsetRange, VISwarm, X, XI

Uupdate, VIII

XIX

Documents

Métaheuristiques - Freedevezeb.free.fr/downloads/projets/metaheuristique.pdf · 3.2 Les essaims particulaires L’optimisation par essaims particulaires1 (OEP) est une technique