INSTITUT SUPERIEUR

DINFORMATIQUE DE MODELISATION ET DE LEURS APPLICATIONS COMPLEXE DES CEZEAUX BP 125 63173 AUBIERE CEDEX

Rapport de Projet 3me anne Modlisation et Calcul Scientifique

Optimisation par essaim particulaire pour un problme dordonnancement et daffectation de ressources

En vue de lobtention du diplme dingnieur

Pressente par : Arnaud Rioland Alexandre Eudes Responsable ISIMA : Michel Gourgand / Sylverin Kemmo

Dure : 150h Date : 2007

INSTITUT SUPERIEUR DINFORMATIQUE DE MODELISATION ET DE LEURS APPLICATIONS COMPLEXE DES CEZEAUX BP 125 63173 AUBIERE CEDEX

Rapport de Projet 3me anne Modlisation et Calcul Scientifique

Optimisation par essaim particulaire pour un problme dordonnancement et daffectation de ressources

En vue de lobtention du diplme dingnieur

Pressente par : Alexandre Eudes Arnaud Rioland Responsable ISIMA : Michel Gourgand / Sylverin Kemmo

Dure : 150h Date : 2007

Remerciements

Nous remercions Monsieur Sylverin Kemmo et Monsieur Michel Gourgand pour leur soutien et leur aide apportes tout au long de ce projet.

Rsum
Notre projet de dernire anne dcole dingnieur consistait t udier une mta heuristique, loptimisation par essaim particulaire. Cela consiste trouver loptimum dune fonction ou dun problme donn en dplaant des particules dans son ensemble de dfinition. Nous lavons implment pour des fonctions continues, et pour des problmes de recherche oprationnelle : de type flow shop et de type R.C.P .S.P. (Resource Constraint Project Scheduling Problem). Ensuite, nous avons ralis une interface graphique qui permet de visualiser les rsultats et de les commenter, mais qui pourra tre aussi rutilis pour dautres problmes doptimisation. Mot cl : Optimisation, Essaim particulaire, Mta-heuristique, Recherche oprationnelle, flow shop, R.C.P.S.P. , Interface graphique

Abstract
During our last Engineering School year, we have to study a meta-heuristic: the particular swarm optimization (P.S.O.). It consists in finding the function or problems optimum. We have programmed for continuous functions and for operations research problem which are flow shop and R.C.P.S.P. (Resource Constraint Project Scheduling Problem). Then, we design a graphical interface to be enabled to display results and to comment its, but it would be reused on other optimization problem. Keyword: Optimization, Particular swarm, Meta heuristic, Operations research, Flow shop, R.C.P.S.P., graphical interface

Tables des Matires

Introduction .......................................................................................................................................... 1 I. 1. 2. 3. Prsentations de l'algorithme d'optimisation par essaim de particules ........................................ 2 Dfinitions ................................................................................................................................. 2 Principe gnral de l'optimisation par essaim de particule ....................................................... 2 Optimisation continue ............................................................................................................... 4 a) Le flow-shop ............................................................................................................................ 6 b) Le RCPSP (Resource Constraint Project Scheduling Problem) .............................................. 9 II. 1. 2. 3. 1. 2. Implmentation .......................................................................................................................... 12 Lapplication ........................................................................................................................... 12 Technologie XML ................................................................................................................... 13 Programmation de la mta heuristique.................................................................................... 13 Les classes gnriques ..................................................................................................... 15 Classe spcifiques ............................................................................................................ 16

4. Optimisation discrte ................................................................................................................... 6

4) Linterface graphique................................................................................................................. 18

Table des figures

Figure 1 - Exemple de voisinage gographique ................................................................................... 3 Figure 2 - Deux cas de voisinage social ............................................................................................... 4 Figure 3 - Principe du dplacement d'une particule ............................................................................. 5 Figure 4 - Prsentation des 2 cas pour le calcul du makespan ............................................................. 7 Figure 5 - Evaluation du makespan pour le RCPSP .......................................................................... 10 Figure 6 Flux et utilisation de lXML .............................................................................................. 12 Figure 7 - Reprsentation UML de la partie calcul ............................................................................ 14 Figure 8 Arbre dhritage de la classe problme ............................................................................ 16 Figure 9 - Description de la partie dition de linterface graphique .................................................. 19 Figure 10 - Description de la partie rsultat de linterface graphique ............................................... 20

