蚁群算法——一种新型的优化算法.ppt

《蚁群算法——一种新型的优化算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、蚁群算法——一种新型的优化算法名称：AntColonyOptimization创始人：Dorigo(1993)思路：模拟蚂蚁集群觅食规律基本原理禁忌列表（tabulist）信息素（pheromone）蚁巢障碍物食物BADC111122算法步骤（以TSP为例）初始化蚂蚁随机分布到各个城市环游蚂蚁依次选择路径直到返回出发点更新路径算法核心转移概率的计算i：蚂蚁当前位置；j：蚂蚁可以到达的位置；A：蚂蚁可以到达位置的集合；ηij：启发性信息；τij：i到j的路径的信息素数量算法核心(续)信息素更新Δτijk：蚂蚁k由i到j的路径上留下的单位长度

2、轨迹信息素数量0≤α≤5，1≤β≤5，0.1≤ρ≤0.99，10≤Q≤10000信息素更新与算法在线更新onlineupdate完全模拟蚂蚁运动规律离线更新offlineupdate人为在线更新方式已被可获得更佳效果的离线更新方式所取代信息素更新与算法（续）三种蚁群算法antcolony：精英策略antsystem：更新所有路径antMin-Max：信息素的值限制到Min和Max之间Ant-Q算法将蚁群算法解释成一种增强学习（reinforcementlearning）——Q学习发展现状目前研究和应用主要集中在比利时、意大利、英国、法国、德

3、国等欧洲国家，日本和美国开始启动1998年和2000年在比利时布鲁塞尔大学召开了第一届和第二届蚂蚁优化国际研讨会国内开始有少量公开报道和研究成果严格理论基础尚未奠定，有关研究仍停留在实验探索阶段与遗传算法比较需设置参数少，无交叉变异操作对有些优化问题如TSP效果更佳运行速度慢遗传算法蚂蚁算法iter:迭代次数m:种群规模实际应用——测试集优化问题描述完全测试集最小完全测试集测试集优化问题就是最小完全测试集的求解问题该问题属于NP问题实例演示测试矢量和故障的对应关系矩阵最小完全测试集为(t1,t2,t6)或(t2,t5,t6)求解思路转移概率

4、求解思路（续）启发性信息实验结果与常规算法比较测试集蚁群算法行列消去法8V10F3318V20F3330V32F5740V70F67实验结果（续）与遗传算法比较测试集蚁群算法遗传算法80V100F526100V200F616200V400F61580V1000F710