基于规划图的蚁群规划算法

《基于规划图的蚁群规划算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据计算机研究与发展ISSNi000—12391CN11—1777／TPJournalofComputerResearchandDevelopment46(9)：1471—1479，2009基于规划图的蚁群规划算法柴啸龙1’2姜云飞1陈蔼祥21(中山大学软件研究所广州510275)2(广东商学院数学与计算科学学院广州510320)(chaixiaolongok@163．corn)AntColonyPlanningAlgorithmBasedonPlanningGraphChaiXiaolon91”，JiangYunfeil。

2、andChenAixian921(InstituteofSoftware，SunYat—senUniversity，Guangzhou510275)2(SchoolofMathematicsandComputingScience，GuangdongUniversityofBusinessStudies，Guangzhou510320)AbstractGraphplanisanimportantalgorithmofintelligentplanninginrecentyears．Ithaspromotedgreatdevelop

3、mentofintelligentplanning．Firstly，theGraphplanalgorithmwillgenerateflplanninggraphbyactionlevelexpandingandpropositionlevelexpandingalternatively．Secondly，avalidplanwillbeextractedfromtheplanninggraphbybacktrackinginexhaustiveway．Theplanextractingofthealgorithmalways

4、consumetoomuchtimeinthisway．Andthealgorithmisapttoplungeintothelocalsearching．Inthispaper，awayofplansolutionsearchingbyusingtheantcolonyalgorithmisgiven．ThatistheACP(antcolonyplanner)algorithm．Intheantcolonyalgorithm，positivefeedbackanddistributedcoordinationareusedt

5、ofindthesolutionpath．Andtheantcolonyalgorithmevenhasthecharacteristicofrobustness，thusithasbeensuccessfullyappliedinmanyapplicationswhichareNP-hardproblems．ThesearchingoftheACPhasthecharacteristicofglobalandparallelsearching．AndACPhastheabilityofconvergenceaccelerati

6、oninthesolutionsearching．TheexperimentsshowthatACPisadvantageOUSespeciallyinsolvingthelargescaleplanningproblems．Toabsorbtheoptimizingtechniqueandthelearningtechniqueisarisingwayinthestudyoftheintelligenceplanning．Sincetheantcolonyplanningalgorithmisjustbasedontheopt

7、imizingtechnique，thustheantcolonyplanningalgorithmispromisingtomakesomebetterprogressesinthestudyofintelligenceplanningareabyusingtheantcolonyplanningmethod．Keywordsintelligenceplanning；planninggraph；antcolonyalgorithm；parallelsearching；convergenceacceleration摘要图规划是智

8、能规划领域近年来出现的一种重要规划方法，对智能规划的发展起到了很重要的推动作用，图规划算法首先扩展生成规划图，然后通过逐层组合不断回溯的穷举方式进行解提取，这种方式使解提取不仅耗时而且容易陷入局部搜索中．在规划图基础上定义了蚁群智能体，并定义了在规划图上的蚁群搜