辽宁大学智能控制课件蚁群优化算法.ppt

第五部分 蚁群优化算法AntColonyOptimization 参考文献 M DorigoandT Stutzle AntColonyOptimization M MITPress 2004段海滨 蚁群算法原理极其应用 M 2007 科学出版社 0蚁群优化算法的历史沿革 意大利学者MarcoDorigo AlbertoColorni 于1991年在其博士论文中提出 和VittorioManiezzo一同设计了第一个ACO算法 蚂蚁系统 AntSystem 在真实蚂蚁觅食行为的启发下提出的一种高度创新性的启发式算法 MarcoDorigo MacroDorigo 重要文献 Colorni等 1994 AntSystemforJob shopScheduling Colorni等 1996 HeuristicsFromNatrureforHardCombinatorialOptimizationProblems DorigoM等 1996 Antsystem optimizationbyacolonyofcooperatingagents Antsystem optimizationbyacolonyofcooperatingagents 更加系统地阐述了蚁群算法的基本原理和数学模型 与遗传算法 禁忌搜索算法 模拟退火算法 爬山法等进行了仿真实验比较 把单纯地解决对称TSP拓展到解决非对称TSP QAP和JSP 对蚁群算法中的初始化参数对性能的影响做了初步探讨 蚁群算法发展史上的一篇奠基性文章 近期发展 2000年 DorigoM和BonabeauE等在 Nature 上发表蚁群算法的研究综述 把这一领域的研究推向了国际学术的最前沿 进入21世纪的最近几年里 Nature 曾多次对蚁群算法的研究成果进行报告 相关书籍 2004年9月 MarcoDorigoandThomasSt tzle AntColonyOptimization 系统介绍蚁群算法 为蚁群算法的传播和科普做出了很重要一步 2007年翻译成中文出版 理论建设 在理论建设方面 ACO取得的成果比较少 也是最薄弱的一方面 1999年GutjahrWJ的技术报告和2000年的论文中首次对蚁群算法的收敛性进行了证明 将蚁群算法的行为简化为在一幅代表所求问题的有向图上的随机行走过程 进而从有向图论的角度对一种改进蚁群算法 图搜索蚂蚁系统 Graph BasedAntSystem GBAS 的收敛性进行了理论分析 采用的数学工具是Markov链 证明了在一些合理的假设条件下他所提出的GBAS能以一定概率收敛到所求问题的最优解 蚁群优化算法的发展 精华蚂蚁系统 ElitistStrategyforAntSystem EAS 对解构造过程中表现优异的人工蚂蚁给予特殊的信息素释放奖励 Ant Q算法将蚁群算法与Q学习算法结合 利用多个人工蚂蚁的协同效应 后期蚁群系统 AntColonySystem ACS 基于排序的蚂蚁系统 RankBasedversionAS ASrank 最大最小蚂蚁系统 Max MinAntSystem MMAS 蚁群优化算法的应用 路由类问题旅行商 车辆路由 顺序排列等分配类问题二次分配 图着色 广义分配 频率分配 大学生课程时间表等调度类问题工序车间 开放车间 工作流车间 总延迟 总权重延迟 项目调度 组车间等 蚁群优化算法的应用 子集类问题多重背包 最大独立集 冗余分配 集合覆盖 带权约束图树分割 边带权l 基树 最大图等机器学习类问题分配规则 贝叶斯网络 模糊系统等网络路由类问题面向连接的网络路由 无连接的网络路由 光学网络路由等 1蚁群优化算法的生物学基础 阿根廷蚂蚁双桥实验 实验结果 1 摘自AntColonyOptimization 实验结果 2 摘自AntColonyOptimization 实验结果 3 摘自AntColonyOptimization 障碍实验 摘自AntSystem OptimizationbyAColonyofCooperatingAgents 生物蚂蚁的特点 没有视觉计算与记忆能力有限依赖信息素 pheromone 通信 协作释放挥发正反馈 2人工蚁群系统 人工蚂蚁与生物蚂蚁的区别人工蚂蚁具有一定的记忆能力人工蚂蚁具有一定的视力 启发 人工蚂蚁生活在离散的时间环境中 人工蚁群模型 摘自AntSystem OptimizationbyAColonyofCooperatingAgents 人工蚁群 a 初始状态 b t 0 无信息素 人工蚂蚁以等概率选择左转或右转 c t 1 较短的路径上信息素浓度较高 人工蚂蚁以较高的概率选择信息素浓度高的路径 实例 TSP Graph N E Euclidean距离蚂蚁数量 实例 TSP 人工蚂蚁的行为路径选择的概率是城市距离和路径上信息素浓度的函数 符合TSP规则 完成一次旅行后 在经过的路径上释放信息素 无需按原路返回 实例 TSP 参数与机制 路径上的信息素浓度信息素更新信息素释放 ant cycle 实例 TSP 参数与机制 路径选择概率 TSP蚁群算法 ant cycle Step1Initialize Sett 0 tisthetimecounter SetNC 0 NCisthecyclescounter Foreveryedge i j setaninitialvaluefortrailintensityandPlacethemantsonthennodes TSP蚁群算法 ant cycle Step2Sets 1 sisthetabulistindex Fork 1tomdoPlacethestartingtownofthek thantintabuk s TSP蚁群算法 ant cycle Step3Repeatuntiltabulistisfull thisstepwillberepeated n 1 times Sets s 1Fork 1tomdoChoosethetownjtomoveto withprobability attimetthek thantisontowni tabuk s 1 Movethek thanttothetownjInserttownjintabuk s TSP蚁群算法 ant cycle Step4 1Fork 1tomdoMovethek thantfromtabuk n totabuk 1 ComputethelengthLkofthetourdescribedbythek thantUpdatetheshortesttourfound TSP蚁群算法 ant cycle Step4 2Foreveryedge i j Fork 1tomdo TSP蚁群算法 ant cycle Step5Foreveryedge i j computeaccordingtoequationSett t nSetNC NC 1Foreveryedge i j set TSP蚁群算法 ant cycle Step6If NC NCMAX and notstagnationbehavior thenEmptyalltabulistsGotostep2elsePrintshortesttourStop 3蚁群算法调整与参数设置 信息素的相对重要性 启发性因素的相对重要性 信息素残留因子 Q 常数 控制信息素的释放 m 蚁群规模 其他 蚁群的初始分布 信息素释放算法ant cycle ant cycle 信息素释放算法ant density ant density 信息素释放算法ant quantity ant quantity 信息素释放算法对比 测试集 Oliver30problem循环次数 NCMAX 5000测试次数 10 摘自AntColonyOptimization GA 424 635 实验数据1ant cycle 摘自AntColonyOptimization 实验数据2ant cycle 摘自AntColonyOptimization 实验数据3ant cycle 摘自AntColonyOptimization 参数 ant cycleNCMAX 5000 摘自AntColonyOptimization 蚁群规模 m ant cycle4x4grid 摘自AntColonyOptimization 蚁群初始分布 均匀分布优于集中 单一城市 分布随机分布略好于均匀分布 算法复杂度 O NC n2 m step1 O n2 m step2 O m step3 O n2 m step4 O n2 m step5 O n2 step6 O n m 实验数据 算法复杂度 摘自AntColonyOptimization 4实例 JSP Job shopSchedulingProblemM 机器数量J 任务数ojm 工序djm 工时 工序集合 JSP Muth Thompson6x6 JSP 3x2problem JSP 路径选择 JSP 待访问节点集合 下一步允许访问节点集合 算法结束 5实例 PID参数整定 整定参数目标函数 PID参数整定 Kp 12 345Td 6 7890Ti 9 8765 123456789098765 x 1234567890 PID参数整定 信息素释放 PID参数整定 路径选择概率 6蚁群优化算法研究现状 蚁群系统 AntColonySystem ACS 基于排序的蚂蚁系统 RankBasedversionAS ASrank 最大最小蚂蚁系统 Max MinAntSystem MMAS 蚁群系统ACS 结合Q learning ACS采用了更为大胆的行为选择规则 只增强属于全局最优解的路径上的信息素 到当前为止全局最优的路径长度 蚁群系统ACS 引入负反馈机制 每当蚂蚁由一个节点移动到另一个节点时 该路径上的信息素按照如下公式被相应的消除一部分 从而实现一种信息素的局部调整 以减小已选择过的路径再次被选择的概率 最大最小蚂蚁系统MMAS 修改了AS的信息素更