Optimisation par colonie de fourmis
Contents
1. ACO PhilippeCollard com 23 04 09 AntSystem initialisation EN mu i Les m ants sont r parties al atoirement sur les n villes 2 Pour chaque ant la liste tabou contient sa ville de depart 3 Les pistes de pheromones sont initialisees T c cC constant positive non nulle ACO PhilippeCollard com 23 04 09 AntSystem iteration de base Chaque ant choisit une ville de destination et s y d place ED mm ir Une ant k plac e sur une ville i l instant t choisit sa ville de destination 3 en fonction de la 1 visibilit de cette ville n distance inter villes 2 quantit de pheromone qt t d pos e sur arc reliant ces deux villes Le choix est aleatoire selon une probabilite ou deux param tres a et B contr lent l importance relative des ph romones et de la visibilit ACO PhilippeCollard com 23 04 09 AntSysten iteration de base Chaque ant choisit une ville de destination et s y d place Le choix est aleatoire selon une probabilite ou deux param tres a et B contr lent l importance relative des pheromones et de la visibilite La probabilit d un d placement l mentaire est un compromis entre visibilit et piste chimique I Si B 0 les villes les proches ont de chance d tre s lectionn es algorithme glouton I Si a 0 seule l amplification des pheromones agit convergence prematuree ACO PhilippeCollard com 23 04 09 Fin d un cycle de base Toutes les ants ont termine un t2. a Initialement le pont est vide Apres une p riode transitoire des fluctuations al atoires favorisent la piste sup rieure plus les A suivent une piste plus elle devient attractive m Ph nom ne qui se renforce lui m me positive faadhack i Y Pace SIRIA SE Sa m Paes bree r a L i m F a L 4 5 Le ES z ag Terms mitri ACO PhilippeCollard com 23 04 09 Exp rience du double pont binaire EE aaMMHMHMHMHMHHRmnmnmnmnmnmnH T Influence des fluctuations al atoires initiales reduite I Car les 4 chemins possibles sont de longueurs differentes soem dr v Pope iy ACO PhilippeCollard com 23 04 09 Effet de la coupure d une piste ACO PhilippeCollard com 23 04 09 Stigmergie 220 aMHMHRRmnnnmmnmnmAnmH I Stimulation d agents par la performance de ce qu ils ont accompli Grasse 1999 D Communication indirecte D Pas de contact physique entre agents o Pas de centralisation interaction locale m Optimisation Propri t emergente ACO PhilippeCollard com 23 04 09 Ant Colony Optmisation O Introduit par M Dorigo en 1991 Historiquement appliqu sur le TSP L 1 Id e repr senter le probleme r soudre sous la forme de la recherche d un meilleur chemin dans un graphe D Intensification via les ph romones des bons chemins o Diversification par la nature al atoire des d cisions m M ta probl me g rer le compromis exploitation exploration ACO P
3. lock for irt Beturn to nest carrying food Lake at back to nest wiggle ra d diffuse chemical diffusion rate 100 ask patches set chemical chemical 100 evaporation rate 100 slowly evaporate chemical end 23 04 09 PhilippeCollard com Observations EE I Les fourmis exploitent elles les sources en s rie ou en m La source la plus proche est elle exploit e en premier 1 Y a t il mergence d un chemin stable ie ininterrompu entre le nid et une source o Existe t il une taille critique pour la colonie PhilippeCollard com 23 04 09 Observations 1 Determiner le taux de fourmis utiles ratio entre le nombre de fourmis qui ramenent de la nourriture et le nombre total de fourmis Quelle est l influence sur la dynamique du taux de diffusion des pheromones D du taux d vaporation des pheromones PhilippeCollard com 23 04 09 Pour aller plus loin EE aMMImRmmmmnmnmnaRmn m Essayer differents placements pour les sources de nourriture Que se passe t il si deux sources sont a une m me distance du nid exploitation exploitation s rie ou a Que se passe t il avec un obstacle entre le nid et une source 1 Une fourmi utilise une astuce pour revenir au nid en suivant une odeur nest scent Les vrais fourmis ne font pas ici Essayer d implanter d autres solutions PhilippeCollard com 23 04 09 Pour aller plus loin 250 mai iii mai mam
4. m Une fourmi est sensible au niveau de pheromones d pos s par ses congeneres variable chemical entre 0 05 et 2 D La limite inf permet aux fourmis de ne pas rester ind finiment sensibles aux ph romones D Supprimer la limite sup Que ce passe t il Pourquoi m Dans UPHILL CHEMICAL une fourmi suit le gradient de ph romone D Elle sniff dans trois directions et tourne dans celle qui sent le plus o Essayer des variantes en changeant le nombre et la place des voisins PhilippeCollard com 23 04 09 Concepts Mm 1 R gles locales simples parall lisme m Emergence de computation collective globale Pas de leader pas de carte D actions decentralisees m Interactions locales D ant lt gt ant via l environnement m Transition de phase seuil D masse critique minimal de fourmis 23 04 09 PhilippeCollard com Sources R f rences E http www cnrs fr Cnrspresse n386 html n386a09 htm E Bonabeau M Dorigo and G Theraulaz Inspiration for optimization from social insect behaviour Nature Vol 406 juillet 2000 pp 39 42 Bonabeau E amp Theraulaz G 2000 Swarm Smarts Scientific American 282 3 pp 72 79 E Bonabeau M Dorigo and G Theraulaz 1999 Swarm Intelligence From Natural to Artificial Systems Oxford University Press ACO PhilippeCollard com 23 04 09 Routage par colonie de fourmis 1 Les techniq
5. OPTIMISATION PAR COLONIE DE FOURMIS Optimisation par colonie de wm OU I Ethologie Optimisation par Colonie de fourmis 7 Ant System 1 Probl me du voyageur de commerce Mod lisation amp Simulation en NetLogo ACO PhilippeCollard com 23 04 09 Ethologie vs Informatique 5 ee 1 Ethologie D Comportements collectifs des insectes sociaux m Informatique a Traitements et donn es distribu es D Donn es situ es notion d espace D Communication temps espace Stigmergie D m thodes puissantes pour la conception d algorithmes Optimisation combinatoire Routage Contr le distribu ACO PhilippeCollard com 23 04 09 Ethologie vs Informatique a Les probl mes quotidiens r solus par une colonie sont nombreux et de nature tres variee a recherche de nourriture a construction du nid g division du travail o allocation des t ches entre les individus etc m La plupart de ces probl mes se retrouvent dans le domaine des sciences de l ing nieur en informatique et en robotique ACO PhilippeCollard com 23 04 09 M thodes flexibles et robustes m En plus de leur capacit d j surprenante a r soudre un large spectre de probl mes statiques ces techniques offrent un haut degr de flexibilit et de robustesse dans des environnements dynamiques m Elles permettent de r soudre de fa on plus efficace des probl mes d optimisation comme les probl mes g d assignation quadratique QAP D d adapt
6. ation de flux des communications circulant sur un r seau ACO PhilippeCollard com 23 04 09 Les societes d insectes ont une capacite a resoudre des problemes d une maniere eee Flexible D Ja colonie s adapte aux brusques changements d environnement 0 Robuste a Ja colonie continue de fonctionner lorsque certains individus chouent accomplir leur t che ACO PhilippeCollard com 23 04 09 Comportements collectifs des insectes sociaux auto organises Guy Theraulaz CNRS Toulouse ACO PhilippeCollard com 23 04 09 Comportements collectifs Auto Organis s Ea main rn m L auto organisation emergence de structures au niveau collectif a partir d une multitude d interactions simples sans tre codees explicitement au niveau individuel Certaines interactions une fourmi qui suit la piste de ph romone laiss e par une autre aident r soudre collectivement des probl mes difficiles par exemple trouver le chemin le plus court conduisant une source de nourriture ACO PhilippeCollard com 23 04 09 Intelligence en essaim Un nouveau domaine de recherche Me Transformer la connaissance que les ethologistes ont des capacites collectives de resolution de problemes des insectes sociaux en techniques artificielles de resolution de problemes I Les informaticiens et les ing nieurs ont pu transformer des modeles du comportement collectif des insectes sociaux en methodes utiles pour l optimi
7. eCollard com 23 04 09 ACOTSP command line options 1 EN m suhhhaaHHHNHRHRHRHRHRNII I w Se HE AE HE SE SR OSE SE E OE h SE number of independent trials number of steps in each trial maximum time for each trial inputfile TSPLIB format necessary stop if tour gt optimum is found number of ants nearest neighbours in tour construction alpha influence of pheromone trails beta influence of heuristic information rho pheromone trail evaporation q 0 prob of best choice in tour construction number of elitist ants number of ranks in rank based Ant System No of nearest neighbors for local search local search LS 2 000 25 23 0DE 3 7 2 0Dc use don t look bits in local search ACO PhilippeCollard com 23 04 09 ACOTSP command line options 2 EN m NIHHHHNHNHNHNHNHNRHRHRHRHRHRHRHI basic Ant System elitist Ant System rank based version of Ant System MAX MIN ant system best worst ant system ant colony system display the help text and exit as apply v eas apply w ras apply x mmas apply y bwas apply Z acs apply h help Options seas eas ras mmas bwas acs help don t need arguments while all the others do ACO PhilippeCollard com 23 04 09 WetLogo htty ccl northwestern cdu netlogo procedure setup 1 1 nid violet 3 sources de nourriture bleu 4 100 200 fourmis rouge 23 04 09 PhilippeCollard com Resu
8. eCollard com 23 04 09 Algorithme Max MinAS Initialiser repeat Chaque ant construit une solution un tour am liorer les solutions par recherche locale R compenser les meilleurs solutions en ajoutant de la ph romone Evaporer les traces de ph romone w el Si une tracePh romone lt t alors la mettre w a Si une tracePh romone gt t alors la mettre Until maxCycles ou bonneSolution ACO PhilippeCollard com 23 04 09 Algorithme Max MinAS EN min Fournir des r sultats competifs Imposer des bornes T et T aux traces de pheromones Les traces sont initialis s avec cm Quel est l effet de ces choix sur le fonctionnement de l algorithme A voir en Travaux dirig s ACO PhilippeCollard com 23 04 09 Optimisation par colonie de fourmis et TSP Oliver30 Eil50 Eil75 Cette optimisation est o e e Une cons quence prune algorithm 3200 25000 80000 renforcement et Evolutionary 420 426 542 r vaporation de la une annealing 24617 68512 173250 que seules les a subsistent ACO PhilippeCollard com 23 04 09 software package ACOTSP V1 0 EE I Auteur Thomas Stutzle m ACOs appliques aux TSP sym triques I Ant System AS Elitist Ant System EAS a MAX MIN Ant System MMAS a Rank based version of Ant System RAS a Best Worst Ant System BWAS I Ant Colony System ACS m ANSI C sous Linux works fine under Windows and Mac OS X ACO Philipp
9. hilippeCollard com 23 04 09 A C O et T S P m Le probleme du voyageur de commerce Traveller Salesman Problem consiste a trouver le chemin le plus court en passant une seule fois par un nombre donne de villes 1 En utilisant des fourmis artificielles con ues pour d poser des pistes de ph romone dont la concentration varie en fonction de la distance totale qu elles ont parcourue on peut obtenir des chemins quasi optimaux ACO PhilippeCollard com 23 04 09 Probleme du Voyageur de Commerce TSP Complexite de parcours possibles pour n villes est de n 1 6 villes 120 parcours possibles a 10 villes plus de 362 000 D 60 villes plus de 10 atomes dans l univers a Ceci peut expliquer pourquoi le probleme n a pas t tudi s rieusement avant l arriv e des ordinateurs mais depuis de nombreux chercheurs l ont trait ACO PhilippeCollard com 23 04 09 Ant System E I Le premier ACO 1992 Performances tr s moyennes Etendue de nouvelles versions Max Min AS o Robuste la colonie continue de fonctionner lorsque certains individus chouent accomplir leur t che ACO PhilippeCollard com 23 04 09 Algorithme AS E Initialiser repeat Chaque ant construit une solution un tour am liorer les solutions par recherche locale R compenser les meilleures solutions en ajoutant de la ph romone Evaporer les traces de ph romone Until maxCycles ou bonneSolution
10. ltat global observe Les ressources en nourriture sont exploitees selon leurs propre distance et attrait m Emergence d une d cision collective choix d un chemin 23 04 09 PhilippeCollard com Mod liser amp Simuler Un nid et trois sources de nourritures 23 04 09 PhilippeCollard com Comportement local des m OU S m Se d placer au hasard 1 Si trouver nourriture la prendre et retourner au nid 1 Si transporte nourriture d poser de la ph romone m Si ne transporte pas de nourriture suivre les manations de ph romone 23 04 09 PhilippeCollard com Comportement local d une fourmi BOO 4 Si une fourmi est sans nourriture a Si elle trouve de la nourriture elle en prend d pose des ph romones et fait demi tour D Sinon elle avance prioritairement vers la case ayant le plus de pheromone E vers la case sentant le plus la nourriture au hasard 23 04 09 Comportement local d une fourmi EE aMMHRmmmnmnmnmnmnmnAnmH 1 Si une fourmi poss de de la nourriture a Si elle est dans le nid elle la d pose et fait demi tour Sinon elle se dirige vers la case sentant le plus le nid en d posant une dose de ph romones d croissante avec l loignement de la source 23 04 09 mds population Jor Plo Food in each pile time ticks 58 diffusion rate vs evaporation rate CO gO ask turtles ifelse color red look for food Ji not carrying food
11. orsqu elles retourneront vers la source de nourriture ACO PhilippeCollard com 23 04 09 Pheromone 13 mm mm nm im en nn aememmnmmNTNTNAT m Les fourmis choisissent la piste qui porte la plus forte concentration 1 Piste chimique virtuelle Important de comprendre les comportements naturels avant d abstraire dans un algorithme ACO PhilippeCollard com 23 04 09 Pheromone m Substance chimique produite par des glandes d clenchant des r actions comportementales entre individus de la m me esp ce 1 Signaux chimiques odorants agissant a grande distance a dose mol culaire m1 Moyen de communication chez les insectes o Plusieurs types sexuelles de piste gregaires d alarme ACO PhilippeCollard com 23 04 09 Pheromone Chimior cepteurs antennes garnies d organes sensoriels m Applications pratiques en agriculture D pi ges a pheromones compos s d un attractif synth se de la ph romone naturelle de la femelle du ravageur et d un syst me assurant la capture des m les ACO PhilippeCollard com 23 04 09 Mouche de l olive pi ge a ph romones EGE AAMAMHmRmmmmnmnmnmnmnmnmnmA m Pi ge compos d un toit englu et d une capsule de ph romone suspendue au milieu m Mode d emploi dans le cas g n ral il faut 1 pi ge par ha httn hananas Aintan frlNAnrndiite mAA nharnmann htm PhilippeCollard com 23 04 09 Ph nom ne autocatalytique Pont binaire de Deneubourg 1999 E
12. our en revenant a leur propre ville de depart Pour chaque ant k calculer la longueur de son tour L t vider sa liste tabou mettre a jour les pheromones rechercher le plus petit tour et le m moriser sil est meilleur que les precedents Toutes les ants recommencent un nouveau tour a partir de leur propre ville initiale ACO PhilippeCollard com 23 04 09 Mettre a jour les pheromones E T ttn p t t At t e dans 0 1 Entre les instants t et t n 1 9 evaporation de la piste AT t quantit de pheromone d pos e par les ants ACO PhilippeCollard com 23 04 09 Evaporation des pheromones ENI mm em muumiuiaiii ii mess I Si p 1 pas d vaporation donc pas de limitation du ph nom ne autocatalytique I Si p 0 les ants prennent seulement en compte les d p ts du dernier cycle I p repr sente la persistance de la piste ie l effet m moire ACO PhilippeCollard com 23 04 09 Quantite de pheromone d pos e par les ants lors d un tour cycle IN At t quantit de pheromone d pos e par les ants sur larc reliant la ville i la ville 3 entre les instants t et t n Pour chaque ant k passant par l arc i 7 Ar t Q L t o Q repr sente un quota de ph romones attribu a chaque ant souvent Q 100 Idee un tour est court les arcs qui le composent sont approvisionnes Remarque c est une m a j retard e ACO Philipp
13. sation et le contr le ACO PhilippeCollard com 23 04 09 Intelligence en essaim Un nouveau domaine de recherche 10 NhmmmmmmmmeemmmemeemmmRmnmN me memmmmmmmemmmmnmIANRNRTRTA 1 Parmi les techniques de l intelligence en essaim certaines sont arrivees a maturite Les algorithmes de contr le et d optimisation inspir s de mod les de recherche collective de nourriture chez les fourmis en particulier ont connu un succes inattendu et portent le nom d optimisation par colonie de fourmis Ant Colony Optimization et de routage par colonie de fourmis ACO PhilippeCollard com 23 04 09 Optimisation par colonie de fourmis 1 Les fourmis sont capables de s lectionner le plus court chemin pour aller du nid une source de nourriture gr ce au d p t et au suivi de pistes de ph romone m Lorsqu une colonie de fourmis d Argentine doit emprunter un pont deux branches de longueurs diff rentes pour exploiter une source de nourriture elle s lectionne la branche courte si la diff rence entre les longueurs des branches est suffisamment importante ACO PhilippeCollard com 23 04 09 A C O comment ca marche ON m Les fourmis d posent de la pheromone l aller vers la source de nourriture et au retour vers le nid m Au d part le choix est al atoire mais la branche courte devient vite la plus marqu e car les fourmis qui l empruntent arrivent plus vite au nid et auront statistiquement plus de chance de l emprunter l
14. ues de l intelligence en essaim d montrent galement toute leur puissance dans le cas de probl mes dont l nonc les donn es ou les param tres varient en permanence sur des chelles de temps tr s courtes C est le cas du routage dans les r seaux de communications ACO PhilippeCollard com 23 04 09 Routage Lorsqu une communication est tablie entre 2 ordinateurs le message initial est d coup en paquets de donn es qui circulent le long d un reseau constitue de lignes de transmission dont les capacit s de debit peuvent tre tres diverses et variables au cours du temps 2 de routeurs qui constituent les n uds de ce r seau ACO PhilippeCollard com 23 04 09 Routage La fonction des routeurs est de D diriger les paquets de donn es vers l un des autres routeurs du r seau et ce jusqu ce que les paquets de donn es arrivent leur destination finale a tenir compte de l importance du trafic sur les voies de communication auquel il est reli de mani re viter l engorgement de ces voies arrive donc tr s souvent que des paquets de donn es d un m me message suivent des voies compl tement diff rentes ACO PhilippeCollard com 23 04 09 Routage par colonie de fourmis Comment ca marche DE IE mm On fait circuler en parallele avec les paguets de donn es des agents de routage sorte de fourmis virtuelles dui 1 analysent en temps r el l tat d encombrement des diff rentes
15. voies du r seau 2 indiquent cet tat chacun des routeurs 3 calculent le temps qu elles mettent pour aller d un n ud du r seau un autre 4 marquent l aide de ph romone virtuelle la voie qu elles viennent d emprunter ACO PhilippeCollard com 23 04 09 Routage par colonie de fourmis Comment ca marche ES e Plus le d lai est court plus l intensit du marquage est importante Ainsi lorsqu un paquet de donn es arrive au niveau d un routeur donn il aura d autant plus de chance d emprunter une voie que la densit de ph romone virtuelle sur cette voie sera importante De cette mani re le r seau s adapte en permanence et de mani re totalement d centralis e l activit du trafic ACO PhilippeCollard com 23 04 09
Download Pdf Manuals
Related Search