Rpublique Algrienne Dmocratique et populaire

Ministre de lEnseignement Suprieur et de la Recherche Scientifique

Universit Mouloud Mammeri de Tizi-Ouzou

Facult de Gnie Electrique et Informatique

Dpartement Automatique

MEMOIRE DE MAGISTER

En Automatique

Option : Automatique des systmes continus et productique

prsent par

IDIRI Ghania

Thme :

Commande prdictive des systmes non linaires dynamiques

Mmoire soutenu le 06 /07/ 2011 devant le jury dexamen compos de :

Prsident : DJENNOUNE Sad Professeur lUMMTO

Rapporteur : HAMMOUCHE Kamal Matre de confrences A l'UMMTO

Examinateur : OUANES Mohand Matre de confrences A l'UMMTO

Examinateur : MANSOURI Rachid Matre de confrences A l'UMMTO

Examinateur : DJAMAH Tounsia Matre de confrences B l'UMMTO

Sommaire

Chapitre 0. Introduction Gnrale 01

Chapitre 1. Gnralits sur la Commande Prdictive 05 1.1 Introduction 05 1.2 Principe de la commande prdictive 06 1.3 Elments dune commande prdictive 08

1.3.1 Modle du systme 08 1.3.2 Prdiction 10 1.3.3 Critre de performance (fonction objectif) 10 1.3.4 Contraintes 12

1.3.5 Loi de commande 12 1.4 Algorithme DMC 13

1.4.1 Modle de prdiction 13 1.4.2 Synthse dun correcteur DMC 16 1.4.3 Evaluation des performances de lalgorithme DMC 16 1.4.4 Etude de linfluence des paramtres de rglage dune commande prdictive 19

1.5 Stabilit de la commande prdictive 22 1.6 Etat de lart sur la commande prdictive 24 1.7 Conclusion 25

Chapitre 2. Optimisation Globale dans 26 2.1 Introduction 26 2.2 Formulation mathmatique dun problme doptimisation 27

2.3 Classification des problmes doptimisation dans 28 2.4 Conditions pour un minimum 29 2.5 Mthodes de rsolution des problmes doptimisation 30 2.6 Classifications des mthodes doptimisation 32 2.7 Intrt des mthodes globales 34 2.8 Mthodes doptimisation globales et commande prdictive 37 2.9 Conclusion 38

Chapitre 3. Mthodes doptimisation globale : Alienor et Essaim de Particules 40 3.1 Introduction 40 3.2 Mthode dAlienor 41 3.3 Mthode dessaim de particules 45

3.3.1 Principe de la mthode dessaim de particules 46 3.3.2 Algorithme de la mthode dessaim de particules 47

3.4 Application lidentification dun systme non linaire 50 3.4.1 Mthode du modle 52 3.4.2 Modle du systme non linaire identifier 54

3.5 Conclusion 56

Chapitre 4. Commande Prdictive Non linaire Base sur lOptimisation Globale 58 4.1 Introduction 58 4.2 Etat de lart de la commande prdictive non linaire 59 4.3 Commande prdictive non linaire 61

4.3.1 Commande prdictive base sur la mthode dAlienor 63 4.3.2 Commande prdictive base sur la mthode dessaim de particules 66

4.4 Conclusion 69

Chapitre 0. Conclusion Gnrale 74

Liste des figures

1.1 Principe de la commande prdictive 07 1.2 Stratgie de commande prdictive 08 1.3 Rponse indicielle du systme 17 1.4 Poursuite et rejet de perturbation 18 1.5 Evolution de la commande 18 1.6 Influence de lhorizon de commande 20 1.7 Influence de lhorizon de prdiction 21 2.1 Evolution de la fonction objectif du problme doptimisation (2.24) 36 2.2 Evolution de la fonction objectif du problme doptimisation (2.25) 36 2.3 Fonction objectif et son enveloppe convexe 37 3.1 Exploration globale du plan paramtre par (spirale dArchimde) 42 3.2 Schma de principe du dplacement dune particule 47 3.3 Principe de la mthode du modle 53 4.1 Structure gnrale de la commande prdictive non linaire 62

4.2 Mthode dAlienor : cas sans contrainte sur la variable de commande ( )ku 70 4.3 Mthode dAlienor : cas avec contrainte sur la variable de commande

( )ku ( )( )25,1 ku 71 4.4 Mthode dessaim de particules : cas sans contrainte sur la variable de commande ( )ku 72 4.5 Mthode dessaim de particules : cas avec contrainte sur la variable de commande ( )ku 73

Liste des tableaux

1.1 Version commercialiss des correcteurs prdictifs 23 2.1 Classification des problmes doptimisation 28 4.1 Temps moyen pour le calcul de la commande 68

1

Introduction Gnrale

La commande prdictive constitue actuellement lapproche de commande la plus indique pour la commande des systmes complexes dans le milieu industriel. L'intrt est que des spcifications de fonctionnement ainsi que des contraintes d'exploitation (scurit de fonctionnement des biens, des personnels et de lenvironnement, qualit des produits), invitables pour la plupart des systmes, peuvent tre conjointement traites dans l'laboration de la loi de commande (Flaus, 1994 ; Camacho et Bordons, 2008 ; Findeisen et al. 2007). De plus, la mise en uvre dune commande prdictive est relativement simple et il en va de mme pour les outils thoriques ncessaires leur tude, ce qui justifie sa popularit en utilisation industrielle (Henson, 1998). Aussi, lvolution de linformatique sur le plan matriel et logiciel a propuls la commande prdictive pour occuper une place prpondrante dans les milieux acadmique et industriel (Martinsen, 2002).

La commande prdictive est une commande base sur le modle, par consquent avoir de bonnes performances est li directement la prcision et la complexit du modle utilis dans lalgorithme de commande pour la prdiction des sorties futures du systme (Huang, 2008; Magni et al. 2009). Sur ce plan, lexistence des calculateurs numriques avec des vitesses de traitement vertigineuses, et des capacits de stockage normes a largement contribu au succs de la commande prdictive.

Dans une stratgie de commande prdictive, les objectifs de commande sont spcifis par un critre minimiser et des contraintes imposer sur les variables d'tat, de commandes et de sorties (Flaus, 1994 ; Huang et Kadali, 2008 ; Camacho et Bordons, 2008). Par consquent, la commande appliquer, chaque instant dchantillonnage, est obtenue en rsolvant un

2

problme doptimisation avec contraintes en un temps infrieur la priode dchantillonnage (Cannon, 2004 ; Tatjewski, 2007).

La nature du problme doptimisation dpend gnralement du type du modle utilis pour la prdiction puisque le critre est gnralement quadratique et exprime des objectifs de poursuite et de minimisation dnergie (Huang et Kadali, 2008 ; Camacho et Bordons, 2008). Lorsque le modle est linaire, la solution analytique du problme doptimisation existe et simple calculer et les performances seront meilleures puisque loptimum global est atteint (Cutler, 1979 ; Clarke, 1987 ; Flaus, 1994 ; Huang et Kadali, 2008).

Par contre lutilisation dun modle non linaire, bien que les prdictions seront prcises, mais la nature du problme doptimisation est non linaire dont la complexit est li directement la prcision du modle. Avoir un problme doptimisation non linaire, rsoudre chaque priode dchantillonnage, constitue une tche ardue et empche lapplication de la commande prdictive des systmes non linaires (Cannon, 2004 ; Findeisen, 2007 ; Magni et al., 2009).

En effet, dans une stratgie de commande prdictive, les performances seront meilleures si loptimum global du critre est atteint avec une trs grande prcision, et la convergence est assure en un temps infrieur la priode dchantillonnage (Long et al., 2006). Par consquent, lalgorithme doptimisation doit possder les proprits de convergence et de rapidit (Cannon, 2004).

La thorie de loptimisation offre une panoplie de mthodes doptimisation locales et globales (Horst et Pardalos, 1995). Dans une commande prdictive, pour avoir de bonnes performances, les mthodes doptimisation intressantes sont les mthodes globales, cest--dire les mthodes permettant de localiser loptimum global du critre contrairement aux mthodes locales qui localise loptimum local (Cannon, 2004 ; Long et al., 2006). Les mthodes doptimisation globale, proposes dans la littrature, sont scindes en trois classes (Berthiau et Siarry, 2001): les mthodes exactes pour lesquelles la convergence vers loptimum globale est assure au prix dun temps de calcul important, les mthodes heuristiques caractrises par une convergence asymptotique et rapide, et les mthodes hybrides qui combinent des algorithmes exactes et heuristiques pour fusionner leurs avantages et avoir des algorithmes rapides.

Parmi les mthodes doptimisation globale qui ont prouv leurs efficacits, on retrouve la mthode dAlienor (Cherruault, 1991; Ziadi et al. 2001 ; Cherruault and Mora, 2005), qui est une mthode exacte, et la mthode dessaim de particules qui est une mthode heuristique (Van Den Bergh, 2002 ; Poli et al. 2007). La mthode dAlienor permet de ramener, laide

3

dune transformation rductrice, un problme doptimisation plusieurs variables de dcision un problme doptimisation une seule variable de dcision ce qui permet de localiser facilement loptimum globale et avec une prcision souhaite (Cherruault and Mora, 2005). La mthode dessaim de particules est caractrise par un algorithme simple comprendre et programmer. Le principe de la mthode repose sur un ensemble de particules qui reprsente un ensemble de solution admissibles au problme doptimisation (Poli, et al. 2007). Les particules sont initialement disposes de manire alatoire et vont se dplacer dans le domaine de solutions. Chaque particule dispose dune mmoire concernant sa meilleure solution visite ainsi que la capacit de communiquer avec les particules de son voisinage. A partir de ces informations, la particule va suivre une tendance faite, dune part, de sa volont retourner vers sa solution optimale, et dautre part, de son mimtisme par rapport aux solutions trouves dans son voisinage. A partir des solutions initiales, lensemble des particules va converger vers loptimum global.

Dans ce mmoire, on sintresse tudier lapport des mthodes doptimisation globale dans une stratgie de commande prdictive dun systme non linaire. Lobjectif du travail consiste appliquer les mthodes doptimisation globale dAlienor et dessaim de particules pour la rsolution du problme doptimisation non linaire dune commande prdictive non linaire, puis de comparer leurs performances. Ltude se limite au systme non linaire caractris par une dynamique lente, et la poursuite de consigne en prsence des contraintes, de type botes, sur la variable de commande. Notons que la commande des systmes rapides constitue un domaine de recherche ouvert, cest pourquoi la commande prdictive a fait ses preuves dans le cas des systmes caractriss par une trs grande inertie, par exemple les procds chimiques et thermiques.

L'organisation de ce mmoire est la suivante : Le premier chapitre est consacr la commande prdictive dans lequel nous allons

prsenter le principe dun algorithme de commande prdictive, ses diffrents lments, et son rglage, puis pour illustrer le principe dun algorithme prdictif, nous abordons de manire dtaille lalgorithme Dynamic Matrix Control (DMC) et on prsente un exemple dapplication avec des rsultats de simulation pour montrer linfluence des paramtres de rglage sur les performances obtenues. Le chapitre se termine par un tat de lart sur la commande prdictive.

Dans le deuxime chapitre, on sintresse loptimisation globale dans lensemble des nombres rels. Le chapitre commence par des notions de base de la thorie de loptimisation.

4

Dans la premire partie, aprs avoir introduit la formulation mathmatique dun problme doptimisation, nous prsentons la classification des problmes doptimisation suivie des conditions pour un minimum. Dans la deuxime partie, on prsente les diffrentes classes de mthodes doptimisation, et on indique lintrt des mthodes globales. Dans la fin du chapitre, on mentionne le lien fort existant entre loptimisation globale et la commande prdictive non linaire.

Le troisime chapitre est rserv aux mthodes doptimisation globale. Dans ce chapitre, on prsente particulirement la mthode exacte dAlienor et la mthode heuristique dessaim de particules. Pour illustrer et comparer ces deux mthodes, une application concernant lidentification des paramtres dun systme non linaire en utilisant la mthode du modle est prsente.

Au quatrime chapitre, aprs avoir prsent un tat de lart sur la commande prdictive non linaire, les mthodes dAlienor et dessaim de particules seront adoptes dans une stratgie de commande prdictive dun systme non linaire monovariable. Les spcifications exiges imposent dassurer la poursuite de consigne en prsence des contraintes, du type botes, sur la variable de commande. Lobjectif principal est dvaluer lapport de chaque mthode doptimisation, puis de comparer leurs performances en prsence et en absence de la contrainte sur la variable de commande.

La fin du mmoire est rserve la conclusion sur lensemble des applications ralises et aux perspectives de continuit.

5

Chapitre 1

Gnralits sur la Commande Prdictive

1.1 Introduction Ces dernires annes la commande prdictive est largement utilise dans le domaine

industriel et a t applique avec succs pour diffrentes applications. Le terme commande prdictive ne dsigne pas une stratgie de commande spcifique mais un ensemble dalgorithmes qui utilisent explicitement le modle du systme dans un problme doptimisation, rsoudre, pour dterminer la commande appliquer.

Le modle du systme est essentiellement utilis pour deux tches (Huang, et al. 2008) : la prdiction du comportement dynamique future du systme et le calcul de laction correctrice approprie pour assurer la poursuite de la consigne impose.

La commande prdictive base sur le modle prsente des avantages qui ont fait delle une approche de commande attractive. Parmi ces avantages, on peut citer (Flaus 1994 ; Huang et al. 2008) :

elle permet de respecter les diffrentes contraintes sur les tats, les commandes et les sorties,

6

elle permet dassurer la poursuite pour certaines consignes tout en maintenant dautres dans des couloirs bien spcifis,

elle vite les variations excessives pour les variables de commandes, elle peut sappliquer des systmes avec ou sans retard, son rglage est ais et son principe est intuitif,

elle est assez robuste aux erreurs de modle. Lintrt de la commande prdictive est multiple : compars aux techniques classiques, elle est extrmement performante si le procd

ragit avec un certain retard ou si les changements de consignes sont connus lavance,

compars aux techniques plus sophistiques ralisant la minimisation dun critre un pas, les techniques prdictives sont nettement robustes, en particulier lorsque la structure du modle utilise pour dcrire le procd est mal connue.

elle peut tre utilise en conservant un seul paramtre libre pour le rglage. Ce chapitre est consacr la commande prdictive base sur le modle o il sera prsent

le principe de la commande prdictive, la commande prdictive linaire et non linaire et un tat de lart sur les techniques de commande prdictives.

1.2 Principe de la commande prdictive La commande prdictive est base sur le principe de la Figure 1.1, elle est dcrite par la

stratgie suivante :

1. A chaque instant dchantillonnage k, les sorties futures du systme sont prdites sur un

horizon de temps pN , appel horizon de prdiction, qui est relativement long par rapport

la vitesse dvolution du procd. Les prdictions ( )kjky / + , pour ,,,1 pNj K= sont ralises en utilisant le modle du systme et dpendent non seulement du pass du systme (les commandes et les sorties avant linstant k), mais aussi des commandes futures

( ),iku + pour ,1,,0 = pNi K dterminer et appliquer au systme. Par consquent, le modle du systme fait partie de lalgorithme de commande. Ainsi la prdiction ne va pas dpendre uniquement des sorties prcdentes mais aussi de lvolution envisage dans le

temps futur pour la variable de commande. Notons que plusieurs volutions sont possibles pour la variable de commande.

7

2. La squence de commande est dtermine en minimisant un critre de performances

qui permet dassurer la poursuite de la consigne dsire. Le critre est une fonction quadratique des erreurs entre les sorties prdites et la trajectoire de rfrence. Leffort de commande est gnralement inclus dans le critre minimiser. Ainsi, une solution explicite peut tre facilement obtenue dans le cas o le critre est quadratique et le

modle du systme ainsi que les contraintes sont linaires, sinon une mthode doptimisation numrique doit tre applique. Notons que pour la structure de la loi de commande, certaines hypothses peuvent tre considres, par exemple la commande

reste constante aprs un certain instant dchantillonnage .pNk

3. La solution dtermine par optimisation sera ensuite applique au systme rel, mais

seule sa valeur linstant prsent k est rellement utilise. A linstant suivant ,1+k la

procdure complte est rpte. Ceci permet dobtenir une valeur ractualise pour la

( ) 1,,0 ,/ =+ pNjkjku K

uN commande deHorizon

( )kjky / Prdiction +

( )kyd

pN prdiction deHorizon Temps

1+k 2+k uNk + pNk + k 1k

( )kku /1+ ( )ku

Temps 1+k 2+k

uNk + pNk + k 1k

Figure 1.1 Principe de la commande prdictive.

8

commande, en fonction des mesures les plus rcentes en utilisant le concept de

lhorizon glissant.

1.3 Elments dune commande prdictive Tous les algorithmes de la commande prdictive possdent les mmes lments (Figure 1.2), et diffrentes options peuvent tre considres pour chaque lment, ce qui donne une multitude dalgorithmes. Ces lments sont :

1. le modle du systme (pour la prdiction), 2. le critre de performances et

3. lalgorithme doptimisation (pour dterminer la squence de commande).

1.3.1 Modle du systme La pierre angulaire dune stratgie de commande prdictive est le modle du systme. Le

modle du systme comprend gnralement deux parties : le modle du systme et le modle de perturbation. Le premier reprsente les relations entre-sortie du systme et le deuxime

est souvent utilis pour reprsenter les perturbations ou simplement pour approximer les erreurs de modlisation. Il existe diffrentes formes pour le modle utilis dans une

commande prdictive, mais ils doivent tre toujours de nature discrte puisque la commande prdictive est une commande numrique. Les formes couramment utilises sont du type

entre-sortie, elles sont prsentes ci-aprs.

- Rponse impulsionnelle Dans ce cas, la rponse du systme est :

Critre +

Contraintes Modle

(Prdiction)

Algorithme doptimisation

Systme commander

( )ky ( )ku( )kyd

Figure 1.2 Stratgie de commande prdictive.

9

( ) ( ) ( )+

=

=

1

iikuirky (1.1)

o ( )ir reprsentent les coefficients de la rponse impulsionnelle (les valeurs de la sortie, aux instants dchantillonnage, lorsque lentre est une impulsion de Dirac). Souvent cette somme est tronque et seules les sN valeurs sont considres puisque partir de linstant 1+sN la

sortie est nulle. es TN reprsente le temps de rponse du systme.

- Rponse indicielle Dans ce cas, la rponse du systme est :

( ) ( ) ( )+

=

=1

iikuisky (1.2)

o ( )is reprsentent les coefficients de la rponse indicielle pour une entre chelon unit, et ( ) ( ) ( )1= kukuku .

Pour un systme stable, les coefficients ( )is sont constants aprs linstant sN . es TN reprsente le temps de rponse du systme. Comme les coefficients de la rponse impulsionnelle peuvent tre considrs comme la diffrence entre deux coefficients successifs de la rponse indicielle, alors les relations suivantes sont vrifies :

( ) ( ) ( )1= isisir (1.3) ( ) ( )

+

=

=

1jjris (1.4)

- Equation aux diffrences Dans ce cas, la sortie du systme est :

( ) ( ) ( ) ( ) ( )( )uy nkukunkykyFky = ,,1,,,1 KK (1.5) o ny et nu sont des entiers naturels. La fonction ( ).F peut tre linaire ou non linaire selon la nature du systme.

Remarque 1.1 Dautres formes du modle peuvent tre aussi utilises parmi lesquels on peut citer la

fonction de transfert discrte, le modle dtat discret, modle de Volterra, modle neuronal, modle flou. Dans ce mmoire, ltude est limite aux modles prsents dans cette sous-section.

10

1.3.2 Prdiction Dans la commande prdictive, un modle du systme nest pas utilis pour la conception

de la loi de commande, mais il est utilis pour la prdiction des sorties futures du systme. Ces prdictions seront utilises par la suite pour la dtermination de la squence de la variable de commande en rsolvant un problme doptimisation.

Comme exemple, considrons le modle suivant :

( ) ( ) ( )1 1 += kubkyaky (1.6) Les deux premires prdictions futures de la sortie sont donnes comme suit :

( ) ( ) ( )kubkaykky +=+ /1 (1.7) ( ) ( ) ( )( ) ( ) ( )( ) ( )1 /2

1 /1 /2

+++=+

+++=+

kubkubkyaakky

kubkkyakky

( ) ( ) ( ) ( )1 /2 2 ++=+ kubkubakyakky (1.8) Les autres prdictions sont dtermines de la mme manire en utilisant le modle (1.6).

Sous forme matricielle, les deux premires prdictions sont donnes comme suit :

( )( ) ( )

+

+

=

+

+

)1()(0

/2

/12 ku

ku

bab

bky

a

a

kky

kky (1.9)

Les prdictions (1.9) sont composes de deux termes. Le second terme du ct droit de lquation (1.9) dpend des entres futures. Par contre le premier terme dpend seulement des sorties prcdentes ou galement des entres prcdentes selon le systme. Ainsi, les prdictions peuvent tre dcomposes en gnral en deux parties :

( ) ( ) ( )jkyjkykjky +++=+ forcelibre / (1.10) La rponse libre, ( )jky +libre , correspond la prdiction de la sortie lorsque la commande

est maintenue constante sa valeur actuelle ( )ku le long de lhorizon de prdiction .pN Par contre la rponse fore, ( )jky +force , correspond la prdiction de la sortie due aux actions futures ( ) .,,1 , pNjjku K=+

1.3.3 Critre de performance (fonction objectif) Pour dterminer la loi de commande, les algorithmes de la commande prdictive utilisent diffrentes formes pour le critre. Gnralement, le but recherch est dassurer la poursuite de

11

la consigne dsire ( )jkyd + avec un minimum deffort ( )1+ jku . Ainsi, le critre utilis le plus souvent prend la forme quadratique car diffrentiable :

( ) ( )[ ] ( ) ( )[ ]( ) ( )

=

=

+++

++++=

1

011

//

u

p

r

N

jj

T

N

Nj

dj

Td

jkuRjku

kjkyjkyQkjkyjkyJ (1.11)

o les matrices Qj et Rj sont symtriques et dfinies positives. Leur choix caractrise limportance relative que nous souhaitons donner aux diverses composantes du critre

minimiser. Elles peuvent aussi tre constantes. Les paramtres rN , pN et uN sont les

paramtres de rglage du correcteur prdictif et reprsentent respectivement linstant du dbut de la prdiction, lhorizon de prdiction maximal et lhorizon de commande. Lhorizon de

prdiction pN reprsente la longueur de lintervalle de temps futur sur lequel on cherche

minimiser le critre. Lhorizon de commande uN reprsente le nombre de variations de la

commande que lon autorise dans le futur avant quelle ne soit maintenue une valeur constante.

Pour les algorithmes qui utilisent un modle de convolution tronqu, on utilise un autre

paramtre sN qui reprsente la longueur de la rponse indicielle ou impulsionnelle.

Il faut aussi choisir convenablement la priode dchantillonnage eT puisque le correcteur

prdictif est de type discret. Cependant ce problme nest pas spcifique la commande prdictive, mais toute commande numrique. Le seul aspect par lequel le choix de la priode dchantillonnage peut tre li de faon troite la synthse du correcteur prdictif est celui

de la longueur sN du modle de convolution. Si on dfinit le temps de rponse rt comme le

temps partir duquel la rponse du systme a atteint 99% de la valeur finale, on doit vrifier :

res tTN = (1.12) pour tenir compte de la dynamique du systme. Dans le cas o la priode dchantillonnage

eT a t choisie petite (cas dun systme rapide), la longueur du modle de convolution peut devenir excessive et entraner des calculs importants. Linfluence de ces diffrents paramtres sur les performances du systme sera aborde dans le cas de lalgorithme Dynamic Matrix Control (DMC), qui fera lobjectif de la Section 1.4.4, et sera illustr par un exemple dapplication. Notons que les conclusions concernant linfluence des diffrents paramtres pourront facilement tre transposes pour un autre algorithme mme dans le cas de la commande prdictive non linaire.

12

1.3.4 Contraintes Les contraintes caractrisent en gnral les limitations physiques sur la commande, sur

ltat ou sur la sortie du systme. Elles sont introduites pour viter des changements brusques pour la commande. Pour certains systmes, des contraintes sur les sorties (prdites) doivent tre respectes pour des raisons conomiques ou de scurit.

Gnralement, les contraintes sont instantanes et sexpriment par des ingalits de la forme :

( ) maxmin ukuu (1.13) ( ) kNjNykjkyy pr + , ,/ maxmin (1.14)

Dans ce mmoire, on considre que les contraintes sur la commande de type (1.13).

1.3.5 Loi de commande

Les actions de commande, ( )iku + , sont calcules en minimisant le critre (1.11). Ainsi, on commence dabord par la dtermination des prdictions en utilisant le modle du systme (voir lexemple de la sous-section 1.3.2). Ces dernires seront forcment fonction des actions de commande ( )iku + . Ainsi, en substituant ces prdictions dans le critre J minimiser, donne par la relation (1.11), et en rsolvant le systme dquations algbriques obtenu en imposant le gradient J par rapport aux actions de commande ( )iku + gale zro, cest--dire :

( ) ( ) ( )( ) ( ) ( ) ( )( )

( ) ( ) ( )( )( )( ) ( ) ( )( )

( )( ) ( ) ( )( )

( )

0

,,1,

1,,1,

,,1,

,,1,,,1, =

+++

+++

++

=++ ++

u

u

u

u

uNkukuku

NkuNkukukuJ

kuNkukukuJ

kuNkukukuJ

NkukukuJu

K

M

K

K

KK (1.15)

on dtermine les actions de commandes ( )iku +* optimales. Rappelons que daprs le principe de la commande prdictive seul laction de commande ( )ku* sera applique au systme, et la procdure sera rpte linstant dchantillonnage suivant. Annuler le gradient du critre J est une procdure doptimisation. Pour le systme dquations algbriques (1.15) une solution analytique peut tre obtenue, dans le cas contraire une mthode numrique (itrative) doit tre utilise dont le temps de convergence ne doit pas

13

dpasser une priode dchantillonnage pour que laction optimale ( )ku* soit disponible linstant k. Lorsquune mthode numrique est utilise, lobtention de la solution du problme doptimisation suivant :

( ) ( ) ( ) ( ) ( ) ( )( )uNkukuku NkukukuJu ++++ ,,1,min,,1, KK (1.16) nest pas ncessairement garantie surtout si le problme doptimisation est non linaire, et la difficult saccentue davantage en prsence des contraintes sur la commande ou/et sur la

sortie commande. De plus, assurer la convergence en un temps infrieur eT reprsente une

autre contrainte prendre en considration, et la plupart des mthodes numriques peuvent tre piges dans un minimum local pour (1.16) au lieu de minimum global, do la ncessit dutiliser des algorithmes doptimisation globale rapides. Notons que la solution analytique peut tre obtenue seulement dans le cas du modle linaire avec contraintes linaires, par exemple dans le cas de lalgorithme Dynamic Matrix Conrtol (cet algorithme sera tudi dans la section suivante). Pour les autres cas, la solution numrique est inluctable, par consquent le choix de la mthode doptimisation joue un rle du premier plan dans une stratgie de commande prdictive. Le chapitre 2 sinscrit dans cette optique, il sera consacr loptimisation globale. Dans la section suivante, nous prsenterons un des algorithmes de la commande prdictive pour illustrer le principe de cette dernire. Il sagit de lalgorithme DMC (Dynamic Matrix Control).

1.4 Algorithme DMC Lalgorithme DMC a t initialement dvelopp par Cutler et Ramaker (1979) de la socit Shell Oil Co vers la fin des annes 70. Cet algorithme est largement accept et utilis par les industriels, en particulier dans le secteur des hydrocarbures et de la ptrochimie. Dans cette section, nous prsentons une version simplifie de cet algorithme dans le cas o le modle est fourni sous forme de rponse un chelon. Cette formulation est gnralement la plus choisie car elle permet la comprhension intuitive du fonctionnement de la commande prdictive. Nanmoins des dveloppements quivalents peuvent tre conduits pour le modle de rponse impulsionnelle o fonction de transfert conduisant respectivement au Model Algorithmic Control (MAC) et au Generalized Predictive Control (GPC).

14

1.4.1 Modle de prdiction Le modle utilis pour la prdiction dans lalgorithme de commande prdictive DMC est le

modle rponse indicielle. Considrons la rponse indicielle du systme

( ) ( )+

=

=1i

i ikusky (1.17)

quon peut mettre sous la forme suivante :

( ) ( ) ( )+

+==

+=11 s

s

Nii

N

ii ikusikusky (1.18)

( ) ( ) ( )kZikusky sNi

i += = 4434421

finie indicielle Rponse

1 (1.19)

Ainsi, on remarque bien que la rponse indicielle infinie (1.18) du systme fait intervenir une rponse indicielle finie quon peut exploiter pour ltape de prdiction, cest--dire :

( ) ( ) ( )jkZijkuskjky sNi

i +++=+ =1

/ (1.20)

Comme cela a t indiqu prcdemment, la rponse du systme prdite par le modle peut tre divise en deux parties : libre et force. Ainsi, lquation (1.20) peut tre dcompose en deux termes : le premier terme contient les actions de commande futures ( ) ( )( )K,1, + kuku , et le second terme contient les actions de commande passes ( ) ( )( )K,2,1 kuku , ce qui donne

( ) ( ) ( ) ( )jkZijkusijkuskjky sNji

i

j

ii +++++=+

+== 11/ (1.21)

Cette dernire quation peut tre arrange pour faire apparatre les deux termes de la sortie (force et libre) comme suit :

( ) ( ) ( )jkyijkuskjky ji

i +++=+ =

*

1/ (1.22)

o le terme

( ) ( ) ( )jkZijkusjky sNji

i +++=+ += 1

* (1.23)

reprsente le terme libre :

( ) ( )jkyjky +=+ *libre (1.24) Le terme restant reprsente le terme forc qui est lvolution de la rponse du systme partir de linstant k d lapplication des actions de commande futures. Ainsi,

15

( ) ( )=

+=+j

ii ijkusjky

1force (1.25)

Le critre considr dans un algorithme DMC consiste minimiser la diffrence entre la

consigne dsire et la sortie prdite par le modle le long de lhorizon de prdiction pN . Les

sorties prdites sont donnes comme suit :

( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) ( )

( ) ( ) ( ) ( ) ( )1 1 /

1 1 /

2 1 3/3

1 2/2

1/1

11*

11*

123*

12*

1*

+++++++=+

+++++++=+

++++++=+

++++=+

++=+

pNNpp

uNNuu

NkuskuskusNkykNky

NkuskuskusNkykNky

kuskuskuskykky

kuskuskykky

kuskykky

pp

uu

L

M

L

L (1.26)

Notons que ( ) ( ) ( ) 011 =+==++=+ puu NkuNkuNku L car laction de commande est maintenue constante partir de linstant uNk = .

Les prdictions (1.26) peuvent tre crites sous la forme matricielle comme suit : uMyy += * (1.27)

Avec :

( )( )

( )

( )( )

( )

( )( )

( )

+

+

=

+

+

+

=

+

+

+

=

1

1 ,

21

,

/

/2/1

*

*

*

*

upp Nku

kuku

u

Nky

kyky

y

kNky

kkykky

yMMM

et la matrice

=

+

121

121

12

1

00

000

upppp

uuu

NNNNN

NNN

ssss

ssss

ss

s

M

L

MMMMM

L

MMMMM

L

L

est appele matrice dynamique (Dynamic Matrix).

16

1.4.2 Synthse dun correcteur DMC Rappelons que lobjectif consiste poursuivre une trajectoire, le long de lhorizon de prdiction, donne comme suit :

( )( )

( )

+

+

+

=

pd

d

d

d

Nky

ky

ky

yM

2

1

Ainsi, pour dterminer la squence des commandes appliquer, il suffit de rsoudre, chaque instant k, le problme doptimisation suivant :

( ) ( ) ( )

uMyy

yyQyyuJ dTdu

+=

=

: sujet

min

*

(1.28)

En substituant y dans le critre J, il vient :

( ) ( ) ( )uMyyQuMyyuJ dTdu

= min ** (1.29)

La solution optimale est obtenue comme suit :

( ) ( ) 0 2 * == uMyyQMuJ dTTu (1.30) Ce qui donne

( ) ( )*1 yyQMMQMu dTTTT = (1.31)

1.4.3 Evaluation des performances de lalgorithme DMC Pour illustrer et valuer les performances de lalgorithme DMC, nous proposons dtudier la commande dun systme de deuxime ordre avec un retard important. Considrons le procd dcrit par la fonction de transfert :

( ) ( ) ( )se

sssG 8

151 711

++= (1.32)

La rponse indicielle de ce systme est donne par la Figure 1.3. Daprs cette dernire,

nous pouvons prendre la longueur sN du modle de convolution suprieure 80. Dans notre

cas on a pris le double, cest--dire .160=sN Pour dterminer la matrice dynamique M , cette

17

rponse est chantillonne avec une priode dchantillonnage gale 1s. Pour les paramtres de rglage de lalgorithme DMC, on considre que la prdiction commence aprs 8 priodes

dchantillonnage ( )8=rN , lhorizon de commande 2=uN , et lhorizon de prdiction .30=pN Pour le critre minimiser, la matrice de pondration IQ = .

Pour le problme de poursuite, la consigne dsire dy est suppose constante et gale 60.

Pour le test de rgulation (rejet de perturbation), on considre une perturbation d borne qui affecte la sortie du systme avec une dynamique dun systme du premier ordre cest--dire :

( )1 2.0

1+

=

ssGd (1.33)

Par consquent la sortie du systme, en boucle ouverte est :

( ) ( ) ( ) )( )( sdsGsusGsy d+= (1.34) Pour le test concernant le rejet de perturbation, on a appliqu une perturbation damplitude

1,0=d linstant 50 s.

Les Figures 1.4, et 1.5 prsentent les rsultats de simulation obtenus. On constate que lalgorithme DMC assure la poursuite de la consigne et rejette parfaitement leffet de la perturbation (Fig. 1.4). Lvolution de la commande (Fig. 1.5) est physiquement acceptable.

Figure 1.3 Rponse indicielle du systme.

18

Figure 1.5 Evolution de la commande.

Figure 1.4 Poursuite et rejet de perturbation.

19

1.4.4 Etude de linfluence des paramtres de rglage dune commande prdictive En plus de la priode dchantillonnage, une commande prdictive est caractrise par les paramtres de rglage suivant :

Instant de dbut de prdiction rN : ce paramtre est pris gale au retard du systme .

Si le systme ne prsente pas de retard, on prend .1=rN

horizon du systme sN : il est dtermin selon la relation (1.12). Des valeurs entre 20 et 70 sont des recommandations typiques.

horizon de commande uN : il reprsente le nombre dactions futures calcules par

optimisation du critre pour rduire les erreurs de prdictions. La valeur de ce paramtre influe sur le temps de calcul de la solution optimale. Laugmentation de ce paramtre permet dacclrer le systme, mais en contre partie on va avoir des actions plus nergiques. Comme le principe de commande prdictive consiste appliquer seulement la premire commande, alors il est inutile de prendre une valeur suprieure 5.

horizon de prdiction pN : il reprsente le nombre de prdictions utilises dans le

critre optimiser. La valeur minimale doit tre gale 1+ o dsigne le temps

de retard du systme commander. Laugmentation de pN revient considrer plus

de prdictions, par consquent la sortie sera bien amortie et les commandes seront de faibles amplitudes, mais leur traitement ncessite un temps de calcul important.

Ainsi, pour le rglage des paramtres dune commande prdictive, on sintresse en

particulier lajustement de uN et .pN Pour illustrer linfluence de ces deux paramtres, nous proposons de reprendre lexemple tudi prcdemment. Pour montrer, linfluence de chaque paramtre, on fixe un des paramtres puis on considre deux valeurs pour lautre paramtre. La perturbation d est considre nulle.

La Figure 1.6 montre que laugmentation de uN , ( 30=pN ), donne des rponses rapides (Fig. 1.6a), mais au prix dune sollicitation plus importante de la commande (Fig. 1.6b). Pour linfluence de ( )2 , =up NN , daprs la Figure 1.7, on note leffet stabilisant pour la sortie (Fig. 1.7a), avec une commande moins nergique (Fig. 1.7b).

20

a) Evolution de la sortie.

b) Evolution de la commande.

Figure 1.6 Influence de lhorizon de commande.

21

b) Evolution de la commande.

a) Evolution de la sortie.

Figure 1.7 Influence de lhorizon de prdiction.

22

1.5 Stabilit de la commande prdictive La commande prdictive est base sur le modle pour calculer des prdictions de la sortie qui seront utilises par la suite dans lalgorithme doptimisation, souvent itratif, pour dterminer la squence des commandes optimale appliquer. Ainsi, chaque instant dchantillonnage, un problme doptimisation est rsolu en temps rel. Par consquent, la stabilit de la commande prdictive est lie directement, la stabilit du modle utilis (Lee et Park, 1991) pour ltape de prdiction donc du systme commander, et la convergence de lalgorithme doptimisation. Pour assurer la stabilit en boucle ferme, le systme en boucle ouverte doit tre stable pour que les prdictions le seront aussi, et lalgorithme doptimisation doit garantir une convergence mme locale. Pour la commande des systmes instables ou intgrateurs, un correcteur de premier niveau doit tre synthtiser au premier lieu pour stabiliser le systme (Lee et Park, 1991 ; Mayne et al., 2000 ; Richalet et al., 2005), puis on utilise la commande prdictive pour assurer certaines performances, spcifies par un critre optimiser, et respecter bien sr des contraintes de fonctionnement du systme, et de scurit.

1.6 Etat de lart sur la commande prdictive La commande prdictive est largement utilise dans des domaines trs varis de lindustrie

tels que la ptrochimie, en particulier le gnie des procds et lautomobile (Kouvaritakis et Cannon, 2001 ; Findeisen et al., 2007 ; Huang et Kadali, 2008 ; Magni et al., 2009) o elle a dmontr ses preuves. Elle fait partie des stratgies de commande qui utilise explicitement le modle du systme commander en sacquittant de deux tches essentielles : la prdiction explicite du comportement dynamique du systme et le calcul de la commande approprie pour assurer la poursuite de la trajectoire de consigne en minimisant un certain critre de performance (Flaus, 1994 ; Huang et Kadali, 2008).

Le principe de la commande prdictive prsent reste le mme, les diffrentes mthodes proposes dans la littrature diffrent surtout par la structure choisie pour reprsenter le modle de systme, cest--dire pour la prdiction. Pour le critre, en gnral, cest le critre quadratique qui est retenu. Dans le cas de la commande prdictive non linaire, en plus de la structure de modle considre, la diffrence entre les techniques de commande rside aussi dans la technique doptimisation utilise pour la dtermination de la squence des actions de commande.

Les premiers travaux sur la commande prdictive remontent la fin des annes 70 et ont t initis par Richalet (1976) en proposant le Model Algorithmic Control (MAC). Puis De Keyser et Van Cauwenberghe (1979) introduisent le Extended Prediction Self Adaptive

23

Control (EPSAC) qui est une commande auto-adaptative prdictive tendue dveloppe . Lide consiste utiliser un signal de commande constant pour tout l'horizon de prdiction, et qui est appliqu ds le dbut du calcul de la commande qui optimise le critre. Cutler et Ramaker (1979) ont dvelopp le clbre algorithme Dynamic Matrix Control (DMC), bas sur le modle de convolution (rponse indicielle et impulsionnelle), prsent dans ce chapitre. Cet algorithme est le plus indiqu pour illustrer le principe dune commande prdictive. Le DMC est lalgorithme qui connat une large utilisation, dans le domaine industriel, surtout pour les systmes linaires et pour les systmes non linaires lorsquune linarisation autour

dun point de fonctionnement est possible. Ydstie (1984) propose lExtended Horizon Adaptive Control (EHAC) qui est une commande adaptative horizon tendu. L'ide fondamentale consiste calculer chaque instant, la squence des signaux de commande pour essayer de maintenir la sortie future la plus proche possible de la consigne pour un horizon de temps plus grand que le retard prsent sur le systme. Clarke (1987) dveloppe le Generalized Predictive Control (GPC) qui dtrne le DMC et qui devient la mthode la plus populaire. Comparativement au DMC, cet algorithme utilise une adaptation en ligne du modle utilis (modle) pour raliser les prdictions. Le GPC est trs proche de lESPAC et de lEHAC. On peut trouver une synthse sur ces mthodes et de leurs caractristiques les plus importantes dans De Keyser et al. (1988) et dans Clarke et Mohtadi (1989).

Le succs de ces diffrents algorithmes, en particulier le DMC et le GPC, a suscit graduellement un grand intrt pour la commande prdictive, pas seulement au milieu acadmique mais aussi au milieu industriel, depuis les annes 80. Cet engouement a dbouch sur d'autres mthodologies, partageant le mme principe, qui sont apparues dans la littrature spcialise de la commande dont certaines sont actuellement commercialises par certaines firmes (voir le Tableau 1.1).

24

Algorithme Firme DMC (Dynamic Matrix Control)

ASPEN Tech Aspen Target ADMC (Adaptive DMC) CTC IDCOM (Identification and Command)

Adersa HIECON (Hierarchical Constraint Control) PFC (Predictive Functional Control) RMPCT (Robust Multivariable Predictive Control) Honeywell SMCA (Setpoint Multivariable Control Architecture)

Stepoint Inc. IDCOM-M (Identification and Command Multivariable) APCS (Adaptive Predictive Control System) SCAP Europa SMOC (Shell Multivariable Optimising Controller) Shell Connoisseur (Control and Identification package) Invensys MVC (Multivariate Control) Continental Controls Inc. NOVA-NLC (NOVA Nonlinear Controller) DOT Products Process Perfecter Pavilion Technologies

Tableau 1.1 Version commercialiss des correcteurs prdictifs.

Les annes 90, ont marqu une vraie explosion dans le nombre des applications de la commande prdictive principalement en Etats-Unis, en Japon et en Europe. Par exemple, pour lindustrie des processus chimiques et le domaine de la robotique, plusieurs algorithmes ont t appliqus avec succs (De Keyser, 1988). Ces applications ont t accompagn dune forte activit de recherche (Camacho et Bordons, 1998). Comme la plupart des algorithmes utilisent des modles entre-sortie, la commande prdictive a t formule dans le contexte de la reprsentation en variables d'tat (Morari, 1994). Lobjectif vis est de faire usage des thormes et rsultats existant dans la thorie d'espace d'tat, mais aussi facilite l'extension de la thorie MPC des cas plus complexes.

tant donn que la dtermination de la squence de commande demande plus defforts de calcul et exige des algorithmes de programmation non linaire (algorithme doptimisation) rapides et convergeant, alors les travaux de recherche se sont focaliss, dans les annes 2000, sur le dveloppement et ltude des algorithmes permettant d'obtenir une solution, le plus souvent locale, pour le problme d'optimisation rsoudre chaque priode dchantillonnage (Ramirez et Camacho, 2001 ; Bemporad et al. 2002 ; Cannon, 2004, Magni et al., 2009). Ainsi, prsenter un tat de lart concernant cette priode, revient esquisser les

25

diffrents algorithmes et stratgies doptimisation dveloppes pour acclrer la convergence des algorithmes doptimisation et lobtention de la solution globale, en particulier pour le cas de la commande prdictive non linaire. Le travail prsent dans ce mmoire sinscrit dans cette optique dont lobjectif consiste appliquer certains algorithmes de loptimisation globale rputs robustes dans une stratgie de commande prdictive non linaire. Ainsi, une synthse sur les diffrents algorithmes doptimisation et approches utilises dans une stratgie de commande prdictive fera lobjet du chapitre 4 ddi la commande prdictive non linaire.

1.7 Conclusion Ce chapitre a t consacr des gnralits sur la commande prdictive et ltat de lart concernant cette approche de commande. Ainsi, aprs avoir prsent le principe de la commande prdictive, nous avons dtaill les diffrents lments dune commande prdictive, et les paramtres de rglage dune commande prdictive, en loccurrence linstant de dbut de prdiction, lhorizon de commande, lhorizon de prdiction, et lhorizon du systme. Pour illustrer le principe de la commande prdictive, lalgorithme Dynamic Matrix Control (DMC) est prsent dune manire dtaille, et applique un systme de second ordre avec retard. Des rsultats de simulation ont t prsents pour dmontrer les performances du DMC et pour illustrer linfluence de deux paramtres de rglage importants, en loccurrence les horizons de commande et de prdiction. Les conclusions tires concident avec celles rapportes dans la littrature. La fin du chapitre constitue une synthse sur les diffrents travaux raliss dans le cadre de la commande prdictive des systmes. Cette synthse retrace les contributions importantes qui ont marqu le dveloppement de la commande prdictive. Dans une commande prdictive, lobtention de la solution optimale passe par la rsolution dun problme doptimisation souvent non linaire, par consquent cette tape doptimisation joue un rle du premier plan dans une stratgie de commande prdictive. En effet, le succs dune stratgie de commande prdictive est li directement lalgorithme doptimisation utilis. Ainsi, lexamen de la littrature ddie la commande prdictive, en particulier la commande prdictive non linaire montre que les efforts de recherche sont focaliss, ces dernires annes, au dveloppement dalgorithmes doptimisation rapides qui convergent vers loptimum globale en un temps infrieur une priode dchantillonnage, qui constituent actuellement un vrai challenge pour les mathmaticiens appliqus et en particulier aux

automaticiens.

26

Dans ce travail, des algorithmes doptimisation globale seront adopts dans la stratgie de commande prdictive non linaire. Ainsi, le chapitre suivant est consacr loptimisation globale diffrentiable et non diffrentiable des fonctions mathmatiques o les diffrentes notions utilises le long du travail seront exposes.

27

Chapitre 2

Optimisation Globale dans

2.1 Introduction Dans une stratgie de commande prdictive, un problme doptimisation doit tre rsolu

chaque instant dchantillonnage pour dterminer la commande appliquer au systme. Ltape de rsolution du problme doptimisation est primordiale dans une commande prdictive, car les performances attendues dpendent de la solution du problme doptimisation, elles sont meilleures si loptimum global du critre est atteint. A cette contrainte sajoute celle relative au temps de rsolution qui doit tre infrieur une priode dchantillonnage. La nature du problme doptimisation rsoudre dpend de la nature du critre, du systme, et des contraintes. Hormis le cas o le systme et les contraintes sont linaires et le critre est quadratique pour lequel la solution analytique est disponible (cas du Dynamic Matric Control prsent au chapitre 1), les autres cas sont souvent des problmes doptimisation non linaires pour lesquels la localisation de loptimum global est trs difficile.

Rsoudre un problme doptimisation revient localiser loptimum global du critre en prsence ou en absence de contraintes. Le domaine de loptimisation constitue un domaine de

28

recherche immense. Ces dernires annes, avec lvolution de linformatique, une attention particulire a t accorde loptimisation globale dont lobjectif est de dvelopper des algorithmes sophistiqus et rapides permettant de localiser loptimum global dune fonction mathmatique et dchapper ainsi au problme rencontr avec les mthodes de loptimisation locale qui sont souvent piges dans un minimum local.

Ce chapitre est consacr des gnralits sur loptimisation globale dans lensemble des nombres rels. Lobjectif consiste prsenter les diffrentes notions utilises, le long de ce mmoire, relatives aux mathmatiques rpertories sous le vocale optimisation globale. Ainsi, aprs la formulation mathmatique du problme doptimisation, on donne une classification des problmes doptimisation. Puis laide dun exemple, on illustre la ncessit et le besoin de dvelopper des mthodes doptimisation globale, suivi de la classification des mthodes doptimisation globale dveloppes dans la littrature. La fin du chapitre est rserve la relation troite entre loptimisation globale et la commande prdictive non linaire.

2.2 Formulation mathmatique dun problme doptimisation Considrons une fonction scalaire de plusieurs variables nxxx ,,, 21 K , appeles variables de

dcision, note ( )xf , et appele fonction objectif ou critre. Le vecteur de variables de dcision, not ( )Tnxxxx ,,, 21 K= , doit appartenir un domaine donn nD . Ce dernier est dfini par des relations de contraintes du type galit

( ) pixgi ,,1 ,0 K== (2.1) et/ou ingalit

( ) qjxh j ,,1 ,0 K= (2.2) Lobjectif de loptimisation globale est de rechercher parmi les ,Dx un x particulier qui

est appel minimum absolu ou global (nest pas obligatoirement unique), not *x , tel que : ( ) ( ) Dxxfxf ,* (2.3)

Nous prsentons un problme doptimisation mathmatiquement sous la forme suivante :

( )

( )( ) qjxh

pixg

xf

j

i

x

,,1 ,0

,,1 ,0: Sujet

min

K

K

=

==

(2.4)

ou encore

29

( )

( )( ) qjxh

pixg

xf

j

i

x

,,1 ,0

,,1 ,0: Sujet

minarg

K

K

=

==

(2.5)

Largument argmin identifie la valeur des variables de dcision qui atteignent le minimum, cest--dire

( )xfxx

minarg* = (2.6)

Alors que loprateur min identifie la valeur correspondante de la fonction objectif ou critre, cest--dire

( ) ( )xfxfx

min* = (2.7)

Remarque 2.1

Notons que, moyennant le changement de fonctions ( )xf en ( )xf , on peut passer dune formulation minimiser une formulation maximiser et vice versa : minimiser ( )xf revient maximiser ( )xf , cest--dire :

( ) ( )[ ]xfxfxx

= maxmin (2.8)

Dans ltude prsente dans ce mmoire, on considre les diffrents rsultats et thories relatifs la formulation minimiser .

2.3 Classification des problmes doptimisation dans Suivant la nature de la fonction objectif ou du critre et des contraintes qui dfinissent le

domaine des solutions admissibles D, le problme doptimisation correspondant porte des

