Optimisation de la production et de la structure d'énergie électrique par les colonies de fourmis

6.5. Application de l'algorithme d'ACO

Les algorithmes de colonies de fourmis forment une classe des méta-heuristiques parmi :

Recuit Simulé (RS).

Tabou (TSA).

Particule Swarm optimization (PSO).

Genetic Algorithm (GA).

Ant System Algorithm (AS).

Récemment proposée pour les problèmes d'optimisation difficile. Ces algorithmes s'inspirent des comportements collectifs de dépôt de phéromone et de suivi de piste observée dans les colonies de fourmis. Une colonie d'agents simples (les fourmis) communiquent indirectement via des modifications dynamiques de leur environnement (les pistes de phéromone) et construisent ainsi une solution à un problème, en s'appuyant sur leur expérience collective.

Notre problème d'optimisation à résoudre c'est d'optimiser une fonction objective :

Minimiser le Coût de la structure des réseaux de transport.

Sous contrainte que la connexion doit être liée sans rupture et que le transite de puissance de la structure doit être équilibré (ce qui concerne l'écoulement de puissance).

En d'autres termes il s'agit de sélectionner la meilleure combinaison des lignes (dont le chemin global est le plus court au point de vue coût) sans que la liaison de l'arbre soit fermée.

Les lignes peuvent être sélectionnés dans n'importe quelle combinaison parmi ceux qui sont théorique et réelle.

Fig (6- 7). Les fourmis et la transition entre noeuds

Afin d'appliquer la ACO au problème de l'optimisation de la structure est pratiquement identique a celui du VSP, le problème est modéliser par un graphe G = (V; E) dont les sommets correspondent aux différents noeuds soit consommateurs affecter par un signe (+) ou bien producteurs affecter par un signe (-) et dont les arêtes représentent les chemins (lignes électriques) reliant les différents noeuds et leurs caractéristiques correspondantes. A chaque arête est également associé un poids selon la qualité de la ligne (capacité, section, courant et longueur) à laquelle ils aboutissent.

Le choix est fait à base :

Les fourmis sont guidées lors de la construction d'une solution par l'information heuristique spécifique au problème qui est inversement proportionnelle à la longueur du parcourt (les fourmis préfèrent le choix des lignes courtes) et le taux de phéromone (expérience des autres fourmis) :

 : représente la longueur associé entre les noeuds i et j du réseau.

 : représente la section de la longueur associé entre les noeuds i et j du réseau.

L'algorithme est conçu de la manière suivante :

m fourmis sont initialement positionnées sur les m noeuds représentant le réseau ou bien le graphe. Chaque fourmi représente une configuration ou bien une structure (arbre) possible du réseau électrique. Cette configuration est constituée de n-1 noeuds formant l'arbre ou bien la vertèbre du système réseau électrique, chaque noeud i cuminique avec les n-1 noeud du réseau bouclé théoriquement à son tour le noeud i peut englobé le départ et l'arrivée de k_i lignes misent en parallèle. Les k_i ligne de chaque paire de lignes sont choisis dans n'importe quelle combinaison parmi le nombre possible de ligne du graphe qui est :

Alors chaque fourmi construit une solution un arbre, une fourmi placée sur un noeud i choisie une destination vers un autre noeud j en appliquant une règle de transition d'état  donnée par:

(6-27)

(6-28)

: Représente l'importance relative de la piste de phéromone.

: Représente l'importance relative de l'information heuristique

L : Représente la longueur de la ligne (i, j)

S : Représente la section de la ligne (i, j)

AC_i : Représente l'ensemble des lignes (théorique et réelle) existantes pour le graphe.

Q : Nombre aléatoire générée entre 0 et 1.

Le paramètre q_o détermine l'importance relative de l'exploitation: chaque fois qu'une fourmi sur un noeud i doit choisir une destination vers un noeud j qui définisse une ligne ij, en génère d'abord un nombre aléatoire 0= q =1.

Le processus de recherche s'achève quand la fourmi atteint le dernier noeud sans qu'il revienne au noeud de départ en formant une connexion avec l'ensemble des noeud (arrêt au noeud n-1 ) toute en formant l'arbre ou la vertèbre c'est une solution cette instruction est donnée par le teste List Tabu (mémoire virtuelle).

Si la valeur de q = q_o donc la meilleure arête (ligne) est sélectionnée suivant la relation (6-27) (exploitation), autrement une arête est choisie suivant la relation (6-28) (exploration biaisée ).

La mise à jour de la phéromone consiste en deux phases :

? Mise à jour locale

? Mise à jour globale.

Pendant la construction d'une solution, la fourmi modifie la quantité de phéromone sur les arêtes (lignes) visitées par l'application des règles de mise à jour.

La mise à jour locale est introduite afin d'éviter la convergence prématurée et réduite la quantité de phéromone sur l'arête reliant un noeud i avec un autre noeud j (la ligne ij) de manière à décourager la fourmi suivante de choisir la même destination durant le même cycle. La mise à jour locale est donnée par :

(6-29)

Ou est un coefficient de façon que (1-) représente l'évaporation de la trace de phéromone et _o est une valeur initiale de l'intensité de la trace de phéromone.

Une fois toutes les fourmis ont choisi leur structure durant un cycle, la quantité de phéromone sur les arêtes appartenant à la meilleure solution du cycle (meilleure fourmi) est à nouveau renforcé en appliquant la règle de mise à jour globale.

(6-30)

La solution finale c'est la meilleure solution trouvée durant tous les cycles et c'est évidemment celle qui satisfait la contrainte de l'arbre connecte à l'ensemble des noeuds, alors avec la structure la plus optimale au point de vue coût.