Introduction
Loptimisation est omniprsente dans tous les domaines : dans lindustrie, dans lconomie, dans la recherche scientifique, dans larospatiale Cest la recherche des compromis entre un besoin et plusieurs contraintes : entre la rsistance et le poids, entre les cots, les ressources et les temps de production par exemple. De trs nombreuses techniques se sont dveloppes au cours du sicle dernier. Nous en avons tudi une : loptimisation par essaim particulaire. Cet algorithme tait conu lorigine pour rsoudre des problmes dfinis dans sur des ensembles continus. Il consiste en gros dplacer un ensemble de particules dans lespace de dfinition de la fonction que lon veut tudier et de mmoriser les coordonnes de la meilleure position. A lheure actuelle, la communaut scientifique travaille sur des problmes dans un contexte discret, des problmes dordonnancement, daffectation, de gestion de ressources comme le flow shop et le R.C.P.S.P. (Resource Constraint Project Scheduling Problem). Il existe parfois des algorithmes qui peuvent les traiter de manire exacte mais qui ont une complexit temporelle trop grande. Des mthodes ont t mises en place pour rsoudre ce type de problme par valeur approche et parmi elles, ladaptation de loptimisation par essaim particulaire. Elle a t imagine par Maurice Clerc, un chercheur qui travaille au sein de lentreprise France Tlcom, en 2000. On remplace les points par des ordonnancements et les fonctions continues par des fonctions dvaluation. Notre projet a consist mettre en place une interface graphique afin dtudier les diffrentes proprits de loptimisation par essaim particulaire. Nous avons donc programm cet algorithme pour optimiser une fonction continue, un problme de flow shop et un problme type R.C.P.S.P. et grce loutil de visualisation que nous avons produit, on a pu tudier les rsultats que nous avons obtenu. Tout dabord, nous allons vous prsenter loptimisation par essaim particulaire dans ses deux contextes (continus et discret) et les problmes du flow shop et du R.C.S.P.S.P. puis comment nous avons implment les algorithmes doptimisation et linterface graphique. Enfin nous disserterons sur les rsultats que nous ont donn nos diffrents tests.

I.

Prsentations de l'algorithme d'optimisation par essaim de particules

1. Dfinitions

En rgle gnrale, on ne connat pas toujours de mthode exacte pour trouver la solution d'un problme d'optimisation en recherche oprationnelle. Dans ce cas on peut d'abord tenter de voir si le problme que l'on tudie n'a pas de problme quivalent qui ont dj t rsolu. Si l'on n'a toujours pas trouv de mthode de rsolution alors on utilise ce que l'on appelle une heuristique, c'est--dire un algorithme qui donne une solution approche. Ces algorithmes sont assez intuitifs ou simples. On les dduits grce des observations et en faisant preuve de bon sens. Leur principe consiste souvent explorer un certain nombre de solutions et de mmoriser la meilleure. Ils peuvent faire intervenir le hasard: cela permet de balayer un plus grand nombre de solution ventuelle, mais il faut les excuter plusieurs fois pour tendre au mieux vers la solution optimale.

Certaines heuristiques sont classes parmi les mta-heuristiques. Ce sont des algorithmes dont le principe peut tre rutilis pour traiter diffrents problmes d'optimisation. Ce sont des principes gnriques que l'on adapte selon le besoin. La plus utilis des heuristiques et la plus simple est la descente stochastique. Voici son fonctionnement dans le cas d'un problme de minimisation : on choisit une solution initiale, on slectionne au hasard un de ses voisins : Si la valeur de la fonction objectif pour cette nouvelle solution est plus petite alors on prend ce nouveau point comme point de rfrence et on observe ses voisins. Sinon on recherche un autre voisin. On s'arrte quand on se rend compte que l'on ne trouve plus de meilleure solution.

2. Principe gnral de l'optimisation par essaim de particule

La mta-heuristique que nous avons tudie dans le cadre de notre projet est l'optimisation par essaim de particules. On dispose d'une fonction objectif optimiser dans un sens ou dans l'autre. Un essaim est un ensemble de particules positionnes dans l'espace de dfinition de la fonction objectif. Le principe de l'algorithme consiste dplacer ces particules dans l'espace de dfinition afin de trouver la solution optimale.

Une particule est caractrise par plusieurs attributs: sa position actuelle: c'est--dire ses coordonnes dans l'ensemble de dfinition et la valeur de la fonction objectif lui correspondant. sa meilleure position : cest la valeur obtenue par la particule et ses coordonnes. sa vitesse: cette donne, recalcule chaque itration de l'algorithme permet de dduire la position suivante de la particule. Elle est fonction de la meilleure position de la particule depuis le dbut de la recherche, du voisin le mieux positionn l'instant actuel et de la vitesse prcdente de la particule. ses voisins: c'est un ensemble de particule qui influe sur ses dplacements, en particulier celui qui est le mieux positionn.

Il faut ensuite dfinir les voisinages et leur structure, il en existe de deux types :

les voisinages gographiques : les voisins d'une particule sont ses voisines les plus proches. Ce type de voisinage impose l'utilisation d'une distance pour recalculer chaque itration (ou toutes les k itrations) les voisins de chaque particule. Ci-dessous un exemple o les voisins dune particule sont les deux particules qui lui sont le plus proche.

Particule colore

Voisins de la particule
Figure 1 - Exemple de voisinage gographique

Les voisinages sociaux : les voisinages sont tablis l'initialisation et ne sont pas modifis ensuite. Il existe diffrentes structures de voisinages sociaux, nous allons vous en prsenter quelques uns.

Voisinage en ligne et colonne

Figure 2 - Deux cas de voisinage social

Voisinage en cercle

Si on utilise un voisinage en lignes et colonnes alors deux particules de lessaim sont voisines si elles appartiennent la mme ligne ou la mme colonne. Si on utilise un voisinage en cercle, les voisines dune particule sont, par exemple, les deux qui sont positionnes sa gauche et les deux qui sont positionnes sa droite.

Le principe de l'optimisation par essaim particulaire a notamment t conu partir de modles sociaux. En effet, chacune des particules agit en fonction de sa propre exprience et de celle de ses voisins. Pour se dplacer elle prend en compte son histoire (sa meilleure position) et est attire par la meilleure particule actuelle de son voisinage. C'est le modle des comportements d'individu au sein d'une tribu.

3. Optimisation continue
Dans un premier temps, pour nous familiariser avec la mta-heuristique et ses principes nous l'avons utilis dans son cadre originel : l'optimisation de fonctions continues.

Les particules sont dans un premier temps places alatoirement dans l'ensemble de dfinition de la fonction objectif. Ensuite on calcule pour chacune de ses particules leur vitesse. Dans ce but, on mmorise leur meilleure position depuis le dbut et on recherche celle de ses voisins les plus proches cet instant-l.

O :

et

et

sont les vitesses de la particule aux itrations k et k+1. est la meilleure position de la particule. est la meilleure position d'un voisin l'itration k. est la position de la particule litration k. sont des coefficients fixs au dbut du programme ou gnrs alatoirement.

Ensuite, on peut dterminer la position suivante de la particule grce la vitesse que lon vient de calculer :

O :

est la position de la particule l'itration k.

est gnre alatoirement. est nulle.

Position actuelle de la particule Vitesse actuelle

Position du meilleur voisin

Meilleure position de la particule

Nouvelle position

Figure 3 - Principe du dplacement d'une particule

Les fonctions tant gnralement dfinies dans un domaine born, on doit donc grer les effets de bord i.e. les moments o la particule s'chappe de cet ensemble. Dans ce cas deux optiques: on peut imaginer que la particule rebondit sur cette limite ou qu'elle reste bloqu sur la limite et qu'elle ne puisse plus se mouvoir dans cette direction. Nous avons choisit la deuxime solution, elle est plus simple mettre en uvre et permet d'tre plus prcis si la solution recherche se trouve sur les contours de l'ensemble de dfinition. 5

4. Optimisation discrte
Au dpart, les algorithmes doptimisation par essaim particulaire tait destine exclusivement pour des fonctions continues. En 2000, Maurice Clerc s'est rendu compte que cet algorithme pouvait tre utilis d'autres fins, et notamment pour rsoudre des problmes d'ordonnancement, d'affectation ou de planification.

a) Le flow-shop
Dans un premier temps, nous avons d adapter cette mta-heuristique au problme du flow shop. Le problme du flow shop est un problme d'ordonnancement. On a pices fabriquer et machines. On va donc noter le temps de traitement de la pice sur la machine . Les pices sont traites par toutes les machines et on a qu'une seule gamme (une gamme c'est l'ordre dans lequel les pices parcourent la chane de production). L'objectif est de dterminer l'ordonnancement de traitement des pices qui minimise le makespan, c'est--dire le temps total de traitement de l'ensemble des pices.

1. Calcul du makespan pour un ordonnancement des pices donnes :

On dfinit la fonction qui retourne la pice traite en ime position et la date de sortie de la pice de la machine . On commence par placer la premire pice de lordonnancement sur la premire machine.

Ensuite, on calcule les dates de fin de traitement des pices sur la premire machine.

Il en est de mme pour les dates de fin de traitement de la premire pice de lordonnancement sur les diffrentes machines.

Les calculs des autres dates de sortie se fait rcursivement. Il y a diffrents cas considrer, ils dpendent de la date de fin de traitement de la pice prcdente sur la machine et de celle de la pice sur la machine prcdente (figure 3). Dans le premier cas, cest le traitement de la pice sur la machine prcdente qui se termine aprs la fin du traitement de la pice prcdente dans lordonnancement donc lopration commence en . Dans le second, les dates de fin sont inverses et la pice commence tre trait en do la formule :

On peut donc calculer le makespan :

Figure 4 - Prsentation des 2 cas pour le calcul du makespan

2. Notion de vitesse :
Le principal problme du passage du continu au discret rside dans les notions de position et de vitesse. Une position dans lensemble de recherche correspond un ordonnancement. Les vitesses doivent permettre de passer dun ordonnancement un autre cest pourquoi on les dfinit comme un ensemble de permutation.

, , oprateurs

et les deux soustractions ci-dessus correspondent des vitesses. Les et sont des ordonnancements. Il faut donc redfinir les et .

Loprateur + permet dappliquer un ordonnancement un ensemble de permutation (une vitesse). Exemple : Loprateur Exemple :

est utilis pour concatn deux permutations.

Loprateur est la multiplication par un scalaire positif dune permutation. Si ce scalaire est un entier alors on rpte n fois les permutations. Si cest un rel x compris entre 0 et 1, on enlve certaines permutations, plus le nombre est petit et moins on en laisse. Pour les autres entiers positifs on les crit sous la forme n + x. Loprateur retourne lensemble des permutations qui permettent de passer dun ordonnancement un autre. Exemple :

Nous disposons maintenant de tous les outils pour rsoudre un problme de flow shop par la mthode de l'optimisation par essaim particulaire. On peut suivre dsormais le principe de la mta heuristique.

3. No hope
La procdure no hope (pas despoir en franais) permet de relancer lessaim quand on ne parvient plus amliorer la solution optimale du problme. Aprs un nombre important ditration, on rinitialise les particules afin de pouvoir analyser dautres ordonnancements (cf .II.2.1)

b) Le RCPSP (Resource Constraint Project Scheduling Problem)

Le problme du R.C.P.S.P. est la fois un problme d'ordonnancement et un problme de planification. On dispose d'un nombre constant de ressource. On a n tches effectuer, chacune ncessite un certain nombre de ressource pendant un temps de traitement donn. Il s'agit donc de gnrer un planning qui minimise la dure totale ncessaire pour effectuer toutes les tches.

On utilise les mmes principes pour les positions et les vitesses que ceux du flow shop. C'est lors du calcul du makespan que l'on dtermine les dates de dbut et de fin des diffrentes tches. L'algorithme ne se contente pas de calculer la dure totale des oprations mais planifie toutes les tches.

1. Calcul du makespan :
On dispose d'un ordonnancement des tches qui ne correspond pas l'ordre dans lequel ces tches sont effectues (contrairement au flow shop par exemple) mais plutt l'ordre dinsertion des tches dans le planning. En effet, on commence par slectionner la premire opration de l'ordonnancement: on l'insre dans le planning au tout dbut du calendrier. On prend la deuxime tche et on regarde si lon dispose dassez de ressource t=0 :

si oui alors on regarde si ces ressources restent disponibles pendant la dure de la tche. Sinon on recherche une autre date de dbut de la tche (on recherche la date la plus petite possible).

On continue rentrer les tches dans le planning au fur et mesure. Pour rcuprer le temps total de traitement, on mmorise la plus grande des dates de fin de tche, ce qui va nous permettre dvaluer les diffrents ordonnancements. Le passage du flow shop au R.C.P.S.P. s'est donc limit la modification de la fonction objectif.

MAKESPAN
Figure 5 - Evaluation du makespan pour le RCPSP

Sur lexemple ci-dessus, les pices sont insres dans lordre croissant.

2. Prise en compte des contraintes de prcdence

A cela, nous devons ajouter les contraintes de prcdence. La tche i prcde la tche j si la date de fin de la tche i est infrieure la date de dbut de la tche j. Pour grer ces contraintes, il faut bien veiller ce que dans les ordonnancements i est plac avant j pour toutes les contraintes contenues dans ce problme et que la date de dbut dune tche soit suprieure toutes les dates de fin des tches qui la prcde. Dans un premier temps, il faut adapter les ordonnancements ces contraintes : si une tche en prcde une autre, alors elle devra tre plac devant dans lordonnancement. Pour cela, il faut redfinir loprateur qui permet dappliquer une vitesse (cest--dire un ensemble de permutations) un ordonnancement, ceci afin quaucune contrainte de prcdence ne soit viole. Prenons un exemple simple :

Exemple :

avec la contrainte

On veut permuter 2 et 5 sur lordonnancement ci-dessus. On ne peut pas les changer directement comme sur le flow shop car, dans ce cas, on violerait la contrainte , il faut donc procder pas pas. La contrainte nexiste pas : on peut donc les permuter. De la mme manire on dmontre que lon peut intervertir 2 et 4 puis 2 et 5. 2 a pris la place de 5, on obtient lordonnancement suivant : . Il faut maintenant ramener le 5 la place du 2. On peut 10