noms divers. On distingue plus particulirement les cas rassembls dans le Tableau 2.1.

Fonction objectif

Linaire Quadratique (convexe) Non linaire

Contraintes

Linaire Programmation linaire Programmation

Quadratique Programmation

Non linaire Quadratique

(convexe) Programmation

Non linaire Programmation

Convexe Programmation

Non linaire

Non linaire Programmation Non linaire Programmation

Non linaire Programmation

Non linaire Tableau 2.1 Classification des problmes doptimisation

30

- Programmation linaire Il sagit dune classe de problmes doptimisation o la fonction objectif ou le critre est

linaire

( ) xCxf T= (2.9) (C est un vecteur des cfficients) et o lensemble des contraintes est un polydre convexe ferm (reprsent sous la forme bAx par exemple, avec A et b sont respectivement une matrice et un vecteur constants).

- Programmation quadratique Il sagit dun problme doptimisation o la fonction objectif est quadratique convexe,

cest--dire

( ) xCAxxxf TT +=21

(2.10)

avec A est une matrice symtrique semi-dfinie positive et lensemble de contrainte est toujours un polydre convexe ferm comme dans le cas de la programmation linaire.

- Programmation convexe Ici la fonction objectif est convexe, et lensemble admissible D est convexe. Le cas de la

programmation quadratique est un cas particulier de la programmation convexe.

Un domaine D est convexe si :

( ) ( ) DxxxDxx += 2121 1 10et , (2.11) Une fonction ( )xf est convexe dans un domaine convexe D si :

( ) ( )( ) ( ) ( ) ( )212121 1 1 10et , xfxfxxfDxx ++ (2.12)

- Programmation non linaire Toutes les donnes du problme doptimisation sont des fonctions diffrentiables (continment diffrentiables), cest--dire la fonction objectif est diffrentiable et les contraintes sont supposes diffrentiables.

2.4 Conditions pour un minimum Dans la suite du travail prsent dans ce mmoire, on considre seulement un cas

particulier de contraintes du type ingalits, il sagit des contraintes de botes donnes comme suit :

31

maxminiii xxx (2.13)

o minix et max

ix sont des composantes de deux vecteurs minx et ,maxx de dimension n, donnes.

Ces deux vecteurs dfinissent un domaine admissible D hyperrectangulaire.

Deux hypothses classiquement rencontres pour le minimum. La premire hypothse

concerne lhyperrectangulaire 2D suppos convexe et compact. La deuxime est relative la fonction objectif ou critre, minimiser, suppose continue et possde des drives partielles premires et secondes, cest--dire

( )ix

xf

et

( )ni

x

xfi

,,1 ,22

K=

(2.14)

qui sont continues pour tout x.

Sous ces deux hypothses, les conditions ncessaires et suffisantes pour que *x soit un

minimum local ou global de ( )xf sont : - Condition de stationnarit (relative au gradient de la fonction objectif)

( ) 0* = xfx (2.15) - Condition pour un minimum (relative au Hessien de la fonction objectif)

( ) ( ) 0,,1, ;*

2*2 >

=

==

njixx

xfxf

xxjix K (2.16)

La condition (2.16) signifie que le Hessien est une matrice dfinie positive. Les deux conditions (2.15) et (2.16) reviennent supposer que la fonction objectif ( )xf est strictement convexe dans un voisinage de .*x Notons que dans le cas dune fonction convexe, vrifiant la

condition (2.16), la stationnarit elle seule constitue une condition ncessaire et suffisante doptimalit globale.

Horst et Pardalos (1995, chapitre 1) rassemble des rsultats thoriques rcents relatifs des problmes doptimisation globale dots dune structure particulire.

2.5 Mthodes de rsolution des problmes doptimisation Lobtention de la solution du problme doptimisation, revient rsoudre le systme

dquations algbriques (2.15), par consquent la difficult est lie directement la nature de la fonction objectif ( )xf . Ainsi, la solution peut tre obtenue analytiquement dans le cas o la rsolution du systme dquations (2.15) est facile, dans le cas contraire, on procde par des mthodes numriques. Pratiquement, les fonctions objectifs minimiser sont fortement non linaire, par consquent rsoudre analytiquement le systme algbrique (2.15) est quasiment

32

impossible do la ncessit dutiliser les mthodes numriques. Ce besoin a donn naissance

un domaine de recherche, faisant partie des mathmatiques appliques, appel optimisation numrique dont les efforts sont centraliss sur le dveloppement des algorithmes numriques

qui permettent de localiser loptimum dune fonction en un nombre ditrations faible. La programmation linaire (voir la section 2.3) constitue un des rares cas particuliers pour lequel un algorithme itratif, appel algorithme de simplexe, a t dvelopp. Cet algorithme converge en un nombre ditrations fini, et nimpliquent que des calculs assez lmentaires.

Dans le cas dune programmation quadratique convexe (voir la section 2.3), les algorithmes dvelopps sont efficaces et convergent, en gnral, en une seule itration (par exemple la mthode de Newton). Dans le cas de la programmation quadratique (voir la section 2.3), la solution analytique est toujours disponible et facile dterminer (cet avantage a t exploit dans le cas de la commande prdictive pour dvelopper lalgorithme Dynamic Matrix Control prsente au chapitre 1, section 1.4). Comme nous lavons dj signal, une solution explicite ne peut pas tre en gnral obtenue partir des conditions thoriques (2.15). On va donc utiliser des mthodes itratives, dont le principe gnral consiste calculer partir dune valeur initiale ( ),0x la suite des

valeurs ( ) ( ) ( ) KK ,,,, 21 kxxx (2.17)

Si lon choisit les points successifs de faon que : ( )( ) ( )( ) ( )( )kxfxfxf >>> K10 (2.18)

comme cette suite numrique est borne infrieurement par ( )*xf elle convergera. Si le minimum global *x est unique et sil ny a pas dautre minimum local, la mthode converge

alors vers le point *x cherch. Dans le cas contraire seul lun des minimums locaux est atteint.

Ce dernier cas justifie aussi, le besoin dvelopper des algorithmes doptimisation globale. Puisquun algorithme numrique ne peut pas fournir mieux quune rponse approche,

dans le cas de contraintes botes, un lment x dun des ensembles suivants sera considr

comme solution du problme (Berthiau et Siarry, 2001), *x est un minimum global et est un nombre positif quelconque :

( ) { } ; * = xxDxAx (2.19) ( ) ( ) ( ){ } ; * = xfxfDxAf (2.20)

33

2.6 Classification des mthodes doptimisation Pour loptimisation continue, on spare sommairement le cas linaire (qui relve

notamment de la programmation linaire pour lequel la solution est facile obtenir) du cas non linaire. Pour certains problmes qui vrifient la proprit de convexit, la solution peut tre obtenue en utilisant une mthode locale qui exploite, ou non, les gradients de la fonction

objectif. Nanmoins, la plupart des problmes doptimisation sont classs difficiles, car le nombre de minima locaux est trs lev, alors le recours une mthode globale simpose.

Pour le traitement des contraintes, on a recours la mthode des multiplicateurs de Lagrange dans le cas des contraintes du type galits, et la mthode de Kuhn-Tucker ou la

mthode de fonctions dcarts dans le cas de contraintes ingalits. Notons que la mthode de fonctions de pnalisation constitue une approche lgante pour traiter les deux cas. Cette

mthode permet de ramener un problme doptimisation pos avec contraintes un problme sans contraintes, puis dappliquer les mthodes doptimisation numriques.

En utilisant la mthode de fonction de pnalisation, pour le problme doptimisation (2.4), pos avec contraintes galits et ingalits, on obtient :

( ) ( ) ( )[ ] ( )[ ]==

++=q

jjj

p

iii

xxhxgxfxL

1

2

1

2min (2.21)

o les i et j reprsentent les paramtres de pnalisation, positifs, associs respectivement aux contraintes ( )xgi et ( )xh j . Les valeurs de ces paramtres sont en gnral considrs constantes durant la rsolution du problme doptimisation, cest--dire :

qjpi ji ,,1 ,et ,,1 , KK ==== (2.22) Dans la relation (2.21), la fonction ( )xh j est dfinie comme suit :

( ) ( ) ( )( )

>=

0 si0

0 si

xh

xhxhxh

j

jjj (2.23)

Dans la littrature, on distingue trois classes pour les mthodes doptimisation numriques :

les mthodes exactes (appeles encore classiques ou dterministes), les mthodes heuristiques (appeles encore mthodes stochastiques), et les mthodes hybrides (coopration entre une mthode exacte et une mthode heuristique).

- Mthodes exactes Ces mthodes requirent des proprits mathmatiques restrictives de la fonction objectif

optimiser telle que la continuit, la diffrentiabilit, et la convexit. Ces mthodes permettent

34

de localiser la solution avec une trs grande prcision au prix, gnralement, dun nombre

ditrations important, cest--dire ncessite un temps de calcul norme parfois. Comme exemples de mthodes, on peut citer les mthodes du gradient et de Newton, et leurs

variantes. Nanmoins, en pratique, il est trs difficile de savoir si la fonction objectif satisfait ou non de telles proprits mathmatiques. De plus, la plupart des fonctions sont

multimodales (plusieurs maximums et minimums), discontinues et non drivables. Le principe de ces mthodes peut tre explicit par lalgorithme suivant :

Etape 1. Initialisation 0=k , ( )0x et calcul de ( )( )0xf . Etape 2. Pour 1+= kk , on calcule la variation de ( )kx donne par le vecteur suivant :

( )

( )

( )

( )

=

kn

k

k

k

x

x

x

xM

2

1

en utilisant une procdure approprie selon la mthode utilise (par exemple la mthode du gradient, mthode du gradient conjugu ou la mthode de Newton). Etape 3. Calcul ( ) ( ) ( )kkk xxx += 1 .

Etape 4. Calcul de ( )( )kxf et son gradient not ( )( )kx xf , et vrification de la convergence en utilisant un critre appropri (par exemple la norme du gradient de la fonction optimiser doit tre infrieur une valeur , cest--dire ( ( )( )

35

visant rsoudre des problmes doptimisation difficile. Ces mthodes vont chercher un

optimum de faon alatoire (au hasard). En gnral, elles procdent par voisinages successifs. De faon plus prcise : une solution tant obtenue litration k, litration 1+k on cherche

au hasard une solution meilleure dans un voisinage prcdent. Les itrations successives

doivent permettre de passer dune solution de mauvaise qualit la solution optimale. Lalgorithme sarrte aprs avoir atteint un critre darrt, consistant gnralement en

latteinte du temps dexcution imparti ou en une prcision demande. Parmi les heuristiques, on retrouve les heuristiques de voisinage, qui font progresser une

seule solution la fois (par exemple la mthode de recuit simul, la recherche tabou), et les heuristiques distribues, qui manipulent en parallle toute une population de solutions (par exemples les algorithmes gntiques, les essaims de particules). Linconvnient majeur de ces mthodes est quon ne peut garantir leur convergence vers la solution globale que dune

manire asymptotique, cest--dire elles permettant de localiser un ( )xAx ~ (voisinage de loptimum global). Bien que ces mthodes puissent tre adaptes tout type de problme doptimisation, mais elles sont souvent moins puissantes que les mthodes exactes sur certains types de problmes. Elles ne garantissent pas non plus la dcouverte de loptimum global en

un temps fini. Cependant, un grand nombre de problmes rels nest pas optimisable efficacement par des approches purement mathmatiques, les heuristiques peuvent alors tre

utilises avec profit par exemple dans le cas o lexpression analytique de la fonction objectif optimiser est absente ou cette dernire est non diffrentiable.

- Mthodes hybrides Les mthodes hybrides profitent des avantages des mthodes exactes et heuristiques. Le

principe de ces mthodes consiste cooprer une mthode heuristique et une mthode exacte pour localiser loptimum global recherch avec une prcision dtermine. En gnral, la

recherche de loptimum global commence par lutilisation dune heuristique qui localise un x~

appartenant au voisinage de loptimum globale, cest--dire ( ),xA puis on passe le relais une mthode doptimisation exacte qui permet de localiser loptimum globale x avec une

bonne prcision.

2.7 Intrt des mthodes globales Pour reprsenter avec prcision les phnomnes et les grandeurs physiques, on utilise

souvent des modles ou des fonctions de nature non linaire. Ces modles non linaires

36

constituent des cls pertinentes pour russir toute tude scientifique quantitative, en particulier

les problmes pratiques formuls sous forme de problmes doptimisation. Nanmoins, la difficult vient de la manipulation des non linarits.

En optimisation, la prsence des non linarits demande plus defforts de calcul, et une difficult pour localiser loptimum global parmi les extremums possibles pour la fonction

objectif. Le problme doptimisation devient plus complexe avec la prsence de contraintes et selon le degr de leurs non linarits. Aussi, le nombre dextremums devient important avec

laugmentation des variables de dcision. Pour illustrer cette difficult, considrons le problme doptimisation, une seule variable de dcision, suivant :

( ) ( )100:Sujet

sin cos min 2

x

xxxx

(2.24)

Lvolution de la fonction objectif pour ce problme est donne par la Figure 2.1. On constate que la fonction admet plusieurs minimums. Lobjectif de loptimisation est de localiser le minium global en un nombre fini ditrations et avec une trs grande prcision. La

complexit du problme doptimisation augmente exponentiellement avec laugmention du nombre de variables de dcision ou des contraintes. Pour illustrer ce point, considrons le

problme doptimisation obtenu simplement en considrant une fonction objectif dfinie comme la somme de deux fonctions mathmatiques de mme forme que celle du problme

doptimisation (2.24), cest--dire : ( ) ( ) ( ) ( )

100

100: Sujet sin cossin cos min

2

1

22221

211

+

x

x

xxxxxxx

(2.25)

La Figure 2.2, montre que le nombre des minimums a augment avec laugmentation de variables de dcision.

37

La question qui se pose y a-t-il des tests permettant de filtrer des minimums globaux parmi les minima locaux ? Mis part le cas o la fonction objectif est convexe dans lequel il ny a pas lieu de faire de distinguo, les conditions ncessaires et/ou suffisantes de minimisation

globale ne sont accessibles que pour certaines classes de problmes doptimisation spcialement structurs. Nanmoins, reconnatre un minimum global de la fonction objectif parmi les points critiques (les points qui vrifient le systme dquations algbriques (2.5)) de la fonction objectif est possible grce la notion de lenveloppe convexe de la fonction objectif. Lenveloppe convexe note, conv ( )xf est dfinie comme la plus grande fonction convexe minorant ( )xf sur .nD Ainsi, ce qui manque pour un point critique x~ pour tre un minimum global de ( )xf est exactement la proprit suivante (Hiriart-Urruty, 1996) :

Figure 2.2 Evolution de la fonction objectif du problme doptimisation (2.25).

Figure 2.1 Evolution de la fonction objectif du problme doptimisation (2.24).

38

( ) ( )xfxf ~~ conv = (2.26) Evidemment, cette proprit nest pas facile tester puisquil est difficile habituellement

de dterminer conv ( )xf exactement surtout pour une fonction plusieurs variables ou non diffrentiables. De plus, lobtention de cette enveloppe demande plus defforts. La Figure 2.3 illustre la notion de lenveloppe convexe.

Ces difficults rencontres pour localiser le minimum global a incit les mathmaticiens,

en particulier les mathmaticiens appliqus, dvelopper des mthodes numriques permettant de localiser directement le minimum globale dune fonction non linaire

plusieurs variables. Ce qui a donn naissance un domaine de recherche trs actif appel optimisation globale .

2.8 Mthodes doptimisation globales et commande prdictive Dans un problme de commande prdictive un problme doptimisation doit tre rsolu chaque instant dchantillonnage. La nature du problme doptimisation dpend de la nature

du systme, du critre (fonction objectif) et les contraintes considres. Gnralement, le critre considr prend une forme quadratique incluant des objectifs de poursuite et dnergie minimale. Bien que le critre de performances est quadratique, ce qui reprsente une forme de fonction objectif intressante pour localiser la solution globale, nanmoins la non linarit du problme doptimisation vient de la nature du modle utilise pour la prdiction. Dans le cas dun modle linaire, une solution analytique du problme doptimisation peut tre obtenu,

cest le cas de lalgorithme Dynamic Matrix Control, prsent dans la section 1.4 du chapitre

Fonction objectif ( )xf Enveloppe convexe conv ( )xf

Figure 2.3 Fonction objectif et son enveloppe convexe.

39

1, par consquent vu la capacit des calculateurs numriques disponibles, limplmentation ne

pose pas de problme puisque la solution peut tre calcule rapidement. Par contre, si le modle est non linaire, les prdictions le seront aussi, par consquent le critre prend une

forme non linaire dont la complexit dpend directement des non linarits du systme. Ainsi, le problme doptimisation est non linaire, donc lobtention de la solution chaque

instant dchantillonnage est une tche trs dlicate, et ncessite des mthodes numriques qui convergent en un nombre fini ditrations et rapidement vers la solution optimale.

Comme la quasi-totalit des systmes sont de nature non linaire, pour lesquels lhypothse de linarit ne prsente aucun intrt, alors lutilisation dun modle non linaire

pour prdire les sorties du systme commander est invitable. De plus, utiliser un modle non linaire va dans le sens daccrotre la prcision de la prdiction ce qui permet damliorer

davantage les performances du systme en boucle ferme. Nanmoins, la prdiction non linaire complexifie lapplication de la commande prdictive des systmes non linaires

puisque le problme doptimisation rsoudre est de nature fortement non linaire dont la difficult de localiser loptimum globale, en un nombre fini ditrations ou en un temps

infrieur la priode dchantillonnage, se prsente avec acuit. Lapplication dune solution locale dans une stratgie de commande prdictive nest pas dramatique, mais en appliquant

une solution globale les performances seront meilleures, puisque minimiser mieux le critre implique une bonne poursuite de consigne, un bon rejet de perturbation, et un minimum dnergie (objectifs souvent viss par lutilisation dun critre quadratique). Par consquent, lutilisation des mthodes doptimisation globale dans une commande prdictive non linaire

constitue une solution intressante qui permettra dlargir son champ dapplication. Dans ce chapitre, nous avons prcis uniquement la liaison directe entre loptimisation et la

commande prdictive non linaire, et lintrt de lutilisation des mthodes doptimisation globales. Dans le chapitre 4, on prsentera une synthse sur les diffrentes approches

doptimisation globale non linaire proposes et utilises dans le cadre dune commande prdictive.

2.9 Conclusion Ce chapitre a t consacr des gnralits sur loptimisation de fonctions mathmatiques,

en particulier loptimisation globale. Lobjectif consiste prsenter les lments essentiels utiliss le long de ce mmoire, et de montrer lintrt des mthodes de loptimisation globale,

en particulier dans une stratgie de commande prdictive non linaire. Quoique plusieurs mthodes doptimisation globale ont t dveloppes dans la littrature, mais en pratique il est

40

trs difficile, voire impossible, de prconiser une telle mthode ou une autre pour un problme

doptimisation donn. En outre, lexamen de la littrature, montre que la thorie nest pas dun grand secours, puisque les thormes de convergence sont souvent inexistants, ou

applicables sous des hypothses restrictives. De plus, le rglage optimal des paramtres de la mthode prconis par la thorie est souvent inapplicable en pratique surtout dans le cas des

heuristiques. Aussi, les comparaisons entre les diffrentes mthodes disponibles abordes dans la littrature se limitent des problmes de tests idaliss. Ainsi, le choix dune mthode

doptimisation globale fait appel souvent lexprience. En consultant la littrature ddie loptimisation globale, deux mthodes doptimisation

globale trs intressantes ont attir notre attention, elles sagissent de la mthode dAlienor qui fait partie des mthodes exactes, et la mthode des essaims de particules qui est une

mthode heuristique. Ces mthodes sont caractrises par des algorithmes simples comprendre et programmer, et ncessitent peu de paramtres de rglages dont leurs choix

est souvent dictes par des thories mathmatiques pousses, en particulier pour la mthode dAlienor. Ces mthodes constituent des variantes intressantes pour russir une commande

prdictive non linaire. Les principes de ces deux mthodes seront exposs dans le chapitre suivant, et pour valuer leur capacit localiser loptimum globale, ces mthodes seront

appliques pour lidentification des paramtres dun systme non linaire.

41

Chapitre 3

Mthodes doptimisation globale : Alienor et Essaim de Particules

3.1 Introduction Dans le chapitre prcdent, on a montr lintrt des mthodes doptimisation globale, en

particulier dans une stratgie de commande prdictive non linaire. Le monde industriel

affronte une comptition mondiale exacerbe : gagner par exemple ne serait-ce quun pour cent sur lnergie consomme par un procd reprsente un gain de comptitivit trs

important. Pour ce faire, les efforts se sont focaliss sur le dveloppement de mthodes et dalgorithmes doptimisation souples et rapides qui permettant de localiser avec succs

loptimum global tout en respectant les contraintes imposes par le problme. Naturellement, lapproche numrique a t favorise d laugmentation considrable de la puissance des

42

ordinateurs qui a largement contribu rpondre limpratif de temps de calcul, et la

complexit des problmes doptimisation (fortement non linaires). La littrature sur loptimisation dcrit pour lessentiel des mthodes locales qui permettent

lobtention de minima locaux qui peuvent tre certes intressantes dans une tude pralable du phnomne mais quil faudra de toute faon amliorer pour optimiser au mieux le problme

formul ou modlis. Quant aux mthodes globales existantes elles sont la plupart du temps des amliorations des mthodes locales que lon tente de dbloquer dun minimum local pour

aller vers un meilleur minimum, esprant quin fine on obtiendra un minimum global. Parmi ces mthodes, on retrouve la mthode dAlienor dveloppe par lquipe de

recherche dYves Cherruault dans les annes 80, dont le principe est simple et lefficacit nest plus dmontrer. Ces dernires annes, les mthodes heuristiques ont aussi dmontr

leur efficience dans la localisation dun optimum globale, et commence simposer comme des mthodes alternatives intressantes aux mthodes exactes qui exigent une certaine

rgularit des fonctions minimiser (continuit et diffrentiabilit) qui ne sont pas ncessairement vrifie. Parmi ces mthodes, on retrouve la mthode dessaim de particules

qui bnficie dune large utilisation pour la rsolution des problmes doptimisation rputs difficiles. Cet mthode prsente plusieurs avantages par rapport aux autres heuristiques

(Hammouche et al., 2010). Dans ce chapitre, on prsentera les principes des mthodes doptimisation globale

dAlienor et dessaim de particules. Pour illustrer leur efficacit, les mthodes seront utilises pour lidentification des paramtres dun systme non linaire.

3.2 Mthode dAlienor La mthode Alienor, propose par Cherruault (2005), repose sur une suite de

transformations rductrices qui permet de ramener toute fonction de plusieurs variables une

fonction dune seule variable. On peut alors utiliser, pour rsoudre le problme multivariable, les mthodes puissantes habituellement mises en uvre pour le cas unidimensionnel.

Soient deux variables relles, ,1x 2x . Nous allons dabord passer en coordonnes polaires

( ) ( ) 0 ,sin ,cos 21 == rxrx (3.1) Ce faisant nous obtenons deux nouvelles variables r et que nous allons relier grce la

spirale dArchimde dquation

ar = (3.2) o a est un paramtre fix, destin tendre vers 0. Ainsi, les relations (3.1) deviennent

43

( ) ( ) sin ,cos 21 axax == (3.3) Par consquent, elles permettent dexprimer 1x et 2x laide dune unique variable .0

La Figure 3.1 reprsente lexploration globale du plan (fonction objectif deux variables) paramtre par le paramtre unique .

On peut gnraliser cette transformation n variables. Il suffit de relier les variables deux

deux. Considrons, par exemple, trois variables .,, 321 xxx Nous allons dabord relier 1x et 2x

laide de ,1 on obtient :

( ) ( )112111 sin ,cos axax == (3.4) Puis on relie les deux variables qui restent 1 et 3x laide de pour obtenir :

( ) ( ) sin ,cos 31 axa == (3.5) Il est alors clair que 321 ,, xxx sexpriment laide de . En effet, on a :

( ) ( )( )( ) ( )( )

( )

sin

cos sin cos

cos coscos

3

22

21

ax

aax

aax

=

=

=

(3.6)

On voit que, dune faon gnrale, on aboutit des relations

( ) 0 ; ,,1 , == nihx ii K (3.7) avec des les fonctions ih faisant intervenir les fonctions trigonomtriques en sinus et cosinus.

Par consquent, ces fonctions sont infiniment diffrentiables. La mthode dAlienor peut tre exploite pour la rsolution des problmes doptimisation

de la manire suivante : Soit rsoudre le problme doptimisation suivant :

( )nxx

xxfn

,,min 1,,1

KK

(3.8)

Figure 3.1 Exploration globale du plan paramtre par (spirale dArchimde).

44

o f est une fonction non linaire continue. La transformation (3.7) permet de remplacer la fonction ( )nxxf ,,1 K par la nouvelle fonction ( )*f donne comme suit :

( ) ( ) ( )( ) nhhff ,,1* K= (3.9) qui est une seule fonction dune seule variable .

Le problme doptimisation (3.8) est alors remplac par le problme suivant : ( )

*

0min f

(3.10)

qui est un problme de minimisation une seule variable que lon peut rsoudre simplement

condition de savoir dfinir lintervalle [ ] ,0 max sur lequel on va rechercher le (ou les) minima globaux de ( ).* f Le succs de la mthode dAlienor de base prsente a pouss les chercheurs dvelopper dautres transformations rductrices pour simplifier les calculs. Ainsi, plutt que de rduire

deux deux les variables par la mthode dAlienor de base, des transformations rductrices ont t proposes dont lide de base consiste exprimer toutes les variables en fonction de la

variable en une seule tape. Ceci impose de choisir correctement les fonctions ih de la

transformation rductrice (3.7). Par consquent, les efforts se sont focaliss sur ce point dont lobjectif est de dvelopper des transformations rductrices simples qui demande moins de calculs, et surtout de bien approximer le problme doptimisation n variables.

Parmi les transformations rductrices proposes dans la littrature, on retrouve les transformations suivantes :

- Transformation 1 :

( ) cos iix = (3.11) o les paramtres i forment une suite croissante et vrifient la condition suivante :

11

(3.12)

- Transformation 2 :

( )pi cos ii mx = (3.13) avec .1>m

45

- Transformation 3 :

( ) cos iix = (3.14) Les paramtres 11 ,, n K sont choisis proches les uns des autres, tout en constituant une

suite lentement croissante, par exemple

+=+ ii 1 (3.15) avec 0> et choisi trs petit. Le paramtre n est choisi comme suit :

pi 11 = nn n (3.16)

- Transformation 4 :

( )iiix += cos (3.17) o les 0>i forment une suite croissante. i est une suite lentement croissante dont les

termes sont proches lun des autres, par exemple :

+=+ ii 1 (3.18) avec 0> et choisi trs petit.

Notons que la dernire transformation rductrice (3.17), permet une exploration globale du plan paramtr par en assurant une trs bonne prcision par rapport aux autres.

Aussi, dautres variantes ont t proposes pour lier r et afin damliorer la prcision de

lapproximation. Parmi ces relations, on peut citer les suivantes (Bendiab et Cherruault, 1995) :

.0 ,

,

2

>=

=

+

ber

er

b

(3.19)

Pour illustrer la dtermination de la fonction une seule variable ( )*f , considrons le problme doptimisation (2.25). Pour ce faire, on propose dutiliser la transformation 4 donne par la relation (3.17) et de modifier les contraintes du problme doptimisation (2.25), qui sont de type botes, de manire avoir 10,10 21 xx . Ainsi, pour respecter ces

contraintes, il suffit de prendre ,10= ,1001 = ,1012 = ,11 = et 00001.0= ( )( )00001.1 101cos10

1 100cos10

2

1

+=

+=

x

x (3.20)

Ce qui donne la fonction suivante

46

( ) ( )( ) ( )( ) ( )( )( )( ) ( )( ) ( )( )00001.1 101cos 1000001.1 101cos 10sin00001.1 101cos10cos

1 100cos 101 100cos 10sin 1 100cos 10cos2

2*

+++++

+++=

f

(3.21) En rsolvant lquation algbrique suivante :

( ) 0* = f (3.22) on dtermine facilement le minimum global * et partir de la transformation (3.20), on dtermine la solution optimale globale comme suit :

( )( )00001.1 101cos 10

1 100cos 10**

2

**

1

+=

+=

x

x (3.23)

Aprs avoir prsent la mthode dAlienor qui est une mthode exacte, dans la section suivante, on prsentera une mthode doptimisation globale heuristique, en loccurrence la mthode dessaim de particules.

3.3 Mthode dessaim de particules Loptimisation par essaim de particules ou Particle Swarm Optimisation (PSO) en anglais

fait partie des mthodes heuristiques, elle est base sur la reproduction dun comportement social. Elle a t dveloppe en 1995 par Eberhart et Kennedy (1995) suite aux travaux de recherche sur la simulation de vols groups doiseaux et de bancs de poissons raliss par Reynold (1987) et Heppner et Grenander (1990). Les rsultats obtenus ont dmontr la capacit dun groupe en mouvement maintenir une distance optimale entre eux et suivre un mouvement global par rapport aux mouvements locaux de leur voisinage. Un autre rsultat important concerne limportance du mimtisme dans la comptition qui oppose les particules la recherche de la nourriture. Ces dernires sont disperses alatoirement dans un espace de recherche, et lorsquune particule localise une source de nourriture, les autres particules vont alors chercher le reproduire.

Ce comportement social bas sur lanalyse de lenvironnement et du voisinage reprsente rellement une mthode doptimisation par observation des tendances des particules voisines. Le principe impose chaque particule chercher optimiser ses chances en suivant une

tendance quelle modre par ses propres vcus.

47

3.3.1 Principe de la mthode dessaim de particules Un essaim est dispos de faon alatoire et homogne dans lespace de recherche et chaque

particule possde la capacit de se dplacer avec une vitesse alatoire. Ai