rapport du projet

《rapport du projet》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、RapportduprojetOptimisationduvoyageurparcoloniedefourmisPréparépar :Annéeuniversitaire :2010/201116Sommaire1.L’énoncéduprojet …………………………………………………………………………………12.Tableauxdesdistances ……………………………………………………………………………...22.1 VillesFrançaise………………………………………………………………..22.2VillesChinoises

2、…………………………………………………………..……..23.Descriptionetexplicationduprojet………………………………………………………..34.Descriptiongénéraledel’algorithme…………………………………………………….45.Notice…………………………….………………………………………………………………….....55.1-Tableauxdesvariables...........................................................

3、...................55.2-Tableauxdesfonctions………………………………………..……………65.3-Tableaudesfichiers………………………....……………………….……...76.Arbredesfonctions…………………………..…………………………………………….…….77.Exemplesdel’exécution…………………………………………………………………..……88.Conclusion…………………………………………………………………………………..……...1216

4、***optimisationduvoyageurparcoloniedefourmis***1-SujetduprojetLeproblèmeduvoyageurdecommerceestreprésentéparungraphecompletdontlesnnœudsreprésententlesvilles(ilfautaumoinsn=30).Résoudreleproblème,c'esttrouverlepluscourtcheminquedoitprendrelevoyageurpourvisitertouteslesvillesetr

5、eveniràsonpointdedépart.LesarcssontpondérésparlesdistancesdijentrecesvillesetparuneautrepondérationTRij(t)quireprésentelatracedephéromonelaisséeparlesfourmis.Onappellegénérationunesuccessionden-1étapesoùchaquefourmiauravisitélesnvilles.Initialement,onplaceradeuxfourmisparville.

6、OninitialiseTRij(0)demanièrealéatoireentre0et1oubienparleréeln/LavecLlongueurdevisitedesnvillesenprenanttoujoursleplusprochevoisin.Chaquefourmikpossèdeuneliste"tabou"TLkdesvillesdéjàvisitéesetsemeutaléatoirementsuivantlaprobabilitéqu'ilpassedunoeudiàj.Cetteprobabilitéestproport

7、ionnelleàTRij/dij^7(plusilyadephéromones,etplusladistanceestcourte,etpluslafourmiadechancedeprendrecechemin).Pourchaquevilleietchaquefourmikprésenteeni,siTLk(t)n'estpascomplète,onchoisitlavillejaléatoirementparmicellesdeplusforteprobabilité,jestempilédansTLk(t)pourformerTLk(t+1

8、),etlafourmikpasseenj.Lesphéromonessontmisesàjourselon