|
Optimisation de la production et de la structure d'énergie électrique par les colonies de fourmis( Télécharger le fichier original )par Sihem Bouri Université Jilali Liabès - Doctorat 2007 |
Pour l'évaluation de la fiabilité d'un système multi état, on utilise l'équation (2-3).
Alors : 2.6. ConclusionNous nous sommes intéressé à l'évaluation de la fiabilité des systèmes. En règle générale, la fiabilité est considérée comme un critère pertinent quant à l'évaluation de l'efficacité des systèmes. Les méthodes classiques présentent l'inconvénient de ne mesurer la fiabilité que pour des modèles binaires simples, alors la réalité du comportement des composants d'un système peut être en dégradation. Ainsi que la mesure de la fiabilité des systèmes par les méthodes classique donne une mesure quantitative. Par contre, les méthodes numériques déterminent la fiabilité des modèles binaires simples et étendus. Dans le prochain chapitre, on parlera d'une méthode numérique qui est la technique d'Ushakov `'Universal Moment Generating Function'' UMGF et on fera une étude comparative entre elle et la méthode classique pour voir son efficacité. chapitre 3
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Sous système 1 |
Sous système 2 |
|||||
|
Unité 1 |
Unité 2 |
Unité 3 |
||||
|
Etat |
1 |
2 |
1 |
2 |
1 |
2 |
|
Capacité G (%) |
0 |
60 |
0 |
80 |
0 |
150 |
|
Probabilité |
0.10 |
0.90 |
0.05 |
0.95 |
0.05 |
0.095 |
TABLEAU 3-2
CARACTÉRISTIQUES DE LA CHARGE
|
Charge en Mw |
100 |
70 |
|
Durée en (h) (%) |
6570 75 |
2190 25 |
L'UMGF de chacun des trois unités est par définition :
, nous avons donc :
Pour l'unité 1 du sous système 1 :
Pour l'unité 2 du sous système 1 :
Pour l'unité du sous système 2 :
L'UMGF du système est obtenue par l'application des
opérateurs 
et 
, 
pour les éléments en parallèles et 
pour les éléments en séries.
Pour évaluer la probabilité 
que la capacité totale du système multi états
n'est pas inférieure aux différents niveaux requis de la
demande
, nous appliquons l'opérateur 
défini par les équations (3-4) et (3-5).
Donc, la disponibilité pour chaque niveau de demande est calculé par :
La disponibilité totale du système est calculée par :
Ou 
représente les différents niveaux de la demande et 
les différents états du système. 
c'est la probabilité que la production du système
satisfait chaque niveau de demande 
, 
étant la probabilité de cette demande.
Donc, la disponibilité totale du système par rapport à la demande est :
On constate que le système considéré dans cet exemple satisfait la demande de 70Mw avec une probabilité de 90.25% et la demande de 100Mw avec une probabilité de 81.22%. La disponibilité moyenne du système est de 83.48%.
TABLEAU 3-3
PARAMÈTRES DU SYSTÈME ÉLECTRIQUE
|
Sous système 1 |
Sous système 2 |
|||||||||
|
Unité 1 |
Unité 2 |
Unité 3 |
||||||||
|
Etats |
1 |
2 |
3 |
1 |
2 |
3 |
4 |
1 |
2 |
3 |
|
Probabilité |
0.10 |
0.60 |
0.30 |
0.05 |
0.25 |
0.30 |
0.40 |
0.05 |
0.30 |
0.65 |
|
Capacité G (%) |
0.0 |
30 |
60 |
0.0 |
30 |
50 |
80 |
0.0 |
100 |
150 |
TABLEAU 3-4
CARACTÉRISTIQUES DE LA CHARGE
|
Charge en -+Mw |
100 |
70 |
|
Durée en (h) (%) |
6570 75 |
2190 25 |
L'UMGF de chacun des trois unités est par définition :
, nous avons donc :
Pour l'unité 1 du sous système 1 :
Pour l'unité 2 du sous système 1 :
Pour l'unité du sous système 2 :
L'UMGF du système est obtenue par l'application des
opérateurs 
et 
, 
pour les éléments en parallèles et 
pour les éléments en séries.
Pour évaluer la probabilité 
que la capacité totale du système multi états
n'est pas inférieure aux différents niveaux requis de la demande
, nous appliquons l'opérateur 
défini par les équations (3-4) et (3-5).
Donc, la disponibilité pour chaque niveau de demande est calculé par :
La disponibilité totale du système est calculée par :
Où 
représente les différents niveaux de la demande et 
les différents états du système. 
C'est la probabilité que la production du système
satisfait chaque niveau de demande 
, 
étant la probabilité de cette demande.
Donc, la disponibilité totale du système par rapport à la demande est :
On constate que le système considéré dans cet exemple satisfait la demande de 70Mw avec une probabilité de 77.9% et la demande de 100Mw avec une probabilité de 51.31%. La disponibilité moyenne du système est de 57.97%.
En comparant les résultats obtenus de la méthode UMGF et ceux de la méthode classique, on remarque que la méthode classique nous a donnée une valeur, par contre la méthode UMGF nous permet de connaître la valeur pour chaque étape.
La méthode UMGF nous donne des valeurs quantitatives et qualitative, par contre la méthode classique ne nous donne que des valeurs quantitatives. Donc, la méthode UMGF est mieux que la méthode classique.
D
ans les vingt dernières années, on a vu que l'ensemble des techniques mathématiques et algorithmiques de résolution de problèmes de base se développent considérablement. Les progrès significatifs des techniques d'évaluation associés à l'augmentation considérable de la capacité de calcul des machines permettent aujourd'hui de traiter des problèmes de plus en plus complexes, avec des tailles des données de plus en plus importantes. L'une des conséquences de ceci est que la construction même des modèles, de façon fiable et efficace, n'est plus un problème secondaire mais elle est devenue un problème central.
E
n outre, d'autres problèmes apparaissent, aussi bien dans le monde des techniques numériques que dans les méthodes de simulation. Du point de vue des premières, la résolution numérique de systèmes d'équations de grande taille (millions ou milliards d'équations et d'inconnues, voire une infinité) n'est pas une tâche aisée. En ce qui concerne la simulation, la prise en charge de la rareté de certains événements est un problème non trivial.
La résolution des problèmes d'optimisation est utilisée dans un grand nombre de domaines [5,15,16]. A l'origine, ce sont les militaires qui se sont intéressés à ces questions au cours de la seconde guerre mondiale. C'était en fait un nouveau domaine de recherche en mathématiques appliquées qui a vu le jour avec la recherche opérationnelle. Le développement de l'informatique a ouvert de nouveaux horizons à la résolution de ces problèmes, et a permis un élargissement massif des champs d'application de ces techniques.
La résolution d'un problème d'optimisation et un problème complexe, car de nombreux facteurs interviennent et interagissent entre eux. Néanmoins, l'optimisation appliquée au domaine d'électrotechnique permet de résoudre des problèmes qui étaient insolubles auparavant et aboutit souvent à des solutions originales.
Dans ce chapitre, nous présentons différentes méthodes de résolution. L'ensemble de ces méthodes est tellement vaste qu'il est impossible de tout exposer. Ainsi, nous présentons les principales méthodes de résolution.
L'optimisation est une des mathématiques consacré à l'étude du (ou des) minimum(s)/maximum(s) d'une fonction à une ou plusieurs variables sur un certain domaine de définition, de l'étude de leur existence à leur détermination , en général par la mise en oeuvre d'un algorithme et par suite un programme. Pour mener à bien une opération, plusieurs éléments sont indispensables et conditionnent la solution trouvée. La figure suivante présente les quatre éléments essentiels à la résolution d'un problème d'optimisation.
Fig. (IV-1) : Eléments indispensable d'optimisation
En général, un grand nombre de paramètres sont indispensables, il faut être capable de définir les paramètres utiles à l'optimisation. Certains paramètres ont une influence sur la fonction choisie, d'autres pas. Etant donné le coût des simulations, seul les paramètres influents sont à retenir :
Une fonction objective : définie l'objectif à atteindre. La définition de cette fonction est en fait un problème délicat. Car le problème est formule en un problème d'optimisation par l'intermédiaire de la fonction objective. C'est elle qui est au centre de l'optimisation, c'est donc elle que dépend la pertinence de la solution.
Un modèle : précis, robuste et malléable du système étudié est indispensable. Ce modèle doit être utilisable sur un domaine d'étude le plus large possible.
Un algorithme d'optimisation : permet de trouver la solution. Différentes méthodes d'optimisation existent et en sont présentées.
L'optimisation combinatoire [4,16] occupe une place très importante en recherche opérationnelle, en mathématiques discrètes et en informatique. Son importance se justifie d'une part par la grande difficulté des problèmes d'optimisation et d'autre part par de nombreuses applications pratiques pouvant être formulées sous la forme d'un problème d'optimisation combinatoire. Bien que les problèmes d'optimisation combinatoire soient souvent faciles à définir, ils sont généralement difficiles à résoudre. En effet, la plupart de ces problèmes appartiennent à la classe des problèmes NP-difficiles et ne possèdent donc pas à ce jour de solution algorithmique efficace valable pour toutes les données.
L'optimisation combinatoire est minimiser (ou maximiser) une fonction souvent appelée fonction coût, d'une ou plusieurs variables soumises à des contraintes. Le sujet de l'optimisation combinatoire dans un domaine discret. Il faut trouver parmi toutes les possibilités, souvent en nombre fini, la possibilité optimale. Ceci parait facile mais devient infaisable dès que la taille du problème est suffisamment grande. La taille pour laquelle la recherche d'un optimum devient infaisable est petite, très souvent plus petite que la taille des problèmes pratiques. En général, la difficulté d'un problème grandit très vite avec le nombre des variables. Il n'est pas alors faisable d'examiner toutes les possibilités.
Les méthodes d'optimisation peuvent être reparties en deux catégories :
1. Méthodes exactes.
2. Méthodes approchées.
Les méthodes exactes fournissent systématiquement une solution (optimale) au problème traité si une telle solution existe. Dans le cas contraire, ce type de méthode permet d'affirmer qu'il n'existe pas de solution au problème traité.
Les méthodes approchées fournissent une solution approchée au problème traité. Elles sont en général conçues de manière à ce que la solution obtenue puisse être située par rapport à la valeur optimale : de telle méthodes permettent d'obtenir des bornes inférieures ou supérieures de la valeur optimale tel que :
1- Méthodes Heuristiques ;
2- Méthodes Méta heuristiques.
L'heuristique [5,17] est une méthode, une technique ou un critère de guidage ou de décision, en général empirique ou obtenu par approximation, permettant de choisir la voie la plus prometteuse de recherche de la solution au problème posé, ou d'éliminer les voies les moins intéressantes, sans garantie sur la validité ou la précision de l'information ainsi fournie.
Entrer dans le domaine des heuristiques, c'est se départir d'emblée les schémas classiques. En effet, alors que la démarche classique mathématique est centrée sur l'objet de l'étude, sur la compréhension de sa structure et de sa logique, la démarche heuristique repousse le problème lui-même au rang d'illustration pour dégager des schémas de pensée plus généraux et donc originaux.
Les heuristiques disposent d'une simplicité et donc d'une rapidité dans leur exécution plus élevée que les algorithmes classiques. Ces règles s'appliquant à un ensemble particulier la recherche des faits ce voit simplifiée et accélérée (moins de possibilité). D'où une analyse des situations améliorées. Mais une méthode heuristique trop simplifiée ou au contraire trop générale peut conduire à des biais cognitifs, générant des erreurs de décision.
L'utilisation de plus de ces éléments simples (les heuristiques) afin de créer des éléments plus complexes (les méta- heuristiques) permet donc de réduire considérablement l'ensemble de recherche global de l'algorithme.
L'une de leur caractéristique principale et à première vue défaut, dont hérite également les méta- heuristiques, est qu'ils peuvent dans certains cas ne pas proposer de solution optimale au problème. Mais au résultat s'y approchant d'assez près pour qu'il soit considéré comme correct, on parle alors de garantie de performance.
Les métas- heuristiques sont apparues dans les années 1980 et forment une famille d'algorithmes d'optimisation visant à résoudre des problèmes d'optimisation difficile, pour lesquels on ne connaît pas de méthode classique plus efficace. Elles sont généralement utilisées comme des méthodes génériques pouvant optimiser une large gamme de problèmes différents, sans nécessiter de changements profonds dans l'algorithme employé [5,18,19,20,21].
Etymologiquement parlant de ce mot est composé dans un premier temps du préfixe méta qui signifie « au delà »ou « plus haut » en grec puis de « heuristique » qui signifie « trouver ». Cette décomposition permet de facilement comprendre le but premier de ces algorithmes : trouver des solutions à des problèmes en utilisant plusieurs (méta) heuristiques.
Métas- heuristiques utilisent des processus aléatoires comme moyens de récolter de l'information et de faire face à des problèmes comme l'explosion combinatoire. En plus de cette base stochastique, les méta- heuristiques sont généralement itératives, c'est-à-dire qu'un même schéma de recherche est appliqué plusieurs fois au cours de l'optimisation, et directes, c'est-à-dire qu'elles n'utilisent pas l'information du gradient de la fonction objectif. Elles tirent en particulier leur intérêt de leur capacité à éviter les optima locaux, soit en acceptant une dégradation de la fonction objectif au cours de leur progression, soit en utilisant une population de points comme méthode de recherche.
Les méta- heuristiques, du fait de leur capacité à être utilisées sur un grand nombre de problèmes différents, se prêtent facilement à des extensions. Pour illustrer cette caractéristique, citons notamment :
*L'optimisation multi objectif (dites aussi multicritère) [22], ou il faut optimiser plusieurs objectifs contradictoires. La recherche vise alors non pas à trouver un optimum global, mais un ensemble d'optima «au sens de Pareto» formant la «surface de compromis» du problème.
*L'optimisation multimodale, ou l'on cherche un ensemble des meilleurs optima globaux et/ou locaux.
*L'optimisation de problèmes bruités, où il existe une incertitude sur le calcul de la fonction objectif. Incertitude dont il faut alors tenir comptes dans la recherche de l'optimum.
*L'optimisation dynamique, ou la fonction objectif varie dans le temps. Il faut alors approcher au mieux l'optimum à chaque pas de temps.
*La parallélisation, ou l'on cherche à accélérer la vitesse de l'optimisation en répartissant la charge de calcul sur des unités fonctionnant de concert. Le problème revient alors à adapter les métas- heuristiques pour qu'elles soient distribuées.
*L'hybridation, qui vise à tirer parti des avantages respectifs de méta- heuristiques différentes en les combinant [22,23].
Enfin, la grande vitalité de ce domaine de recherche ne doit pas faire oublier qu'un des intérêts majeurs des métas- heuristiques est leur facilité d'utilisation dans des problèmes concrets. L'utilisateur est généralement demandeur de méthodes efficaces permettant d'atteindre un optimum avec une précision acceptable dans un temps raisonnable. Un des enjeux de la conception des métas- heuristiques est donc de faciliter le choix d'une méthode et de simplifier son réglage pour l'adapter à un problème donné.
D'une manière générale, les méta- heuristiques s'articulent autour de trois notions [22]:
Diversification /exploration : désigne les processus visant à récolter de l'information sur le problème optimisé.
L'intensification/exploitation : vise à utiliser l'information déjà récoltée pour définir et parcourir les zones intéressantes de l'espace de recherche.
La mémoire : est le support de l'apprentissage, qui permet à l'algorithme de ne tenir compte que des zones ou l'optimum global est susceptible de se trouver, évitant ainsi les optimums locaux.
Les métas- heuristiques progressent de façon itérative, en alternant des phases d'intensification, de diversification et d'apprentissage. L'état de départ est souvent choisi aléatoirement, l'algorithme se déroulant ensuite jusqu'à ce qu'un critère d'arrêt soit atteint.
Les métas- heuristiques sont souvent inspirées par des systèmes naturels, qu'ils soient pris en physique (les méthodes de voisinage comme le recuit simulé et la recherche tabou), en biologie de l'évolution (les algorithmes évolutifs comme les algorithmes génétiques et les stratégies d'évolution) ou encore en étiologie (les algorithmes de colonies de fourmis).
La méthode de recuit simulé s'inspire du processus de recuit physique [23,24]. Ce processus utilisé en métallurgie pour améliorer la qualité d'un solide cherche un état d'énergie minimale qui correspond à une structure stable du solide. Les origines du recuit simulé remontent aux expériences réalisées par Metropolis et al dans les années 50 pour simuler l'évolution d'un tel processus de recuit physique. Metropolis et al utilisent une méthode stochastique pour générer une suite d'états successifs du système en partant d'un état initial donné. Tout nouvel état est obtenu en faisant subir un déplacement (une perturbation) aléatoire à un atome quelconque.
L'utilisation d'un tel processus du recuit simulé pour résoudre des problèmes d'optimisation combinatoire a été reportée dans. Le recuit simulé peut être vu comme une version étendue de la méthode de descente. Le processus du recuit simulé répète une procédure itérative qui cherche des configurations de coût plus faible tout en acceptant de manière contrôlée des configurations qui dégradent la fonction de coût. A chaque nouvelle itération, un voisin de la configuration courante est généré de manière aléatoire. Selon les cas, ce voisin sera soit retenu pour remplacer celle-ci, soit rejeté. Si ce voisin est de performance supérieure ou égale à celle de la configuration courante, il est systématiquement retenu. Dans le cas contraire, il est accepté avec une probabilité qui dépend de deux facteurs : d'une part l'importance de la dégradation (les dégradations plus faibles sont plus facilement acceptées), d'autre part un paramètre de contrôle, la température (une température élevée correspond à une probabilité plus grande d'accepter des dégradations). La température est contrôlée par une fonction décroissante qui définit un schéma de refroidissement. Les deux paramètres de la méthode définissent la longueur des paliers et la fonction permettant de calculer la suite décroissante des températures. En pratique, l'algorithme s'arrête et retourne la meilleure configuration trouvée lorsque aucune configuration voisine n'a été acceptée pendant un certain nombre d'itérations à une température ou lorsque la température atteint la valeur zéro.
La performance du recuit simulé dépend largement du schéma de refroidissement utilisé. De nombreux schémas théoriques et pratiques ont été proposés. De manière générale, les schémas de refroidissement connus peuvent être classés en trois catégories :
- réduction par paliers : chaque température est maintenue égale pendant un certain nombre d'itérations, et décroît ainsi par paliers.
- réduction continue: la température est modifiée à chaque itération.
- réduction non- monotone: la température décroît à chaque itération avec des augmentations occasionnelles.
Il existe des schémas qui garantissent la convergence asymptotique du recuit simulé. En pratique, on utilise des schémas relativement simples même s'ils ne garantissent pas la convergence de l'algorithme vers une solution optimale.
Le recuit simulé constitue, parmi les méthodes de voisinage, l'une des plus anciennes et des plus populaires. Il a acquis son succès essentiellement grâce à des résultats pratiques obtenus sur de nombreux problèmes NP- difficiles. La preuve de convergence a également contribué à cette popularité, bien que cette preuve n'ait pas de portée en pratique.
Les algorithmes génétiques appartiennent à une famille d'algorithmes appelés méta- heuristique dont le but est d'obtenir une solution approchée [25,26], en un temps correct, à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte pour le résoudre. Les algorithmes génétiques utilisent la notion de sélection naturelle développée par le scientifique Charles Darwin au XIXème siècle.
Dans cette théorie, une population d'individus évolue grâce au mécanisme de la reproduction sexuée. Les individus les plus adaptés à leur milieu se reproduisent plus que les autres, favorisant les caractères les plus adaptés. Ainsi une girafe avec un cou plus long que les autres aura accès à plus de nourriture, et aura donc plus de chances de survivre et de se reproduire. Ses descendants auront un cou plus long, et en moyenne la population de girafe aura un cou plus long.
L'utilisation d'algorithmes génétiques dans la résolution de problèmes est à l'origine des recherches de John Holland dès 1960. La nouveauté introduite a été la prise en compte de l'opérateur crossing over en complément des mutations, et c'est cet opérateur qui permet le plus souvent de se rapprocher de l'optimum d'une fonction en combinant les gènes contenus dans les différents individus de la population [22,28,29].
Les algorithmes génétiques classiques introduits par Holland s'appuient fortement sur un codage universel sous forme de chaînes 0/1 de longueur fixe et un ensemble d'opérateurs génétiques : les sélections, les crossing over ou recombinaison et les mutations. Un individu sous ce codage, appelé un chromosome, représente une configuration du problème. Les opérateurs « génétiques » sont définis de manière à opérer aléatoirement sur un ou deux individus sans aucune connaissance sur le problème.
La génétique a mis en évidence l'existence de plusieurs opérateurs au sein d'un organisme donnant lieu au brassage génétique. Ces opérations interviennent lors de la phase de reproduction lorsque les chromosomes de deux organismes fusionnent.
Ces opérations sont imitées par les algorithmes génétiques afin de faire évoluer les populations de solutions de manières progressives.
Les sélections :
Pour déterminer quels individus sont plus enclins à obtenir les meilleurs résultats, une sélection est opérée. Ce processus est analogue à un processus de sélection naturelle, les individus les plus adaptés gagnent la compétition de la reproduction tandis que les moins adaptés meurent avant la reproduction, ce qui améliore globalement l'adaptation.
Il existe plusieurs techniques de sélection, les principales sont :
1- Sélection par rang,
2- Probabilité de sélection proportionnelle à l'adaptation,
3- Sélection par tournoi,
4- Sélection uniforme.
Les crossing over ou recombinaison :
Lors de cette opération, deux chromosomes s'échangent des parties de leurs chaînes, pour donner de nouveaux chromosomes. Ces crossing over peuvent être simples ou multiples. Dans le premier cas, les deux chromosomes se croisent et s'échangent des portions d'ADN en un seul point. Dans le deuxième cas, il y a plusieurs points de croisement. Pour les algorithmes génétiques, c'est cette opération qui est prépondérante. Sa probabilité d'apparition lors d'un croisement entre deux chromosomes est un paramètre de l'algorithme génétique. En règle générale, on fixe la proportion d'apparition à 0.7.
Les mutations :
D'une façon aléatoire, un gène peut, au sein d'un chromosome être substitué à un autre. De la même manière que pour les crossing over, on définit ici un taux de mutation lors des changements de populations qui est généralement compris entre 0.001 et0.01. Il est nécessaire de choisir pour ce taux une valeur relativement faible de manière à ne pas tomber dans une recherche aléatoire et conserver le principe de sélection et d'évolution. La mutation sert à éviter une convergence prématurée de l'algorithme.
Codage :
Pour les algorithmes génétiques, un des facteurs les plus importants, si ce n'est le plus important, est la façon dont sont codés les solutions, c'est-à-dire les structures de données qui coderont les gènes.
Codage binaire :
Le principe est de coder la solution selon une chaîne de bit. Ce type de codage est le plus utilisé car il présente plusieurs avantages [26,27,28,29]. Il existe au moins un coté négatif qui fait que d'autres existent. Ce codage est peu naturel par rapport à un problème donné.
Codage à caractère multiple :
Ce type de codage est plus naturel que le codage binaire. Il est utilisé dans de nombreux cas poussés [26,27,28,29,30].
Codage sous forme d'arbre :
Ce codage utilise une structure arborescente avec une racine de laquelle peuvent être issus un ou plusieurs fils. Un de leurs avantages est qu'ils peuvent être utilisés dans le cas de problèmes ou les solutions n'ont pas une taille finie. Les arbres de tailles quelconque peuvent être formés par le biais de crossing over et de mutations.
Le problème de ce type de codage est que les arbres résultants sont souvent difficiles à analyser et que l'on peut se retrouver avec des arbres dont la taille est importante.
Pour le choix du type de codage, il suffit de choisir celui qui semble le plus naturel en fonction du problème à traiter et développer ensuite l'algorithme de traitement.
Bien que les algorithmes génétiques soient considérés aujourd'hui comme une méthode d'optimisation, l'objectif initial consistait à concevoir des systèmes d'apprentissage généraux, robustes et adaptatifs, applicables à une large classe de problèmes.
L'universalité d'un tel algorithme pose évidemment des problèmes d'efficacité en pratique. En effet, en tant que méthode d'optimisation, un algorithme génétique classique se base uniquement sur des opérateurs « aveugles ». Une autre voie intéressante pour améliorer l'efficacité des algorithmes génétiques consiste à combiner le cadre génétique avec d'autres méthodes de résolution [28].
Cette méta- heuristique s'inspire des comportements collectifs des fourmis dans leur découvertes de nouvelles sources de nourriture [25,26,27,28] : en effet ces insectes utilisent des phéromones afin de marquer les informations qu'ils ont recueillies sur leur environnement. On appel cela stigmergie.
L'utilisation de ces phéromones leurs permettent de repérer les plus courts chemin entre une source de nourriture et leur nid. Car malgré leur capacité cognitive limitée, elles sont collectivement capables de résoudre des problèmes complexes.
Les méthodes de résolution sont extrêmement nombreuses, elles sont basées sur des principes totalement différents, chacune explore et exploite l'espace de recherche selon des techniques qui lui sont propres.
Comparer ces méthodes entre elles n'est pas une chose facile. Toutefois, il n'existe pas de méthodes de recherche qui soit véritablement plus performante qu'une autre sur l'ensemble des problèmes.
Pour notre étude, nous avons retenu les colonies de fourmis parce qu'elle est extrêmement performante dans de nombreux domaines. C'est une méthode très efficace lorsqu'il s'agit d'exploiter une zone de l'espace de recherche. D'autre part, elle s'adapte assez bien au problème posé.
L
a place des fourmis dans l'étude des sociétés animales est centrale car elles ont développé des formes très avancées de socialité allant jusqu'à partager leur activité de reproduction en confiant la transmission de leurs gènes à quelques individus de la colonie.
Le principe de l'optimisation par colonies de fourmis est apparu au début des années 90. Il est du aux chercheurs M. Dorigo, V. Maniezzo et A. Colorni qui expliquent leur théorie dans un article fondateur [32]. Article dans lequel ils proposent une nouvelle approche pour l'optimisation stochastique combinatoire et mettent en avant la rapidité de leur nouvelle méthode à trouver des solutions acceptables tout en évitant des convergences prématurées. Ils qualifient leur méthode de versatile (elle peut s'appliquer à des versions similaires d'un même problème), robuste et bien sur basée sur une population d'individus [33,34,35,36,37,38,39,40].
Les algorithmes de colonies de fourmis sont nés à la suite d'une constatation : les insectes sociaux en général, et les fourmis en particulier, résolvent naturellement des problèmes relativement complexes. Les biologistes ont étudié comment les fourmis arrivent à résoudre collectivement des problèmes trop complexes pour un seul individu, notamment les problèmes de choix lors de l'exploitation de sources de nourriture.
L'optimisation par colonies de fourmis s'inspire du comportement des fourmis lorsque celles-ci sont à la recherche de nourriture. Les fourmis en se déplaçant déposent des phéromones, substances olfactives et volatiles. Chaque fourmi se dirige en tenant compte des phéromones qui sont déposées par les autres membres de la colonie. Les fourmis choisissent leur chemin de manière probabiliste. Comme les phéromones s'évaporent progressivement, le choix probabiliste que prend une fourmi pour choisir son chemin évolue continuellement.
Les fourmis constituent à l'heure actuelle un support majeur pour les théories développées en écologie comportementale et en sociobiologie. On peut citer plusieurs raisons à cet engouement :
* L'influence des fourmis sur leur environnement naturel est extrêmement importante. Il a par exemple été montré qu'elles déplacent plus de terre en foret tropicale que les vers de terre, ou encore que le poids total des fourmis sur terre est du même ordre de grandeur que le poids des humains. De plus, la domination des fourmis est une preuve de leur adaptation `a des environnements très variés : Dans la foret vierge amazonienne du Brésil, le poids sec de l'ensemble des fourmis est environ quatre fois supérieur `a celui de tous les vertébrés terrestres (mammifères, oiseaux, reptiles et amphibiens) réunis [19]. On trouve ainsi des fourmis dans tous les écosystèmes terrestres situés entre les deux cercles polaires. La connaissance de leur mode de vie est donc primordiale à la compréhension des espèces animales et végétales qui les côtoient;
* L'étude des fourmis se fait assez facilement en laboratoire car elles s'adaptent sans trop de difficultés à des environnements différents de leur habitat d'origine ;
* Les fourmis possèdent une gamme de comportements très variés, collectifs ou individuels.
La place des fourmis dans l'étude des sociétés animales est centrale car elles ont développé des formes très avancées de socialité allant jusqu'à partager leur activité de reproduction en confiant la transmission de leurs gènes `a quelques individus de la colonie (les reines et les males) [17,41].
Le nombre d'espèces sociales (environ 13 500 connues [19]) est assez réduit par rapport au nombre d'espèces d'insectes répertoriées, soit environ 750 000, alors que les insectes sociaux représentent la moitié de la biomasse des insectes. La grande diversité des fourmis (environ 10 000 espèces connues [19]) propose une large variété de morphologies et de comportements. L'étude des fourmis, la myrmécologie, est donc un vaste et passionnant champ d'investigation.
Une fourmilière peut aussi être assimilée à un super organisme s'apparentant à un organisme vivant composé de cellules. Chaque cellule remplit un rôle précis tout comme les fourmis accomplissent certaines taches pour la survie et le développement du nid. Les fourmis sexuées ont par exemple le même rôle que les cellules sexuelles. Les parallèles entre ces deux types de systèmes sont étonnants et l'étude de leur développement, la morphogenèse pour un organisme et la sociogenèse pour une société d'insectes, permet de faire certains rapprochements. L'étude de la sociogenèse a l'avantage d'être plus facile à réaliser puisque l'on peut retirer et injecter des constituants sans mettre en péril le développement du super organisme.
De par la grande diversité des écosystèmes colonisés (des forets vierges aux déserts), les fourmis offrent une grande diversité de comportements et de morphologies [41]. L'étude précise de leur comportement (l'éthologie) est souvent limitée aux espèces les moins populeuses pour des raisons pratiques évidentes d'étude en laboratoire. Cette diversité exubérante est une mine d'inspiration fascinante pour les systèmes informatiques. C'est ainsi que les capacités des fourmis en matière de coopération, de communication, de compétition et d'apprentissage, entre autres, peuvent être mises à profit pour la conception de robots ou d'algorithmes de résolution de problèmes.
Les insectes sociaux en général, et les fourmis en particulier, ont développé des mécanismes de communication très élaborés [44] pour les insectes sociaux pour les animaux en général). Il a été défini douze types de réponse mettant en oeuvre une forme de communication [45] :
1. L'alarme ;
2. L'attraction simple ;
3. Le recrutement (pour une source de nourriture ou un site de nidification);
4. L'entretien et la mue ;
5. La trophallaxie (échange de liquides) ;
6. L'échange d'aliments solides ;
7. Les effets de groupe (augmentation ou inhibition d'une activité) ;
8. La reconnaissance des apparentés ou de caste ;
9. La détermination de caste ;
10. La compétition pour la reproduction ;
11. Le marquage du territoire et du nid ;
12. La reproduction (différenciation du sexe, de l'espèce, de la colonie...).
La communication chimique est de loin la plus présente chez les fourmis. Les phéromones (mélange d'hydrocarbures) sont `a la base de la communication de nombreuses espèces. La chémoréception présente les avantages suivants :
La diversité des molécules pouvant intervenir permet de fournir des informations qualitatives ;
La stabilité du signal pour une molécule peu volatile permet d'assurer une certaine permanence.
Par contre, les principaux inconvénients de la communication chimique sont les suivants :
Elle n'offre que peu d'informations sur la direction ;
Sa propagation est relativement lente et elle est peu adaptée pour la transmission de messages urgents ou pour l'intégration de deux stimulations successives sous une forme temporelle.
Les ouvrières sont par exemple capables de déposer des traces chimiques sur le trajet qu'elles empruntent pour ramener de la nourriture. Au delà du fait que ce marquage leur permet de retrouver leur chemin jusqu'à la fourmilière pour ce qui est du retour et jusqu'à la source de nourriture pour ce qui est d'exploiter une source abondante, cela leur permet de transmettre à leur congénères l'emplacement de l'aubaine.
La communication chimique est aussi mise à l'oeuvre pour déclencher des alarmes quand le nid est attaqué et ainsi mobiliser un grand nombre d'individus pour défendre la fourmilière.
Ces deux mécanismes font partie des comportements de recrutement. De plus, plusieurs phéromones peuvent être utilisées et avec des concentrations différentes, constituant ainsi une sorte de langage chimique. Les principales manifestations du recrutement sont la recherche de nourriture, la construction du nid, la défense de la colonie et la migration vers de nouveaux sites de nidification.
Bien que peu répandue, certaines espèces ont développé une forme de communication acoustique soit en utilisant un grattoir ou en utilisant les vibrations du sol. Les mouvements peuvent aussi servir de canal de communication : certaines fourmis tisserandes se livrent `a une sorte de danse pour recruter des ouvrières. On trouve aussi des ouvrières qui transportent d'autres ouvrières pour leur indiquer le nouvel emplacement du nid [19]. La communication tactile entre aussi en jeu dans de nombreux rituels d'invitation et de recrutement. Enfin la communication visuelle est assez difficile à mettre en évidence mais certaines espèces semblent utiliser ce canal pour déclencher des mouvements collectifs notamment lors de l'attaque de proies.
La communication entre les individus peut se faire directement ou indirectement.
L'utilisation des phéromones est majoritairement une forme indirecte puisque l'échange d'information se fait grâce au support du sol. Quand deux individus interagissent indirectement en modifiant l'environnement on parle de stigmergie. Ce terme a été introduit par Grassé à propos des mécanismes collectifs de construction du nid chez les termites.
Les différentes applications informatiques qui découlent des capacités de communication des fourmis se retrouvent par exemple en optimisation combinatoire ou la coopération stigmergétique s'applique parfaitement à la recherche du plus court chemin dans un graphe. Ces applications seront détaillées dans le chapitre suivant.
Une des caractéristiques particulièrement intéressante est la capacité des sociétés d'insectes à se partager le travail. Les taches que doivent accomplir les ouvrières sont en effet multiples :
* La recherche de nourriture ;
* La défense du nid ;
* L'entretien et la construction du nid ;
* L'entretien des larves et leur approvisionnement en nourriture.
Toutes ces activités, dont l'importance est variable dans le temps et l'espace, doivent être assurées simultanément pour la survie et le développement de la colonie. C'est essentiellement la plasticité de l'organisation déployée par les fourmis qui nous intéresse. Il a été mis en évidence que certains groupes d'individus se spécialisent dynamiquement pour une tache particulière. Cette dynamique peut être mise en oeuvre pour un individu particulier : sa tache de prédilection varie dans le temps, dans ce cas toutes les ouvrières sont potentiellement capables d'accomplir n'importe quelle tache. On trouve aussi des spécialisations morphologiques, avec par exemple des variations de taille de un `a dix `a l'intérieur de la même espèce. Dans ce cas la dynamique est assurée par un contrôle des naissances sur chaque type de morphologie.
L'architecture des nids construits par les fourmis est un exemple frappant de structure complexe. L'intérêt pour des modèles pouvant expliquer l'apparition de telles structures provient encore une fois de l'organisation distribuée qui est sous-jacente. Il n'y a pas, a priori, de contrôle centralisé, de coordination de niveau supérieur à l'individu. La structure émerge des interactions inter- individuelles et avec l'environnement. La communication indirecte entre les individus est la encore mise à profit.
Les fourmis tisserandes sont par exemple capables d'unir leurs efforts pour rapprocher des feuilles en formant de véritables ponts puis d'unir les bords des feuilles en utilisant la soie produite par leurs larves. La construction du nid chez les termites a été étudiée par Deneubourg. L'apparition des piliers dans une termitière pouvant être expliquée par l'amplification de multiples fluctuations chaotiques : la structure, modèle d'équilibre des forces par sa stabilité, naît de l'amplification de multiples déséquilibres. La construction des nids de guêpes est aussi un modèle d'action collective ou les agents répondent plus particulièrement à des stimuli issus de certaines configurations dans la structure.
La recherche de la nourriture (le fourragement) est une activité souvent plus dispersée spatialement que la construction du nid et qui peut aussi être mise en oeuvre de facon tr`es différente suivant les espèces de fourmis. Les stratégies de recherche de nourriture sont en effet extrêmement diversifiées. Par exemple `a cause des différences de régime alimentaire : certaines espèces peuvent être spécialisées sur un unique type d'aliment. On peut aussi trouver des mécanismes très élaborés comme la culture de champignon ou l'élevage de pucerons. La recherche de nourriture est une activité risquée (les fourrageuses de Cataglyphis bicolor ont par exemple une espérance de vie de 6.1 jours [19])) mais souvent efficace (la quantité de nourriture ramenée au nid au cours d'une vie représente de 15 `a 20 fois le poids d'un individu). La communication peut avoir un impact important, en particulier pour les mécanismes de recrutement dont le principal intérêt collectif est de rassembler les ouvrières sur les sources de nourriture rentables. D'un point de vue plus général, la communication mise en oeuvre pour la recherche de nourriture peut être considérée comme une forme de mémoire collective quand elle s'appuie sur la modification de l'environnement telle que l'utilisation des phéromones.
Les capacités individuelles des fourmis peuvent servir de modèle à des systèmes artificiels tant leur adaptation à leur environnement peut être efficace. Nous citons par exemple les points suivants :
* Individuellement, une fourmi possède certaines capacités d'apprentissage, et notamment quand elle se déplace autour du nid. Les expériences de Schatz et ses collègues montrent que les fourmis du genre Cataglyphis sont capables d'apprendre visuellement des routes familières pour se déplacer entre un site alimentaire et leur nid;
* Du point de vue physique, certaines espèces ont des capacités étonnantes comme les fourmis Gigantiops destructor capables de faire des bonds impressionnants et dotées de capacités visuelles inhabituelles ce qui les a rendues difficiles à observer.
La plupart des caractéristiques qui intéressent l'informatique sont cependant collectives. Les caractéristiques individuelles ne sont évidemment pas une particularité des fourmis mais de tous les organismes vivants ayant un souci de survie.
Les théories rassemblées sous le terme d'auto organisation ont originellement été développées en physique ou en chimie pour décrire l'émergence de phénomènes macroscopiques à partir d'interactions et de processus définis au niveau microscopique. L'auto organisation se prête bien à l'étude des insectes sociaux qui montrent des comportements collectifs complexes issus de comportements individuels simples. On peut regrouper les processus d'auto organisation chez les insectes sociaux en quatre groupes tant leur diversité est importante :
* Le recrutement et l'exploitation collective de sources de nourriture : le fourragement met à jour des stratégies qui permettent aux insectes une grande adaptation à leur milieu ;
* La division du travail et l'organisation des rôles sociaux : à l'intérieur d'une même société, on peut observer différentes castes spécialisées dans un certain nombre de taches (élevage du couvain, recherche de nourriture, construction du nid, ...) ;
* L'organisation de l'environnement : la construction du nid est un symbole de l'organisation distribuée des insectes. Le nid est construit sans que les insectes soient dirigés, ils répondent à un certain nombre de stimuli provenant de leur environnement ;
* La reconnaissance inter-individuelle : chaque fourmi est capable d'identifier ses congénères tout en participant elle même `a l'identité de sa colonie (l'échange d'aliments entre les individus d'une même colonie, la trophallaxie, est un exemple d'acte altruiste permettant en plus d'homogénéiser l'identité de la colonie, l'identité coloniale). Les explications du mécanisme de reconnaissance ne sont pas encore parfaitement établies. Cependant, il s'avère qu'il y ait `a la fois une composante génétique et une composante acquise par apprentissage. Un réseau de neurones a par exemple été utilisé pour reproduire ce mécanisme d'apprentissage puis de différenciation entre les composés chimiques, dans le cas des termites.
Ces processus d'auto-organisation sont à l'origine de ce que l'on dénomme l'intelligence collective. On parle d'intelligence collective quand un groupe social peut résoudre un problème dans un cas ou un agent isolé en serait incapable.
La stigmergie est un des concepts à la base de la création des méta- heuristiques de colonies de fourmis. Elle est précisément définie comme une «forme de communication passant par le biais de modifications de l'environnement», mais on peut rencontrer le terme « interactions sociales indirectes » pour décrire le même phénomène. La spécificité de la stigmergie est que les individus échangent des informations par le biais du travail en cours, de l'état d'avancement de la tache globale à accomplir [46].
Dans un système auto- organisé, il n'y a pas de prise de décision à un niveau donné, suivie d'ordres et d'actions prédéterminées. En effet, dans un système décentralisé, chaque individu dispose d'une vision locale de son environnement, et ne connaît donc pas le problème dans son ensemble. La littérature des systèmes multi- agents emploie souvent ce terme ou celui « d'intelligence artificielle distribuée », bien que, d'une manière générale, l'étude des systèmes multi agents tende à utiliser des modèles de comportement plus complexes, fonde notamment sur les sciences de la cognition. Les avantages d'un contrôle décentralise sont notamment la robustesse et la flexibilité : systèmes robustes, car capables de continuer à fonctionner en cas de panne d'une de leurs composantes ; flexibles, car efficaces sur des problèmes dynamiques.
L'hétérarchie dense est un concept issu directement de la biologie, utilisé pour décrire l'organisation des insectes sociaux, et plus particulièrement des colonies de fourmis [19]. La définition peut être traduite comme suit :
Une colonie de fourmis est une variante particulière de hiérarchie qui peut avantageusement être appelée une hétérarchie. Cela signifie que les propriétés des niveaux globaux agissent sur les niveaux locaux, mais que l'activité induite dans les unités locales influence en retour les niveaux globaux. L'hétérarchie est dite dense dans le sens ou un tel système forme un réseau hautement connecte, ou chaque individu peut échanger des informations avec n'importe quel autre. Ce concept est en quelque sorte opposé à celui de hiérarchie ou, dans une vision populaire mais erronée, la reine gouvernerait ses sujets en faisant passer des ordres dans une structure verticale, alors que, dans une hétérarchie, la structure est plutôt horizontale Figure (5-1).
Fig. (5-1) : [a] Hiérarchie dense ; [b] Concept opposé
On constate que ce concept recoupe celui de contrôle décentralisé, mais aussi celui de stigmergie, en ce sens que l'hétérarchie décrit la manière dont le flux d'information parcourt le système. Cependant, dans une hétérarchie dense, tout type de communication doit être pris en compte, tant la stigmergie que les échanges directs entre individus.
Les fourmis ont la particularité d'employer pour communiquer des substances volatiles appelées phéromones. Elles sont attirées par ces substances, qu'elles perçoivent grâce à des récepteurs situés dans leurs antennes. Ces substances sont nombreuses et varient selon les espèces. Les fourmis peuvent déposer des phéromones au sol, grâce à une glande située dans leur abdomen, et former ainsi des pistes odorantes, qui pourront être suivies par leurs congénères Figure (5-2).
Les fourmis utilisent les pistes de phéromone pour marquer leur trajet, par exemple entre le nid et une source de nourriture. Une colonie est ainsi capable de choisir (sous certaines conditions) le plus court chemin vers une source à exploiter, sans que les individus aient une vision globale du trajet.
En effet, comme l'illustre la figure (5-2), les fourmis le plus rapidement arrivées au nid, après avoir visite la source de nourriture, sont celles qui empruntent les le chemin le plus court. Ainsi, la quantité de phéromone présente sur le plus court trajet est légèrement plus importante que celle présente sur le chemin le plus long. Or, une piste présentant une plus grande concentration en phéromone est plus attirante pour les fourmis, elle a une probabilité plus grande d'être empruntée. La piste courte va alors être plus renforcée que la longue, et, à terme, sera choisie par la grande majorité des fourmis.
On constate qu'ici le choix s'opère par un mécanisme d'amplification d'une fluctuation initiale. Cependant, il est possible qu'en cas d'une plus grande quantité de phéromone déposée sur les grandes branches, au début de l'expérience, la colonie choisisse le plus long parcours.
D'autres expériences, avec une autre espèce de fourmis, ont montré que si les fourmis sont capables d'effectuer des demi-tours sur la base d'un trop grand écart par rapport à la direction de la source de nourriture, alors la colonie est plus flexible et le risque d'être piégé sur le chemin long est plus faible.
Fig. (5-2) : Les Fourmis réelles suivent un chemin entre le Nid et la Nourriture. (B) Un obstacle apparaît sur le chemin : Les Fourmis choisissent de tourner soit à gauche soit à droite avec une probabilité égale. (C) La phéromone est déposé plus rapidement sur le chemin le plus court. (D) Toutes les fourmis ont choisi le chemin le plus court.
Il est difficile de connaître avec précision les propriétés physico-chimiques des pistes de phéromone, qui varient en fonction des espèces et d'un grand nombre de paramètres. Cependant, les métas- heuristiques d'optimisation de colonies de fourmis s'appuient en grande partie sur le phénomène d'évaporation des pistes de phéromone. Or, on constate dans la nature que les pistes s'évaporent plus lentement que ne le prévoient les modèles. Les fourmis réelles disposent en effet « d'heuristiques » leur apportant un peu plus d'informations sur le problème (par exemple une information sur la direction). Il faut garder à l'esprit que l'intérêt immédiat de la colonie (trouver le plus court chemin vers une source de nourriture) peut être en concurrence avec l'intérêt adaptatif de tels comportements. Si l'on prend en compte l'ensemble des contraintes que subit une colonie de fourmis (prédation, compétition avec d'autres colonies, etc.), un choix rapide et stable peut être meilleur, et un changement de site exploite peut entraîner des coûts trop forts pour permettre la sélection naturelle d'une telle option.
La fourmi artificielle se présente sous la forme d'un ensemble de procédures qui définissent son comportement [42,43]. Celui-ci est très semblable à celui de la fourmi naturelle quand elle recherche de la nourriture Figure (V-2). Dans ce cas, une fourmi n'a qu'un rôle assez simple qui consiste à se déplacer du nid jusqu à la source de nourriture et à y revenir. Le code qui définit leur comportement permet aux fourmis artificielles de se déplacer dans l'espace combinatoire formé par les différents éléments qui peuvent être utilisés pour le problème à résoudre. Pour utiliser un vocabulaire informatique, nous dirons qu'elle construit une solution. La mémorisation de ces déplacements donne la forme d'une solution où chaque étape est désignée par I'indice de l'élément et où I'ordre de parcours désigne la position des éléments dans la solution.
1. Dans le cas des fourmis artificielles, il n'y a pas obligatoirement de phase de recrutement.
1. Qui est capable d'agir dans un environnement;
2. Qui peut communiquer directement avec d'autres agents;
3. Qui, est mue par un ensemble de tendances (sous la forme d'objectifs individuels ou d'une fonction de satisfaction, voire de survie, qu'elle cherche à optimiser) ;
4. Qui possède des ressources propres;
5. Qui, est capable de percevoir (mais de manière limitée) son environnement ;
6. Ne dispose que d'une représentation partielle et éventuellement nulle de cet environnement ;
7. Qui, possède des compétences et offre des services;
8. Qui, peut éventuellement se reproduire;
9. Dont le comportement tend à, satisfaire ses objectifs, en tenant compte des ressources et des compétences dont elle dispose, et en fonction de sa perception, de ses représentations et des communications qu'elle reçoit.
En se basant sur ces définitions, il est possible de décrire le comportement des fourmis virtuelles en tant qu'agents :
1- Les entités informatiques que nous venons de définir sont dites virtuelles car elles n'ont pas d'existence matérielle au contraire des entités physiques qui interagissent dans le monde concret (Des exemples de ces agents physiques sont un robot, un avion, une voiture) ;
2- Les agents sont capables d'agir : dans le cas des fourmis virtuelles, elles modifient les valeurs de phéromone associées aux différents éléments. Par cette action elles changent leur environnement, ce qui influera sur le choix des autres fourmis à l'itération suivante ;
3- Les agents sont capables de communiquer : les fourmis utilisent comme on I'a vu précédemment la phéromone comme médium de communication indirecte;
4- les agents sont doués d'autonomie : chaque fourmi â pour but de construire une solution pour un problème donné, se contentant pour cela d'appliquer les règles de sélection qui définissent son comportement, la fourmi utilise la phéromone et parfois des valeurs heuristiques;
5- Les agents n'ont qu'une représentation partielle de leur environnement : lors de la construction d'une solution, la fourmi ne connaît à chaque étape que les éléments qu'elle a déjà choisis et les valeurs de phéromone correspondant aux éléments qui pourront l'être.
Comme nous avons pu le voir, les fourmis peuvent résoudre collectivement des problèmes complexes. Un des exemples marquant est celui de la découverte du chemin le plus court dans l'expérience du choix entre les deux chemins. Chacune des fourmis, isolément, ne peut trouver la meilleure solution. C'est grâce au mécanisme d'auto- organisation qui émerge de la communication indirecte (stigmergie) que le plus court chemin peut être découvert. Le modèle de la stigmergie peut être facilement étendu aux agents artificiels en associant aux éléments d'un problème des variables d'état spécifique, qui serviront de support à la communication indirecte entre fourmis.
Pour simuler ce mécanisme, il faut intégrer un processus de renforcement positif. Dans le cas des fourmis, plus le chemin est court, plus les fourmis le parcourront vite et plus la quantité de phéromone associée sera élevée. Afin de pouvoir comparer les solutions, il est nécessaire d'introduire une mesure qui donne l'adéquation de la solution au problème : c'est la fonction qualité (en anglais fitness). La valeur de cette qualité est utilisée dans le calcul de la mise à jour des valeurs associées aux éléments du problème lors de la phase de renforcement. Pour la recherche chemin le plus court, on peut prendre tout simplement la distance comme mesure de qualité : plus le chemin est court, plus il sera renforcé.
Une des propriétés de la phéromone est son caractère volatil. Dans le modèle virtuel, un mécanisme similaire sera utilisé afin d'éviter une convergence prématurée (stagnation) due à la découverte d'un optimum local.
Entre ces deux modèles, nous passons d'un univers continu à un univers discret. Ainsi, les fourmis virtuelles sautent d'un élément à un autre, tandis que les fourmis naturelles progressent de façon continue sur le chemin. Cette discrétisation impose que l'évaporation ou la modification des valeurs de phéromone ne puisse se faire en continu. Cet ajustement de valeurs n'est souvent réalisable qu'après la construction de la solution complète.
Le problème du voyageur de commerce (Travelling Salesman Problem, TSP) a fait l'objet de la première implémentation d'un algorithme de colonies de fourmis : le [Ant Syste (AS)] [34].
Le problème du voyageur de commerce consiste à
trouver le trajet le plus court (désigne par «tournée»
ou plus loin par «tour») reliant n villes données, chaque
ville ne devant être visitée qu'une seule fois. Le problème
est plus généralement défini comme un graphe
complètement connecte
, ou les villes sont les noeuds N et les trajets entre ces
villes, les arêtes A.
Dans l'algorithme AS, à chaque itération
, chaque fourmi 
parcourt le graphe et construit un trajet complet de 
étapes (on note
le cardinal de l'ensemble N). Pour chaque fourmi, le trajet entre une
ville i et une ville j dépend de :
La liste des villes déjà visitées, qui
définit les mouvements possibles à chaque pas, quand la fourmi k
est sur la ville i : 
;
L'inverse de la distance entre les villes : 
, appelée visibilité. Cette information
«statique» est utilisée pour diriger le choix des fourmis vers
des villes proches, et éviter les villes trop lointaines ;
La quantité de phéromone déposée sur l'arête reliant les deux villes, appelée l'intensité de la piste. Ce paramètre définit l'attractivité d'une partie du trajet global et change à chaque passage d'une fourmi. C'est, en quelque sorte, une mémoire globale du système, qui évolue par apprentissage.
La règle de déplacement (appelée «règle aléatoire de transition proportionnelle» par les auteurs) est la suivante :
(5-1)
Ou 
et 
sont deux paramètres contrôlant l'importance relative de
l'intensité de la piste,
, et de la visibilité
. Avec
, seule la visibilité de la ville est prise en compte; la ville
la plus proche est donc choisie à chaque pas. Au contraire, avec 
, seules les pistes de phéromone jouent. Pour éviter une
sélection trop rapide d'un trajet, un compromis entre ces deux
paramètres, jouant sur les comportements de diversification et
d'intensification est nécessaire.
Après un tour complet, chaque fourmi laisse une certaine quantité de phéromone
sur l'ensemble de son parcours, quantité qui dépend de la
qualité de la solution trouvée :
(5-2)
Où
: est le trajet effectué par la fourmi 
à l'itération
: la longueur de la tournée et 
un paramètre fixé.
L'algorithme ne serait pas complet sans le processus d'évaporation des pistes de phéromone. En effet, pour éviter d'être piégé dans des solutions sous optimales, il est nécessaire de permettre au système «d'oublier» les mauvaises solutions. On contrebalance donc l'additivité des pistes par une décroissance constante des valeurs des arêtes à chaque itération. La règle de mise à jour des pistes est donc :
(5-3)
Ou 
et m est le nombre de fourmis. La quantité initiale de
phéromone sur les arêtes est une distribution uniforme d'une
petite quantité 
.
La figure (5-3) présente un exemple simplifié de problème du voyageur de commerce.
Fig. (5-3) : Le problème du voyageur du commerce, les points représente les villes et l'épaisseur des arêtes la quantité de phéromone déposée. (a) exemple de trajet construit par une fourmi. (b) au début du calcul, tous les chemins sont explorés. (c) le chemin le plus court est plus renforcé que les autres. (d) l'évaporation permet d'éliminer les moins bonne solutions.
Une première variante du « Système de Fourmis » a été proposée : elle est caractérisée par l'introduction de fourmis « élitistes ». Dans cette version, la meilleure fourmi (celle qui a effectué le trajet le plus court) déposé une quantité de phéromone plus grande, dans l'optique d'accroître la probabilité des autres fourmis d'explorer la solution la plus prometteuse.
Dans cette variante de AS, la règle de mise à jour locale est inspirée du « Q learning ». Cependant, aucune amélioration par rapport a l'algorithme AS n'a pu être démontrée. Cet algorithme n'est d'ailleurs, de l'aveu même des auteurs, qu'un pré version du « Ant Colony System ».
L'algorithme « Ant Colony System » (ACS) [47,48,49,50] a été introduit pour améliorer les performances du premier algorithme sur des problèmes de grandes tailles. ACS est fondé sur des modifications du AS :
ACS introduit une règle de transition dépendant
d'un paramètre 
, qui définit une balance diversification/intensification. Une
fourmi k sur une ville i choisira une ville j par la règle :
(5-4)
Ou 
est une variable aléatoire uniformément distribuée
sur 
et 
une ville sélectionnée aléatoirement selon la
probabilité :
(5-5)
En fonction du paramètre 
, il y a donc deux comportements possibles : si 
le choix se fait de la même façon que pour l'algorithme
AS, et le système tend à effectuer une diversification ;
si 
, le système tend au contraire vers une intensification. En
effet, pour 
, l'algorithme exploite davantage l'information récoltée
par le système, il ne peut pas choisir un trajet non exploré.
La gestion des pistes est séparée en deux niveaux : une mise à jour locale et une mise à jour globale. Chaque fourmi dépose une piste lors de la mise à jour locale :
(5-6)
Où 
est la valeur initiale de la piste. A chaque passage, les arêtes
visitées voient leur quantité de phéromone diminuer, ce
qui favorise la diversification par la prise en compte des trajets non
explorés. A chaque itération, la mise à jour globale
s'effectue comme ceci :
(5-7)
Où les arêtes 
appartiennent au meilleur tour T+de longueur L+
et ou
. Ici, seule la meilleure piste est donc mise à jour, ce qui
participe à une intensification par sélection de la meilleure
solution.
Le système utilise une liste de candidats. Cette liste
stocke pour chaque ville les 
plus proches voisines, classées par distances croissantes. Une
fourmi ne prendra en compte une arête vers une ville en dehors de la
liste que si celle-ci a déjà été explorée.
Concrètement, si toutes les arêtes ont déjà
été visitées dans la liste de candidats, le choix se fera
en fonction de la règle (5-5) sinon c'est la plus proche des villes non
visitées qui seront choisies.
Cette variante est une hybridation entre le ACS et une recherche locale de type 3-opt [29]. Ici, la recherche locale est lancée pour améliorer les solutions trouvées par les fourmis et donc les ramener à l'optimum local le plus proche.
Le problème Max-Min Ant System noté par (MMAS) est fondé sur l'algorithme AS et présente quelques différences notables. Seule la meilleure fourmi met à jour une piste de phéromone ;
Les valeurs des pistes sont bornées par 
et 
;
Les pistes sont initialisées à la valeur maximum
;
La mise à jour des pistes se fait de façon proportionnelle, les pistes les plus fortes étant moins renforcées que les plus faibles ;
Une réinitialisation des pistes peut être effectuée.
Les meilleurs résultats sont obtenus en mettant à jour la meilleure solution avec une fréquence de plus en plus forte au cours de l'exécution de l'algorithme.
Pour l'algorithme AS, les auteurs préconisent que, bien que la valeur de Q ait peu d'influence sur le résultat final, cette valeur soit du même ordre de grandeur qu'une estimation de la longueur du meilleur trajet trouvé. D'autre part, la ville de départ de chaque fourmi est typiquement choisie par un tirage aléatoire uniforme, aucune influence significative du placement de départ n'ayant pu être démontrée.
En ce qui concerne l'algorithme ACS, les auteurs conseillent
d'utiliser 
, ou 
est le nombre de villes et 
la longueur d'un tour trouvé par la méthode du plus
proche voisin.
Le nombre de fourmis m est un paramètre important ; les auteurs suggèrent d'utiliser autant de fourmis que de villes (i.e. m = n) pour de bonnes performances sur le problème du voyageur de commerce. Il est possible de n'utiliser qu'une seule fourmi, mais l'effet d'amplification des longueurs différentes est alors perdu, de même que le parallélisme naturel de l'algorithme, ce qui peut s'avérer néfaste pour certains problèmes. En règle générale, les algorithmes de colonies de fourmis semblent assez peu sensibles à un réglage fin du nombre de fourmis.
Le problème est représenté par un jeu de solutions, une fonction objective assignant une valeur à chaque solution et un jeu de contraintes. L'objectif est de trouver l'optimum global de la fonction objectif satisfaisant les contraintes. Les différents états du problème sont caractérisés comme une séquence de composants. On peut noter que, dans certains cas, un coût peut être associe à des états autres que des solutions[51,52,53].
Dans cette représentation, les fourmis construisent des solutions en se déplaçant sur un graphe G = (C; L), ou les noeuds sont les composants de C et où l'ensemble L connecte les composants de C. Les contraintes du problème sont implémentées directement dans les règles de déplacement des fourmis (soit en empêchant les mouvements qui violent les contraintes, soit en pénalisant de telles solutions).
Les fourmis artificielles peuvent être
caractérisées comme une procédure de construction
stochastique construisant des solutions sur le graphe G = (C; L). En
général, les fourmis tentent d'élaborer des solutions
faisables mais, si nécessaire, elles peuvent produire des solutions
infaisables. Les composants et les connexions peuvent être
associés à des pistes de phéromone 
(mettant en place une mémoire adaptative décrivant
l'état du système) et à une valeur heuristique 
(représentant une information a priori sur le problème,
ou venant d'une source autre que celle des fourmis ; c'est bien souvent le
coût de l'état en cours). Les pistes de phéromone et la
valeur de l'heuristique peuvent être associées soit aux
composants, soit aux connexions figure (5-4)).
Chaque fourmi dispose d'une mémoire utilisée pour stocker le trajet effectué, d'un état initial et de conditions d'arrêt. Les fourmis se déplacent d'après une règle de décision probabiliste fonction des pistes de phéromone locales, de l'état de la fourmi et des contraintes du problème. Lors de l'ajout d'un composant à la solution en cours, les fourmis peuvent mettre à jour la piste associée au composant ou à la connexion correspondante. Une fois la solution construite, elles peuvent mettre à jour la piste de phéromone des composants ou des connexions utilisées. Enfin, une fourmi dispose au minimum de la capacité de construire une solution du problème.
Fig. (5-4) : Dans un algorithme de colonie de fourmis, les piste de phéromone peuvent être associées aux composants (a) ou au connections (b) du graphe représentant le problème à résoudre.
En plus des règles régissant le comportement des fourmis, un autre processus majeur a cours : l'évaporation des pistes de phéromone. En effet, à chaque itération, la valeur des pistes de phéromone est diminuée. Le but de cette diminution est d'éviter une convergence trop rapide et le piégeage de l'algorithme dans des minimums locaux, par une forme d'oubli favorisant l'exploration de nouvelles régions.
Selon les auteurs du formalisme ACO, il est possible d'implémenter d'autres processus nécessitant un contrôle centralisé (et donc ne pouvant être directement pris en charge par des fourmis), sous la forme de processus annexes. Ce n'est, à notre sens, que peu souhaitable ; en effet, on perd alors la caractéristique décentralisée du système. De plus, l'implémentation de processus annexes entre difficilement dans une formalisation rigoureuse.
L
a planification des réseaux électriques est l'une des parties les plus importantes du problème d'optimisation et de distribution de l'énergie électrique. Le problème primordial est la détermination optimale de la configuration des réseaux HT/THT tout en tenant compte de l'évolution atroce de la demande en énergie électrique.
N
otre optimisation est principalement la reconstruction d'un réseau de transport dont le coût conventionnel soit minimal
Les soucies majeurs de plusieurs chercheurs dans le domaine d'optimisation s'est penché plus particulièrement dans les réseaux soit électriques [51,52,53,54], de communication ou bien hydraulique. La théorie de recherche opérationnelle aborde la totalité des problèmes d'optimisation primale et duale.
L'optimisation de la structure du réseau revient à structurer une configuration optimale parmi plusieurs en la modélisant par un graphe qui admet des noeuds et des arêtes. La détermination du graphe optimal revient à déterminer la connexion optimale du système par laquelle son coût conventionnel Z soit minimal [2,29].
Considérons une configuration d'un réseau virtuel de S branches, le coût conventionnel est donné par :
(6-1)
: Coût conventionnel de la branche ij.
(6-2)
Ou :
: Investissement de la ligne (ij).
: Taux d'exploitation.
: Taux d'amortissement.
: Pertes d'énergie sur la ligne (ij).
Pour simplifier les équations du problème, on pose :
Dont :
A : Représente une composante d'investissement qui ne dépend ni de (section, pylône, fondation) et est exprimée en [DA/Km].
: Coefficient exprimé en [DA/Km
mm2].
: Section du conducteur [mm2].
: Longueur de la ligne (ij) [Km].
(6-3)
: Temps de pertes de puissances maximale en [h].
: Coût d'un KWh de perte d'énergie en
[DA/KWh
: Courant maximal sur la branche (ij) en [A].
: Résistance de la ligne (ij) en 
.
(6-4)
: Résistivité du conducteur
.
En ce qui concerne les configurations maillées de transport, le calcul de la section économique des conducteurs est donné par le courant économique suivant le modèle mathématique :
(6-5)
(6-6)
Avec :
(6-7)
(6-8)
(6-9)
(6-10)
Avec
(6-11)
(6-12)
Si
(6-13)
Le cout conventionnel pour une configuration du réseau est de la forme suivante :
(6-14)
(6-15)
De la formulation, mathématique, on voit que la
détermination de la configuration optimale du réseau est de
trouver un ensemble de courant 
égal à la valeur nulle, cela justifie l'inexistence de la
branche ij dans le schéma de connexion du réseau pour
laquelle le coût conventionnel 
est minimal.
La fonction 
est interrompue au point 
, et elle se compose de deux composantes :
La première 
qui dépend de la somme des branches existantes dans la
configuration.
La deuxième 
qui dépend de la somme des produits des courants 
par les longueurs
.
La détermination de la configuration optimale d'un
réseau se traduit par la détermination des courants 
de manière que le coût conventionnel du réseau
soit :
(6-16)
Avec
(6-17)
Pour laquelle :
: Courant de charge ou de la source au point i.
: Nombre des noeuds du réseau.
: Nombre des noeuds reliés directement avec le noeud
i.
: Somme des courants entrants et sortants du noeud i loi
de Kirchhoff.
Pour une configuration à 
noeuds, le nombre S des courants inconnus 
sera :
(6-18)
Ce nombre de courants donné par (6-18) découle
du fait qu'on a deux courants dans chaque branche 
et 
, en réalité on peut négliger les courants
résiduels provenant de la charge vers la source, et d'après la
première loi de Kirchhoff nous aurons 
équation.
Donc, pour un réseau ouvert de n noeuds, on
aura 
branches, dont le coût conventionnel de la variable 
est non linéaire, et sa modélisation est de la forme
suivante :
pour 
(6-19)
(6-20)
: Composante relative à l'investissement et proportionnel
à la longueur des lignes.
: Composante relative aux pertes de puissance dans le
réseau. Donc, on peut dire que la fonction objective :
Minimiser
(6-21)
Sujet à
(6-22)
Dans la structure des réseaux, une configuration est un
ensemble de graphes. On définit un graphe comme une construction
topologique d'un ensemble de points ou sommets d'un système industriel
[2,], la conduite reliant ces points exemple réseau électrique
(noeud générateur, noeud de charge) constituent une
structure de branches entre eux. Dans la modélisation, on désigne
un graphe de 
noeuds et de 
branches par :
On dit qu'une construction topologique est complet si le graphe dans lequel l'ensemble des couples de noeuds est relié par une conduite c'est à dire (branches).
Considérons la configuration complète suivante, constituée par quatre (4) noeuds à six (6) branches.
Fig. (6-1) : Réseau à quatre noeuds
=4 01, 02, 03, et 04.
=6 ( 12 ), ( 23 ), ( 34 ), ( 41 ), ( 24 ), ( 13 ).
Cela nous conduit à modéliser la topologie complète par :
(6-23)
Un arbre c'est le graphe d'une topologie sans boucle (cycle). Par les mêmes noeuds on peut déterminer différents arbres.
Fig. (6-2) : Les arbres possibles
Un arbre de 
noeuds à :
(6-24)
= 4 donc S = 4-1 = 3 branches.
Si on ajoute un arc à un arbre, on crée une branche supplémentaire, on aura un graphe avec une boucle.
Fig. (6-3) : Arbre avec boucle
Si ont supprime un arc de l'arbre, nous obtenons des schémas illogiques.
Fig. (6-4) : Schéma incomplet
D'après le théorème de Cayley, avec n sommets, le nombre d'arbres qu'on peut former est déterminé par :
(6-26)
Comme exemple une topologie formée par 04 sommets n = 04, nous avons un graphe complet :
Fig. (6-5) : Graphe complet
Mais avec c = 4(4-2) = 16 différents arbres.
Fig. (6-6) : Différents arbres d'un réseau à quatre noeuds
Dans ce chapitre on utilise une nouvelle méta- heuristique basée sur les colonies de fourmis pour résoudre le problème d'optimisation de la structure des réseaux électriques connu généralement sous le nom NP- Dur redondant (problème combinatoire de redondances).
Le problème d'optimisation des systèmes parallèles série à été largement étudié en utilisant des méthodes itératives telle que Prim Krustal et Djikstra. Récemment, les algorithmes génétiques et des fourmis. Peu de travaux ont utilisé les algorithmes de fourmis (ACO) en anglais `'Ant Colony Algorithm'' pour résoudre les problèmes d'optimisation de type NP- Dur. Cependant, étant donnée la grandeur de la taille de l'espace de recherche du NP- Dur, ce dernier constitue un sujet d'étude approprié par les méthodes ACO.
La méthode ACO est inspiré par le comportement naturel observé chez les fourmis. Les éthologistes ont étudié comment des insectes aveugles, comme les fourmis, peuvent établir les chemins les plus courts à partir de leur fourmilière vers les sources de nourriture.
M. Dorrigo était le premier auteur à introduire le concept d'optimisation par ACO en 1992. les méthodes ACO `'ant colony algorithm'' ont été appliquées avec beaucoup de succès dans différent problèmes d'optimisation combinatoire tel le voyageur de commerce en anglais Travelling Sillismen Problem TSP en langue française Voyageur de Commerce entre Ville VSP , réseaux de télécommunication, routage de véhicule, et planification des taches.
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 ki lignes misent en parallèle. Les ki 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)
ACi : 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 qo 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 = qo 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.
STEP 1. Initialiser:
Set t:=0 {t est le compteur temporelle},
For Chaque arc (i,j) Faire une valeur initiale ij (t) et Faire ij (t,t+n):= 0,
Place bi(t) Fourmis sur chaque noeuds i {b i (t) c'est le nombre de fourmis sur chaque noeuds i au temps t},
Set s:=1 {s c'est la list tabu indexé}
For i:=1 to n do
For k:=1 to bi (t) do
tabuk (s):= i {Noeud de départ c'est le 1er élément de la liste tabu pour la k-th Fourmi}.
STEP 2. Répéter jusqu'au tabu list is full {ce step est répéter (n-1) fois}
2.0. Set s:=s+1
2.1. For i:=1 to n do {Pour chaque noeuds}
For k:=1 to bi (t) do {Pour chaque k-th Fourmi sur le noeud i pas encore déplacer}
Choisir le noeud j à déplacer avec une probabilité pij (t)
(1)
Déplacer la k-th Fourmi to j {Cette Instruction Crée une nouvelle valeurs de bj (t+1)}
Insérer le Noeud j in tabuk (s).
STEP 3. For k:=1 to m do {Pour Chaque fourmi }
Calculer Lk {C'est le résultat du tabu list}
For s:=1 to n-1 do {scanner la liste tabu de la k-th Fourmi}
Set (h,l):=(tabuk (s),tabuk (s+1))
{[h, l] c'est l'arc de connexion du noeud s et s+1 dans la liste tabu de la Fourmi k}
(2)
LK: représente la longueur parcourue par la Kth Fourmi.
Q: représente la quantité de la phéromone déposée par la Kth Fourmi.
STEP 4. For Chaque arc (i,j) calculer ij (t+n) accorder à l'équation (2)
Set t:=t+n
For chaque arc (i,j) set ij (t,t+n):=0.
STEP 5. Mémoriser la parcours trouvé jusqu'à maintenant
If (NC < NCMAX ) ou bien (Pas toutes les Fourmis choisir le même parcours) {NC est le nombre des cycles de l'algorithme; dans NC cycles sont tester NC·m parcours}
then
Vider toutes les listes Tabu
Set s:=1
For i:=1 to n do
For k:=1 to b i (t) do
tabuk (s):=i {Après le parcours de la k-th Fourmi est encore sur la position de départ}
Goto STEP 2
else
Print le meilleur parcours et faire Stop.
Un programme (ANT-OPTI) à été conçu pour l'optimisation des structures des réseaux électriques de transport soit Haute ou bien Moyenne tension.
L
ors de la conception d'un système fluide de type RAP (problème d'allocation de redondance), aucun équipement n'est à l'abri d'une défaillance, cette dernière se traduit par une perte de production qui se répercute par une insatisfaction au client (demande). Afin de prévoir des moyens de couvrir cette perte de production, on se procure au domaine d'étude des systèmes à haute disponibilité /ou fiabilité. Ce travail fait objet de la résolution d'un ensemble de problème cohérents, auxquelles ils faut maximiser, minimiser /ou minimiser- maximiser des fonctions mono- objectives ou multi- objectives sous un ensemble de contraintes. Ce types de problèmes sont appeler fonctions Max- Min /ou Min- Max.
Ce travail aborde essentiellement la résolution des fonctions objectives Min- Max sous forme budget (investissement) / ou fiabilité de la structure a choisir sous un ensemble de contraintes de type fiabilité, budget et production des systèmes fluides à concevoir.
La tâche primordiale de ce travail consiste tout d'abord à résoudre un problème partiel qui revient à optimiser la structure des réseaux de transport haute tension et moyenne tension par la méthode des colonies de fourmis. Les résultats obtenus de ce problème partiel seront exploiter comme données au problème général.
La structure arborescente côté haute et moyenne tension du réseau considéré font l'objet d'un optimum partiel du problème traité, outre ces structures arborescentes optimales se trouvent dans un système plus complexe dit réseau électrique vue par sa taille et sa forme.
Généralement la reformulation optimale d'un tel système complexe devienne un problème de type combinatoire NP- dur. S'il s'agit de solution exacte à ces problèmes les méthodes à la recherche deviennent moins puissantes et demandent assez d'espaces et de temps, leur nature est exhaustif impossible parfois à atteindre cette solution. Alors le recours aux méthodes approchées devient nécessaire soit aux heuristiques ou aux méta- heuristique.
Généralement, le système électro- énergétique se présente sous deux principales structures :
* Structure série- parallèle : la moins rencontrée dans la pratique, exemple les systèmes de production décentralisés cas de la production photo voltaïque.
* Structure parallèle- série : la plus rencontrée dans la pratique, exemple les systèmes de production centralisés cas des réseaux électriques.
Considérons un système parallèle-
série contenant n sous-système Ci
(i=1,2,....,n) dans un arrangement série comme est illustré
dans la fig.(7-1). Chaque sous-système Ci contient
un certain nombre d'éléments ou composant connecter en
parallèle. Pour chaque sous-systèmes i, il existe
différente version des éléments
(générateurs, transformateurs et lignes) disponible dans le
marché. Pour chaque sous-système d'éléments,
différentes versions et nombre de composant peut être choisi. Pour
chaque sous-système i les éléments sont
caractérisés par leurs coûts (Civ),
fiabilité (Riv) et leurs performances
(Giv) accordés à leurs versions. La structure
du système d'éléments i peut être
définit par le nombre des éléments ou composants en
parallèle (de chaque version) kiv pour 
, ou Vi est le nombre de versions pour les
éléments de type i. La structure du système
entier est définit par les vecteurs 
. Pour un ensemble de vecteurs k1,
k2,...., kn le coût total du
système est donné par l'expression suivante :
(7-1)
Fig. (VII-1) : Schéma détaillé d'un système parallèle- série
Le problème d'optimisation d'un système multi état redondant peut être formuler comme suite: trouver la configuration / ou structure du système à coût minimale k1, k2, ..., kn qui est à un niveau de fiabilité supérieur ou égale au seuil donnée R0.
Minimiser
(7-2)
Sous Contraintes
(7-3)
Le problème d'optimisation d'un système multi état redondant peut être formuler comme suite: maximiser R d'une structure (k1, k2, ..., kn ) dont le coût soit inférieur ou égal à un certain budget donné.
Maximiser
(7-4)
Sous Contraintes
(7-5)
Ce problème englobe une fonction bi- objective à optimiser pour un système multi état redondent qu'on peut le formuler comme suite:
Trouver la configuration / ou structure du système k1, k2, ..., kn à coût minimale au même temps sa fiabilité soit maximale R sous un ensemble de contraintes.
Ces problèmes prennent le nom généralement de l'optimisation Multi- Objective. Cette méthode d'optimisation rend une utilisation souple au besoin du concepteur.
Min- Max
(7-6)
(7-7)
Sous Contraintes
(7-7)
(7-8)
Considérons un système série-
parallèle contenant n sous-système Cj
(j=1,2,....,J) dans un arrangement parallèle. Chaque
sous-système Cj contient un certain nombre
d'éléments ou composant connecter en série. Pour chaque
sous-système, différentes versions et nombres de composants peut
être choisi. Les éléments sont caractérisés
par leurs coûts (Cjv), disponibilité
(Ajv)/ ou (Rjv) et leurs performances
(Gjv) accordés à leurs versions. La structure
du système d'éléments j peut être
définit par le nombre des éléments ou composants en
série (de chaque version) kjv pour
, ou Vj est le nombre de versions pour les
éléments de type j. La fig. (7-2) illustre ces notations
par un schéma synoptique d'un sous-système j de
production. La structure du système entier est définit par les
vecteurs 
. Pour un ensemble de vecteurs k1,
k2,...., kJ le coût total du
système est donné par l'expression suivante :
(7-1)
Fig. (7-2) : Schéma synoptique d'un système série- parallèle
Le problème d'optimisation d'un système multi état redondant peut être formuler comme suite: trouver la configuration / ou structure du système à coût minimale k1, k2, ..., kn qui est à un niveau de fiabilité supérieur ou égale au seuil donnée R0 / ou A0 .
Minimiser
(7-9)
Sous Contraintes
(7-10)
Le problème d'optimisation d'un système multi état redendant peut être formuler comme suite: maximiser R d'une structure (k1, k2, ..., kn ) dont le coût soit inférieur ou égal à un certain budget donné.
Maximiser
(7-11)
Sous Contraintes
(7-12)
Ce problème englobe une fonction bi- objective à optimiser pour un système multi état redondent qu'on peut le formuler comme suite:
Trouver la configuration / ou structure du système k1, k2, ..., kn à coût minimale au même temps sa fiabilité soit maximale R .sous un ensemble de contraintes.
Ces problèmes prennent le nom généralement de l'optimisation Multi- Objective. Cette méthode d'optimisation rend une utilisation souple au besoin du concepteur.
Min- Max
(7-13)
(7-14)
Sous Contraintes
(7-14)
(7-15)
Remarque
Dans le cas d'un système binaire simple ou on utilise la méthode classique, seule l'équation qui détermine la fiabilité qui change.
*Pour un système parallèle- série :
(7-16)
*Pour un système série- parallèle :
(7-17)
Notre problème d'optimisation à résoudre c'est d'optimiser une fonction objective coût sous contrainte fiabilité. En d'autres termes il s'agit de sélectionner la meilleure combinaison des éléments de façon à minimiser le coût total toutes en respectant un niveau de fiabilité prescrit.
Les éléments peuvent être sélectionnés dans n'importe quelle combinaison d'éléments disponibles sur le marché.
Afin d'appliquer la ACO au problème de l'optimisation des systèmes série- parallèle, le problème est représenté par un graphe G = (V; E) dont les sommets correspondent aux sous-systèmes et les éléments disponibles et dont les arêtes représentent les chemins reliant les sous-systèmes à leurs éléments correspondants. A chaque arête est également associé un poids selon la qualité de la machine (fiabilité, performance et coût) à laquelle il aboutit.
Fig. (7-3) : Système électro- énergétique parallèle- série
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 au coût des éléments (les fourmis préfèrent le choix des éléments moins chères) et le taux de phéromone (expérience des autres fourmis). Cette modélisation pour nos problèmes mono- objective, bi- objective et Multi- objective prennent les formes suivantes :
(7-18)
: Représente le coût associé à la
machine 
du sous système 
.
(7-19)
(7-20)
L'algorithme est conçu de la manière suivante :
m fourmis sont initialement positionnées sur un sommet représentant un sous-système. Chaque fourmi va représenter une configuration possible du système. Cette configuration est constituée de n sous-systèmes en série, chaque sous-système i à son tour se compose de ki éléments en parallèle. Les ki éléments de chaque sous-système sont choisis dans n'importe quelle combinaison parmi les éléments disponibles. Chaque fourmi construit une solution, une fourmi placée sur le sous-système i choisie une machine j en appliquant une règle de transition d'état donnée par:
(7-21)
(7-22)
Ou :
: Représente l'importance relative de la piste de
phéromone.
: Représente l'importance relative de l'information heuristique
.
: Représente l'ensemble des éléments disponibles
pour le sous-système i.
: Nombre aléatoire entre 0 et 1.
Le paramètre 
détermine l'importance relative de l'exploitation contre
l'exploration: chaque fois qu'une fourmi sur un sous-système i
doit choisir une machine j, elle génère d'abord un
nombre aléatoire 
si 
, donc la meilleure arête est sélectionnée suivant
la relation (7-21) (exploitation), autrement une arête est choisie
suivant la relation (VII-22) (exploration biaisée ).
La mise à jour de la phéromone consiste en deux phases :
? Mise à jour local.
? Mise à jour global.
Pendant la construction d'une solution, la fourmi modifie la quantité de phéromone sur les arêtes 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 une machine donnée à son sous-système de manière à décourager la fourmi suivante de choisir la même machine durant le même cycle. La mise à jour locale est donnée par :
(7-23)
Où :
: est un coefficient de façon que 
représente l'évaporation de la trace de phéromone
et 
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
(7-24)
La solution finale c'est la meilleure solution trouvée durant tous les cycles et c'est évidemment celle qui satisfait la contrainte de la fiabilité à moindre coût.
Un programme (ANT OPTI) à été conçu pour l'optimisation des structures des systèmes séries parallèles Multi- Etats.
Cas d'une structure de production fluide {exemple industrie électro- énergétique (production, transport et distribution d'énergie électrique), industrie de recyclage de plastique, industrie électronique en chaîne ect.....}.
STEP 1:
Set NC:=0 /*{NC: Conteur de Cycle}*/.
Pour chaque arc (i,j) mettre une valeur initiale ij(0)= o /*{ Niveau de phéromone initial }*/.
STEP 2:
For k=1 to Nb{Fourmis} do /*{Nb nombre de fourmis sur le sub-system}*/.
For i=1 to NbSubSystem do
For j=1 to Mmax Composants do /*{(Mmax : Composants ou éléments le maximum technique sur un sub-système (Générateur, transformateurs ou bien lignes de transport)}*/.
Choisir un composant ou éléments, faire introduire un composant vide {blanks}, en respectant les équations de probabilité (1) et (2) .
Faire un Update Locale de la piste de phéromone pour choisir un composant du sous système arc (i,j) :
End For
End For
STEP 3:
Calculer Ak ou bien Rk /*{Fiabilité du System pour chaque fourmi}*/.
{Méthode D'Ushakov }:
For j=1 to kmax /*{kmax}: /* Nombre maximum de composant ou éléments en parallèle */.
{Appliquant les équations}:
For i=1 to n /*n: nombre de sub-système en séries */.
{Appliquant les équations}:
,
Calculer le coût total 
/* Coût de la structure ou topologie de chaque fourmis*/ .
{Appliquant l'équation}:
Faire un Update globale et sauvegarder la meilleure solution
/* Structure de la meilleure fourmi*/.
STEP 4:
Globale Update pour la piste de phéromone /* Structure de la meilleure fourmi*/
Pour chaque arc (i,j) à la meilleure solutions, Update la piste de phéromone
{Appliquant les équations}:
End For
STEP 5:
Ccycle=Ccycle +1
If {NC < NCmax} et /* comportement sans stagnation {comportement sans stagnation /*
Then
Goto step 2
Else
Imprimer et sauvegarder la meilleure solution /* structure avec composant les plus meilleure*/.
STOP.
M : nombre de fourmis
Tmax : nombre de cycles
To : phéromone initiale
Ro : Éaporation de la phéromone
E0 : Niveau de fiabilité désire
Lecture du fichier des :
Caractéristiques
Nombre de sub-systèmes, Nbre de composant Performance, Coût et Disponibilité
Détermination du :
- Nbre des sub-système
- Nbre d'éléments
ç(I,j)=1/ (1+coût[I,J]
I : sub-systeme 1..n
J : Éléments 1..Pmax
Lecture des niveaux de charge
N°, niveau de charge
Calcul de la probabilité des niveaux de charge
Sélection de l'élément selon
ou bien
e=e+1
Non
Calculer le coût et la Fiabilité
e<=Nbre d'element sub-systeme
2
Non
1
U
n système est un ensemble de processus et d'équipements pour assurer une tâche ou bien une mission. L'exploitation rationnelle du système dépend de sa configuration. Une configuration optimale évite des dépenses excessives.
L
a fonction primaire d'un système moderne d'énergie électrique est de fournir à ses clients de l'énergie électrique aussi économiquement possible avec un degré acceptable de fiabilité. Ce degré d'espérance exige une conception optimale.
D
ans le contexte d'ingénierie, le choix des équipements en fonction de leurs disponibilité, coût et performance est la variable de décision la plus importante pour optimiser un processus. Suivant la disponibilité des technologies sur le marché, la mise au point d'un algorithme itératif sera nécessaire afin d'adapter à chaque demande sa structure optimale.
L'adaptation du réseau électrique à sa charge se fait par analogie à un process industriel parallèle série tel que l'agroalimentaire. Souvent un réseau électrique (production, transport, répartition et distribution) se présente comme une configuration contenant plusieurs colonnes à composants parallèles mises en série (sous-systèmes) couplés à un model de charge comme le montre la figure suivante :
Fig. (-1) : Structure parallèle- série d'un réseau électrique
Sous-système de production : C'est la vertèbre principale du système globale réseau électrique, c'est le sous-système N°1 de l'ensemble des sous-systèmes parallèle- série. L'énergie électrique est bien née de ce berceau formé par un ensemble de générateurs de productions, ces derniers peuvent être présentés par leur nature ou version (type -fournisseur), par leurs coûts et leurs performances (puissance active ou bien apparente).On note par Gi les performances individuelles et Ci les coûts de chaque générateur formant le sous système. Le produit final de ce sous système est le Kwh. Cette dernière est transitée à un autre sous-système ou elle doit être transformée et évacuée.
Sous-système de transformation : Généralement, le sous-système générateurs fonctionne sons une tension comprise entre 3-20 Kv, alors transporter cette énergie nécessite une transformation MT/HT. Ces transformateurs fonctionnant parallèlement sont supposés à pertes nulles. Ce sous-système englobe un ensemble de transformateurs hétérogène (performance, version et coût différents).
Sous-système des transport : Fait à la base d'une configuration arborescente dont le niveau de tension est le même. Alors ces lignes sont placées en parallèle et serrent à transiter l'énergie du point amont vers le point aval.
Sous-système de transformation : Ce sous-système est formé d'un ensemble de transformateurs placés en parallèle dont la capacité ou bien la performance totale est la somme des performances des différentes versions et types des transformateurs, la caractéristique qui change est le niveau de tension HT/MT.
Sous-système des transport : Le sous-système de transport est généralement fait à base de lignes moyenne tension qui alimentent des clients moyenne tension .Les configurations sont toujours arborescentes. Ces lignes sont placées en parallèle.
Fig. (-2) : Sous système de transport
En vue d'une optimisation globale, une optimisation partielle est nécessaire. Cette dernière concerne l'optimisation des réseaux de transport haute tension et moyenne tension par la méthode des colonies de fourmis. Le résultat de l'optimisation partielle sur les réseaux haute et moyenne tension nous conduit à des configurations arborescentes optimales.
Les résultats obtenus font l'objet d'un optimum partiel appartenant aux données du problème global à traité, alors ces deux réseaux optimaux se trouvent dans un système plus complexe de type problème combinatoire à redondance d'allocation optimale. Ce problème sera considéré comme problème de types RAP (problème d'allocation de redondance). Leurs solutions exactes fait intervenir des méthodes combinatoires ou des méta- heuristiques.
Le tableau suivant montre les caractéristiques de production du réseau de transport HT.
TABLEAU 8-1
CARACTÉRISTIQUES DE LA PRODUCTION HAUTE TENSION
|
N° de la charge |
Cordonnées Cartésiennes x y |
Taux De Production |
100% DE LA Production 800 MW |
|
1 |
50 50 |
25 % 200 |
|
|
2 |
150 320 |
25 % 200 |
|
|
3 |
300 100 |
25 % 200 |
|
|
4 |
350 200 |
25 % 200 |
Le tableau suivant montre les caractéristiques de la charge du réseau de transport HT.
TABLEAU 8-2
CARACTÉRISTIQUES DE LA CHARGE HAUTE TENSION
|
N° de la charge |
Cordonnées Cartésiennes x y |
Taux de Durée |
Taux |
100% DE LA CHARGE 800 MW |
|
5 |
130 170 |
4380 |
30 400 |
|
|
6 |
100 250 |
1095 |
40 400 |
Le tableau suivant montre les caractéristiques de production du réseau de transport MT.
TABLEAU 8-3
CARACTÉRISTIQUES DE LA PRODUCTION MOYENNE TENSION
|
N° de la charge |
Cordonnées Cartésiennes x y |
Taux De Production |
100% DE LA Production 600 MW |
|
1 |
50 50 |
33 200 |
|
|
2 |
150 320 |
16 100 |
|
|
3 |
300 100 |
33 200 |
|
|
4 |
350 200 |
16 100 |
Le tableau suivant montre les caractéristiques de la charge du réseau de transport MT.
|
N° de la charge |
Cordonnées Cartésiennes x y |
Taux de Durée |
Taux |
100% DE LA CHARGE 600 MW |
|
5 |
50 150 |
1560 |
20 120 |
|
|
6 |
100 250 |
1560 |
10 60 |
|
|
7 |
400 300 |
2340 |
30 180 |
|
|
8 |
250 25 |
20 120 |
||
|
9 |
150 125 |
20 120 |
TABLEAU 8-4
CARACTÉRISTIQUES DE LA CHARGE MOYENNE TENSION
Les chemins (les lignes HT) qui forment l'arbre optimal sont :
Cette structure est obtenue par la méthode des colonies de fourmis, elle représente une structure d'un réseau de sept noeuds dont quatre producteurs et trois consommateurs. Cette structure optimale concerne le réseau de répartition HT qui consomme 20% de la charge totale.
Cette interface montre la topologie du réseau de transport haute tension dont on peut avoir un ensemble de paramètres géométriques et électriques.
Le tableau suivant montre les résultats de calcul de la performance (puissance active, réactive et puissance apparente) sur les lignes HT.
TABLEAU 8-5
PARAMÈTRES DU RÉGIME ET DU RÉGIME DE FONCTIONNEMENT
|
Paramètres du régime |
Cuivre |
Aluminium |
||||||||
|
Arc |
Pij |
Qij |
Iij |
Psij |
Sij |
Rij |
R0ij |
Sij |
Rij |
R0ij |
|
1->5 2->4 2->6 3->4 5->6 |
-200 400 -600 -200 200 |
149.9 299.9 449.9 149.9 149.9 |
656.07 1312.1 1968.2 656.07 656.07 |
249.99 499.99 750.0 249.99 249.99 |
546.73 1093.4 1640.1 546.73 546.73 |
0.3353 0.1676 0.1117 0.3353 0.3353 |
0.0012 7.8683 0.0021 0.0016 0.0021 |
385.92 771.85 1157.7 385.92 385.92 |
0.3353 0.1676 0.1117 0.3353 0.3353 |
8.9869 5.5541 0.0015 0.0011 0.0015 |
Les chemins (les lignes MT) qui forment l'arbre optimal sont :
Cette structure est obtenue par la méthode des colonies de fourmis, elle représente une structure d'un réseau de sept noeuds dont quatre producteurs et trois consommateurs. Cette structure optimale concerne le réseau de répartition MT qui consomme 80% de la charge totale.
Cette interface montre la topologie du réseau de moyenne tension dont on peut avoir un ensemble de paramètres géométriques et électriques.
Le tableau suivant montre les résultats de calcul de la performance (puissance active, réactive et puissance apparente) sur les lignes MT.
TABLEAU 8-6
PARAMÈTRES DU RÉGIME ET DU RÉGIME DE FONCTIONNEMENT
|
Paramètres du régime |
Cuivre |
Aluminium |
||||||||
|
Arc |
Pij |
Qij |
Iij |
Psij |
Sij |
Rij |
R0ij |
Sij |
Rij |
R0ij |
|
1->3 2->4 2->6 3->4 3->8 5->9 6->9 7->8 |
-200 -100 -100 100 -300 -80 40 180 |
149.9 74.99 74.99 74.99 224.9 59.99 29.99 134.9 |
656.07 328.03 328.03 328.03 984.11 262.43 131.21 590.47 |
249.99 124.99 124.99 124.99 375.0 100.0 50.0 225.0 |
546.73 273.36 273.36 273.36 820.09 218.69 109.34 492.05 |
0.3353 0.6706 0.6706 0.6706 0.2235 0.8383 1.6766 0.3725 |
0.0018 7.8683 0.0021 0.0016 0.0020 0.0017 0.0013 5.8572 |
385.92 192.96 192.96 192.96 578.89 154.89 77.185 347.33 |
0.3353 0.6706 0.6706 0.6706 0.2235 0.8383 1.6766 0.3725 |
0.0012 5.5541 0.0015 0.0011 0.0014 0.0012 9.6575 4.1345 |
Partant de la matière brute (fioul charbon, mazout, nucléaire pour une centrale thermique), production de l'électricité dans la 1ère colonne (Sous Système 1).
Ce produit final se caractérise par les paramètres de mesure capacité ou performance (puissances actives P réactives Q apparente S ou bien par intensité de courant I) sous une tension moyenne U qui tends vers 20-30 kV au bornes des composants de cette colonne qui sont les générateurs. Ensuite, l'énergie électrique passe à la 2ème Colonne (Sous Système 2) ou une transformation est subite par un ensemble de transformateurs MT/HT mis en parallèle, cette contrainte en tension est primordiale au transport.
Après transformation, le produit passe à la 3ème Colonne (Sous Système 3) ou il est transporté à haute tension par les lignes haute tension, un maillage de la structure est formé par ces lignes de transport raccorder sur un ensemble de noeuds producteurs et consommateurs. Les opérations dans ce maillage sont à double rôle transport et distribution. Après transport et distribution, une seconde transformation doit être subie par une 4ème Colonne (Sous Système 4) qui renferme un ensemble de transformateurs HT/MT, ensuite un autre transport s'effectue à la base d'un maillage de lignes MT irrigant un ensemble de noeuds consommateurs.
Ces lignes sont au même potentiel, alors elles se comportent comme des lignes parallèles et cela s'effectue par la dernière colonne qui est la 5ème Colonne (Sous Système 5). Les figures (8-4) et (8-5) montrent le détail et le synoptique du système série parallèle de production transport et répartition du produit dans le système électro-énergétique.
Fig. (8-3) : Schéma du réseau électrique parallèle- série
Fig. (8-4) : Schéma synoptique du réseau électrique parallèle- série
La structure du parc réseau électrique, fait intervenir les colonnes (sous-systèmes) suivantes pour exécuter l'ensemble des phases concernant la production transformation répartition et distribution d'énergie. Ces colonnes sont illustrées ci-dessous:
Gi : Représente la performance ou bien la capacité en % de la puissance totale.
pi : Représente la fiabilité de l'élément considéré en %.
Ci : Représente le coût en % de l'investissement sur chaque colonne (sou système).
1-Colonne {1} représente le sous-système 1 (production d'énergie) qui comprend quatre (04) générateurs de puissance de 4. 200 Mw.
|
1 |
2 |
3 |
4 |
|
|
Gi % |
100 |
98 |
95 |
120 |
|
Pi % |
89.9 |
99.7 |
78 |
79.7 |
|
Ci % |
45 |
115 |
2.5 |
15 |
2-Colonne {2} représente le sous-système 2 (Colonne de transformation d'énergie. Les transformateurs MT / HT qui comporte quatre (04) transformateurs :
|
1 |
2 |
3 |
4 |
|
|
Gi % |
100 |
97 |
99 |
80 |
|
Pi % |
89.9 |
96 |
69.7 |
89.7 |
|
Ci % |
140 |
215.6 |
30 |
74 |
3-Colonne {3} représente le sous-système 3 (Colonne des lignes de transport HT) qui comporte cinq (05) lignes.
|
1 |
2 |
3 |
4 |
5 |
|
|
Gi % |
100 |
100 |
98 |
100 |
120 |
|
Pi % |
78 |
79.8 |
98 |
79.8 |
89.8 |
|
Ci % |
21 |
32 |
50 |
21 |
80.1 |
4-Colonne {4} représente le Sous-système 4 (Colonne des transformateurs HT/MT) qui comporte trois (04) transformateurs.
|
1 |
2 |
3 |
4 |
|
|
Gi % |
96 |
98 |
100 |
100 |
|
Pi % |
97 |
79.7 |
98 |
89.5 |
|
Ci % |
39 |
75 |
120 |
25 |
5-Colonne {5} représente le sous-système 5 (Colonne des lignes MT) qui comporte sept (07) lignes.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
Gi % |
98 |
100 |
95 |
90 |
100 |
96 |
85 |
|
Pi % |
95 |
89.5 |
79.5 |
65 |
85 |
89.8 |
79.9 |
|
Ci % |
41.5 |
210 |
10 |
61 |
81 |
99 |
110 |
Le tableau (8-7) pressente les caractéristiques des composants ou éléments prédisposés pour la conception d'un design pour le système réseau de répartition. Ces caractéristiques varient en forme et taille pour chaque composants (Type qui la version k et la performance ou capacité G) ainsi sur leurs prix C et fiabilité P ou disponibilité A.
TABLEAU 8-7
CARACTÉRISTIQUES DES ÉLÉMENTS PRÉDISPOSÉS
|
Technologie # |
||||||||||||
|
Sous- Systèmes # |
Composants |
# 1 |
# 2 |
# 3 |
# 4 |
# 5 |
# 6 |
# 7 |
||||
|
Générateurs 1 |
fiabilité |
0.898 |
0.997 |
0.780 |
0.797 |
/ |
/ |
/ |
||||
|
coût |
0.45 |
1.15 |
0.025 |
0.15 |
/ |
/ |
/ |
|||||
|
performance |
100 |
98 |
95 |
120 |
/ |
/ |
/ |
|||||
|
Transformateurs 2 |
fiabilité |
0.898 |
0.96 |
0.697 |
0.897 |
/ |
/ |
/ |
||||
|
coût |
1.4 |
2.156 |
0.3 |
0.74 |
/ |
/ |
/ |
|||||
|
performance |
100 |
97 |
99 |
80 |
/ |
/ |
/ |
|||||
|
Lignes HT 3 |
fiabilité |
0.78 |
0.798 |
0.98 |
0.798 |
0.898 |
/ |
/ |
||||
|
coût |
0.21 |
0.32 |
0.5 |
0.21 |
0.801 |
/ |
/ |
|||||
|
performance |
100 |
100 |
98 |
100 |
120 |
/ |
/ |
|||||
|
Transformateurs 4 |
fiabilité |
0.97 |
0.797 |
0.98 |
0.895 |
/ |
/ |
/ |
||||
|
coût |
0.39 |
0.75 |
1.2 |
0.25 |
/ |
/ |
/ |
|||||
|
performance |
96 |
98 |
100 |
100 |
/ |
/ |
/ |
|||||
|
Lignes MT 5 |
fiabilité |
0.95 |
0.895 |
0.795 |
0.65 |
0.85 |
0.898 |
0.799 |
||||
|
coût |
0.415 |
2.1 |
0.1 |
0.61 |
0.81 |
0.99 |
1.1 |
|||||
|
performance |
98 |
100 |
95 |
90 |
100 |
96 |
85 |
|||||
La demande de la clientes HT et MT qui représentent les 20% en HT et 80% en MT pour l'année en cours est estimée à une puissance de 800 Mw sur le réseau électrique. Cette demande est estimée sur la base annuelle de 8760 h. La demande est de 100 % pour un pic annuel de valeur semestrielle qui se réduit à 75% pendant un trimestre ainsi la réduction se suit de 50 et 25% pendant les deux autres trimestres restants. Le tableau (8-8) illustre cette demande cumulative.
TABLEAU 8-8
DONNÉES DE LA DEMANDE CUMULATIVE ANNUELLE
|
Niveau de demande (%) |
100 |
75 |
50 |
25 |
|
Durée (h) |
4380 |
1095 |
1095 |
1095 |
|
Probabilité (%) |
50 |
12.5 |
12.5 |
12.5 |
Pour analyser au mieux l'application de notre programme ACF sur la robustesse et l'efficacité, nous allons tester ce programme d'optimisation par une variation des caractéristiques touchant profondément le Coût et la Fiabilité par deux autres tests par rapport au système de référence (système analyser) et un troisième test touchera la variation de ces deux variables (Coût et Fiabilité).
TABLEAU 8-9
CARACTÉRISTIQUES DES ÉLÉMENTS PRÉDISPOSÉS
|
Technologie # |
||||||||||||
|
Sous- Systèmes # |
Composants |
# 1 |
# 2 |
# 3 |
# 4 |
# 5 |
# 6 |
# 7 |
||||
|
Générateurs 1 |
fiabilité |
0.898 |
0.997 |
0.780 |
0.797 |
/ |
/ |
/ |
||||
|
coût |
0.100 |
0.95 |
0.44 |
1.23 |
/ |
/ |
/ |
|||||
|
performance |
100 |
98 |
95 |
120 |
/ |
/ |
/ |
|||||
|
Transformateurs 2 |
fiabilité |
0.898 |
0.96 |
0.697 |
0.897 |
/ |
/ |
/ |
||||
|
coût |
0.82 |
1.09 |
0.5 |
2.15 |
/ |
/ |
/ |
|||||
|
Performance |
100 |
97 |
99 |
80 |
/ |
/ |
/ |
|||||
|
Lignes HT 3 |
fiabilité |
0.78 |
0.798 |
0.98 |
0.798 |
0.898 |
/ |
/ |
||||
|
coût |
0.18 |
2.09 |
1.1 |
0.59 |
0.3 |
/ |
/ |
|||||
|
performance |
100 |
100 |
98 |
100 |
120 |
/ |
/ |
|||||
|
Transformateurs 4 |
fiabilité |
0.97 |
0.797 |
0.98 |
0.895 |
/ |
/ |
/ |
||||
|
coût |
1.55 |
1.2 |
0.73 |
0.29 |
/ |
/ |
/ |
|||||
|
performance |
96 |
98 |
100 |
100 |
/ |
/ |
/ |
|||||
|
Lignes MT 5 |
fiabilité |
0.95 |
0.895 |
0.795 |
0.65 |
0.85 |
0.898 |
0.799 |
||||
|
coût |
1.135 |
1.25 |
0.734 |
0.23 |
0.645 |
0.971 |
2.09 |
|||||
|
performance |
98 |
100 |
95 |
90 |
100 |
96 |
85 |
|||||
TABLEAU 8-10
CARACTÉRISTIQUES DES ÉLÉMENTS PRÉDISPOSÉS
|
Technologie # |
||||||||||||
|
Sous- Systèmes # |
Composants |
# 1 |
# 2 |
# 3 |
# 4 |
# 5 |
# 6 |
# 7 |
||||
|
Générateurs 1 |
fiabilité |
0.811 |
0.567 |
0.75 |
0.843 |
/ |
/ |
/ |
||||
|
coût |
0.45 |
1.15 |
0.025 |
0.15 |
/ |
/ |
/ |
|||||
|
performance |
100 |
98 |
95 |
120 |
/ |
/ |
/ |
|||||
|
Transformateurs 2 |
fiabilité |
0.676 |
0.95 |
0.84 |
0.965 |
/ |
/ |
/ |
||||
|
coût |
1.4 |
2.156 |
0.3 |
0.74 |
/ |
/ |
/ |
|||||
|
performance |
100 |
97 |
99 |
80 |
/ |
/ |
/ |
|||||
|
Lignes HT 3 |
fiabilité |
0.551 |
0.98 |
0.828 |
0.972 |
0.587 |
/ |
/ |
||||
|
coût |
0.21 |
0.32 |
0.5 |
0.21 |
0.801 |
/ |
/ |
|||||
|
performance |
100 |
100 |
98 |
100 |
120 |
/ |
/ |
|||||
|
Transformateurs 4 |
fiabilité |
0.991 |
0.815 |
0.83 |
0.7 |
/ |
/ |
/ |
||||
|
coût |
0.39 |
0.75 |
1.2 |
0.25 |
/ |
/ |
/ |
|||||
|
performance |
96 |
98 |
100 |
100 |
/ |
/ |
/ |
|||||
|
Lignes MT 5 |
fiabilité |
0.828 |
0.733 |
0.921 |
0.751 |
0.634 |
0.544 |
0.589 |
||||
|
coût |
0.415 |
2.1 |
0.1 |
0.61 |
0.81 |
0.99 |
1.1 |
|||||
|
performance |
98 |
100 |
95 |
90 |
100 |
96 |
85 |
|||||
TABLEAU 8-11
CARACTÉRISTIQUES DES ÉLÉMENTS PRÉDISPOSÉS
|
Technologie # |
||||||||||||
|
Sous- Systèmes # |
Composants |
# 1 |
# 2 |
# 3 |
# 4 |
# 5 |
# 6 |
# 7 |
||||
|
Générateurs 1 |
fiabilité |
0.811 |
0.567 |
0.75 |
0.843 |
/ |
/ |
/ |
||||
|
coût |
0.100 |
0.95 |
0.44 |
1.23 |
/ |
/ |
/ |
|||||
|
performance |
100 |
98 |
95 |
120 |
/ |
/ |
/ |
|||||
|
Transformateurs 2 |
fiabilité |
0.676 |
0.95 |
0.84 |
0.965 |
/ |
/ |
/ |
||||
|
coût |
0.82 |
1.09 |
0.5 |
2.15 |
/ |
/ |
/ |
|||||
|
performance |
100 |
97 |
99 |
80 |
/ |
/ |
/ |
|||||
|
Lignes HT 3 |
fiabilité |
0.551 |
0.98 |
0.828 |
0.972 |
0.587 |
/ |
/ |
||||
|
coût |
0.18 |
2.09 |
1.1 |
0.59 |
0.3 |
/ |
/ |
|||||
|
performance |
100 |
100 |
98 |
100 |
120 |
/ |
/ |
|||||
|
Transformateurs 4 |
fiabilité |
0.991 |
0.815 |
0.83 |
0.7 |
/ |
/ |
/ |
||||
|
coût |
1.55 |
1.2 |
0.73 |
0.29 |
/ |
/ |
/ |
|||||
|
performance |
96 |
98 |
100 |
100 |
/ |
/ |
/ |
|||||
|
Lignes MT 5 |
fiabilité |
0.828 |
0.733 |
0.921 |
0.751 |
0.634 |
0.544 |
0.589 |
||||
|
coût |
1.135 |
1.25 |
0.734 |
0.23 |
0.645 |
0.971 |
2.09 |
|||||
|
performance |
98 |
100 |
95 |
90 |
100 |
96 |
85 |
|||||
TABLEAU 8-12
SOLUTION OPTIMALE DES STRUCTURES AVEC DIFFÉRENTES CONTRAINTES DE FIABILITÉ
|
Contrainte de fiabilité R0 |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
fourmi |
|
85 |
Sub Système 1 : 4(3) Sub Système 2 : 4(3) Sub Système 3 : 3(1)-2(4) Sub Système 4 : 4(4) Sub Système 5 : 7(3) |
0.93678 |
8.4 |
441 |
7 |
|
99 |
Sub Système 1 : 3(3)-1(4) Sub Système 2 : 1(1)-3(3) Sub Système 3 : 2(1)-1(3)-2(4) Sub Système 4 : 4(4) Sub Système 5 : 7(3) |
0.97358 |
5.5649 |
8 |
4 |
|
99 |
Sub Système 1 : 1(1)-1(2)-2(3) Sub Système 2 : 1(2)-2(3)-1(4) Sub Système 3 : 2(1)-2(4)-1(5) Sub Système 4 : 1(1)-1(3)-2(4) Sub Système 5 : 1(1)-4(3)-1(5)-1(6) |
0.99011 |
11.4919 |
6 |
2 |
TABLEAU 8-13
SOLUTION OPTIMALE DES STRUCTURES AVEC DIFFÉRENTES CONTRAINTES DE FIABILITÉ
|
Contrainte de fiabilité R0 |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
Fourmi |
|
85 |
Sub Système 1 : 4(1) Sub Système 2 : 4(3) Sub Système 3 : 5(1) Sub Système 4 : 4(4) Sub Système 5 : 7(4) |
0.94932 |
6.07 |
445 |
8 |
|
97 |
Sub Système 1 : 4(1) Sub Système 2 : 1(1)-3(3) Sub Système 3 : 5(1) Sub Système 4 : 4(4) Sub Système 5 : 7(4) |
0.98246 |
6.39 |
438 |
0 |
|
99 |
Sub Système 1 : 3(1)-1(3) Sub Système 2 : 1(1)-1(2)-2(3) Sub Système 3 : 3(1)-1(4)-1(5) Sub Système 4 : 4(4) Sub Système 5 : 6(4)-1(6) |
0.99155 |
8.591 |
6 |
7 |
TABLEAU 8-14
SOLUTION OPTIMALE DES STRUCTURES AVEC DIFFÉRENTES CONTRAINTES DE FIABILITÉ
|
Contrainte de fiabilité R0 |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
Cycle |
Fourmi |
|
85 |
Sub Système 1 : 4(3) Sub Système 2 : 4(3) Sub Système 3 : 3(1)-2(4) Sub Système 4 : 4(4) Sub Système 5 : 7(3) |
0.95876 |
4.05 |
441 |
7 |
|
97 |
Sub Système 1 : 3(3)-1(4) Sub Système 2 : 4(3) Sub Système 3 : 2(1)-2(4)-1(5) Sub Système 4 : 4(4) Sub Système 5 : 7(3) |
0.97184 |
4.7659 |
19 |
1 |
|
99 |
Sub Système 1 : 1(1)-1(3)-2(4) Sub Système 2 : 1(1)-2(3)-1(4) Sub Système 3 : 1(1)-2(2)-1(3)-1(4) Sub Système 4 : 2(1)-1(2)-1(4) Sub Système 5 : 1(1)-1(2)-3(3)-1(4)-1(7) |
0.99105 |
11.3799 |
6 |
1 |
TABLEAU 8-15
SOLUTION OPTIMALE DES STRUCTURES AVEC DIFFÉRENTES CONTRAINTES DE FIABILITÉ
|
Contrainte de fiabilité R0 |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
Cycle |
fourmi |
|
85 |
Sub Système 1 : 4(1) Sub Système 2 : 4(3) Sub Système 3 : 5(1) Sub Système 4 : 4(4) Sub Système 5 : 7(4) |
0.96485 |
6.07 |
445 |
8 |
|
97 |
Sub Système 1 : 4(1) Sub Système 2 : 1(1)-1(2)-2(3) Sub Système 3 : 4(1)-1(5) Sub Système 4 : 1(3)-3(4) Sub Système 5 : 7(4) |
0.97066 |
7.54 |
445 |
3 |
|
99 |
Sub Système 1 : 3(1)-1(4) Sub Système 2 : 1(1)-(2)-1(3)-1(4) Sub Système 3 : 1(1)-1(3)-1(4)-2(5) Sub Système 4 : 1(3)-3(4) Sub Système 5 : 1(1)-1(3)-3(4)-1(5)-1(7) |
0.99037 |
15.454 |
5 |
4 |
TABLEAU 8-16
SOLUTION OPTIMALE DES STRUCTURES AVEC CONTRAINTE DU COÛT
|
Contrainte du coût d'investissement en % |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
fourmi |
|
10 |
Sub Système 1 : 1(1)-2(3)-1(4) Sub Système 2 : 1(2)-2(3)-1(4) Sub Système 3 : 1(1)-2(2)-1(3)-1(4) Sub Système 4 : 2(1)-2(4) Sub Système 5 : 1(1)-4(3)-1(5)-1(7) |
0.98725 |
9.7109 |
9 |
8 |
|
15 |
Sub Système 1 : 1(1)-1(2)-1(3)-1(4) Sub Système 2 : 1(1)-1(2)-1(3)-1(4) Sub Système 3 : 1(1)-1(2)-1(3)-1(4)-1(5) Sub Système 4 : 1(1)-1(2)-1(3)-1(4) Sub Système 5 : 2(1)-2(3)-1(4)-1(5)-1(6) |
0.99483 |
14.4419 |
6 |
7 |
|
20 |
Sub Système 1 : 1(1)-1(2)-1(3)-1(4) Sub Système 2 : 1(1)-1(2)-1(3)-1(4) Sub Système 3 : 2(1)-1(2)-1(4)-1(5) Sub Système 4 : 1(1)-1(2)-1(3)-1(4) Sub Système 5 : 1(1)-1(2)-1(3)-1(4)-1(5)-1(6)-1(7) |
0.995067 |
16.837 |
4 |
4 |
TABLEAU 8-17
SOLUTION OPTIMALE DES STRUCTURES AVEC CONTRAINTE DU COÛT
|
Contrainte du coût d'investissement en % |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
fourmi |
|
10 |
Sub Système 1 : 4(1) Sub Système 2 : 1(1)-3(3) Sub Système 3 : 4(1)-1(5) Sub Système 4 : 1(3)-3(4) Sub Système 5 : 6(4)-1(5) |
0.985676 |
7.365 |
15 |
4 |
|
15 |
Sub Système 1 : 3(3)-1(3) Sub Système 2 : 1(1)-1(2)-1(3)-1(4) Sub Système 3 : 2(1)-1(3)-1(4)-1(5) Sub Système 4 : 1(3)-3(4) Sub Système 5 : 1(1)-1(3)-5(4) |
0.995713 |
12.269 |
14 |
6 |
|
20 |
Sub Système 1 : 2(1)-1(3)-1(4) Sub Système 2 : 2(1)-1(2)-1(3) Sub Système 3 : 2(1)-1(2)-1(4)-1(5) Sub Système 4 : 1(1)-1(2)-1(3)-1(4) Sub Système 5 : 1(1)-1(3)-3(4)-1(5)-1(6) |
0.996467 |
16.385 |
10 |
1 |
TABLEAU 8-18
SOLUTION OPTIMALE DES STRUCTURES AVEC CONTRAINTE DU COÛT
|
Contrainte du cout d'investissement en % |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
fourmi |
|
10 |
Sub Système 1 : 1(2)-1(3)-2(4) Sub Système 2 : 3(3)-1(4) Sub Système 3 : 1(1)-1(2)-1(3)-2(4) Sub Système 4 : 2(1)-1(2)-1(4) Sub Système 5 : 1(1)-3(3)-1(4)-1(5)-1(7) |
0.988172 |
9.5799 |
7 |
1 |
|
15 |
Sub Système 1 : 1(1)-1(3)-2(4) Sub Système 2 : 1(1)-1(3)-2(4) Sub Système 3 : 1(1)-1(2)-1(3)-1(4)-1(5) Sub Système 4 : 2(1)-1(2)-1(4) Sub Système 5 : 1(1)-2(3)-1(4)-1(5)-1(6)-1(7) |
0.9944 |
11.9 |
0 |
2 |
|
20 |
Sub Système 1 : 1(1)-1(3)-2(4) Sub Système 2 : 1(2)-2(3)-1(4) Sub Système 3 : 1(1)-1(2)-1(3)-1(4)-1(5) Sub Système 4 : 2(1)-1(2)-1(4) Sub Système 5 : 1(1)-2(3)-1(4)-1(5)-1(6)-1(7) |
0.9944 |
11.9 |
0 |
2 |
TABLEAU 8-19
SOLUTION OPTIMALE DES STRUCTURES AVEC CONTRAINTE DU COÛT
|
Contrainte du coût d'investissement en % |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
fourmi |
|
10 |
Sub Système 1 : 4(1) Sub Système 2 : 4(3) Sub Système 3 : 4(1)-1(4) Sub Système 4 : 4(4) Sub Système 5 : 7(4) |
0.98167 |
6.48 |
11 |
8 |
|
15 |
Sub Système 1 : 4(1) Sub Système 2 : 1(1)-1(2)-1(3)-1(4) Sub Système 3 : 2(1)-1(2)-1(3)-1(5) Sub Système 4 : 4(4) Sub Système 5 : 7(4) |
0.98672 |
11.5799 |
11 |
0 |
|
20 |
Sub Système 1 : 2(1)-1(3)-1(4) Sub Système 2 : 1(2)-2(3)-1(4) Sub Système 3 : 2(1)-1(4)-2(5) Sub Système 4 : 1(1)-1(2)-1(3)-1(4) Sub Système 5 : 1(2)-1(3)-2(4)-1(5)-1(6)-1(7) |
0.98869 |
17.58 |
7 |
8 |
TABLEAU 8-20
SOLUTION OPTIMALE DES STRUCTURES AVEC DIFFÉRENTES CONTRAINTES DE FIABILITÉ ET DU COÛT
|
Contraintes de fiabilité R0, et du coût d'investissement en % (Mln DA) |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
fourmi |
|
85 10 |
Sub Système 1 : 1(1)-2(3)-1(4) Sub Système 2 : 3(3)-1(4) Sub Système 3 : 1(1)-1(2)-1(3)-2(4) Sub Système 4 : 1(1)-1(2)-2(4) Sub Système 5 : 2(1)-3(3)-1(4)-1(5) |
0.96938 |
7.93 |
0 |
1 |
|
97 15 |
Sub Système 1 : 1(1)-1(2)-1(3)-1(4) Sub Système 2 : 1(1)-1(2)-1(3)-1(4) Sub Système 3 : 1(1)-1(2)-1(3)-1(4)-1(5) Sub Système 4 : 1(1)-1(2)-1(3)-1(4) Sub Système 5 : 2(1)-2(3)-1(4)-1(5)-1(6) |
0.99483 |
14.442 |
391 |
1 |
|
99 20 |
Sub Système 1 : 2(1)-1(3)-1(4) Sub Système 2 : 1(1)-1(2)-1(3)-1(4) Sub Système 3 : 1(1)-1(2)-1(3)-1(4)-1(5) Sub Système 4 : 1(1)-1(2)-1(3)-1(4) Sub Système 5 : 1(1)-1(2)-1(3)-1(4)-1(5)-1(6)-1(7) |
0.99578 |
16.427 |
192 |
3 |
TABLEAU 8-21
SOLUTION OPTIMALE DES STRUCTURES AVEC DIFFÉRENTES CONTRAINTES DE FIABILITÉ
|
Contrainte de fiabilité R0 et du coût d'investissement en % |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
fourmi |
|
85 10 |
Sub Système 1 : 4(1) Sub Système 2 : 4(3) Sub Système 3 : 5(1) Sub Système 4 : 4(4) Sub Système 5 : 7(4) |
0.94932 |
6.07 |
0 |
0 |
|
97 15 |
Sub Système 1 : 3(1)-1(3) Sub Système 2 : 1(1)-1(2)-2(3) Sub Système 3 : 2(1)-1(4)-2(5) Sub Système 4 : 1(3)-3(4) Sub Système 5 : 1(3)-3(4)-2(5)-1(6) |
0.99353 |
10.485 |
0 |
1 |
|
99 20 |
Sub Système 1 : 2(1)-1(3)-1(4) Sub Système 2 : 2(1)-1(2)-1(3) Sub Système 3 : 1(1)-1(2)-1(4)-2(5) Sub Système 4 : 1(1)-1(2)-1(3)-1(4) Sub Système 5 : 1(1)-1(2)-1(3)-1(4)-1(5)-1(6)-1(7) |
0.99668 |
19.385 |
35 |
2 |
TABLEAU 8-22
SOLUTION OPTIMALE DES STRUCTURES AVEC DIFFÉRENTES CONTRAINTES DE FIABILITÉ
|
Contrainte de fiabilité R0 et du coût d'investissement en % |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
fourmi |
|
85 10 |
Sub Système 1 : 1(1)-2(3)-1(4) Sub Système 2 : 3(3)-1(4) Sub Système 3 : 1(1)-1(2)-1(3)-2(4) Sub Système 4 : 1(1)-1(2)-2(4) Sub Système 5 : 2(1)-3(3)-1(4)-1(5) |
0.98144 |
7.93 |
0 |
1 |
|
97 15 |
Sub Système 1 : 1(1)-1(3)-2(4) Sub Système 2 : 1(2)-2(3)-1(4) Sub Système 3 : 1(1)-1(2)-1(3)-1(4)-1(5) Sub Système 4 : 2(1)-1(2)-1(4) Sub Système 5 : 1(1)-1(2)-1(3)-1(4)-1(5)-1(6)-1(7) |
0.99463 |
14.217 |
445 |
4 |
|
99 20 |
Sub Système 1 : 1(1)-1(3)-2(4) Sub Système 2 : 1(2)-2(3)-1(4) Sub Système 3 : 1(1)-1(2)-1(3)-1(4)-1(5) Sub Système 4 : 2(1)-1(2)-1(4) Sub Système 5 : 1(1)-1(2)-1(3)-1(4)-1(5)-1(6)-1(7) |
0.99463 |
14.217 |
445 |
4 |
TABLEAU 8-23
SOLUTION OPTIMALE DES STRUCTURES AVEC DIFFÉRENTES CONTRAINTES DE FIABILITÉ
|
Contrainte de fiabilité R0 et du coût d'investissement en % |
Meilleures configurations |
Fiabilité Calculer R en % |
Coût d'investissement en % (Mln DA) |
cycle |
fourmi |
|
85 10 |
Sub Système 1 : 4(1) Sub Système 2 : 4(3) Sub Système 3 : 5(1) Sub Système 4 : 4(4) Sub Système 5 : 7(4) |
0.96485 |
6.07 |
0 |
0 |
|
97 15 |
Sub Système 1 : 3(1)-1(3) Sub Système 2 : 1(1)-1(2)-2(3) Sub Système 3 : 2(1)-1(4)-2(5) Sub Système 4 : 1(3)-3(4) Sub Système 5 : 1(3)-3(4)-2(5)-1(6) |
0.9833 |
10.485 |
0 |
1 |
|
99 20 |
Sub Système 1 : 2(1)-1(3)-1(4) Sub Système 2 : 1(1)-1(2)-1(3)-1(4) Sub Système 3 : 2(1)-1(2)-1(4)-1(5) Sub Système 4 : 1(1)-1(2)-1(3)-1(4) Sub Système 5 : 1(1)-1(2)-1(3)-2(4)-1(5)-1(6) |
0.98903 |
18.735 |
395 |
8 |
Le tableau 8-12 récapitule les résultats obtenus par les colonies de fourmis pour les seuils de fiabilité, 0.85, 0.97 et 0.99.
On constate qu'en augmentant la fiabilité, le coût augmente. Donc pour avoir une meilleure fiabilité il faut investir plus.
Pour un niveau de fiabilité très important de 0.99, le coût est important 11.4919. Alors que pour un niveau de fiabilité de 0.97, le coût est réduit de moitié 5.5649.
Vue que notre but est d'obtenir une bonne fiabilité à moindre coût, la meilleure configuration est celle de la contrainte de fiabilité de 0.97.
Les résultats obtenus seront une référence pour les prochains tests.
On vari le coût et on garde la même fiabilité et performance du problème de référence, et on compile pour les mêmes contraintes de fiabilité soit 0.85, 0.97 et 0.99.
On a obtenu trois configurations différentes comme solution pour les trois seuils de fiabilité.
Le coût a diminué pour les trois contraintes de fiabilité pour une augmentation de la fiabilité par rapport à la référence. Les écarts obtenus montre l'influence du coût dans le choix de la structure adéquate par les agents fourmis.
On vari la fiabilité et on garde les même valeurs du coût et de la performance du problème de référence, et on compile pour les mêmes contraintes de fiabilité soit 0.85, 0.97 et 0.99.
La fiabilité a augmenté et le coût a nettement diminué rapport aux résultats de la référence.
La structure la moins chère est pour le niveau 85%, et la plus chère est celle de 99%.
On vari la fiabilité et le coût et on garde seulement les valeurs de la performance du problème de référence, et on compile pour les mêmes contraintes de fiabilité soit 0.85, 0.97 et 0.99.
Pour la première structure la fiabilité a augmenté avec une diminution du coût, pour les deux autres structures la fiabilité a augmenté mais avec une augmentation du coût par rapport aux résultats de la référence.
Le coût de la troisième structure est le double de celui de la seconde. On peut avoir une bonne fiabilité avec un coût réduit de moitié.
Pour le problème dual on a varié le coût pour les différentes valeurs 10%, 15% et 20%.
On constate que la fiabilité a augmenté, mais le coût a également augmenté.
Pour le problème dual, il faut investir plus pour avoir une bonne fiabilité.
On vari le coût et on garde la même fiabilité et performance du problème de référence, et on compile pour les mêmes contraintes du coût soit 10%, 15% et 20%.
La fiabilité a diminué avec une diminution du coût cela pour la première configuration, par contre la fiabilité a augmenté avec une diminution du coût pour la seconde et la troisième structure par rapport à la référence.
On vari la fiabilité et on garde le même coût et performance du problème de référence, et on compile pour les mêmes contraintes de fiabilité soit 10%, 15% et 20%.
Pour les deux dernières configurations on a obtenu les mêmes résultats. Par rapport à la référence, on constate une légère augmentation de la fiabilité avec une diminution du coût pour la première configuration, pour les deux autres, la fiabilité a diminué avec une diminution du coût d'investissement.
On vari le coût et la fiabilité et on garde la même performance du problème de référence, et on compile pour les mêmes contraintes de fiabilité soit 10%, 15% et 20%.
On constate une diminution de la fiabilité pour les trois configurations avec une diminution du coût pour les deux premières et une légère augmentation pour la troisième.
Pour le problème trial, on a varié la fiabilité pour les différentes valeurs 85%, 97% et 99% et le coût pour les différentes valeurs 10%, 15% et 20%.
On constate que la fiabilité a augmenté, mais le coût a également augmenté par une proportionnalité linéaire.
La deuxième configuration est la meilleure puisqu'on obtient une bonne fiabilité avec un coût réduit.
On vari le coût et on garde la même fiabilité et performance du problème de référence, et on compile pour les mêmes contraintes de fiabilité soit 0.85, 0.97 et 0.99 et le coût pour les différentes valeurs 10%, 15% et 20%.
La fiabilité a diminué avec une diminution du coût cela pour les deux premières configurations, par contre la fiabilité a augmenté avec une augmentation du coût pour la troisième structure par rapport à la référence.
On vari la fiabilité et on garde le même coût et performance du problème de référence, et on compile pour les mêmes contraintes de fiabilité soit 0.85, 0.97 et 0.99 et le coût pour les différentes valeurs 10%, 15% et 20%.
Pour les deux dernières configurations on a obtenu les mêmes résultats. Par rapport à la référence, on constate une augmentation de la fiabilité avec le coût pour la première configuration, pour les deux autres, la fiabilité a diminué avec une diminution du coût d'investissement.
On vari le coût et la fiabilité et on garde la même performance du problème de référence, et on compile pour les mêmes contraintes de fiabilité soit 0.85, 0.97 et 0.99 et le coût pour les différentes valeurs 10%, 15% et 20%.
On constate une diminution de la fiabilité pour les trois configurations avec une diminution du coût pour les deux premières et une augmentation pour la troisième.
On a proposé trois types de problèmes (primal, dual et trial). D'après les résultats de simulation la variable de décision la plus dominante est la variable coût. Une faible variation de cette dernière permet d'avoir différentes configurations. Outre une large variation de la fiabilité influe peu sur le résultat.
Le choix des configurations revient aux objectifs planifiés par le client. En fonction de l'objectif visé pour garantir un système hautement fiable, à moindre coût ou bien un compromis entre les deux.
L'importance de la conception d'un système électro- énergétique comme réseau électrique se trouve actuellement confrontée à un nouveau paradigme dont on n'a pas encore mesuré toutes les conséquences sur le fonctionnement et la sûreté de ces composantes ou sous système qui le forment (production, transport, répartition et distribution) afin d'avoir un système industrialisée moderne.
La conception d'un système d'énergie électrique moderne doit être capable de fournir continuellement aux clients de l'énergie électrique aussi économiquement possible et avec un degré acceptable de sûreté ou fiabilité. Alors ce degré d'espérance exige une conception optimale. Cependant, aucun composant du système n'est à l'abri de défaillances, leurs conséquences sont très lourdes pour le système conçu. Tout le monde à l'esprit des conséquences. Il s'agit donc de l'effondrement des réseaux ou « black-out ».
Cette combinaison entre défaillance et conséquences importantes demande une analyse rigoureuse des risque dés la conception afin de procéder à de nombreuses prises de décision. La banalisation et la grande disponibilité de l'électricité ont poussé certains à vouloir la traiter au même titre que d'autres biens de consommation courante. Elle a cependant des caractéristiques uniques qui doivent être gardées à l'esprit.
Le contexte particulier de la prise de décision en temps limité implique de borner le temps conception. De ce fait, il n'est pas possible d'utiliser un mécanisme classique. La résolution de problèmes de type combinatoires par des méta- heuristiques en particulier l'algorithme des colonnes de fourmi offre de nombreux avantages. C'est un compromis entre la qualité des solutions et le temps de calcul.
Dans cette thèse, nous avons présenté une problématique relative à la prise en compte de trois types de problèmes aux investisseurs de faire le choix en fonction de leurs objectives planifiés :
§ La première formulation nous permet d'avoir une conception à moindre coût au point de vue production et structure toute en garantissant un niveau de fiabilité acceptable ce type est Primal.
§ La deuxième formulation donne aux investisseurs la possibilité d'atteindre leur niveau de sûreté désiré toute en respectant le chiffre d'affaire à allouer au projet type Dual.
§ La troisième formulation nous permet d'avoir un compromis entre le type Primal et Dual c'est un type Min-Max ou/ et Max-Min.
Ces trois formulations agissent en permutation entre trois fonctions objectives non linéaire avec leurs contraintes non linéaires.
Nous avons développé, dans ce cadre un programme plateforme Java spécifique basé sur l'approche ACO optimisant les objectives planifiés sous contraintes "fiabilité - coût / et performance".
Les résultats dans cette thèse nous ont conduit à proposé des structures avec différents niveaux de contraintes : fiabilité, coûts, fiabilité/coût et fiabilité coût/puissance qui donnent à l'investisseur le choix et lui facilitent la prise de décision concernant tel ou tel investissement. Les trois stratèges adoptés nous permettent de valider nos structure ou configuration les plus optimales selon les cas:
§ La première formulation nous permet d'avoir un coût d'investissement du système optimal (composant et production énergétique) dans une plage de 5.5-11.4% par rapport au niveau de fiabilité exigé par le client 85-99%. Ces résultats montre une proportionnalité entre un investissement et une haute sûreté du système optimal a concevoir.
La variation des variables de décision nous ont donné par simulation d'autre alternatives optimales par rapport a celle de référence, outre une simple variation du paramètre coûts dans le système influe fortement sur les résultats de simulation qui nous donne des configuration assez importante a celle de la référence. Ces nouvelles configurations vaut 6.07-8.5%. Les deux autres paramètres puissance et fiabilité influe peut sur les résultats de la simulation.
§ La deuxième formulation nous permet d'avoir des conceptions optimales à haute fiabilité (composants du système et puissance) dans une plage de 98.7-99.5% correspondant a des investissements de 9.7-16.8%. la variation des deux autres paramètres s'articule autours d'un certain nombre de solutions dont leurs écart type par rapport à la référence peut sensible. Outre le paramètre fiabilité montre une grande influence est les résultats de simulations nous donne des alternatives entre 98.8-99.4% qui valent un investissement de 9.5-11.9%. donne aux investisseurs la possibilité de limiter les coûts investissements d'un projet d'alimentation.
§ La troisième formulation nous permet d'avoir des conceptions optimales à compromis entre une haute fiabilité/ un coût minimale d'investissement sur (composants du système et puissance) c'est un type de problème Max-Min cette dernière formulation appartenant à le domaine multi- objectives. Les résultats de simulation nous ont conduit a faire le compromis entre ces deux variables de décisions. La configuration optimale est de 96.6-99.5% et 7.93-16.4% de compromis entre fiabilité / coût respectant la garantie du budget a allouer ainsi un seuil de sûreté de : 85-99% et 10-20%.
En variant les deux variable de décisions fiabilité/ coût nous obtenant par simulation une variante plus optimale dont le compromis est de 98.1-99.4% de fiabilité et 7.9-14.2% budgétaire aux même contraintes. Reste à dire que ce travaille est flexible à l'utilisation par des client dont la stratégie revient au décideur qui est le client pour choisir son objective planifiée est de trouver sa solution optimale.
Le comportement des ces programmes devient dynamique et intelligent dans le cas de la variation brusque et aléatoire de la charge. Dans ce cas cet outil prend le nom de : `'Problèmes Dynamiques et Intelligents d'Optimisation Multi- Objectives''.
La dynamique de cet outil réside par le choix de l'objectif planifié par le designer le système peut se ramener à sa fonction objective par un enclenchement et déclenchement des composants déjà utilisés.
La signification pratique de chaque simulation suivant l'objectif planifié réside par un changement brusque de la structure productive, de ce fait une balance pivotante entre demande et production doit se maintenir à chaque instant. Ce point théorique existe rarement en pratique.
La vision future pour étendre cette recherche consiste à faire une fouille minutieuse sur les caractéristiques du cahier de charge qui peuvent changer totalement la nature des problèmes traités. La problématique de résolution de ces nouveaux problèmes peut s'articuler autours de plusieurs axes :
1- Cas ou les caractéristiques des composants sont des
fonctions continues 
2- Système non fluide avec stock tampons (Compensateurs) qui nous ramène à faire face à des problèmes d'allocation et de dimensionnement optimales des compensateurs dans le système.
3- S'il s'agit d'un système déjà existant alors on touche le problème de reconfiguration optimale des systèmes productifs.
4- L'étude des systèmes série- parallèle (cas de la conception des panneaux solaires).
|
1 |
G. Habchi, «Conceptualisation et Modalisation pour les simulations de production», UNIVERSITE DE SAVOIE Document de Synthèse L.F. Escudero, An inexact algorithm for the sequential ordering problem. European Journal of Operational Research 37 (1988), 232-253 2001. |
|
2 |
Réseau Electrique, Encyclopédie Encarta, 2006. |
|
3 |
G.J. Anders, Probability concepts in electric power system, Wiley Publication, New York, 1996. |
|
4 |
A. Yalaoui., Allocation de fiabilité et de redondance dans les systèmes parallèle- série et série- parallèle, thèse de doctorat, 2004. |
|
5 |
Meziane. R, Optimisation de la structure d'un réseau de production d'énergie électrique et amélioration de sa performance, thèse de doctorat, USTO 2007. |
|
6 |
K. Mendez, N. Skouni, Optimisation de la structure des réseaux de répartition en utilisant les algorithmes de fourmis, mémoire d'ingéniorat, Sidi Bel abbés 2006. |
|
7 |
Y. Massim, Availability and performance optimisation of series- parallel industrial process, thèse de doctorat, Sidi bel abbés 2005. |
|
8 |
Reinschke., System of elements with many states. radio i svyaz, Moscow, 1985 |
|
9 |
El-Neweihi and Proschan. Degradable systems: A survey of multi-states system theory. Common. Statist. Theor. math., 13(4), 1984. C.R. REEVES (Ed.) Modern heuristic techniques for combinatorial problems, Blackwell Scientific Publications, Oxford, 1993. |
|
10 |
R. Meziane, Y. Massim, A. Zeblah, and A. Ghoraf. Reliability Computation For Algerian Power Network Considering Mss, An International Journal Of Nonlinear Dynamics And Chaos In Engineering Systems, Klewer Academic Publisher, Vol 40 number 4 june 2005 pp 309 321. |
|
11 |
R Meziane, Y. Massim, A. Zeblah, A. Ghoraf and Mustapha Rahli. Reliability Optimization Using Ant Colony Under Cost and Performance Constraintes, Power System Research Journal ESRJ, 2005, Elsevier Publisher, Vol N°76, pp-1-8, 2005. |
|
12 |
A. Zeblah, A. Ghoraf, S. Hadjeri, H. Hamdaoui. Optimization for Series-Parallel Continuous Power Systems with Buffers Uder Reliability Constraints Using Ant Colony Accepted paper in international Journal of Industrial and Management Optimization,Vol N°2, Number4, pp-467-479 (JIMO) 2006 |
|
13 |
Y Massim, A. Zeblah, R. Meziane and M. Rahli. Ant Colony Optimization For Multi-State Series-parallel System Expansion-Sheduling, Electrical Engineering Journal, Springer Verlags, under press, 2005. |
|
14 |
Y. Massim, A. Zeblah, A. Ghoraf and R. Meziane. Reliability Evaluation Of Multi-State Series-Parallel Power System Under Multi-States Constraints, Electrical Engineering Journal, Springer Verlags, Vol N°87, pp-327-336, 2005. |
|
15 |
E.H.L. AARTS, J.K. LENSTRA (Eds.), Local search in combinatorial optimization, John Wiley & Sons, 1997. |
|
16 |
D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, 11-32. |
|
17 |
O. Roux, La mémoire dans les algorithmes à colonie de fourmis : applications à l'optimisation et à la programmation automatique, thèse de doctorat de l'Université du Littoral Cote d'Opale, 2001. |
|
18 |
Méta heuristique, Wikipédia encyclopédie, 20 décembre 2005 |
|
19 |
Holldobler and Wilson, Voyage chez les Fourmis. Seuil, 1996. |
|
20 |
B. Bullnheimer, R.F. Hartl, and C. Strauss, A new rank-based version of the ant system: a computational study, Central European Journal of Operations Research 7 (1) (1999), 25-38. |
|
21 |
D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, 11-32. |
|
22 |
Jin-Kao Hao, Philippe Galinier, Michel Habib, Méta heuristiques pour l'optimisation combinatoire et l'affectation sous contraintes, Revue d'Intelligence Artificielle, Vol : No. 1999. |
|
23 |
Méta heuristique, Wikipédia encyclopédie, 20 décembre 2005 |
|
24 |
J. Dreo, A. Petrowski, P. Siarry et E. Taillard, Métaheuristiques pour l'optimisation difficile, Eyrolls, 2003. |
|
25 |
S., Martello S., Osman I.H., Roucairol C. (eds.) Meta- Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, Boston, 1999. |
|
26 |
Algorithmes génétiques, Wikipedia, encyclopédie, 20 décembre 2005. |
|
27 |
J.H. HOLLAND, Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor, 1975. |
|
28 |
M. Dorigo, Optimization, learning and natural algorithms, Ph.D. Thesis, Politecnico di Milano, Milano, 1992. |
|
29 |
E. Bonabeau, M. Dorigo, G. Theraulaz, Nature, Volume 406, Number 6791, Pag. 39 -42 (2000) |
|
30 |
S. Chen, S. Smith., Commonality and genetic algorithms. Technical Report CMU-RITR- 96-27, The Robotic Institute, Carnegie Mellon University, Pittsburgh, PA, USA, 1996. |
|
31 |
C. N. Bendtsen, T. Krink, Phone routing using the dynamic memory model, in Proceedings of the 2002 congress on Evolutionary Computation, Honolulu, USA |
|
32 |
V. Maniezzo, M. Dorigo and A. Colorni, The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1) :29-41, 1996. |
|
33 |
L. Bianchi, L.M. Gambardella, M.Dorigo. An ant colony optimization approach to the probabilistic traveling salesman problem. In Proceedings of PPSN-VII, Seventh Inter17 national Conference on Parallel Problem Solving from Nature Science. Springer Verlag, Berlin, Germany, 2002 |
|
34 |
J.L. Bentley, Fast algorithms for geometric traveling salesman problem, ORSA Journal on Computing, vol. 4, pp. 387-411, 1992. |
|
35 |
B. Bullnheimer, R.F. Hartl, and C. Strauss, Applying the ant system to the vehicle routing problem, In: Voss |
|
36 |
C. Blum, M. Sampels, Ant colony optimization for FOP shop scheduling: a case study on different pheromone representations, in Proceedings of the 2002 congress on Evolutionary Computation, Honolulu, USA |
|
37 |
M. den Besten, T. Stützle, M. Dorigo, Ant colony optimization for the total weighted tardiness problem, Parallel Problem Solving from Nature: 6th international conference, September 2000. Springer Verlag. |
|
38 |
A. Colorni, M. Dorigo, and V. Maniezzo, Distributed optimization by ant colonies, Proceedings of ECAL'91, European Conference on Artificial Life, Elsevier Publishing, Amsterdam, 1991. |
|
39 |
O. Cordon, I. Fernandez de Viana, F. Herrera, L. Moreno, A new ACO model integrating evolutionary computation concepts: the best-worst ant system, in Proceedings of ANTS2000 -from ant colonies to artificial ants, Universitè Libre de Bruxelles |
|
40 |
D. Camara, A.A.F. Loureiro, A GPS/ant-like routing algorithm for ad hoc networks, in 2000 IEEE Wireless Communications and Networking Conference, Chicago, USA. |
|
41 |
N. Monmarché, Algorithmes de fourmis artificielles : applications à la classification et à l'optimisation, thèse de doctorat, l'Université de Tours, le 20 décembre 2000. |
|
42 |
G. Dicaro and M. Dorigo, Antnet: distributed stigmergetic control for communications networks, Journal of Artificial Intelligence Research, 9 (1998), 317-365. |
|
43 |
G. di Caro and M. Dorigo, Mobile agents for adaptive routing, Proceedings of HICSS-31, 1998. |
|
44 |
R. Vander Meer, M. Breed, K.E., E., and M.L., W., editors (1998). Pheromone Communication in Social Insects. Westview Press. |
|
45 |
Brossut, R. (1996). Phéromones, la communication chimique chez les animaux. CNRS editions, Belin. |
|
46 |
G. di Caro and M. Dorigo, AntNet: distributed stigmergetic control for communications network , Journal of Artificial Intelligence Research (JAIR), Vol. 9, Pag. 317- 365, 1998. |
|
47 |
M. Dorigo and G. Di Caro (1999). The Ant Colony Optimization Meta-Heuristic. In |
|
48 |
M. Dorigo, G. Di Caro & L.M. Gambardella (1999). Ant Algorithms for Discrete Optimization. Artificial Life, 5(2):137-172. |
|
49 |
M. Dorigo and L.M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transaction on Evolutionary Computation 1(1997), 53--66. |
|
50 |
M. Dorigo, V. Maniezzo, and A. Colorni, The ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics-Part B 26(1) (1996), 29--41. |
|
51 |
S.Bouri., A. Zeblah, A. Ghoraf, S. Hadjeri, H. Hamdaoui,Ant Colony Optimization to Shunt Capacitor Allocation in Radial Distribution Systems Acta and Electronica et informatic journal Schekoslovacia N°4,Vo5; 2005 |
|
52 |
R. Meziane, H. Hamdaoui, M. Rahli, and A. Zeblah Structure Optimization of Electrical Power Network Using Ant Colony Approach. Facta Univ. Ser.: Elec. Energ., vol. 16, No. 2, August 2003, pp. 233-250. |
|
53 |
R. Ouiddir, M. Rahli, R. Meziane and A. Zeblah. Ant colony Optimization For New Redesign Problem Of Multi-States Electrical Power Systems. Journal Of Electrical Engineering, Vol 55, N° 1-2, 2004, pp 1-7, ISSN 13-35-36-32 FEISTU |
|
54 |
A. Zeblah, Réalisation D'un Logiciel Pour La Reconstruction D'un Réseau Fiable Et sa Reconfiguration Optimale, thèse de doctorat, USTO, 2002. |
(2-1)
(2-2)
(2-3)
(2-4)
. Elle a pris les noms : 
transformé, et à fait naître L'UMGF (Universal
Moment Generating Function) ou simplement u-transform. D'UMGF est
largement connu à partir de l'extension de UGF (Ordinary
Générationg Function).
(3-1)
présente 
possible valeur et 
est la probabilité que 
soit égale à 
peut se calculer par l'utilisation de la fonction d'Ushakov :
.
d'un système Multi- Niveaux ou Multi- States (MSS) est
définit pour une performance de sortie stationnaire (Output Stationary
Performance), dans ce cas la disponibilité est notée par 
est donnée par la probabilité suivante :
(3-2)
(3-3)
: Représente les niveaux de charges
: Représente un opérateur disruptif définit
par :
(3-4)
(3-5)
(3-6)
. Finalement les coefficients du polynôme 
sont sommés pour tous les termes avec
. Considérons le cas d'une machine simple avec un seul mode de
défaillance (Tous- Rien) et chaque élément 
à une performance 
et disponibilité 
. L'UMGF avec deux états peut être définit
par :
(3-7)
(3-8)
: Représentent la performance ou bien la capacité des
éléments 
.
}.
: Représente la performance la plus faible dans le
système de l'élément Mn-1.
qui peut être utilisé dans les expressions
suivantes :
:
: est un opérateur qui permet de faire un produit simple
entre les fonctions individuelle
.
.
et 
consécutive nous obtenons L'UMGF du système total
série Parallèle, pour faire ça en premier il faut
déterminer individuellement L'UMGF pour chaque composant.
,
; nous obtenons L'UMGF du iéme composant du
système contenant Ki élément en
parallèle comme :
et disponibilité
. Dans ce cas nous aurons la 
et
. L'UMGF des éléments à défaillance totales
se procure par deux états qi peuvent être formuler comme
suite :
, nous obtenons L'UMGF du iéme
élément du système contenant Ki
éléments en parallèle par : 
/* Z : transformé de Laplace*/
/* Polynôme d'Ushakov de la colonne */
=
/*A : Disponibilité des aux niveaux de Charges */
/*W : Niveaux de Charges */ 
