一文搞懂什么是蚁群优化算法(Ant Colony Optimization, ACO)【附应用举例】 |
您所在的位置:网站首页 › 什么叫做信息素 › 一文搞懂什么是蚁群优化算法(Ant Colony Optimization, ACO)【附应用举例】 |
Python代码链接放文末。 本文参考了很多张军老师《计算智能》的第五章知识。 本文来源:https://blog.csdn.net/qq_44186838/article/details/109181453 蚁群优化算法 总感觉这些数学家们怎么都这么聪明。 有句话叫“艺术源于生活”,但其实数学也来源于生活哈哈。 1.1 基本原理 先来聊下该算法的思想来源: 自然界蚂蚁群体在寻找食物的过程中,通过一种被称为信息素(Pheromone)的物质实现相互的间接通信,从而能够合作发现从蚁穴到食物源的最短路径。 通过对这种群体智能行为的抽象建模,研究者提出了蚁群优化算法(Ant Colony Optimization, ACO),为最优化问题、尤其是组合优化问题的求解提供了一强有力的手段。 蚂蚁在寻找食物的过程中往往是随机选择路径的,但它们能感知当前地面上的信息素浓度,并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放,是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短,单位时间内经过该路径的蚂蚁多,所以信息素的积累速度比较长路径快。因此,当后续蚂蚁在路口时,就能感知先前蚂蚁留下的信息,并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发,最终所有的蚂蚁都在最优路径上行进。
AS对于TSP的求解流程大致可分为两部:路径构建和信息素更新。 (1)路径构建 伪随机比例选择规则(random proportional)。 长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。a和b是两个预先设置的参数,用来控制启发式信息与信息素浓度作用的权重关系。当a=0时,算法演变成传统的随机贪心算法,最邻近城市被选中的概率最大。当b=0时,蚂蚁完全只根据信息素浓度确定路径,算法将快速收敛,这样构建出的最优路径往往与实际目标有着较大的差异,算法的性能比较糟糕。 (2)信息素更新 在算法初始化时,问题空间中所有的边上的信息素都被初始化为t0。算法迭代每一轮,问题空间中的所有路径上的信息素都会发生蒸发,我们为所有边上的信息素乘上一个小于1的常数。信息素蒸发是自然界本身固有的特征,在算法中能够帮助避免信息素的无限积累,使得算法可以快速丢弃之前构建过的较差的路径。蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。迭代(2),直至算法终止。看不懂?那结合下面公式来看。
通过调整q0,我们能有效调节“开发”与“探索”之间的平衡,以决定算法是集中开发最优路径附近的区域,还是探索其它的区域。 (2)使用信息素全局更新规则,每轮迭代中所有蚂蚁都已构建完路径后,在属于至今最优路径的边上蒸发和释放信息素。
(3)引入信息素局部更新规则,在路径构建过程中,对每一只蚂蚁,每当其经过一条边(i, j)时,它将立刻对这条边进行信息素的更新。 1.3.5 连续正交蚁群系统 连续正交蚁群算法(Continuous Orthogonal Ant Colony, COAC):近年来,将应用领域扩展到连续空间的蚁群算法也在发展,连续正交蚁群就是其中比较优秀的一种。COAC通过在问题空间内自适应地选择和调整一定数量的区域,并利用蚂蚁在这些区域内进行正交搜索、在区域间进行状态转移、并更新各个区域的信息素来搜索问题空间中的最优解。 COAC的基本思想是利用正交试验的方法将连续空间离散化。 1.4 参数设置 代码下载链接,有需要的请自行提取,不想hua前的朋友,可评论同我说,我会回复你,但可能会比较慢。祝好! https://download.csdn.net/download/qq_44186838/62603929 智能优化算法大礼包 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |