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.1.1 Codage binaire

Holland et de Jong ont imposé le codage binaire de longueur fixe pour un chromosome qui s'écrit sous la forme d'une chaîne de l bits avec

n

l=?₌ ( )

l x_i

i 1

Où l ( x_i ) est le nombre de bits du gène numéro i correspondant au paramètre x_i .

Un des avantage du codage binaire est que l'on peut ainsi facilement coder toutes sortes de paramètre : réel, entiers booléens et chaînes de caractère. Cela nécessite simplement l'usage de fonction de codage et décodage pour passer d'une présentation à l'autre. Ce choix le rend virtuellement applicable à tous les problèmes dont les solutions sont numériques, c'est-à-dire calculées par ordinateur.

Le génotype d'un individu caractérise la structure du chromosome tandis que le phénotype désigne la chaîne obtenue par la concaténation des paramètres réels ou gênes(x₁ , x ₂, x₃, ...) .

Le décodage convertit le chromosome en phénotype grâce au génotype. Les valeurs des paramètre sont extraites sont extraites du phénotype et ensuite fournies à la fonction d'adaptation qui retourne la performance permettant ainsi de classer l'individu dans la population.

Le phénotype est obtenu à partir du génotype par l'équation :

im

? l- xim

2j + x

x_i = 2 l( xi) -1 ?j=0

( x)

b est le j^eme bit dans le gène numéro i.

Cette méthode de codage est relativement facile à implanter mais elle présente l'inconvénient de limiter la précision des paramètres à une valeur correspondant à l'écart entre deux configurations réelles adjacentes obtenues, pour une variation du bit le moins significatif. On constate que la précision du codage dépend du nombre de bits utilisé. Pour un nombre de bits par gène valant 8, 16 et 32, les précisions relatives valent ,1.5.10^-5 et 2.3.10^-10, respectivement.

A chaque paramètre x_i , on associe un gène g_i qui est un entier obtenue par :

g i

- x im x iM -x im

. ( 2 ( ) - 1) l xi

III -2.1.2 Codage de gray

Avec le codage binaire, deux configurations proches dans l'espace des paramètres peuvent avoir deux chromosomes très distincts, par exemple, les chaînes « 01111 » et « 10000 » correspondent à deux configurations réelles voisines alors qu'elles diffèrent de cinq bits. Cette caractéristique peut s'avérer pénalisante pour la recherche locale par croisement.

L'utilisation de code gray a été recommandée pour répondre à ce problème. En effet, avec ce code, les entiers adjacents ne différents que d'un bit. Le passage entre deux configurations réelles voisines ne nécessite que de modifier un seul bit dans le chromosome.

Le passage du code binaire au code de gray est effectué de la manière suivante :

? b sij l x sij l x

= ( ) ( )

=

gray j

b i i

= ??

j ? - =

1 ( )

? b b sij l x

j j i

Où ? représente l'addition modulo 2.

La transformation inverse s'obtient avec l'équation suivante :

b

) gray

b_k

= ? =

l x

( i

j k j

Si on considère que le chromosome est représenté en code de gray, on effectuera d'abord la transformation avant un décodage binaire standard.

Ces opérations sont transcrites dans la table III-1.

Entier	Code binaire	Code Gray
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

Tab III- 1 : Code binaire et code gray sur 4 bits

L'intérêt du codage de Gray se comprend mieux lorsque les opérateurs de croisement et de mutation sont présentés.