Utilisation des méthodes d'optimisations métaheuristiques pour la résolution du problème de répartition optimale de la puissance dans les réseaux électriques

III - 2.4 Le croissement

Dans un algorithme génétique, des parties des individus sélectionnés (parents) sont échangées par croisement. Le croisement peut être effectué sur un ou plusieurs parents pour former un ou plusieurs enfants (ou descendants). Il existe, là aussi, de nombreuses méthodes de croisement.

Nous présentons ici les croisements classiques, qui sont le croisement en un point, le croisement en deux points et le croisement uniforme, il y à d'autres méthodes de croisement appelées le croisement diagonal et le croisement de bloc. Ces derniers opérateurs sont bien adaptés à la transmission des propriétés topologiques entre les parents et les descendants [25].

III - 2.4.1 Croisement en un point

On choisit au hasard un point de croisement, pour chaque couple figure III-2. Notons que le croisement s'effectue directement au niveau binaire, et non pas au niveau des gènes. Un chromosome peut donc être coupé au milieu d'un gène.

2 parents 2 enfants

10010

1001101011

10000

011010111

100100

001101

100100 10101001001

001101 10011010111

Figure III-2 : Principe de croissement en un point

III - 2.4.2 Croisement en un et deux points

On choisit au hasard deux points de croisement figure III-3. Par la suit, nous avons utilisé cet opérateur car il est généralement considéré comme plus efficace que la précédent. Néanmoins nous n'avons pas constaté de différence notable dans la convergence de l'algorithme.

Notons que d'autre formes de croisement existent, du croisement en K points jusqu'au cas limite du croisement uniforme.

2 parents 2 enfants

10101

001101

100100

001001

010111

10011

100100 10101 001001

001101 10011 010111

Figure III-3 : Principe de croissement en deux points

III - 2.4.3 Croisement uniforme

Le croisement binaire utilise un masque (en binaire) de même longueur que les parents. Chaque 1 contenu dans le masque déclenche de l'inversion du gène visé avec celui de l'autre parent. Voir le figure III-4 [25] :

0 0 0 1 1 1

Masque

2 enfants

0

0 0 1 0 0 1

0 010 0

0 1 0 1 1 1

011 0 1

1

1 0 0		0 0	0 1		1 1		0 0
2 parents
1 0 0		1 0	0 1		0 1		0 1
0 0 1		1 0	1 1		0 0		1 1
100	01 00			1		110 1
100	1 10 1			0		1 1 00

Figure III-4 : Croisement uniforme

III - 2.5 Mutation

Nous définissons une mutation comme étant l'inversion d'un bit dans un chromosome. Cela revient à modifier aléatoirement la valeur d'un paramètre du dispositif. Les mutations jouent le rôle de bruit et empêchent l'évolution de se figer. Elles permettent d'assurer une recherche aussi bien globale que locale, selon le poids et le nombre des bits mutés. De plus, elles garantissent mathématiquement que l'optimum global peut être atteint.

1 0 0 1 0 0

1 0 0 1 0 0

0 1 0 1 0 0 1 0 0 1

0 0 1 0 1 0 0 1 0 0 1

Une mutation

1 1

Figure III-5 : Opérateur de mutation

Début

III - 2.6 Organigramme de la procédure génétique

L'organigramme fonctionnel de la figure III-6 illustre la structure de l'algorithme génétique standard. Nous détaillerons les diverses phases qui le constituent et présenterons les mécanismes associés à chacune d'entre elles dans les sections suivantes [26].

Population initiale

T=T+1

Recombinaison : Croisement

Nouvelle Population

Non

Evaluation

Terminer

Sélection

Oui

Résultat

Figure III-6 : Organigramme d'un algorithme génétique.

III - 2.7 Application de l'AG à la répartition économique des puissances

Nous appliquons ici l'algorithme génétique de base étape par étape à la répartition économique des puissances sur un simple réseau test constitué de 9 jeux de barres, 6 lignes électriques, 3 générateurs, 3 transformateurs et 3 charges.

G

G

G

Figure III-7 : Schéma unifilaire de réseau électrique

Le tableau III-2 montre les données techniques et économiques des trois générateurs interconnectés. La puissance de base utilisée est de 100 MVA.

° N	Pmin ( Pu )	Pmax ( Pu )	($ / h )	( $ / Mwhr)	( Mw^2 hr) $ /
1	0.30	1.8	105.0	2.45	0.01
2	0.15	0.9	44.1	3.51	0.01
3	0.40	1.9	40.6	3.89	0.01

Tableau III-2 : Ensemble des paramètres des puissances actives générées PGi

Le problème de la REP consiste à trouver le minimum de la fonction objective. Chaque puissance active générée PGi est limitée par une limite inférieure PGi min et une limite supérieure PGi max . Puisque la

fonction objective est bornée supérieurement, on va choisir une fonction sélective à maximiser de la forme suivante [22] :

fitness

? F - F x ( ) si F x ( ) < max = ? ?0 sinon

Fmax

III - 2.7.1 Codage des chromosomes et le décodage

La première étape consiste à coder les variables P_Gi sous forme de chromosome. Pour sa simplicité et sa commodité, le codage binaire est utilisé dans cet exemple. Avec le codage binaire, les puissances actives générées du réseau test(PG ₁ , P _G2 , P_G3) vont être codées comme une chaîne de « 0 » et « 1 » avec,

respectivement, des longueurs(L₁ , L ₂ , L ₃ ) (peuvent être différentes).

Chaque paramètre P_Gi a une limite supérieure PGi max = B et une limite inférieure PGi min = A. Le choix de L1,L ₂ et L₃ pour les paramètres est sujet de la résolution spécifiée par l'utilisateur dans l'espace de la

recherche. Avec le codage binaire, la relation entre la longueur de bit Li et la résolution correspondante Ri est donnée par :

R i	=	B A - i I
		2 - 1 Li

Donc, l'ensemble P_Gi peut être transformé en une chaîne binaire (chromosome) avec une longueur

? L_i et puis l'espace de recherche est exploré. Il est à noter que chaque chromosome présente une solution possible du problème. Par exemple, supposer le domaine des paramètres de (PG ₁ , P _G2 , P_G3) qui est présenté dans le Tableau 1. Si la résolution R ₁ , R ₂, R₃ est spécifiée comme 0.1, 0.05, 0.1 d'après l'équation (7) on aura L₁, L ₂ et L₃ = (4,4,4) . Alors l'ensemble de paramètres (PG ₁ , P _G2 , P_G3 ) peut être codé selon le tableau III-3.

N°	P1 (Pu)	Code	P2 (Pu)	Code	P3 (Pu)	Code
1	0.3	0000	0.15	0000	0.4	0000
2	0.4	0001	0.20	0001	0.5	0001
3	0.5	0010	0.25	0010	0.6	0010
4	0.6	0011	0.30	0011	0.7	0011
5	0.7	0100	0.35	0100	0.8	0100
6	0.8	0101	0.40	0101	0.9	0101
7	0.9	0110	0.45	0110	1.0	0110
8	1.0	0111	0.50	0111	1.1	0111
9	1.1	1000	0.55	1000	1.2	1000
10	1.2	1001	0.60	1001	1.3	1001
11	1.3	1010	0.65	1010	1.4	1010
12	1.4	1011	0.70	1011	1.5	1011
13	1.5	1100	0.75	1100	1.6	1100
14	1.6	1101	0.80	1101	1.7	1101
15	1.7	1110	0.85	1110	1.8	1110
16	1.8	1111	0.90	1111	1.9	1111

Tableau III-3 : Codage de l'ensemble des paramètres de PGi

Pour construire un codage multi-paramétrié, on peut tout simplement concaténer autant de codage d'un seul paramètre qu'il est nécessaire. Le chromosome correspond à l'ensemble de paramètres (1.7, 0.30, 1.1) est alors la chaîne de caractères binaire suivante 111000110111. Le décodage est la procédure inverse