基于证据理论决策的蚁群优化算法

《基于证据理论决策的蚁群优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9期计算机技术与发展Vo1．19No．82009年8月COMPUTERTECHNOIX~YANDDEVELOPMENTAug．2009基于证据理论决策的蚁群优化算法姜学鹏，洪贝，曹耀钦(第二炮兵工程学院，陕西西安710025)摘要：针对基本蚁群算法中存在的早熟现象，提出了基于证据理论的搜索方法。该方法在每个蚂蚁遍历到某节点时就进行信息融合，并将融合结果动态更新该节点的信息素，使得在蚂蚁个体寻优过程中隔代强化了，并在随机搜索过程中呈现自组织特性，蚂蚁个体利用各自的遍历信息不断加强优秀可行解的权重，从而有效地降低了搜索空间，提高了搜索效率。仿真结果显示，该方法在有无先验知识的情况下，都能

2、在解空间的全局寻优时具有良好的收敛性和鲁棒性。关键词：证据理论；蚁群优化算法：TSP问题中图分类号：TP301．6文献标识码：A文章编号：l673—629X(2009)08—0120—04AntColonyOptimalAlgorithmsBasedonEvidenceTheoryJIANGXue-peng，HONGBei，CAOYao-qin(TheSecondArtilleryEngineeringCollege，Xi’an710025，China)Abstract：Aneffectivemethodbasedonthetheoryofevidenceisputforthtoimp

3、mvethesearchingperformanceofbasicantcolonyalgo．rithms-Aimingatthestagnationphenomenon，awayofintervalstrengtheningisapplied，thusthenewmethodhasagoodabilityoffindingnewsolution．Meanwhile，weightanalysisisadoptedtoadjLLqtthediversionprobabilityandisappliedbyeachagenttostrengthenthosedurablesolutions

4、，whichmakesthestochasticsearchingprocessoftherr~lifiedalgorithmsappearself—organizingcharacteristicsandre．ducethehuntingspherelargelyandimprovethesearchingefficiency．TheresultsofexperimentshowthattheWopo~method，withOrwithoutanypriordistributionknowledgeofdiversionprobability，hasfavorableconverge

5、nceandrobustnessinfindingtheoptimalsolution．Keyw0rd：evidencetheory；antcolonyoptimalalgorithms；TSPproblemO引言以在收敛速度和防止早熟这两者之间找到合适的平衡蚁群算法(antcolonyalgorithm)是由意大利学者点。若过分强调不同路径上的信息素密度的差异虽然Colomi等人与20世纪90年代初期通过模拟自然界中能加快收敛速度但很容易导致停滞现象，从而妨碍对的蚂蚁集体寻径的行为而提出的一种基于种群的启发解空间作进一步搜索以发现更优解，而弱化这种差异式仿生进化算法。该算法可以用于解

6、决许多组合优化又会使整个算法的收敛性变差，可见，通过刷新信息问题，只要能用一个图表来阐述将要解决的问题，并定素，合理地强化不同路径间的差异是影响算法性能的义一种正反馈过程(inTSP问题中的残留信息)，问题重要因素之一。文献[1]提出了基于贝叶斯决策的优结构本身能提供解题用的启发式信息(如TSP问题中化算法，利用贝叶斯决策理论中的后验分析技术作为城市间的距离)，能够建立一种约束机制(如TSP问题刷新信息素的基本准则，在一般情况下能很好地解决收敛速度和防止早熟这两者的矛盾l2，3J。中已访问城市的距离)。相对于一些发展已经比较完备的算法(比如GA、GP、ES)，蚁群算法的优点在于：正在未

7、知时，贝叶斯决策论必须按照等量进行概率分配。称为无差别原理。当只有两种可能性时，无差别反馈，从而能迅速找到好的解决方法；分布式计算可以避免过早收敛；强启发能在早期的寻优中迅速找到合原理就会发生极端情况。例如“地球之外是否有生命”这一命题，在现有科学条件和知识的情况下，两种可能适的解决方案。的概率都应该很小，如果应用主观贝叶斯则会得出两虽然蚁群算法有许多优点，但也存在一些不足：难种可能各占50％之和为1的结论，实际上是两种之和根本不可能等于1。这