WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

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
  

précédent sommaire suivant

Extinction Rebellion

5.4.2. Variantes

5.4.2.1. Ant System & elitisme

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.

5.4.2.2. Ant-Q

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 ».

5.4.2.3. 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)

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.

précédent sommaire suivant






Extinction Rebellion





Changeons ce systeme injuste, Soyez votre propre syndic





"I don't believe we shall ever have a good money again before we take the thing out of the hand of governments. We can't take it violently, out of the hands of governments, all we can do is by some sly roundabout way introduce something that they can't stop ..."   Friedrich Hayek (1899-1992) en 1984