资源描述
第五部分,蚁群优化算法Ant Colony Optimization,参考文献,M. Dorigo and T. Stutzle, Ant Colony OptimizationM: MIT Press, 2004 段海滨，蚁群算法原理极其应用M，2007.科学出版社,0 蚁群优化算法的历史沿革,意大利学者Marco Dorigo（Alberto Colorni）于1991年在其博士论文中提出。 和Vittorio Maniezzo一同设计了第一个ACO算法蚂蚁系统（Ant System）。 在真实蚂蚁觅食行为的启发下提出的一种高度创新性的启发式算法。,Marco Dorigo,Macro Dorigo,重要文献,Colorni等，1994，“Ant System for Job-shop Scheduling” Colorni等，1996，“Heuristics From Natrure for Hard Combinatorial Optimization Problems” Dorigo M等，1996，“Ant system: optimization by a colony of cooperating agents”,Ant system: optimization by a colony of cooperating agents,更加系统地阐述了蚁群算法的基本原理和数学模型； 与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行了仿真实验比较； 把单纯地解决对称TSP拓展到解决非对称TSP、QAP和JSP； 对蚁群算法中的初始化参数对性能的影响做了初步探讨； 蚁群算法发展史上的一篇奠基性文章。,近期发展,2000年，Dorigo M和Bonabeau E等在Nature上发表蚁群算法的研究综述，把这一领域的研究推向了国际学术的最前沿； 进入21世纪的最近几年里，Nature曾多次对蚁群算法的研究成果进行报告。,相关书籍,2004年9月，Marco Dorigo and Thomas SttzleAnt Colony Optimization； 系统介绍蚁群算法，为蚁群算法的传播和科普做出了很重要一步； 2007年翻译成中文出版。,理论建设,在理论建设方面，ACO取得的成果比较少，也是最薄弱的一方面。 1999年Gutjahr W J的技术报告和2000年的论文中首次对蚁群算法的收敛性进行了证明。 将蚁群算法的行为简化为在一幅代表所求问题的有向图上的随机行走过程，进而从有向图论的角度对一种改进蚁群算法图搜索蚂蚁系统（Graph-Based Ant System，GBAS）的收敛性进行了理论分析。 采用的数学工具是Markov链，证明了在一些合理的假设条件下他所提出的GBAS能以一定概率收敛到所求问题的最优解。,蚁群优化算法的发展,精华蚂蚁系统（Elitist Strategy for Ant System，EAS） 对解构造过程中表现优异的人工蚂蚁给予特殊的信息素释放奖励； Ant-Q算法 将蚁群算法与Q学习算法结合，利用多个人工蚂蚁的协同效应； 后期 蚁群系统（Ant Colony System，ACS）， 基于排序的蚂蚁系统（Rank Based version AS，ASrank）， 最大最小蚂蚁系统（Max-Min Ant System，MMAS）,蚁群优化算法的应用,路由类问题 旅行商、车辆路由、顺序排列等 分配类问题 二次分配、图着色、广义分配、频率分配、大学生课程时间表等 调度类问题 工序车间、开放车间、工作流车间、总延迟、总权重延迟、项 目调度、组车间等,蚁群优化算法的应用,子集类问题 多重背包、最大独立集、冗余分配、集合覆盖、带权约束图树分割、边带权l-基树、最大图等 机器学习类问题 分配规则、贝叶斯网络、模糊系统等 网络路由类问题 面向连接的网络路由、无连接的网络路由、光学网络路由等,1 蚁群优化算法的生物学基础,阿根廷蚂蚁 双桥实验,实验结果（1）,摘自Ant Colony Optimization,实验结果（2）,摘自Ant Colony Optimization,实验结果（3）,摘自Ant Colony Optimization,障碍实验,摘自Ant System: Optimization by A Colony of Cooperating Agents,生物蚂蚁的特点,没有视觉 计算与记忆能力有限 依赖信息素(pheromone)通信、协作 释放 挥发 正反馈,2 人工蚁群系统,人工蚂蚁与生物蚂蚁的区别 人工蚂蚁具有一定的记忆能力 人工蚂蚁具有一定的视力（启发） 人工蚂蚁生活在离散的时间环境中,人工蚁群模型,摘自Ant System: Optimization by A Colony of Cooperating Agents,人工蚁群,a) 初始状态； b) t=0，无信息素，人工蚂蚁以等概率选择左 转或右转； c) t=1 ，较短的路径上信息素浓度较高，人工 蚂蚁以较高的概率选择信息素浓度高的路径,实例：TSP,Graph (N,E) Euclidean距离 蚂蚁数量,实例：TSP,人工蚂蚁的行为 路径选择的概率是城市距离和路径上信息素浓度的函数； 符合TSP规则； 完成一次旅行后，在经过的路径上释放信息素； 无需按原路返回。,实例：TSP（参数与机制）,路径上的信息素浓度 信息素更新 信息素释放(ant-cycle),实例：TSP（参数与机制）,路径选择概率,TSP蚁群算法(ant-cycle),Step 1 Initialize: Set t:=0 t is the time counter Set NC:=0 NC is the cycles counter For every edge (i,j) set an initial value for trail intensity and Place the m ants on the n nodes,TSP蚁群算法（ant-cycle）,Step 2 Set s:=1 s is the tabu list index For k:=1 to m do Place the starting town of the k-th ant in tabuk(s),TSP蚁群算法（ant-cycle）,Step 3 Repeat until tabu list is full this step will be repeated (n-1) times Set s:=s+1 For k:=1 to m do Choose the town j to move to, with probability at time t the k-th ant is on town i=tabuk(s-1) Move the k-th ant to the town j Insert town j in tabuk (s),TSP蚁群算法（ant-cycle）,Step 4.1 For k:=1 to m do Move the k-th ant from tabuk(n) to tabuk(1) Compute the length Lk of the tour described by the k-th ant Update the shortest tour found,TSP蚁群算法（ant-cycle）,Step 4.2 For every edge (i,j) For k:=1 to m do,TSP蚁群算法（ant-cycle）,Step 5 For every edge (i,j) compute according to equation Set t:=t+n Set NC:=NC+1 For every edge (i,j) set,TSP蚁群算法（ant-cycle）,Step 6 If (NC NCMAX) and (not stagnation behavior) then Empty all tabu lists Goto step 2 else Print shortest tour Stop,3 蚁群算法调整与参数设置,：信息素的相对重要性； ：启发性因素的相对重要性； ：信息素残留因子； Q ：常数，控制信息素的释放； m ：蚁群规模； 其他： 蚁群的初始分布,信息素释放算法ant-cycle,ant-cycle,信息素释放算法ant-density,ant-density,信息素释放算法ant-quantity,ant-quantity,信息素释放算法对比,测试集： Oliver30 problem 循环次数：NCMAX=5000 测试次数：10,摘自Ant Colony Optimization,GA：424.635,实验数据1 ant-cycle,摘自Ant Colony Optimization,实验数据2 ant-cycle,摘自Ant Colony Optimization,实验数据3 ant-cycle,摘自Ant Colony Optimization,参数：,ant-cycle NCMAX=5000,摘自Ant Colony Optimization,蚁群规模：m,ant-cycle 4x4 grid,摘自Ant Colony Optimization,蚁群初始分布,均匀分布优于集中（单一城市）分布 随机分布略好于均匀分布,算法复杂度,O(NCn2m) step 1 : O(n2+m), step 2 : O(m), step 3 : O(n2m), step 4 : O(n2m), step 5 : O(n2), step 6 : O(nm).,实验数据（算法复杂度）,摘自Ant Colony Optimization,4 实例：JSP,Job-shop Scheduling Problem M:机器数量 J :任务数 ojm:工序 djm:工时 :工序集合,JSP(Muth & Thompson 6x6),JSP,3x2 problem,JSP,路径选择,JSP,待访问节点集合： 下一步允许访问节点集合： 算法结束：,5 实例：PID参数整定,整定参数 目标函数,PID参数整定,Kp=12.345 Td=6.7890 Ti =9.8765 (123456789098765)x(1234567890),PID参数整定,信息素释放,PID参数整定,路径选择概率,6 蚁群优化算法研究现状,蚁群系统（Ant Colony System，ACS） 基于排序的蚂蚁系统（Rank Based version AS，ASrank） 最大最小蚂蚁系统（Max-Min Ant System，MMAS）,蚁群系统ACS,结合Q-learning； ACS采用了更为大胆的行为选择规则； 只增强属于全局最优解的路径上的信息素；,到当前为止全局最优的路径长度,蚁群系统ACS,引入负反馈机制。每当蚂蚁由一个节点移动到另一个节点时，该路径上的信息素按照如下公式被相应的消除一部分，从而实现一种信息素的局部调整，以减小已选择过的路径再次被选择的概率。,最大最小蚂蚁系统MMAS,修改了AS的信息素更新方式； 每次迭代之后只有一只蚂蚁能够进行信息素的更新，以获取更好的解； 为了避免搜索停滞，路径上的信息素浓度被限制在MAX，MIN 范围内； 信息素的初始值被设为其取值上限，有助于增加算法初始阶段的搜索能力。,基于排序的蚂蚁系统ASrank,与“精英策略”相似； 算法中总是更新更好进程上的信息素； 选择的标准是其行程长度决定的排序；,基于排序的蚂蚁系统ASrank,每个蚂蚁释放信息素的强度通过排序加权处理确定。其中，为每次迭代后释放信息素的蚂蚁总数。,
展开阅读全文