changer 4 et 5. Ensuite, en principe, il faudrait permuter 3 et 5 mais cela violerait la contrainte : dans ce cas l, on dcide de laisser 5 cette place. Le principe gnral consiste donc dplacer les deux tches dans l ordonnancement dune place chaque fois, on commence par bouger vers la droite la premire tche dans lordonnancement et on sarte si on a atteint la place dsire ou si il y a une situation de blocage dues aux contraintes de prcdence. On opre de la mme manire avec la seconde tche changer, mais en se dplaant vers la gauche.

Il faut aussi prendre en compte cette contrainte au niveau du calcul du makespan. On peut fixer la date minimale de dbut dune tche comme tant le maximum de toutes les dates de fins des tches qui la prcde. On les connait toutes car grce lordonnancement car on les a dj calcules.

11

II.

Implmentation
1. Lapplication

Le but de ce projet tait de raliser une application capable doptimiser diffrents problmes grce loptimisation par essaim particulaire. Il tait aussi demand davoir une interface graphique permettant de dfinir les diffrents paramtres. Lapplication se devait dtre rapide et modulaire. Pour cela il a t dcid de dcoupler la partie implmentation de la mta-heuristique et la visualisation graphique. Le systme dentre sortie t construit de manire dcoupler le plus possible le module de calcule de linterface. Pour cela on a utilis la technologie XML pour la conception de linterfaage entre les deux modules :

Gnration Automatique

Fichier de Rsultat

Module de Calcul Interface Graphique

Fichier de configuration

Outil Statistique

Interface Graphique

Figure 6 Flux et utilisation de lXML

Lutilisation de lXML permet de crer des flux entre les diffrentes partie du logiciel qui sont ainsi dcoupler et peuvent tre lancs sur des machines diffrentes mais aussi tre rutilis plus facilement. Notre travail a consist crer le module de calcul et linterface graphique, un module de gnration automatique du fichier de configuration pourra tre implment par la suite. Lapplication se divise en deux parties distinctes : Le code de calcul ralis en c++ pure. Cela permet de pouvoir, utiliser ce code sur tout type de machine. Il lit en entr un fichier de configuration qui dcrit les actions effectuer : Le Problme et la manire de loptimiser. Et gnre en sortie un fichier de rsultat. Linterface graphique, ralis en c++ .net qui fonctionne seulement sous Windows. 12

Elle est capable de gnre le fichier de configuration et de lire le fichier de donnes.

2. Technologie XML

La technologie Xml( Extensible Markup Language) provient des technologie web et permet de construire, utiliser ,explorer des documents contenant des donnes structures par un systme de balise. Ce format de fichier a lavantage dtre facile parser(lire le fichier et stocker ses informations dans lapplication) Le fait de rendre compte de la structure des donnes, la rend parfaitement compatible avec le concept dobjet des langages volus actuels. Ces deux technologies se combinent parfaitement. Le langage objet permet de crer les structures dynamiques et le XML apporte la partie transport, stockage et conversion de linformation. Puisque lie aux technologies web, cette technologie est en plein essor et de ce fait, son utilisation est simplifie par lexistence de parseur prt lemploi. Dans notre cas nous avons utilis la bibliothque Xerces qui a lavantage dtre en c++ et de plus dtre portable. Cette bibliothque fournit un patron de conception dun parseur Xml qui permet de crer son propre parseur adapt ses donnes.

3. Programmation de la mta heuristique

Nous avons choisi le C++ comme langage de programmation pour ce projet. Il a lavantage dtre orient objet et cela nous a permis de factoriser le code et de n'crire quune fois les principes gnraux de loptimisation par essaim particulaire. De plus, la bibliothque S.T.L. (standard Template Library) contient des outils pour manipuler trs facilement des listes utiles pour dfinir un essaim ou des voisinages.

On peut partager en deux catgories les diffrentes classes que l'on a implmentes : Les classes gnriques, c'est--dire celles qui sont indpendantes du problme rsoudre: Essaim : cette classe contient l'ensemble des particules et les voisinages, elle contient la position de la valeur optimale trouve. Particule : c'est une composante de l'essaim qui se dplace dans l'espace de dfinition de la fonction objectif. Elle contient sa position actuelle, sa meilleure position et leurs valeurs.

13

1 1 Essaim

Meilleure particule

1 Particule

Problme

1 Position actuelle

1 Meilleur position

Vitesse

Instance Gnre

Gnre

Figure 7 - Reprsentation UML de la partie calcul

Les autres classes sont spcifiques au problme rsoudre : Problme : elle contient les informations gnrales qui sont recueillies dans les fichiers d'entre et la fonction objectif. Instance : cest les coordonnes dune particule dans lensemble de dfinition et la valeur de la fonction objectif en ce point. Vitesse : elle contient les donnes qui permettent de passer d'une instance une autre.

14

1. Les classes gnriques

La classe Essaim contient le nombre de particules et la liste les regroupant. Elles sont stockes dans un vecteur de la S.T.L. (vector<Particule*>). On lui associe un Problme. Elle possde aussi un attribut qui pointe sur la meilleure particule trouve depuis le dbut de la recherche de loptimum et une particule par voisinage qui contient la meilleure position trouve par le voisinage. Cest partir de cette classe que lon gre lavance de lalgorithme. Elle ordonne le dplacement des particules. A chacune on leur demande dans un premier temps de dterminer leur nouvelle vitesse avant de les dplacer. La classe Particule permet de reprsenter les points qui se dplacent dans lespace de dfinition de la fonction objectif. Elle contient deux lments de la classe Instance, lun contenant la position actuelle de la particule, et lautre la meilleure position visite par cette mme particule. Elle est associe une vitesse qui permettra de calculer la prochaine position.

La classe Essaim possde une mthode No Hope qui est active si la meilleure position nest pas amliore pendant les X dernires itrations. Elle consiste , dans un premier temps, faire revenir la particule sa meilleure position. Et partir de la a ce dplacer alatoirement. Pour cela chaque itration on cr une nouvelle vitesse et on lapplique sur la particule. On sarrte dans le cas o la valeur de la particule sest amliore ou si lon a effectu X itration. Cette procdure permet de ressusciter une particule qui sest orient dans une direction noffrant plus de valeurs intressantes et restaurer la diversit au sein de lessaim.

Le second problme concernant les voisinages concerne leur stockage. Nous avons test deux mthodes: Pour chaque particule, on cre une liste o on mmorise ladresse de chacun des voisins. Pour rechercher le meilleur, on parcourt cette liste pour chacune des particules et on retient le meilleur. On dfinit tous les voisinages par rapport lessaim. On commence pour chacun des voisinages par rcuprer la meilleure position actuelle puis pour toutes les particules, on slectionne la meilleure position des voisinages auxquelles elle appartient.

Nous avons commenc par mettre en place la premire mthode puis nous nous sommes rendu compte quen utilisant la deuxime on ne parcourt quune seule fois chaque voisinage par itration, ce qui permet de gagner du temps en cas dun nombre important de particule.

15

2. Classe spcifiques

Pour chaque problme traiter par la mthode dessaim particulaire, on implmente trois classes spcifiques : Une classe qui drive de Problme qui contiendra les attributs spcifiques chaque problme et la fonction dvaluation dune Instance. Une classe qui drive de Instance qui contiendra spcificit des solutions du problme et lapplication dune vitesse une Instance. Une classe qui drive de Vitesse qui contiendra la reprsentation dune vitesse et les operateurs pour les manipuler entre elles.

Problme

RCPSP Problme

Flow Shop Problme

Continu Problme

Figure 8 Arbre dhritage de la classe problme

Larbre ci-dessus est aussi valable pour les classes Instance et Vitesse, en prcisant que les classes Vitesse spcifique au RCPSP et au flow shop sont identiques.

16

a) Le Problme continu
Dans le cas du Problme continu, il faut dfinir le problme, linstance, la vitesse correspondante. En continu, la dfinition du Problme revient donner la fonction dvaluation, le domaine de validit, le nombre de dimensions. Une instance contient la position courante, un point de , c'est--dire un tableau de rel. Elle doit vrifier que la position reste valide aprs chaque dplacement (on reste dans les bornes). La vitesse est un vecteur de , donc un tableaux de rel aussi.

b) Le Problme de Flowshop
Pour implmenter le problme du flow shop, une Instance est une liste qui contient lordre dans lequel les pices doivent tre traites. Les listes sont initialises par lintermdiaire de la fonction random_shuffle( iterator deb, iterator fin) de la S.T.L. Cette fonction prend un lment de la classe vector (son dbut et sa fin) en paramtre puis rordonne alatoirement ses lments. La classe Instance contient aussi la valeur du makespan correspondant lordonnancement. Cette valeur est calcule dans la classe Problme, qui contient la fonction dvaluation spcifique au problme du flow shop explicite dans au chapitre prcdent, et elle contient aussi une mthode permettant de lire et denregistrer les donnes des fichiers de donnes, qui sont le nombre de pice, le nombre de machines et tous les temps de traitement.

La classe Vitesse contient une liste qui stocke les permutations. On rentre les coordonnes des points qui devront tre intervertis. Cette liste contient 2n entiers, chaque permutation correspondant 2 entiers (les 2 permuter). Ensuite, nous avons cod les oprateurs ncessaires aux calculs. Loprateur dfini une simple concatnation, loprateur en rptant plusieurs fois la liste ou en la scindant. Loprateur est en fait ici un constructeur : on lui fournit deux ordonnancements dentre et il retourne une nouvelle instance de la classe Vitesse qui permet daller dun ordonnancement un autre. Il ne reste plus qu appliquer ces permutations la particule que lon va dplacer.

C) Le RCPSP
On est parti de lexistant pour le flow shop, on conserve la gestion des ordonnancements. Seul change leur initialisation : on gnre dans un premier temps une liste qui est commune pour toutes les particules qui assure le respect des contraintes de prcdence (pour cela on insre les tches une une dans lordonnancement si leurs prdcesseurs sont dj insrs dans la liste. Ensuite pour chacune des particules on applique une vitesse gnre alatoirement, ce qui permet de diversifier les particules avant de lancer loptimisation. Dans la classe Instance, on a modifi aussi loprateur +, celui que lon utilise pour appliquer une vitesse une particule. On bouge chaque fois dune place les tches dans lordonnancement, afin de ne pas violer une contrainte de prcdence quand on effectue une 17

permutation (cf. I.4.b.2). Quand on programme ces vitesses, on commence par dplacer vers la droite la premire tche permuter : Si elle peut tre positionne la place de lautre tche que lon voulait permuter alors dcale cette autre tche dune case vers la droite, et il faut prendre en compte ce dcalage lorsquon va vouloir ramener cette tche la place de la premire. Sinon, la deuxime tche de la permutation na pas boug et on la ramne partir de sa position initiale.

Enfin, dans la classe Problme, on rcupre les donnes ncessaires contenues dans les fichiers dentre, cest--dire le nombre de tche, leurs dures et leurs quantits de ressources ncessaires, le nombre total de ressource disponible par unit de temps, le nombre maximum ditrations, et toutes les contraintes de prcdence. Ces dernires sont stockes dans une matrice PREC.

Reste ensuite coder la fonction dvaluation (cf. I.4.b.1) qui retourne le makespan, les dates de dbut et de fin de chacune des tches tout en prenant bien en compte les contraintes de prcdence. On a ajout dans la classe Instance deux tableaux pour mmoriser ces donnes.

4) Linterface graphique
Linterface graphique est une surcouche permettant dutiliser le code de calcul sans programmer directement ou diter les fichiers xml la main. Son but est de simplifier la tche de lutilisateur en lui donnant accs directement aux diffrents paramtres et en lui apportant une visualisation graphique des rsultats. Elle a t programme grce la technologie c++.net qui permet de crer relativement simplement des interfaces graphiques pour Windows. Le choix du c++ simposait naturellement pour garder une continuit avec le module de calcul. Elle est compose de deux panneaux : Le premier permet de gnrer le fichier de configuration en crant une liste de tche effectuer. Elle donne la possibilit de charger ou dexporter un fichier de configuration ou dexcuter le calcul directement. Elle se prsente comme suit (voir figure): La premire partie gre la configuration : Un panneau permet dajouter une nouvelle tche en dfinissant les paramtres : - Nombre de rplication : le nombre de fois o lon excute la procdure destimation. En effet les positions et les vitesses initiales dpendent dun gnrateur alatoire. Pour tre sr que la mthode donne des rsultats dans tout les cas, il est ncessaire dexcuter un grand nombre de fois la mthode pour en garder que la tendance gnrale. 18

Nombre ditration : le nombre maximum ditration effectu La valeur optimal ou la meilleure solution connue : ce paramtre permet de calculer quelle distance on se situe de la solution optimale et elle sert de test darrt pour le calcul du temps de convergence. - La case cocher Optimale permet de dire sil sagit de la valeur optimale ou non. Dans le cas dune valeur optimale, on arrte la mthode sitt cette valeur rencontre. - La case cocher mmoriser tout permet de dcider si on veut stocker toute les valeurs au cours des itrations ou seulement les rsultats statistiques. - Le cadre suivant sert dfinir les proprits de lessaim : les paramtres C1 et C2 et le nombre de particule. - Le bouton ajouter permet dajouter la tache dfinie prcdemment dans la liste. Le deuxime panneau permet de grer la liste des tches : - Le bouton Supprimer supprime une tche. - Les boutons charger et exporter permettent de grer le fichier xml de configuration associ la liste des taches. - Le bouton calculer sert excuter le calcul et afficher les rsultats dans la deuxime partie. Mode dition Liste des tches

Paramtre gnrale

Proprit de lessaim

Type de problme

Ajouter une tche la liste

Supprimer une tche de la liste

Charger/Exporter le ficher de configuration

Excuter la liste de Tches

Figure 9 - Description de la partie dition de linterface graphique

19

La deuxime partie gre laffichage des rsultats : Un arbre permet daccder tous les niveaux de donnes stockes : du problme qui donne les statistiques gnrales de chaque excution qui donne la moyenne et la meilleure position au court du temps et enfin de chaque particule. Le graphe permet de visualiser graphiquement les rsultats associ llment slectionn dans larbre. Le curseur permet de slectionner litration dont on veut afficher les proprits. Le cadre du bas affiche les informations courantes. Les boutons charger et exporter permettent de grer le ficher de rsultat.

Mode rsultat

Liste des rsultats

Evolution dune

particule
Evolution de la meilleure particule

Position du curseur

Dplacer la position courante

Charger/Exporter le ficher de rsultat

Proprits de la position courante

Figure 10 - Description de la partie rsultat de linterface graphique

20

5) Rsultat

Optimisation de fonction continu : Pour 30 rplications de 20 particules et 100 itrations avec C1=0.5 C2=0.5

fonction

Norme
Rosenbrock Rastrigin Griewank

Nb ditration moyen 22 34.6333 1.33333 4.2 100

Valeur moyenne 0. 00569911 150.926 0.000541188 0.0195548 0.00245586

objectif

Minimum 3*10-16 3.2546e-013 0 1.55312e011 0.00245586

T moyen(s)

Objectif atteint 28 19 30 20 0

0.01 100 100 0.1 10-5

0.13 0.13 0.13 0.13 0.16

shaffer

Pour 30 rplications de 20 particules et 100 itrations avec C1=0.2 C2=0.8 fonction Nb ditration moyen 10.7333 25.0667 1.06667 11.6667 100 Valeur moyenne 3.62173e-006 32.5276 0.00377072 0.0396408 0.0108516 objectif minimum T moyen(s) Objectif atteint 28 25 30 28 0

Norme
Rosenbrock Rastrigin Griewank

0.01 100 100 0.1 10-5

1.56636e-021 1.96272e-009 0.00377072 0.0396408 0.00245586

0.13 0.13 0.13 0.13 0.16

shaffer

On voit que loptimisation par essaim particulaire optimise les fonctions objectifs. La valeur objectif est atteint dans la plupart des cas et le minimum est trs proche de 0. Linfluence des coefficients c1 et c2 est manifeste mais son influence dpend de la fonction la certain jeu de coefficient amliore la solution de certain problme, ces coefficients en dgrade dautre.

21

Pour le Flow shop, Avec C1=0.5 et C2=0.5

fonction Pb.1
Pb.19 Pb.1 Pb.19

Nb ditration Valeur moyen moyenne 400 2457.6 400 2000 2000 2366.5 2311.9 2455.2

objectif 2213 2180 2213 2180

minimum 2408 2316 2381 2290

T moyen(s) 3 3 20 20

Objectif atteint 0 0 0 0

Pour le Flow shop la meilleure solution connue est approche asymptotiquement mais ncessite un grand nombre ditration pour latteindre (convergence lente). Les coefficients C1 et C2 doivent tre rgl prcisment pour converger plus vite.

22

Conclusion
Nous avons implment loptimisation par essaim particulaire sur des fonctions dfinies dans des domaines continus, et sur des problmes de type flow shop ou R.C.P.S.P. Le point dlicat concerne la recherche des bons coefficients c1 et c2 (les constantes que lon applique aux vitesses) pour sapprocher au maximum des solutions optimales connues. Linterface graphique que lon a produite est extensible tous les problmes doptimisation. Ces algorithmes peuvent tre coder en Fortran, par exemple, puis les rsultats sont sauvegards dans un fichier XML. Ce dernier sera recharg par notre interface graphique qui pourra afficher toutes les donnes dont on a besoin. On peut, de plus, gnrer un module statistique qui fait varier une constante de lalgorithme doptimisation, ce qui nous permet dtudier diffrentes alternatives. En partant de ce programme, on pourrait imaginer un logiciel qui pourrait appliquer diffrentes mta heuristiques (recuit simul, algorithme tabou) des problmes de combi natoire, daffectation, dordonnancement et alors comparer chacune des mthodes sur un exemple prcis. Les graphiques permettraient de confronter les algorithmes et notamment leur vitesse de convergence.

23

Bibliographie :
[Link] Discrete Particle Swarm Optimization illustrated by the Traveling Salesman Probleme 2003 David LEMOINE Optimisation par essaim particulaire (Examen probatoire du diplme dingnieur C.N.A.M.) 2004

Instance du flowshop
[Link] Instance du Rcpsp [Link]

24