网站策划ppt,网站后台怎么做水印图片,泰安做网站公司哪家好,聚名网认证目录
1. 简介
2. 基本思想
3. 研究进展
4. 基本流程
#xff08;1#xff09;路径构建
#xff08;2#xff09;信息素更新
5. 应用举例
6. 改进版
6.1 精华蚂蚁系统
6.2 基于排列的蚂蚁系
6.3 最大最小蚂蚁系
6.4 蚁群系统
7. 参数设置编辑
8. 练习题 …目录
1. 简介
2. 基本思想
3. 研究进展
4. 基本流程
1路径构建
2信息素更新
5. 应用举例
6. 改进版
6.1 精华蚂蚁系统
6.2 基于排列的蚂蚁系
6.3 最大最小蚂蚁系
6.4 蚁群系统
7. 参数设置编辑
8. 练习题 1. 简介 蚁群算法(Ant Colony Optimization,ACO)由Dorigo 等人于1991年在第一届欧洲人工生命会议(European Conference on Artificial Intelligence,ECAL)上提出,是模拟自然界真实蚂蚁觅食过程的一种随机搜索算法。蚁群算法与遗传算法(GeneticAlgorithm,GA)、粒子群优化算法(Particle Swarm OptimizationPSO)、免疫算法(Immune Algorithm,IA)等同属于仿生优化算法,具有鲁棒性强、全局搜索、并行分布式计算、易与其他方法结合等优点,在典型组合优化问题如旅行商问题(Traveling SalesmanProblemTSP)、车辆路径问题(Vehicle Routing ProblemVRP),车间作业调度问题(Job-shop Scheduling Problem,JSP)和动态组合规划问题如通信领域的路由问题中均得到了成功的应用。
2. 基本思想 在自然界中蚂蚁群体在寻找食物的过程中无论是蚂蚁与蚂蚁之间的协作还是蚂蚁与环境之间的交互均依赖于一种被称为信息素Pheromone的物质实现蚁群的间接通信从而通过合作发现从蚁穴到食物源的最短路径。 蚂蚁在寻找食物的过程中往往是随机选择路径的但它们能感知当前地面上的信息素浓度并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短单位时间内经过该路径的蚂蚁多所以信息素的积累速度比较长路径快。因此当后续蚂蚁在路口时就能感知先前蚂蚁留下的信息并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发最终所有的蚂蚁都在最优路径上行进。 通过对自然界蚁群觅食过程进行抽象建模,我们可以对蚁群觅食现象和蚁群优化算法中的各个要素建立一 一 对应关系 3. 研究进展 4. 基本流程
蚂蚁系统Ant SystemAS是最基本的ACO算法是以TSP作为应用实例提出的。
AS对于TSP的求解流程大致可分为两步路径构建和信息素更新。
1路径构建
伪随机比例选择规则random proportional。 对于每只蚂蚁k路径记忆向量按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i则其选择城市j作为下一个访问对象的概率如上式。表示从城市i可以直接到达的、且又不在蚂蚁访问过的城市序列中的城市集合。η(i, j)是一个启发式信息通常由直接计算。表示边(i, j)上的信息素量。 长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。a和b是两个预先设置的参数用来控制启发式信息与信息素浓度作用的权重关系。当a0时算法演变成传统的随机贪心算法最邻近城市被选中的概率最大。当b0时蚂蚁完全只根据信息素浓度确定路径算法将快速收敛这样构建出的最优路径往往与实际目标有着较大的差异算法的性能比较糟糕。
2信息素更新
在算法初始化时问题空间中所有的边上的信息素都被初始化为。算法迭代每一轮问题空间中的所有路径上的信息素都会发生蒸发我们为所有边上的信息素乘上一个小于1的常数。信息素蒸发是自然界本身固有的特征在算法中能够帮助避免信息素的无限积累使得算法可以快速丢弃之前构建过的较差的路径。蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。迭代2直至算法终止。
可以结合下面公式来看哦 m是蚂蚁个数r是信息素的蒸发率规定。是第k只蚂蚁在它经过的边上释放的信息素量它等于蚂蚁k本轮构建路径长度的倒数。表示路径长度它是中所有边的长度和。 5. 应用举例
接着我们结合一个实例来做进一步介绍 步骤2.2中有提到轮盘赌法。是的和我们遗传算法用的是一样的当然后面新的方法会有不一样。
轮盘赌法具体怎么操作在这里稍微解释一下 比方说现在A占比为0.2B占比为0.5C占比为0.3。 则当你随机值大小位于为0-0.2时选A大小位于0.2-0.7时选B大小位于0.7-1.0时选C。
6. 改进版
6.1 精华蚂蚁系统 精华蚂蚁系统Elitist Ant SystemEAS是对基础AS的第一次改进它在原AS信息素更新原则的基础上增加了一个对至今最优路径的强化手段。 引入这种额外的信息素强化手段有助于更好地引导蚂蚁搜索的偏向使算法更快收敛。
6.2 基于排列的蚂蚁系 基于排列的蚂蚁系统rank-based Ant System在AS的基础上给蚂蚁要释放的信息素大小加上一个权值进一步加大各边信息素量的差异以指导搜索。在每一轮所有蚂蚁构建完路径后它们将按照所得路径的长短进行排名只有生成了至今最优路径的蚂蚁和排名在前(ω-1)的蚂蚁才被允许释放信息素蚂蚁在边(i, j)上释放的信息素 的权值由蚂蚁的排名决定。 权值(ω−k)对不同路径的信息素浓度差异起到了一个放大的作用能更有力度地指导蚂蚁搜索。
6.3 最大最小蚂蚁系 最大最小蚂蚁系统MAX-MIN Ant SystemMMAS在基本AS算法的基础上进行了四项改进
只允许迭代最优蚂蚁在本次迭代构建出最短路径的蚂蚁或者至今最优蚂蚁释放信息素。迭代最优更新规则和至今最优更新规则在MMAS中会被交替使用。 如果只使用至今最优更新规则进行信息素的更新搜索的导向性很强算法会很快收敛到T b T_bTb附近反之如果只使用迭代最优更新规则则算法的探索能力会得到增强但收敛速度会下降。实验结果表明对于小规模的TSP问题仅仅使用迭代最优信息素更新方式即可。随着问题规模的增大至今最优信息素规则的使用变得越来越重要。信息素量大小的取值范围被限制在一个区间内。 当信息素浓度也被限制在一个范围内以后位于城市i的蚂蚁k选择城市j作为下一城市的概率也将被限制在一个区间内。算法有效避免了陷入停滞状态所有蚂蚁不断重复搜索同一条路径的可能性。(3)信息素初始值为信息素取值区间的上限并伴随一个较小的信息素蒸发速率。 利好增强算法在初始阶段的探索能力有助于蚂蚁“视野开阔地”进行全局范围内的搜索。随后蚂蚁逐渐缩小搜索范围。(4)每当系统进入停滞状态问题空间内所有边上的信息素量都会被重新初始化。我们通常通过对各条边上信息素量大小的统计或是观察算法在指定次数的迭代内至今最优路径有无被更新来判断算法是否停滞。 有效地利用系统进入停滞状态后的迭代周期继续进行搜索使算法具有更强的全局寻优能力。
6.4 蚁群系统
1997年蚁群算法的创始人Dorigo在“Ant colony system: a cooperative learning approach to the traveling salesman problem”一文中提出了一种具有全新机制的ACO算法——蚁群系统Ant Colony SystemACS进一步提高了ACO算法的性能。 1使用一种伪随机比例规则pseudorandom proportional选择下城市节点建立开发当前路径与探索新路径之间的平衡。 是一个[0, 1]区间内的参数当产生的随机数q≤ 时蚂蚁直接选择使启发式信息与信息素量的指数乘积最大的下城市节点我们通常称之为开发exploitation反之当产生的随机数q 时ACS将和各种AS算法一样使用轮盘赌选择策略我们称之为偏向探索bias exploration。 通过调整我们能有效调节“开发”与“探索”之间的平衡以决定算法是集中开发最优路径附近的区域还是探索其它的区域。
2使用信息素全局更新规则每轮迭代中所有蚂蚁都已构建完路径后在属于至今最优路径的边上蒸发和释放信息素。 其中不论是信息素的蒸发还是释放都只在属于至今最优路径的边上进行这里与AS有很大的区别。因为AS算法将信息素的更新应用到了系统的所有边上信息素更新的计算复杂度为而ACS算法的信息素更新计算复杂度降低为O(n)。参数ρ代表信息素蒸发的速率新增加的信息素 被乘上系数ρ后更新后的信息素浓度被控制在旧信息素量与新释放的信息素量之间用一种隐含的又更简单的方式实现了MMAS算法中对信息素量取值范围的限制。
3引入信息素局部更新规则在路径构建过程中对每一只蚂蚁每当其经过一条边(i, j)时它将立刻对这条边进行信息素的更新。 信息素局部更新规则作用于某条边上会使得这条边被其他蚂蚁选中的概率减少。这种机制大大增加了算法的探索能力后续蚂蚁倾向于探索未被使用过的边有效地避免了算法进入停滞状态。 顺序构建和并行构建。顺序构建是指当一只蚂蚁完成一轮完整的构建并返回到初始城市之后下一只蚂蚁才开始构建并行构建是指所有蚂蚁同时开始构建每次所有蚂蚁各走一步从当前城市移动到下一个城市。对于ACS要注意到两种路径构建方式会造成算法行为的区别。 在ACS中通常我们选择让所有蚂蚁并行地工作。
6.5 连续正交蚁群系统 连续正交蚁群算法Continuous Orthogonal Ant Colony, COAC近年来将应用领域扩展到连续空间的蚁群算法也在发展连续正交蚁群就是其中比较优秀的一种。COAC通过在问题空间内自适应地选择和调整一定数量的区域并利用蚂蚁在这些区域内进行正交搜索、在区域间进行状态转移、并更新各个区域的信息素来搜索问题空间中的最优解。 COAC的基本思想是利用正交试验的方法将连续空间离散化。
7. 参数设置 8. 练习题 洋洋就介绍到这里了我也是初次学请大家指教有问题之间评论或私聊即可看到就会回复哦先说好我不知我什么时候会上线哦有时候一个星期也不来一次的。哈哈哈
