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 tudier 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. Prsentations de l'algorithme d'optimisation par essaim de particules ........................................ 2

1. Dfinitions ................................................................................................................................. 2

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

3. Optimisation continue ............................................................................................................... 4

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

a) Le flow-shop ............................................................................................................................ 6

b) Le RCPSP (Resource Constraint Project Scheduling Problem) .............................................. 9

II. Implmentation .......................................................................................................................... 12

1. Lapplication ........................................................................................................................... 12

2. Technologie XML ................................................................................................................... 13

3. Programmation de la mta heuristique.................................................................................... 13

1. Les classes gnriques ..................................................................................................... 15

2. Classe spcifiques ............................................................................................................ 16

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

1

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.

2

II.. PPrrsseennttaattiioonnss ddee ll''aallggoorriitthhmmee dd''ooppttiimmiissaattiioonn ppaarr eessssaaiimm ddee ppaarrttiiccuulleess

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.

3

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.

Figure 1 - Exemple de voisinage gographique

Particule Voisins de la particule

colore

4

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.

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.

Voisinage en ligne et colonne Voisinage en cercle

Figure 2 - Deux cas de voisinage social

5

O : 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.

, et 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.

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.

Position

actuelle de

la particule

Meilleure

position de

la particule

Position du

meilleur

voisin

Nouvelle position

Vitesse

actuelle

Figure 3 - Principe du dplacement d'une particule

6

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.

7

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

1

8

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.

, et les deux soustractions ci-dessus correspondent des vitesses. Les

, et sont des ordonnancements. Il faut donc redfinir les

oprateurs et .

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

Exemple :

Loprateur est utilis pour concatn deux permutations.

Exemple :

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.

9

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.

10

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

Figure 5 - Evaluation du makespan pour le RCPSP

MAKESPAN

R

1 2 3 4

11

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 lordonnancement 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.

12

IIII.. IImmppllmmeennttaattiioonn

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 :

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.

Figure 6 Flux et utilisation de lXML

Interface

Graphique

Module de

Calcul

Outil

Statistique

Fichier de

configuration

Fichier de

Rsultat

Gnration

Automatique

Interface

Graphique

13

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.

14

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.

Figure 7 - Reprsentation UML de la partie calcul

Essaim

Particule

Problme

Instance

Vitesse

Gnre Gnre

N Meilleure

particule

1

1 1

Position

actuelle

Meilleur

position

1

1

15

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). 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.

16

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.

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.

Figure 8 Arbre dhritage de la classe problme

RCPSP

Problme

Problme

Continu

Problme

Flow Shop

Problme

17

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

18

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.

19

- 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.

Type de

problme

Mode dition Liste des tches

Ajouter une

tche la liste Supprimer une

tche de la liste

Charger/Exporter le

ficher de configuration

Excuter la

liste de Tches

Paramtre

gnrale

Proprit de

lessaim

Figure 9 - Description de la partie dition de linterface graphique

20

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

Proprits de la

position courante

Dplacer la

position courante

Charger/Exporter le

ficher de rsultat

Position du

curseur

Evolution dune

particule Evolution de la

meilleure particule

Figure 10 - Description de la partie rsultat de linterface graphique

21

5) Rsultat

Optimisation de fonction continu :

Pour 30 rplications de 20 particules et 100 itrations avec C1=0.5 C2=0.5

fonction Nb

ditration moyen

Valeur

moyenne

objectif Minimum T moyen(s) Objectif

atteint

Norme 22 0. 00569911 0.01 3*10-16

0.13 28

Rosenbrock

34.6333 150.926 100 3.2546e-013 0.13 19

Rastrigin

1.33333 0.000541188 100 0 0.13 30

Griewank 4.2 0.0195548 0.1 1.55312e-

011

0.13 20

shaffer 100 0.00245586 10-5

0.00245586 0.16

0

Pour 30 rplications de 20 particules et 100 itrations avec C1=0.2 C2=0.8

fonction Nb

ditration moyen

Valeur

moyenne

objectif minimum T moyen(s) Objectif

atteint

Norme 10.7333 3.62173e-006

0.01 1.56636e-021 0.13 28

Rosenbrock

25.0667 32.5276 100 1.96272e-009 0.13 25

Rastrigin

1.06667 0.00377072

100 0.00377072 0.13 30

Griewank 11.6667 0.0396408 0.1 0.0396408 0.13 28

shaffer 100 0.0108516 10-5

0.00245586 0.16

0

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.

22

Pour le Flow shop,

Avec C1=0.5 et C2=0.5

fonction Nb ditration moyen

Valeur

moyenne

objectif minimum T moyen(s) Objectif

atteint

Pb.1 400 2457.6

2213 2408 3 0

Pb.19

400 2366.5

2180 2316 3 0

Pb.1 2000 2311.9 2213 2381 20 0 Pb.19

2000 2455.2 2180 2290 20 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.

23

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 combinatoire, 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.

24

Bibliographie :

M.Clerc 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 http://www.cs.colostate.edu/sched/generatorNew/index.html

Instance du Rcpsp

http://129.187.106.231/psplib/

IntroductionPrsentations de l'algorithme d'optimisation par essaim de particulesDfinitionsPrincipe gnral de l'optimisation par essaim de particuleOptimisation continue4. Optimisation discrtea) Le flow-shop1. Calcul du makespan pour un ordonnancement des pices donnes :2. Notion de vitesse :3. No hope

b) Le RCPSP (Resource Constraint Project Scheduling Problem)Calcul du makespan :Prise en compte des contraintes de prcdence

ImplmentationLapplicationTechnologie XMLProgrammation de la mta heuristiqueLes classes gnriquesClasse spcifiquesa) Le Problme continub) Le Problme de FlowshopC) Le RCPSP

4) Linterface graphique