【优化求解】基于matlab蚁群算法配电网故障定位【含Matlab源码 165期】 |
您所在的位置:网站首页 › 蚁群算法与其他算法结合 › 【优化求解】基于matlab蚁群算法配电网故障定位【含Matlab源码 165期】 |
✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。 🍎个人主页:海神之光 🏆代码获取方式: 海神之光Matlab王者学习之路—代码获取方式 ⛳️座右铭:行百里者,半于九十。 更多Matlab仿真内容点击👇 Matlab图像处理(进阶版) 路径规划(Matlab) 神经网络预测与分类(Matlab) 优化求解(Matlab) 语音处理(Matlab) 信号处理(Matlab) 车间调度(Matlab) ⛄一、蚁群算法简介1 引言 在自然界中各种生物群体显现出来的智能近几十年来得到了学者们的广泛关注,学者们通过对简单生物体的群体行为进行模拟,进而提出了群智能算法。其中, 模拟蚁群觅食过程的蚁群优化算法(Ant Colony Optimization, A CO) 和模拟鸟群运动方式的粒子群算法(ParticleS warm Optimization,PSO) 是两种最主要的群智能算法。 蚁群算法是一种源于大自然生物世界的新的仿生进化算法,由意大利学者M.Dorigo, V.Mani ezzo和A.Color ni等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法[1].蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短路径,并且能随环境的变化,适应性地搜索新的路径,产生新的选择。其根本原因是蚂蚁在寻找食物时,能在其走过的路径上释放一种特殊的分泌物――信息素2,随着时间的推移该物质会逐渐挥发,后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越时,其留下的信息素也越来越多,后来蚂蚁选择该路径的概率也就越高,从而更增加了该路径上的信息素强度。而强度大的信息素会吸引更多的蚂蚁,从而形成一种正反馈机制。通过这种正反馈机制,蚂蚁最终可以发现最短路径。 最早的蚁群算法是蚂蚁系统(Ant System, AS) , 研究者们根据不同的改进策略对蚂蚁系统进行改进并开发了不同版本的蚁群算法,并成功地应用于优化领域。用该方法求解旅行商(TSP) 问题、分配问 题、车间作业调度(job-shop) 问题, 取得了较好的试验结果[3-6] 。蚁群算法具有分布式计算、无中心控制和分布式个体之间间接通信等特征,易于与其他优化算法相结合,它通过简单个体之间的协作表现出了求解复杂问题的能力,已被广泛应用于求解优化问题。蚁群算法相对而言易于实现,且算法中并不涉及复杂的数学操作,其处理过程对计算机的软硬件要求也不高,因此对它的研究在理论和实践中都具有重要的意义。 目前,国内外的许多研究者和研究机构都开展了对蚁群算法理论和应用的研究,蚁群算法已成为国际计算智能领域关注的热点课题。虽然目前蚁群算法没有形成严格的理论基础,但其作为一种新兴的进 化算法已在智能优化等领域表现出了强大的生命力。 2 蚁群算法理论 蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。蚂蚁在运动过程中,能够在它所经过的路径上留下信息素进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此来指导 自己的运动方向。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大[7]。 2.1真实蚁群的觅食过程 为了说明蚁群算法的原理,先简要介绍一下蚂蚁搜寻食物的具体过程。在自然界中,蚁群在寻找食物时,它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出 一种特殊的信息素。蚁群算法的信息交互主要是通过信息素来完成的。蚂蚁在运动过程中,能够感知这种物质的存在和强度。初始阶段,环境中没有信息素的遗留,蚂蚁寻找事物完全是随机选择路径, 随后寻找该事物源的过程中就会受到先前蚂蚁所残留的信息素的影响,其表现为蚂蚁在选择路径时趋向于选择信息素浓度高的路径。同时,信息素是一种挥发性化学物,会随着时间的推移而慢慢地消逝。如果每只蚂蚁在单位距离留下的信息素相同,那对于较短路径上残留的信息素浓度就相对较高,这被后来的蚂蚁选择的概率就大,从而导致这条短路径上走的蚂蚁就越多。而经过的蚂蚁越多,该路径上残留的信息素就将更多,这样使得整个蚂蚁的集体行为构成了信息素的正反馈过程,最终整个蚁群会找出最优路径。 若蚂蚁从A点出发,速度相同,食物在D点,则它可能随机选择路线ABD或A CD。假设初始时每条路线分配一只蚂蚁, 每个时间单位行走一步。图5.1所示为经过8个时间单位时的情形:走路线ABD的蚂蚁到达终点:而走路线A CD的蚂蚁刚好走到C点, 为一半路程。 2.2人工蚁群的优化过程 基于以上真实蚁群寻找食物时的最优路径选择问题,可以构造人工蚁群, 来解决最优化问题, 如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高,所以能够最终被所有蚂蚁选择,也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。同时,人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径,而不是盲目的。例如在TSP问题中, 可以预先知道当前城市到下一个目的地的距离。在TSP问题的人工蚁群算法中, 假设m只蚂蚁在图的相邻节点间移动,从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定:一是信息素值,也称信息素痕迹:二是可见度,即先验值。 信息素的更新方式有两种:一是挥发,也就是所有路径上的信息素以一定的比率减少,模拟自然蚁群的信息素随时间挥发的过程;二是增强,给评价值“好”(有蚂蚁走过)的边增加信息素。蚂蚁向下一个目标的运动是通过一个随机原则来实现的,也就是运用当前所在节点存储的信息,计算出下一步可达节点的概率,并按此概率实现一步移动,如此往复,越来越接近最优解。蚂蚁在寻找过程中,或在找到一个解后,会评估该解或解的一部分的优化程度,并把评价信息保存在相关连接的信息素中。 2.3真实蚂蚁与人工蚂蚁的异同 蚁群算法是一种基于群体的、用于求解复杂优化问题的通用搜索技术。与真实蚂蚁通过外信息的留存、跟随行为进行间接通信相似,蚁群算法中一群简单的人工蚂蚁通过信息素进行间接通信,并利用该信息和与问题相关的启发式信息逐步构造问题的解。 人工蚂蚁具有双重特性:一方面,它们是真实蚂蚁的抽象,具有真实蚂蚁的特性:另一方面,它们还有一些真实蚂蚁没有的特性,这些新的特性使人工蚂蚁在解决实际优化问题时,具有更好地搜索较优解的能力。 人工蚂蚁与真实蚂蚁的相同点为: (1)都是一群相互协作的个体。与真实蚁群一样,蚁群算法由一群人工蚂蚁组成,人工蚂蚁之间通过同步/异步协作来寻找问题的最优解。虽然单只人工蚂蚁可以构造出问题的解,但只有当多只人工蚂蚁 通过相互协作,才能发现问题的最优(次优)解。人工蚂蚁个体间通过写/读问题的状态变量来进行协作。 (2)都使用信息素的迹和蒸发机制。如真实蚂蚁一样,人工蚂蚁通过改变所访问过的问题的数字状态信息来进行间接的协作。在蚁群算法中,信息素是人工蚂蚁之间进行交流的唯一途径。这种通信方式在群体知识的利用上起到了至关重要的作用。另外,蚁群算法还用到了蒸发机制,这一点对应于真实蚂蚁中信息素的蒸发现象。蒸发机制使蚁群逐渐忘记过去的历史,使后来的蚂蚁在搜索中较少受到过去较差解的影响,从而更好地指导蚂蚁的搜索方向。 (3)搜索最短路径与局部移动。人工蚂蚁和真实蚂蚁具有相同的任务,即以局部移动的方式构造出从原点(蚁巢)到目的点(食物源)之间的最短路径。 (4)随机状态转移策略。人工蚂蚁和真实蚂蚁都按照概率决策规则从一种状态转移到另一种相邻状态。其中的概率决策规则是与问题相关的信息和局部环境信息的函数。在状态转移过程中,人工蚂蚁和 真实蚂蚁都只用到了局部信息,没有使用前瞻策略来预见将来的状态。 人工蚂蚁和真实蚂蚁的不同点为: (1)人工蚂蚁生活在离散的时间,从一种离散状态到另一种离散状态。 (2)人工蚂蚁具有内部状态,即人工蚂蚁具有一定的记忆能力,能记住自己走过的地方。 (3)人工蚂蚁释放信息素的数量是其生成解的质量的函数。 (4)人工蚂蚁更新信息素的时机依赖于特定的问题。例如,大多数人工蚂蚁仅仅在蚂蚁找到一个解之后才更新路径上的信息素。 2.4蚁群算法的特点 蚁群算法是通过对生物特征的模拟得到的一种优化算法,它本身具有很多优点: (1)蚁群算法是一种本质上的并行算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信。所以蚁群算法可以看作一个分布式的多智能体系统,它在问题空间的多点同时开始独立的解搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。 (2)蚁群算法是一种自组织的算法。所谓自组织,就是组织力或组织指令来自于系统的内部,以区别于其他组织。如果系统在获得空间、时间或者功能结构的过程中,没有外界的特定干预,就可以说系统是自组织的。简单地说,自组织就是系统从无序到有序的变化过程。 (3)蚁群算法具有较强的鲁棒性。相对于其他算法,蚁群算法对初始路线的要求不高,即蚁群算法的求解结果不依赖于初始路线的选择,而且在搜索过程中不需要进行人工的调整。此外,蚁群算法的参 数较少,设置简单,因而该算法易于应用到组合优化问题的求解。 (4)蚁群算法是一种正反馈算法。从真实蚂蚁的觅食过程中不难看出,蚂蚁能够最终找到最优路径,直接依赖于其在路径上信息素的堆积,而信息素的堆积是一个正反馈的过程。正反馈是蚁群算法的重 要特征,它使得算法进化过程得以进行。 3 基本蚁群算法及其流程 4.3基于排序的蚁群算法 基于排序的蚁群算法(Rank-BasedAntSystem)是Bull n heimer、Hartl和Strauss等人提出的[11] 。在该算法中, 每个蚂蚁释放的信息素按照它们不同的等级进行挥发,另外类似于精英蚁群算法,精英蚂蚁在每次循环中释放更多的信息素。在修改信息素路径前,蚂蚁按照它们的旅行长度进行排名(短的靠前),蚂蚁释放信息素的量要和蚂蚁的排名相乘。在每次循环中,只有排名前w-1位的蚂蚁和精英蚂蚁才允许在路径上释放信息素。己知的最优路径给以最强的反馈,和系数w相乘;而排名第r位的蚂蚁则乘以系数“w-(≥0)。信息素如下式所示: %function [bestroute,routelength]=Ant clc clear tic % 读入城市间距离矩阵数据文件 CooCity = load( ‘CooCity.txt’ ) ;% 城市网络图坐标数据文件,txt形式给出 NC=length(CooCity); % 城市个数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))2+(CooCity(i,3)-CooCity(j,3))2); end end % distance=xlsread(‘DistanceCity.xls’); % 城市间距离矩阵数据文件,excel形式给出 MAXIT=10; % 最大循环次数 Citystart=[]; % 起点城市编号 tau=ones(NC,NC); % 初始时刻各边上的信息痕迹为1 rho=0.5; % 挥发系数 alpha=1; % 残留信息相对重要度 beta=5; % 预见值的相对重要度 Q=10; % 蚁环常数 NumAnt=20; % 蚂蚁数量 %bestroute=zeros(1,48); % 用来记录最优路径 routelength=inf; % 用来记录当前找到的最优路径长度 for n=1:MAXIT for k=1:NumAnt %考查第K只蚂蚁 deltatau=zeros(NC,NC); % 第K只蚂蚁移动前各边上的信息增量为零 %[routek,lengthk]=path(distance,tau,alpha,beta,[]); % 不靠率起始点 [routek,lengthk]=path(distance,tau,alpha,beta,Citystart); % 指定起始点 if lengthk |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |