蚁群优化算法（共12篇）
蚁群优化算法 篇1
1引言
蚁群算法源于1992年一篇博士论文提出的模拟蚂蚁寻找食物所选路径的概率型找寻最优解的方案,这种算法本质是基于一定规则的随机运行来寻找最优方案,模仿蚂蚁寻找和搬运食物时释放信息素的机理,不断优化行走路线,在算法实现中执行时间越长,所获得的路径就越可能接近最优路径。
蚁群优化算法已应用于许多组合优化问题,例如二次分配问题,还有很多实变量动力学问题、随机问题、多目标并行的实现等方面,但在实际算法中需要避免的一个问题是过早收敛的问题,算法在执行中很快陷入到了局部最优解的搜索,难以实现广度搜索。因此,在标准算法基础上出现了优化算法,这些优化算法主体通过对于信息素的调节,防止过早收敛问题。在优化算法中核心在于平衡广度搜索与深度搜索, 保证算法的执行效率、有效性。本文通过对目前常见的蚁群优化算法进行综合分析与比较, 较为清晰的梳理出常见优化算法的特点,有助于在解决实际问题中选择合适方法以及算法优化。
2常见蚁群算法的优化算法
标准蚁群算法存在收敛慢、易停滞、运算时间长等缺陷,后续对其做了一系列的改进,以解决该算法存在的问题,产生了许多改进型算法。下面将介绍三种最典型的改进算法:蚁群系统算法(ACS)、最大最小蚁群系统算法(MMAS)、具有变异特征的蚁群算法。
2.1蚁群系统算法
蚁群系统算法(ACS)是对蚁群算法(AC)的改进,这些改进包括:蚂蚁选择的状态转移规则;全局最优更新规则仅运用于属于最优解路径上的信息素;对所有的路径的信 息量进行 局部更新 规则 (Local UpdatingRule)。在ACS中 ,全局更新只是运用在每一次循环中走最优解路径的蚂蚁,而不再运用与所有的蚂蚁。在所有的蚂蚁搜完成了一次循环后,全局更新才会执行。
2.2最大最小蚁群系统算法
最大最小 蚁群系统 算法 (Max-Min Ant System,MMAS) 是解决TSP、QAP等问题的经典蚁群优化算法之一,其结果要优于一般的蚁群算法。MMAS与ACS一样都只允许在每次迭代中表现最好的蚂蚁更新其路径上的信息素, 这样做可以防止算法过早的出现停滞现象。而MMAS与ACS相比不同的地方在于防止这种停滞现象的方法。MMAS的做法为:限定信息素浓度允许值的上下限,并且采用平滑机制。在算法启动时,MMAS将所有路径上的信息素浓度初始化为最大值。在每次循环之后, 只有在最佳路线上的蚂蚁进行信息素的更新,并将其保持在一个高的水平上,其他之路上的信息素将会按照信息素残留度降低浓度。
2.3与变异结合的蚁群算法
吴庆洪等人提出了一种优化蚁群算法———具有变异特征的蚁群算法。其核心思想为采用逆转变异方式,随机地进行变异,以增大进化时所需的信息量,从而克服传统蚁群算法收敛较慢的问题。这种变异机制之所以会具有较快的收敛速度,是因为它充分利用了2-OPT交换法简洁高效的特点。
3蚁群算法优化的新策略
对蚁群算 法所作的 优化是在 已有的改 进型算法———ACS算法的基础上进行的,下文即将描述的优化途径也都是在前人所做改良(即ACS已有的改良途径)的基础上作的更进一步的改进。
3.1路径选择机制的改良
在ACS的路径选择策略中, 我们需要对ij边上已有的信息进行有效的利用,而对于变量q的设定,存在着很大的偶然性使得我们不能很有效地利用已有信息。对此,为了进一步对已有知识加以充分利用,新变量(∑ijk)/m被引入用以替代变量q,其中∑ijk表示上一次循环中选择路径ij的蚂蚁个体的总数。在q0确定的情况下,∑ijk将伴随着算法的运行而随之增大,从而使蚂蚁个体能在下一次路径选择中优先利用已有的信息来选择将要前往的城市,进一步地提高了算法的搜索性能。
3.2全局信息素更新机制的改进
对于信息素的全局更新,我们不仅仅要运用在每一次循环中走最优解路径的蚂蚁,还要运用与每一次循环中最差的蚂蚁使用。但是对于最差蚂蚁的全局更新规则与走最优解路径蚂蚁的规则不同,其更新规则采用如下的公式
τij(t)←(1-ε)×τij(t)+ε×△τij(t) ;
其中,ε为区间(0,1)上的参数;而△τij(t)则用如下的公式计算:
△τij(t)= Q/L - Q/L’若ij路径是算法已求出的最差路径的一部分
或 = 0若ij路径不是已求出的最差路径的一部分 ;
在ACS算法的基础上, 增加对最差的蚂蚁采用以上的更新机制,能更有效地模拟蚂蚁在自然界的觅食过程中分泌的信息素,能准确得出路径长度与时间之间的关系,可使得更多的已有知识被利用,同时在后续的循环中能够增加好的路径被选择的概率并减少差的路径被选择的概率,这样算法的性能可以大大提高。
3.3增加最小信息素浓度设置
MMAS给每一条支路都设置了一个最小信息素浓度,在算法运行过程中,各个支路的信息素浓度不会降到τmin以下。这样保证了即使没有任何一只蚂蚁选择走某条路径,在再一次的循环中这条路径依然有一定的概率被选中,从而避免了一些可能存在的好的路径被过载地抛弃,同时也避免了算法过早地收敛。设置了一个最小信息素浓度τmin,它的计算公式为:
τmin = 1/[2n?(1-ρ)?L] ;
n表示当前问题的城市节点数 ,ρ为信息素残留度 ,L为算法运算到当前为止,已求出的最优路径的长度 ;为了保证所有路径上的信息素浓度不低于τmin,每当一次循环中的信息素局部及全局更新完成后,就需要比较τij和τmin,如果τij<τmin,则将τij强行设置为τmin。
3.4杂交算子的引入
遗传算法具有良好的搜索能力,引入了杂交算子来对现有的所有解进行重组,这样可以发现潜在的更好的解。我们现在尝试一种新的增强解的方法:杂交算子被引入到ACS算法中, 以对在算法运行过程中产生的新的解进行杂交, 并充分利用当前所知的所有路径信息,两者结合可以发现更好的解,从而对最终我们希望得到的结起了增强作用。
4结束语
蚁群算法作为组合优化的经典算法,在实际问题的应用中仍然存在一些问题,这些问题需要进一步研究。
(1)正反馈机制的建立 ,启发函数的定义 ,求解问题增式的进行,以及最优解与问题定义中的现实世界的况相对应等问题需要考虑。
(2)在开始运行蚁群算法求解问题时 ,需要对大量的变量进行初始化,这些变量的初始值会对算法的性能产生较大的影响。然而这些变量初始值的选取方法和原则在目前还没有一个理论上的依据,只能在多次实验中积累经验从而选择比较好的值。因此在初始化变量的最佳值设置问题上还有待进一步的研究。
摘要：对于求解TSP问题,新型的启发式算法——蚁群算法,是成功解决此类问题核心的算法之一。本文简要介绍了几种启发式算法并引出蚁群算法,并对蚁群算法基本原理、常用算法进行了深入的研究,并介绍了一种新的优化策略。
关键词：TSP问题,蚁群算法,优化策略
蚁群优化算法 篇2
基于蚁群算法的无人机航路规划
为了提高无人机(UAV)作战任务的成功率,在执行敌方防御区域内攻击任务前必需规划设计出高效的无人机飞行航路,保证无人机能够以最小的被发现概率及可接受的`航程到达目标点.针对这一问题,对新近发展的蚁群算法进行了讨论,提出适用于航路规划的优化方法,并对无人机的攻击任务航路进行了仿真计算.仿真结果表明该方法是一种有效的航路规划方法.
作 者：柳长安 李为吉 王和平作者单位：西北工业大学,航空学院,陕西,西安,710072刊 名：空军工程大学学报(自然科学版) ISTIC PKU英文刊名：JOURNAL OF AIR FORCE ENGINEERING UNIVERSITY (NATURAL SCIENCE EDITION)年，卷(期)：5(2)分类号：V279关键词：无人机 航路规划 蚁群算法 生物信息激素
蚁群优化算法 篇3
摘要：蚁群优化算法作为单目标优化问题，由于只有一个目标函数，通常会将解限制到特定的范围内。当优化的目标不恰当时，算法可能失效，比如分辨率限制问题。我们将多目标优化的思想与传统的用于社区检测的蚁群优化算法相结合，增加了目标函数个数，即增加了解的评价指标数目。该算法引入多目标策略，提出多目标ACO算法，该算法在一次运行过程中会产生一组Pareto最优解。并在三个真实世界网络证明该算法的有效性和准确性。
关键词：复杂网络；社区检测；蚁群优化算法；多目标优化
中图分类号：TP18文献标识码：A
1引言
1991年意大利学者Dorigo M等人首次提出了蚁群优化算法[1，2]引起了学者的广泛关注与研究。蚁群算法是一种基于种群的启发式仿生进化系统，该算法采用了正反馈分布式并行计算机制，易于与其它方法相结合并且具有较强的鲁棒性。
本文介绍了一种基于蚁群优化的多目标社区检测方法，将蚁群优化算法与多目标策略[3]相结合，是一种优化模块度的社区检测方法。对于多目标优化问题，通常无法得到最优解，若同时考虑多个目标函数则算法将会得到一组优于其它解的最优解集。该集合叫做帕雷托（Pareto）解集或者非支配解集。
2基于蚁群优化的多目标社区检测
蚁群优化算法（ACO），是一种基于蚂蚁觅食行为的启发式方法，用来解决困难的组合优化问题，并且已经成功的应用到了各种棘手的问题，像二次分配问题（QAP），车辆路径问题（VRP）等。在1996年，Gambardella等人提出了一种修正的蚁群优化算法——蚁群系统（Ant System，AS），已经成功地应用在旅行商问题上。在这之后，科学家们也发明了一些改进的算法，比如精英蚁群系统（Elitist Ant System，EAS），最大最小蚁群系统（MaxMin Ant System，MMAS）以及排序蚁群系统（RankBased Ant System，ASrank）。
运用蚁群优化来做社区检测，首先需要指出如何表达一个解，其次就是如何构建一个解，然后就是信息素的初始化以及更新。下面我们将详细描述该算法。
2.1编码方式
社区就是复杂网络的子图，因而检测社区结构就等价于找出能揭示网络最好分割的一组子图。因此，社区检测问题的解可以明确地表示为：一个n个元素的向量表示图，其连通分量相当于社区。向量的元素和索引对应于图G=（V，A）中的节点。例如，向量中第i个元素等于j，即节点Vi和Vj之间有边相连，也就是说这两个节点在同一个连通分量里面，即处于同一个社区。
该编码框架的优点有很多，最重要的是不需要预先知道复杂网络的社区划分数目。解码的过程需要找出所有的连通分量。所有属于同一个连通分量的节点被划分到一个社区，解码过程是有必要的且可以通过广度优先搜索（breadthfirst search，BFS）或者深度优先搜索（depthfirst search，DFS）在线性时间内完成。解码完成后，会得到一个表示每个节点归属的向量。这种基于基因近邻的编码框架已经应用到了多目标聚类领域。该框架在社区检测的应用中有几个主要的优点，最重要的是，不需要预先知道社区的真实划分数目K，因为在解码过程中能够自动地得到K的取值。
3.1真实世界网络
本节将MOACO算法应用在三个真实世界网络上，分别是Zacharys Karate Club、Bottlenose Dolphins、Books about US politics。以上复杂网络是社会网络分析领域中的经典数据集，将这些数据在并与没有加入多目标策略的ACO算法以及GA、GAloacal算法进行了对比。由表2可以看出，三十次独立运行后，在Zacharys Karate Club网络中，ACO和MOACO的平均模块度值均不如GA和GA-local算法的结果好，而MOACO和ACO的平均模块度相差不大；在Dolphin social network网络中，本文提出的MOACO算法的平均NMI值明显好于其它算法。在Dolphin social network网络中，MOACO算法的模块度Q平均值与ACO算法的结果相差不大，而NMI的平均值要好于ACO算法。
为了验证蚁群规模和迭代次数对算法的影响，以Zacharys Karate Club网络为例进行参数分析，参数α、β、T、ρ、ε的值不变化，算法独立运行三十次求平均模块度值Q和平均NMI值，讨论蚁群规模N对算法结果的影响。
由表3可以看出，随着蚁群规模的增加，平均模块度值呈增长趋势，在蚁群规模为80时，达到了最大值。而由于蚁群优化算法中蚂蚁个体选择路径是随机的，因而平均NMI值没有呈现一定的规律，而当蚁群规模为40时，平均NMI值取得最大值。
表4表示参数α、β、N、ρ、ε保持不变，讨论迭代次数T对算法结果的影响，算法独立运行三十次的算法结果如表4所示。
由表4可知，迭代次数对算法的平均模块度值影响不大，而当迭代次数为150次的时候，平均NMI值取得了最大值。
图2表示调节参数过程中，算法取得的最优结果，即每一次运行的模块度值和NMI值，data1表示平均模块度值，data2表示平均NMI值。最优参数为：迭代次数150次，种群规模40。可以看出模块度值非常稳定。
3.2计算机仿真网络
本节使用经典的GN benchmark复杂网络来检测算法的可行性和有效性。GN基准网络是由Newman等提出。对于该基准网络，每个图包含了128个节点，分为4个由32个节点构成的社区。每个节点平均有Zin条边与同社区内节点连接，Zout条边与社区外节点连接。其中Zin+Zout = 16，作为每个节点的期望的度。随着Zout的增大，所产生的随机网络给社区检测算法带来了更大的挑战。特别是当Zout大于8时，意味着每个节点在社区内的边都要小于社区外的边，这时网络的社区结构就会非常模糊。当Zout≤ 8时，节点外度所占的比例小于内度所占的比例，因此算法应该能检测出网络中存在的社区结构，当Zout = 0时，表明节点的外度为0，此时节点仅与自身社区内的节点相连接，社区结构非常明显。分别对Zout从0到2进行了测试，对每种类型的网络产生一个复杂网络，使用NMI来衡量算法检测的结果和真实网络划分之间的相似性。对于每个网络，计算三十次独立运行的平均值。
由表5可以看出，当GN网络的外度为0时，该算法可以准确地检测出网络划分情况；当GN网络的外度为1和2的时候，该算法得到的结果也还都是有效的。
但是，在蚁群优化方法中，其算法复杂度比较高，所需要的搜索时间很长，而且容易出现所有的蚂蚁所对应的解完全相同这种“停滞现象”。导致了当复杂网络的社区数目较大时，算法不能产生有效解。另外，该算法对计算机生成的仿真网络不能得到有效的结果，这是我们进一步研究的内容。
4小结
基于传统的蚁群优化算法（ACO）算法的缺陷，提出了一种用于复杂网络社区检测的多目标蚁群优化算法MOACO，该算法将继续沿用传统的基于模块度优化的策略，加入了多目标的思想，每次迭代过程中，根据两个目标函数的不同折中，最终得到Pareto解集，选取每一代中优先级最高的那一组解。在三个真实世界网络和GN网络中的外度较小的网络上证明了算法的有效性，并将提出算法与ACO算法进行了比较，NMI平均值要优于ACO算法，模块度Q的平均值与ACO算法相当。缺点是不能处理社区划分类别多的复杂网络，对于结构模糊的GN网络，算法的效果不明显。
参考文献
[1]HONGHAO C， ZUREN F， ZHIGANG R. Community detection using ant colony optimization [C] Evolutionary Computation （CEC）， 2013 IEEE Congress on. IEEE， 2013： 3072-3078.
[2]DORIGO M，BIRATTARI M，STUTZLE T. Ant colony optimization[J]. Computational Intelligence Magazine， IEEE， 2006， 1（4）： 28-39.
[3]SOLNON C， Ghédira K. Ant colony optimization for multi-objective optimization problems[J]. Internation Journal on computer science， 2010.
[4]GONG M， CAI Q，CHEN X， et al. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition[J]. Evolutionary Computation， IEEE Transactions on， 2014， 18（1）： 82-97.
蚁群优化算法应用研究 篇4
蚁群算法本质是一个复杂的智能搜索算法,具有较强的鲁棒性、良好的正反馈性能、优良的分布式计算机制、易于与其他优化算法相结合等特点。如今,该算法已经成为智能优化算法中的研究热点,对它的研究已经渗入到多种不同的应用领域。
1 基本蚁群算法原理
在自然界中,单个的蚂蚁个体行为极为简单,但由多个蚂蚁所组成的群体却成功地在搜寻食物等方面表现出复杂的行为。研究发现,蚂蚁总能找到巢穴与食源之间最短路径。蚁群算法就是借鉴和吸取现实世界中蚂蚁这种集体寻径行为来寻求函数的最优解。
蚂蚁个体之间通过一种称为信息素的物质进行信息传递,蚂蚁在移动过程中通过感知遗留在路径上的该种物质来指导自己的运动方向,并在自己经过的路径上留下该类物质。这样,大量蚂蚁所组成的群体便构成了一种信息正反馈,从而成功地实现了食物搜索,最短路径选择等行为。为了具体说明蚁群算法的原理,举出人工蚁群路径搜索的例子。
如图1所示,路径AB、ED、DH、HB长度分别为1,BC和BD长度分别为0.5。如图1(a)所示,在t=0时刻,有30只蚂蚁分别在A点和B点,蚂蚁单位时间内行程为1并留下1个浓度的信息素。如图1(b)所示,在t=1时刻,A点和E点的蚂蚁同时到达B点和E点,由于此前路径上没有信息素,它们随机选取路径,在DH、HB、BC、DC上将各有15只蚂蚁。如图1(c)所示,在t=2时刻,将有30只蚂蚁到达H点,而有15只蚂蚁分别到达B点和D点,在这段时间内,遗留在BC、CD上的信息素将是DH或是HB的两倍。而蚂蚁是根据遗留在路径上信息素的强弱来选择自己前进的方向,信息素强路径的将会吸引更多的蚂蚁,因此在后续的选择中,选择DC或是BC蚂蚁数量将是DH和HB的两倍,所以,20只蚂蚁选择BC,10只选择BH。如此反复进行下去,直至所有的蚂蚁都选择最短的路径BCD或是DCB。通过上面的例子,可以简单的说明蚁群算法主要的特点:
1)正反馈性。蚂蚁群体行为表现出正反馈过程,通过反馈机制的调整,可对系统的较最优解起到一个自增强的作用,从而使问题的解向着全局最优的方向演变,最终能有效的获得全局最优解。
2)并行性。蚁群算法是一个本质并行的算法,个体之间不断的进行信息的交流与传递,相互协作,有利于最优解的发现,从而在很大程度上减少了陷于局部最优的可能。
2 算法描述[1]
蚁群算法首次提出是用于解决TSP问题,因此我们就以求解n个城市的TSP问题为例来说明基本蚁群算法的求解过程。
TSP问题是一个典型的离散优化问题。其定义是:给定n个城市,TSP等价于寻找一条只经过各个城市一次且长度最短的闭合路径。令dij为城市i和j之间的距离,在欧式空间中,。。
假设蚁群数量为m,τkij(t)表示t时刻在ij上遗留的信息素。在初始时刻,各条路径上的信息素是相等的,τij(0)=C(C为常数),蚂蚁k(k=1,2,,m)在运动的过程中根据各条路径上遗留的信息素决定移动方向。pkij(t)表示t时刻蚂蚁k由城市i选择城市j的转移概率
allowedk={0,1,………,n-1}表示蚂蚁k下一步允许选择的城市,α和β分别反映了蚂蚁在运动的过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性,ηij为由城市i转移到城市j的期望程度,在TSP问题中取ηij=1/dij。建立禁忌表tabuF(F=1,2,……n)记录在t时刻蚂蚁已经走过的城市,不允许该蚂蚁在本次循环中再经过这些城市。当本次循环结束以后,禁忌表将被用来计算改蚂蚁当前所经过的路径长度。之后,禁忌表将被清空,用以准备下一次循环。经过n个时刻,蚂蚁完成一次循环,各条路径上的信息素根据下式调整:
用△τkij表示第k只蚂蚁在本次循环中留在路上的信息素,则,ρ为信息素残留系数,1-ρ表示信息素的消逝程度。
根据具体的算法的不同,△τij、△kij和pkij(t)表达形式也有所不同,可根据具体问题而定。M.Dorigo曾给出三种不同的模型,分别是蚁周系统、蚁量系统、蚁密系统。经过一系列标准测试问题的测试,蚁周系统的性能要优于其他两种算法,故常用的就是蚁周系统更新模式:
其中,Lk为第k只蚂蚁在本次循环中所走的路径长度。
3 蚁群算法的改进[2,3,4,5,6,7]
基本蚁群算法具有很强的全局搜索能力,但是也存在一些问题,例如:搜索时间过长,执行过程中容易出现停滞现象,当问题规模较大时存在陷入局部最优解的可能。因此,很多学者对蚁群算法进行了改进。
3.1 基于优化排序的蚂蚁系统
蚁群算法和遗传算法一样,都有一个共同的缺陷就是容易陷入局部最优解。当路径差别不大,解元素之间的差异减少,致使选择概率的差异也随之减少,从而阻止了对最优解进一步的搜索。借用遗传算法中适应度排序法,将每次循环以后生成的路径进行排序,依照序列的顺序进行信息素加权更新。
3.2 最大最小蚂蚁系统
为了防止过早的算法停滞现象,德国学者T.Stuetzle和H.Hoos提出了最大最小蚂蚁系统(Max-Min Ant System,MMAS),其特点是在算法中引入了信息素最大值和最小值限制。当某条路径上的信息素大于上限,就强制为上限值;小于则为下限值,通过设定信息素的上下限。这样一方面避免了某条路径上的信息素远大于其他路径的信息素浓度,从而有效的降低了过早停滞的可能;另一方面,不会因为某条路径的信息素浓度过低而丧失发现新路径的可能。
有实验表明,MMAS算法较传统的蚁群算法相比,在寻优的有效性方面和防止算法的过早停滞方面具有更好的效果,但是,仅采用最大最小信息素的限制还不足在较长的时间里持久消除停滞现象,因此,可以对其进行进一步改进,如在算法中引入信息素平滑机制等。
3.3 自适应蚁群算法
为了既能保持蚁群算法全局搜索能力,又能提高搜索速度,王颖等人提出了自适应蚁群算法。该算法能在进行过程中自适应的改变ρ值,ρ的初始值取ρ(t0),当算法求得的最优解在固定的N次循环内没有明显得改进时候,对ρ值作出适当的调整。
式中,ρmin为ρ的最小值,可以防止ρ过小而降低算法的全局搜索能力。通过多种实验表明,该算法比一般的算法具有更好的收敛速度和稳定性,更适合于求解大规模的TSP。
4 结论
蚁群算法是一种新的仿生进化计算方法,已经在TSP、图与组合优化、Job-shop等问题上取得了成功的应用,并具有其独特的优越性。但由于蚁群算法还是一种新型的优化算法,其研究刚刚开始,还没像遗传算法和模拟退火算法等那样形成系统的分析方法和坚实的数学基础,因此算法中一些参数的确定目前还没理论上的依据,以公布的实验结果都是针对特定问题而言。
总之,蚁群算法作为一种新兴的研究领域,将会得到不断深入的研究,其模型将会更加丰富,也将相应的得到更加广泛的应用。
摘要：蚁群算法是一种新型的进化算法,在离散函数和连续函数优化中都有着广泛的应用前景。该文简要对算法的研究现状做以概述,介绍该算法的基本原理、算法的模型和若干改进算法。
关键词：蚁群算法,基本原理,改进算法
参考文献
[1]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[2]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
[3]段海滨,王道波.蚁群算法的全局收敛性研究及改进[J].系统工程与电子技术,2004,26(10).
[4]邵晓巍,邵长胜,赵长安.利用信息量留存的蚁群遗传算法[J].控制与决策,2004,19(10).
[5]段海滨,王道波.一种快速全局优化的改进蚁群算法及仿真[J].信息与控制,2004,33(2).
[6]张纪会,徐心和.一种新的进化算法——蚁群算法[J].系统工程理论与实践,1999(3).
蚁群优化算法 篇5
基于改进蚁群算法的无人机侦察航路规划研究
蚁群算法是一种新的源于大自然生物界的仿生随机优化方法,在一系列组合优化问题求解中取得了成效.本文将蚁群算法引入无人机侦察航路的规划,对基本蚁群算法提出了改进,提供了一种新的有效的航路优化算法,并对无人机的侦察航路进行了仿真计算.仿真结果表明改进的`蚁群算法克服了基本蚁群算法的收敛速度慢、易于过早陷入局部最优的缺点,仿真结果验证了该算法的有效性.
作 者：蒋定定 李万泉 JANG Ding-Ding LI Wan-Quan 作者单位：海军航空工程学院,青岛分院,山东,青岛,266041刊 名：飞机设计英文刊名：AIRCRAFT DESIGN年，卷(期)：28(2)分类号：V279+.2关键词：蚁群算法 无人机 航路规划 生物信息
蚁群优化算法 篇6
摘 要：针对通信网络因链路失效而产生的网络拥塞问题，基于元胞蚁群算法提出了一种新的网络生存性评价方法SACA（Survivability Algorithm based on Cellular Ant）。该方法首先给出了网络生存性定义，并且通过元胞蚁群算法设计了生存性算法流程，以此获得网络剩余数据传输量。同时，利用NS2和MATLAB进行仿真实验，结果表明，相比于其它算法，SACA算法具有出较好的适应性。
关键词：生存性；剩余能量；失效；元胞蚁群
中图分类号：G642 文献标识码：B 文章编号：1002-7661（2014）09-285-02
目前，如何提高网络安全性成为网络的研究重点和研究热点。网络生存性已经成为影响其性能的关键问题[1]。网络生存性主要是指网络在遭遇外部攻击或自身故障等异常情况下，仍然能够及时维持可接受的业务质量的能力。为了有效评价并解决这一问题，国内外学者开展大量研究工作。2000年，Albert等[2]首先研究了不同度分布下复杂网络的有效性。Paolo Crucitti等[3]利用度和介概念提出了关键节点和链路评估模型，并讨论了不同状态下的网络生存能力。但是这些优化思想并没有从网络模型和网络状态进行深入分析，所以对于从本质上解决网络抗毁性的作用有限。皇甫伟等[4]定义了网络生存性指标，并基于灾害条件对具有SDH自愈环拓扑结构的网络生存性进行了定量分析。包学才等[5]针对全连通网络定义了不相交路径抗毁性评估模型，研究了全连通网络节点间不相交路径数的比重，从而能够定量计算通信网络的抗毁性。Wang Jianwei等[6]提出了基于局部负荷分配策略的级联失效模型，并且发现在某些条件下攻击低度节点对网络的破坏程度反而大于高度的节点。
针对上述问题，本文首先给出了网络生存性定义，并且利用元胞蚁群算法来计算剩余数据传输量[7-8]，进而获得当前网络生存性。同时通过NS2和MATAB进行仿真实验，深入研究了影响该方法的关键因素。
1、网络生存性定义
假设存在网络G（V， W， F）中，V代表节点集合（V=[1， 2， …， n]），W代表链路权重集合，F表示网络中任意两点之间的流量集合，假设网络中各节点位置具有随机性，并且节点的性质相同（如数据转发能力，缓冲大小等），这里将各节点出现失效的情况归纳为对应链路出现失效，同时假设各链路出现失效的概率相等。令网络中存在n段链路，正常情况下整个网络数据传输量为f，有k条链路失效时网络剩余流量为f（k）。那么，网络生存性则可以定义为：
（1）
其中：
（2）
在上述定义中，关键在于求解网络剩余流量f（k）。本文结合元胞自动机和蚁群智能算法对f（k）进行研究，将定义的元胞演化规则替换变异和交叉操作，以达到快速收敛的目的，同时降低了算法的运算量。
2、元胞蚁群算法
元胞自动机是一种时间和空间离散、可扩散的、状态有限的多维系统，普遍应用于非线性科学领域。
本文采用Moore型元胞结构，如图1所示，在下一时刻蚂蚁按照概率p选择周围8个元胞和自身中的最优状态进行转移：
（3）
其中，ξ和ζ为非负常数，λi为蚂蚁i为中心r为半径的邻域内的单位面积内的节点分布，Δλ表示两相临邻域内的节点分布差，yi为每个蚂蚁对应的状态函数，Δyij=yi-yj，并且状态函数yi为定义为：
（4）
同时这里定义如下元胞演化规则：
（a） 选择任意一个元胞i，通过计算临域内各yi值，记录其中最优值yopt=yi。
（b） 在临域半径r内任意选取元胞i和j，并计算相应的yi和yj；如果yi 这里利用元胞蚁群给出上述数学模型的求解算法（Botnet Detecting algorithm based on Cellular Ant，BDCA）： 1、在开始时刻T，初始化网络拓扑结构，网络剩余数据传输量f（k）、元胞蚁群规模为M，并确定元胞蚁群的转移概率p和搜索区域半径r，最大迭代阈值MAX； 2、确定蚂蚁的搜索区域及搜索中心位置Oi： （13） 其中，xmax和xmin为搜索区域上下边界，rand（）产生（0， 1）之间的随机数； 3、在Oi为中心、r为搜索半径的区域内，蚂蚁i搜索是否存在比当前状态函数yi更优的元胞；如果存在则按照概率p进行移动，如果移动成功，则丢弃当前中心区域Oi，重新计算当前蚂蚁i的目标函数值，以及当前最优解，同时更新方程修改轨迹强度； 4、重复上述步骤（3），完成所有蚂蚁的更新操作； 5、令T=T+1，跳转到步骤（2）继续执行，直至Δλ趋于0或者跌代次数超过阈值MAX时停止； 6、输出当前的最优解，即为稳定状态下最优的网络剩余数据传输量f（k）； 算法结束。 本文针对网络生存性提出了一种新的刻画方法SACA。该方法首先根据网络剩余数据传输能力给出了网络生存性指标，通过定义元胞演化规则并结合蚁群算法，将网络节点集合看作蚁群，使得在网络失效的情况下能够快速收敛，从而获得全局最优。最后，本文将提出的SACA算法与SAICSA 算法、ASATS算法进行仿真实验，结果发现该算法具有较好的适应性。同时在今后的研究中，可以考虑联系网络有效性和抗毁性进行动态建模，以此形成较为完善的评价体系结构。 参考文献： [1] Lazarou G Y， Baca Julie， Frostv S， Evans J B. Describing network traffic using the index of variability[J]. IEEE /ACM Transactions on Networking， 2009， 17 （5）： 1672-1683. [2] Albert R， Jeong H， Barabasi A L. Error and attack tolerance of complex networks [J]. Nature， 2000， 406： 378-382. [3] Crucitti P， Latora V， Marchiori M， Rapisarda A. Error and attack tolerance of complex networks [J]. Physica A， 2004， 340（1）： 388-394. [4] 皇甫伟， 容鹏， 曾烈光. SDH 自愈环生存性定量分析[J]. 电子学报， 2001， 29（11）： 1558-1560. [5] 包学才， 戴伏生， 韩卫占. 基于拓扑的不相交路径抗毁性评估方法[J]. 系统工程与电子技术， 2012， 34（1）： 168-174. [6] Wang Jianwei， Rong Lili. Cascade-based attack vulnerability on the US power grid[J]. Safety Science， 2009， 47（10）： 1332-1336. [7] 曹春红，王利民，赵大哲. 基于离散元胞蚂蚁算法的几何约束求解技术研究[J].电子学报，2011，38（5）：1127. 1问题提出 本节分析蚁群算法优缺点,探讨不足之原因,蚁群算法利用特有的正反馈特性,使得算法具有较高的自组织能力。然后系统内部成员之间分布式运行,成为一个统一体。正反馈机制使虽然能强化较好解,但却使算法出现停滞现象,即只取得了局部最优解就停止,而未达到全局最优解。 易早熟,求解问题解的时候过早的陷入局部最优解。正反馈的存在,算法运行到一定程度,信息素的贫富加剧,使得算法在局部区域摇摆,不向其他方向搜索,全局搜索能力降低。全局收敛速度慢,随机性发挥着较大作用。算法的效果和参数设置敏感,算法参数相互影响,在设置相关系数的时候要注意相互的耦合关系。针对算法上面这些不足,本文对算法本身提出改进,同时结合具体的优化问题,结合微粒子群算法对算法主要参数的进行调优。 2优化蚁群算法 2.1引入“赏罚”机制 蚂蚁个体依据信息素浓度进行路径选择。算法的正反馈性,无论搜索到的解如何,所有被搜索到的路径上的信息素都会在一定程度上得到增强,所以存在不公平竞争。本文引入“赏罚”机制,即奖励表现好的路径,惩罚不好的路径。每当蚂蚁所有任务点完成一次遍历后的路径与之前的最优路径相比较,若此路径更优则在该路径上增加一定浓度的信息素,该路径暂时最优,以增加下次遍历时选择该路径的概率;反之,若路径不是最优则要在该路径上减少一定浓度的信息素,以减小下次被选中的概率。 2.2最大最小蚁群系统 2.3信息素更新策略的改进 2.3.1信息素全局更新策略的改进 在每次迭代构建解空间后,记录所有蚂蚁构建的可行解的路径长度,然后与当前最优解的路径长度进行比较。若长度小于当前最优解的长度,则该路径上的蚂蚁在其经过的路径上释放相应的信息素,反之,不释放信息素。这样保持了算法的朝向是持续优化,而又防止算法过早地陷入局部最优解。节点Ci到节点Cj之间路径上的信息素量更新公式: 2.3.2信息素局部更新策略的改进 依据前文讲述的赏罚机制,蚂蚁在构建解的过程中对经过的路径上的信息素进行局部更新,去除掉该路径上的一些信息素,以有利于后面的蚂蚁探索其他路径解,提高其探索的概率,避免进入停滞或者局部最优解。对于某蚂蚁个体,当其经过一条路径(i,j)时,立即对此路径上的信息素进行更新。 2.4引入状态转移控制参数 2.5小结 在最大最小蚁群系统基础之上引入“赏罚”机制,然后从全局和局部优化算法信息素浓度的更新策略,加入不同状态变化概率对算法进行优化和改进。 3调优算法参数 算法关键参数:浓度消逝速度ρ、信息素因子φ、启发因子γ、蚂蚁的数量规模M以及信息素总量Q,参数相互耦合,需要结合具体问题,对其进行调优。本节采用公交调度优化问题,以某市27路的实际数据,利用微粒子群算法调优关键参数。信息素因子启发因子 3.1粒子群优化 本文所选用调优参数的算法是粒子群(PSO)算法。作为基于种群的随机全局优化算法,其每一次的迭代过程中,微粒个体i通过其自己所构建到的个体最优解Pi_best和目前整个种群范围内找到的全局最优解Gbest,按式(3-1)来进行更新迭代处理。其中,vi表示微粒个体的速度向量;Xi表示微粒现在的位置;学习因子C1、C2是常数;r1,r2是在[0,1]上均匀分布的随机数;w是惯性权重。 3.2参数调优实验 将目标参数组合作为优化对象(微粒的位置),在每轮迭代过程中,使用微粒的现在所处的位置来运行改进的蚁群算法,求解标准优化问题,同时结合适应度评价函数对刚刚求解的性能进行评价,最终指引各微粒朝适应值高的方向行进。流程如下: 改进蚁群算法及参数优化研究 篇7
图1:各时段客流统计分布
(1)在一定范围内选取C1、C2和权重w的值,同时随机选取各微粒的初始位置和速度;
(2)利用每个微粒个体所在的位置信息执行蚁群优化算法,进行一次求解,同时依据适应值评价函数对刚刚求解结果进行评价分析,从而获取各个微粒个体的适应度值;
(3)针对各微粒个体,通过对其当前位置适应度值和Pi_best的适应值进行比较,若较优,那么就需要用当前位置来更新个体最优解Pi_best;
(4)用每个微粒个体最优解Pi_best的适应值与全局最优解Gbest的适应值比较,若较优,则更新全局最优解Gbest;
(5)然后依据式(5)更新每个微粒个体的速度和位置;
(6)对终止条件进行判断,若满足条件,就输出全局最优解Gbest,否则跳转步骤2。
依据上文提出的参数优化算法仿真过程,蚁群算法采用本文改进的算法,参数ρ、φ、γ、M、Q为调优对象,其参数取值范围如表1所示。经过对比分析,总结出适合该公交调度模型的优化参数组合,最终得到算法的调优关键参数见表2。
4公交优化调度的仿真实例分析
4.1优化蚁群的调度求解步骤
前文我们已经分别对算法本身和关键参数进行了改进和调优,本章将利用经典的公交调度优化问题,来验证其有效性。
为了能够根据实际的客流数据,更好地解决公交调度问题,从而满足乘客的需求,将全天运营时间进一步细分为早平峰[6:00,7:00]、早高峰[7:00,9:00]、上平峰[9:00,11:30]、午高峰[11:30,14:00]、午平峰[14:00,16:30]、晚高峰[16:30,19:00]、晚低峰[19:00,21:30]七个时段优化。本文实证分析以某市27路公交,通过调整优化在各个时段内公交车的发车间隔,兼顾公交公司盈利和公众满意,以此来实现对调度问题的优化。该趟公交线路拥有33个站点,图1是27路某工作日全天各时段内客流统计分布图。如图2所示为某工作日一天运营时段内的客流。
4.2算法仿真求解比较
从表4说明了本文优化算法的合理性,公交公司如果将全天的运营时段划分的越多,虽然公众坐车会很方便,但是那么势必会增加车辆的发车次数,从而增加了其运营成本。对图3、表4进行分析,可以看出当如果将把全天的运营时间划分为七个时段,可以使得发车量更符合公众出行的需求,当客流偏少时,就通过提高公交发车间隔,来降低公交的发车次数,这样就能够满足公众的需求,保证服务水平,同时兼顾公交公司的成本花费,做到了共赢。
5结论
本文首先对算法本身进行优化调整,对信息素变更机制进行完善,引入“赏罚”机制,并借鉴改进的最大最小蚁群系统,将信息素的浓度限制在一定范围内,避免轻易出现停滞状态,以及对节点的选择进行调整等等。然后针对参数取值问题,利用微粒子群优化算法对组合参数ρ、φ、γ、M和Q进行调优。最后利用优化的算法和调优参数对公交调度优化问题进行求解,仿真对比结果表明本文改进的蚁群搜索速度得到加快,搜索效率得到提高。说明本文的改进能有效地改善蚁群算法的性能,是可行的。
参考文献
[1]Tropical cyclone spiral band extraction and center locating by binary ant colony optimization[J].Science China(Earth Sciences),2012,02:332-346.
[2]A Multi-pipe Path Planning by Modified Ant Colony Optimization[J].Computer Aided Drafting,Design and Manufacturing,2011,01:1-7.
[3]Munan Li.Efficiency improvement of ant colony optimization in solving the moderate LTSP[J].Journal of Systems Engineering and Electronics,2015,06:1301-1309.
[4]赵航.基于机会约束的公交调度研究[J].数学的实践与认识,2005,35.
[5]张聪.基于并行计算的公交车调度优化研究[D].合肥:安徽理工大学,2014.
基于改进蚁群算法的无功优化研究 篇8
1 无功优化模型
采取考虑有功网损最小的无功优化模型, 目标函数如下:
式中:n为系统的支路数;Gk为线路的电导;V为电压的幅值;θ为对应的相角。
等式约束条件:
式中:i∈N;Pi、Qi分别为注入节点i的有功功率和无功功率;PGi、PLi是发电机节点和负荷节点的有功功率;QGi、QLi是发电机节点和负荷节点的无功功率;QCi是无功补偿的容量;V是节点电压;Gij、Bij是节点i、j之间的电导和电纳。
不等式约束条件:
控制变量的约束方程为
式中:NG、SC、ST分别为发电机台数、无功补偿节点数和变压器台数。
状态变量的约束方程为
式中:NG、ND分别为发电机台数、负荷节点数。
2 蚁群算法及其改进方案
2.1 蚁群算法模型
蚁群优化算法最早应用于求解著名的旅行商问题, 目前该算法已经应用于多个研究领域, 如函数优化、网络路由和系统辨识等, 具有广阔的发展前景[1,2,3]。
蚂蚁k在移动过程中通过可选路径上信息素的多少来判断转移方向, 蚂蚁k在城市i选择城市j的状态转移概率定义为
式中:pkij (t) 表示t时刻蚂蚁k在城市i选择下一城市j的转移概率;τij (t) 表示t时刻残留在城市i、j连线上的信息素量;ηij (t) 用来表示启发函数;α和β分别反映蚂蚁在移动过程中所积累的信息素和启发信息在路径选择策略上的相对重要性。
蚂蚁k的搜索路径就是TSP问题的一个可行解, 在经过n个城市的遍历后, 蚂蚁就完成了一次搜索, 各段路径上的信息素量根据以下公式进行调整:
式中:ρ表示信息素的挥发系数; (1-ρ) 则表示信息素的残留因子。
对于Δτkij (t) 的提出了3种不同的实现方法, 也是目前常用的3种蚂蚁系统模型[4]:
1) ant-cycle system模型:
2) ant-density system模型:
3) ant-quantity system模型:
式中:Q是常数, 表示的是蚂蚁进行搜索一周所释放的信息素总量;Lk表示第k只蚂蚁在本次循环中所走路径的总长度。
对于计算Δτkij (t) 的3个模型, 文献[5]的实验证明了蚁周模型要比其余2种模型优秀, 蚁周模型的更新策略是当所有蚂蚁每完成一次循环才进行信息素的全局调整。
2.2 蚁群算法步骤
1) 初始化:将m只蚂蚁随机分布在n个城市并初始化信息素及蚁群算法参数等。
2) 构造可行解:对每只蚂蚁用状态转移概率在可供选择城市中选择要到达的下一个城市, 并将所选城市放入禁忌表中;当蚂蚁遍历完所有城市, 计算所选路径长度, 所选路径即为所求问题的一个可行解。
3) 信息素的更新:当所有蚂蚁都完成一次搜索之后, 通过信息素更新规则对各边上的信息素进行更新;比较所有的遍历长度, 找出最短路径;将禁忌表清空, 返回到上一步。
4) 不断进行迭代直至满足最大迭代次数或满足所求问题的精度要求为止。
2.3 蚁群算法的改进
2.3.1 参数改进
定义一个自适应系数μ, 令μ=Lwa/Lk, 针对公式 (4) , 根据本文提出的改进方法调整为
这样做可以增强短路径的信息素强度, 减弱长路径的信息素强度, 提高收敛速度, 从而缩短获得最优解的时间。
2.3.2 应用微分进化算法改进
微分进化 (differential evolution, DE) 是一种高效率的智能优化计算方法。DE算法来自遗传算法, 是一种极具潜力的跨学科优化算法[6]。
在蚁群算法中引入发散项可以增加随机扰动来帮助算法跳出局部最优。
式中:F为属于[0, 1]的微分进化发散因子;p, q∈{1, 2, …, m}。因此信息素更新公式变为
通过加入微分进化算法的发散项, 对蚁群算法信息素的更新引入了一个微小扰动量, 使得随机性增加, 有利于减小算法过早陷入局部最优的可能性。
3 基于改进蚁群算法的无功优化
改进算法在无功优化中的流程如图1所示。改进算法在无功优化中的具体步骤为
1) 对每一个支路和节点的原始数据进行读取。
2) 初始化, 将系统的控制变量进行离散化处理, 在可行域里随机产生m个个体, 然后进行参数的设置, 形成初始蚁群。
3) 依据公式 (1) 让蚁群k进行搜索, 并且记录每一个控制变量的大小, 从而依据节点和支路信息来计算潮流、网损和适应值。
4) 进行适应值的比对, 若Xk比当前最优解Xbest更优, 则更新最优解Xbest;否则就向当前最优解的方向前进一步, 然后再根据节点和支路信息计算潮流、网损和适应值。
5) 当一次迭代完成后根据式 (2) 、式 (3) 、式 (5) 进行信息素的更新。
6) 满足迭代次数或计算精度, 计算出最优潮流和最小网损, 然后输出最优潮流、最优解。否则回转步骤3) 继续进行搜索。
4 电力系统算例分析
4.1 IEEE-30节点系统数据
本文所采用算例系统的参数均采用标幺值表示, 电压相角单位是弧度, 基准功率为100 MVA, 所用的优化计算程序采用MATLAB7.0编程实现。
对于标准测试系统IEEE-30节点系统[7]的参数如下:
6台发电机 (其中平衡节点号为1, PV节点号为2、5、8、11、13) ;有4台可调变压器分布在支路 (6-9、6-10、4-12、27-28) 上;有2台并联无功补偿装置补偿点 (节点10、24) ;21条负荷母线及41条支路。IEEE-30节点系统结构如图2所示, IEEE-30节点系统控制变量约束条件如表1所示, IEEE-30节点系统状态变量约束条件如表2所示。功率数据都是以100 MVA为基准功率的标幺值, IEEE-30系统的初始网损为0.0694。
4.2 计算结果分析
除平衡节点外, 有5个发电机、4个可调变压器、2个无功补偿节点, 所以控制变量总数为11个。通过改进蚁群算法来确定最佳控制方案。
参数设置:蚂蚁数目m=50, 信息素挥发系数ρ=0.3, 信息素启发因子α=1, 期望值启发因子β=2, 初始信息素为0.1, 总信息量Q=100;移动步长STEP为0.005;F为属于[0, 1]的微分进化发散因子;p, q∈{1, 2, …, m};算法终止条件为相邻的两次最优解的差别小于10-6或达到最大迭代次数200次。
为了验证本文所用算法的有效性, 通过50次的计算结果来取平均值。将改进蚁群算法与现今常用的遗传算法[8]、蚁群算法、多智能体粒子群算法[9]、免疫蚁群算法[10]的优化结果进行比较, 结果如表3—表6所示。
由表3结果可知, 改进蚁群算法比遗传算法、蚁群算法、多智能体粒子群算法、免疫蚁群算法的网络损耗更小, 其计算精度也更高, 全局寻优能力更强, 达到了降低有功网损的目的。
由表4—表6结果可以看出, 发电机的无功处出力、变压器变比和无功补偿容量均在允许范围内, 可以正常运行。
对IEEE-30节点系统采用遗传算法、蚁群算法和本文提出的改进蚁群算法分别进行50次优化计算, 有功网损最小值的统计分布如图3所示。
从图3可以看出, 对电力系统进行无功优化, 采用遗传算法进行的优化计算表现出稳定性较差的特点, 而改进蚁群算法 (IACO) 无论是在算法的初期还是后期, 收敛情况都要强于蚁群算法 (ACO) 。通过改进方案使得IACO算法在收敛速度和寻优结果上都有所提高, 可见IACO算法的稳定性及搜索全局最优解的能力要比遗传算法和蚁群算法优秀很多。
5 结语
以发电机端电压、变压器变比和无功补偿容量作为控制变量, 以网损最小作为目标函数, 建立无功优化数学模型。在分析大量智能算法优缺点的基础上, 选择蚁群算法作为优化算法, 并针对其缺点进行了相应改进。将电压稳定引入无功优化形成多目标无功优化, 并将多目标转化为了单目标无功优化问题, 最后采用IEEE-30节点系统作为测试系统进行优化计算, 验证了本文所采用算法的可行性和合理性。
摘要：建立了网损最小的数学模型, 对蚁群算法的缺陷进行改进, 包括对蚁群搜索到的路径进行排序, 自适应调节路径上释放的信息素。同时又在信息素更新机制里引入微分进化算法的发散项, 提高算法的收敛速度和全局寻优能力。通过IEEE-30节点的仿真计算, 验证了改进蚁群算法在电力系统无功优化领域的可行性和有效性。
关键词：电力系统,无功优化,蚁群算法,改进蚁群算法
参考文献
[1]MARTINEZ C, CASTILLO O, MONTIEL O.Comparison between ant colony and genetic algorithms for fuzzy system optimization[J].Soft Computing for Hybrid Intelligent Systems, 2008, 165 (10) :71-86.
[2]陈敬宁, 何桂贤.带杂交变异因子的自适应蚁群算法在电力系统无功优化中的应用[J].继电器, 2003, 31 (11) :36-39.
[3]胡小兵, 黄席樾.基于混合行为蚁群算法的研究[J].控制与决策, 2005, 20 (001) :69-72.
[4]DORIGO M, MANIEZZO V, COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems, Man, and Cybernetics-Part B, 2002, 26 (1) :29-41.
[5]STUTZLE T, HOOS H.MAX-MIN ant system[J].Future Generation Computer Systems, 2000, 16 (8) :889-914.
[6]刘自发, 闫景信, 张建华, 等.基于改进微分进化算法的电力系统无功优化[J].电网技术, 2007, 31 (18) :68-72.
[7]寸巧萍.基于量子遗传算法的电力系统无功优化[D].成都:西南交通大学, 2004.
[8]LAI L L, 杨以涵.遗传算法在电力系统无功优化中的应用[J].中国电机工程学报, 1995, 15 (5) :347-353.
[9]赵波, 曹一家.电力系统无功优化的多智能体粒子群优化算法[J].中国电机工程学报, 2005, 25 (5) :1-7.
一种蚁群算法疏散模型优化的方法 篇9
最短路径算法是智能疏散系统中疏散模型的核心算法,目前常见的最短路径算法有Dijkstra算法、模拟退火算法、遗传算法等。这些算法 运算效率 低,计算过程 复杂,花费时间长。意大利学者Dorigo等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径的行为,提出的一种基于种群启发式仿生进化系统的蚁群算法,具有分布式计算、信息正反馈和启发式搜索的特征,有较强的鲁棒性、优良的分布式计算机制等优点。
笔者模拟楼层拓扑结构,建立楼层疏散节点地图,用蚁群算法计算出各个节点到出口的最短路径。提出一种最短最大的节点预处理方法,对节点进行排序,优化蚁群算法处理节点的顺序,减少疏散模型求解最短路径的时间,通过实验对比表明该方法的有效性。
1疏散模型分析
用蚁群算法求出某个节点到安全出口的最短路径。 首先建立有多个安全出口的楼层拓扑节点的蚁群算法疏散模型,其次提出最短最大的方法对模型进行优化。
1.1楼层拓扑结构构建
模拟某一楼层的拓扑结构,在中间节点、拐弯点和安全出口等处建立若干节点,将各个节点依次编号并设置节点间的连通关系。节点号集为V={1,2,…,n},连通关系为边集E={e1,e2,…,el},建立节点 间关系图G= (V,E),设置安全出口节点,节点以二维坐标存储。
1.2多出口的蚁群算法
蚁群算法是启发式算法的局部更新的自适应算法, 算法迭代的次数和循环次数越多,计算所得的最短路径越准确。
假设禁忌表Tabuk(k=1,2,…,n)记录蚂蚁k当前所走过的节点,蚂蚁数量为m;α、β分别表示蚂蚁积累的信息及启发式因子在选择路径中所起作用的程度;Tauij(t)表示t时刻在节点i、j之间残留的信息量;启发式因子ηij(t)=1/dij,dij表示节点i和j之间的权值;Pikj(t)表示在t时刻蚂蚁k由位置i转移到位置j的概率,如式 (1)所示。
式中:alowedk={0,1,2,…,n-1}-Tabuk为蚂蚁k允许选择的节点;Taui,j(t),ηij(t)与Pikj成正比。
蚂蚁k通过Pikj(t)来确定下一步节点,如果仅依据转移概率确定下一步的节点,会有较快的收敛速度,可能导致局部最优的产生。此时,用0~1的随机数r,如果r< Pikj(t),则选择该节点,扩大搜索范围,较好地避免了局部最优化。集合Tabuk随着进化过程作动态调整,已经走过的节点放在Tabuk中,不再作为 下一步判 断的节点。 每只蚂蚁k在寻找到出口或达到最大循环次数时结束循环,同时把路径保存起来。在某代循环结束时找到到达出口的最短路径,通过式(2)更新该路径上的信息素。
式中:ρ为信息素蒸发的系数;ΔTauij为每代循环中到达出口的蚂蚁在节点i,j上的信息量的增量,当第k只蚂蚁在某次循环中得到最短的路径,用Ant-cycle模型策略更新最短路径信息素,如式(3)所示。
式中:Q为常数,其值为每次释放信息素的总量;Tauikj为第k只蚂蚁在一次循环中到达出口留在路径i、j上的信息量;Lk为第k只蚂蚁在本次循环所走路径的长度。
1.3疏散模型的优化
蚁群算法的时间复杂度较高,智能疏散模型的运算时间主要由蚁群算法的运算时间决定。疏散模型调用蚁群算法每次只能求出若干个节点到出口的最短路径,需要多次调用蚁群算法,又因蚁群算法比较成熟,疏散模型优化的关键是减少蚁群算法的调用次数。最短最大方法是按照到出口最远的距离对节点进行排序,增加蚁群算法每次经过节点的数量,经过的节点不再进行计算,以达到减少蚁群算法计算的次数的目的。
在发生火灾的应急条件下,将楼层的拓扑结构图中节点的坐标值、连通关系和出口的标号值作为数据用于蚁群算法计算节点到出口的最短路径。疏散模型的流程图如图1所示。
2疏散模型实验分析
在如图2的楼层中设置24个节点V={1,2,…,24},连通关系为边集E={e1,e2,…,e32},节点号2、23是安全出口,左右节点连通权值是10,上下连通权值为15,安全出口是2、23,如图2所示。
通过多次仿真计算设置参数值为α=0.1,β=0.1,ρ =0.1,Q=1,初始化信息素矩阵值Tauij(0)=c=1,m= 100,循环次数Nc=100,实验平台是HPZ820工作站。
假设节点3和4之间发生火灾,收到火灾报警信息, 设置节点3和4之间距离为无穷大。在相同的实验条件下,实验1是从节点值1开始计算,未预处理节点的某次运算得到的疏散路径顺序,如表1所示。实验2用最小最大方法预处理,某次运算得到的疏散路径顺序,见表2所示。
两个实验得到了相同的疏散路径,如图3所示。
由图3可知,两次实验结果得出的指示路径是相同的,其中表1经过12次运算,所有节点运算结束,表2运算9次即可,说明经过节点预处理后,每次蚁群算法得到最短路径的节点数增加,疏散模型调用蚁群算法的次数较少。对实验1和2分别进行50次实验,进行优化前和优化后蚁群执行次数和疏散模型运算时间进行对比,如图4、图5所示。
在重复实验时,虽然实验1和实验2的结果有时不完全相同,但得到的疏散路径是等效的,即各个节点到出口的疏散路径长度相等。由图4和图5可知,优化后疏散模型调用蚁群算法的次数减少,运算时间减少。通过计算可知,调用的次数减少了18.53%,运算时间减少了10.52%。此外,改变图2中楼层的拓扑结构后对优化前后进行50次实验对比,结果同样表明,优化后调用蚁群算法次数和运行时间减少。
3结论
通过蚁群算法建立疏散模型,在火灾应急的条件下计算各个节点到出口的最短路径。根据节点的坐标计算节点到出口的欧式距离,提出最小最大算法对节点的进行排序,优化蚁群算法调用节点的顺序,减少了蚁群算法的运算次数,缩短了运 行的时间,提高了疏 散模型的 效率。未来可以考虑烟气的减光性、毒害性、高温等因素, 将楼道的长度改为当量长度,随着楼道环境不断的变化更新其通行能力。
摘要：针对智能疏散系统中运算时间复杂度高的问题,提出一种预处理方法优化疏散模型。建立楼层蚁群算法疏散模型,用该方法对拓扑节点进行排序,使得模型每次调用蚁群算法求最短疏散路径时尽可能地经过多个节点,减少调用蚁群算法的次数,缩短模型的运算时间,通过对优化前后的实验对比表明该方法的有效性。
多目标优化的生长竞争蚁群算法 篇10
多目标优化问题的目标往往是互相冲突的, 能满足所有约束条件且使所有目标函数都能达到全局最优的解往往不存在, 而只是存在一组Pareto最优解或非劣解。近年来, 智能优化方法在解决多目标优化问题已取得一些成果。很多学者使用遗传算法[1,2,3]、 粒子群算法[4]、 蚁群算法[5,6]等对求解多目标问题的Pareto最优解进行了有益的探讨。
蚁群算法是一种源于大自然生物世界的仿生类算法[7]。蚁群算法已在一系列困难的组合优化问题求解中已取得了成效。基于植物生长向光性和竞争性机理, 本文提出了一种求解多目标连续系统优化问题的生长竞争蚁群算法及其数学描述, 并对部分典型多目标连续函数优化问题进行了测试和验证。
2 多目标优化的生长竞争蚁群算法
2.1 多目标优化
在实际应用领域中, 存在大量的多目标优化问题。如何在多个目标中寻找折中最优解是一个比较复杂的问题。多目标优化的数学描述如下:
其中, F (x) 为多目标优化问题的目标函数, 其分量fi (x) , i=1, 2, …, k均越小越优, 对x*∈X, 若在X中不存在x使fi (x) ≤fi (x*) , i=1, 2, …, k, 且至少对一个i严格不等式成立, 则称x*为多目标优化问题的Pareto最优解或非劣解。
常用的优化技术本身并不能直接处理多目标优化问题, 往往将其转化为比较容易处理的单目标问题, 典型的方法有:主要目标法、线性加权法、平均和加权法、理想点法、乘除法和几何平均法等[8]。这些优化技术一般每次都只得到Pareto解集中的一个, 或是相对于Pareto最优解的一个折中解。
2.2 生长竞争机制
自然界中的竞争是在一定竞争规则下, 在竞争者的实力、竞争者和环境间的关系、竞争者之间的实力的差距等多种因素的作用下, 经过多次竞争, 使不同的竞争者分别占有一定的资源而达到一种新的竞争状态, 只要新的竞争状态优于旧竞争状态, 就会达到优化的目的。
生物学实验已经证明, 植物生长过程中, 当植物有1个以上的节时, 具体哪个节能生长出新枝取决于其形态素浓度, 形态素浓度大的节获得长出新枝的机会比浓度小的节大[9]。而形态素的浓度取决于对光资源的获取。在此我们引入如下的定义:
植物的n个节点为n个竞争者集合, m个可能长出新枝的机会构成m个资源集合, 第i个节点的状态s (i) , 即该生长点的生长素浓度。
n个节点的竞争力函数pk (i) 定义为:
其中, snew (i) 为第i个节点长出新枝后的生长素浓度。pk (i) 的含义是在当前状态下, 第i个竞争者占用资源后, 获得生长素的能力, 若pk (i) <rank (1) , 则该节点退化, 无竞争能力, 将不可能长出新枝。
2.3 多目标生长竞争蚁群算法的描述
一个孤立的蚂蚁随机移动时, 能检测到其它同伴所释放的信息素, 并沿着该路线移动, 同时又释放自身的信息素, 从而增强了该路线上的信息素数量。蚁群个体之间就是通过这种信息的交流达到搜索食物的目的。
一个典型的带约束函数优化问题可以使用常规的罚函数法将所有约束方程转入目标函数中。这样, 在算法的具体搜索过程中就不必考虑约束是否满足的问题, 而直接考虑目标函数优化。
对于连续函数fi (x1, x2, …, xn) , i=1, 2, …, k, 其定义域集合为n维欧氏空间, 可将其的定义区域等分作为搜索区域, 蚂蚁在搜索区域内按基于生长竞争机制进行局部优化, 并按不同情况释放不同的信息素, 而这些信息素可以被整个定义域空间中其它蚂蚁所感知。
定义1 多目标优化生长竞争机制
(1) 破土而出的茎杆有n个节点可能长出m个新枝;
(2) 每个生长点的生长素浓度s (i) = (f1 (x (i) ) , f2 (x (i) ) , …, fk (x (i) ) ) ;snew (i) = (fnew1 (x (i) ) , fnew2 (x (i) ) , …, fnewk (x (i) ) ) 为第i个节点长出新枝后的生长素浓度;
(3) 对于多目标问题, 为了保持pk (i) 大于等于零, 要求每个目标项的差值大于零。为此对竞争力函数pk (i) 作适当修改, 具体如下:
(4) 若pk (i) >rank (1) , 共有k个。 若k>m, 按pk (i) 从大到小取前m个节点长出新枝。 若k<m, 取k个节点长出新枝;
(5) 若k=0或新枝越出规定的范围, 生长结束。
定义2 信息素释放规则
(1) 初试化区域初试最佳值Ziopt和全局初试最佳值Zopt
(2) 选取区域Ni按生长竞争机制获得最好解Zi,
①若Zi≥Ziopt, 不释放信息素;
②若Zi<Ziopt, 替换区域的最佳值;
若Zi<Zopt, 替换空间最优值, 释放信息素Q;若Zi与Zopt无法比较, 将其作为新的最优值保存, 释放信息素Q;若Zi≥Zopt, 释放信息素Q/2;
③若Zi与Ziopt无法比较
若Zi<Zopt, 替换空间最优值, 释放信息素Q;若Zi 与Zopt无法比较, 将其作为新的最优值保存, 释放信息素Q;若Zi≥Zopt, 释放信息素Q/2。
蚂蚁的寻优方向与空间中其他区域的信息素浓度以及它们之间的目标函数的平均差异程度有关。
定义3 蚂蚁的邻域的转移概率定义为
其中, τj为区域j的信息素强度, ηij为为目标函数平均差异程度, 即为:
α为邻域吸引强度的相对重要性 (α≥0) ;β为目标函数平均差异的相对重要性 (β≥0) 。
定义4 信息素强度更新方程为:
这里, Δτkj的值为第k个蚂蚁在区域Nj每迭代一次所释放的信息素, ρ体现强度的持久性。
算法主要流程:
随着蚂蚁在区域内的信息素的释放, 依据蚂蚁的转移概率, 蚂蚁将集中于非劣解较多的区域, 获取更多的非劣解;同时蚂蚁在不同的区域内搜索, 使得所得的解有一定的分布度。
由算法实现的描述可知, 生长竞争机制区域搜索的时间和空间复杂度和新枝的长度及新枝中节点数有关, 实际计算过程中新枝的长度一般取区域半径的1/100～1/10, 而对应新枝中节点数为10～100。搜索过程超出区域, 则停止。因此, 整个算法的时间和空间复杂度主要和区域划分数、区域中的蚂蚁个数及非劣解的数量有关。假设区域的数量为k, 区域中的蚂蚁也为k, 非劣解的数量为s, nc为运算迭代次数, 则算法整个过程的时间复杂度为O (nck2s) , 空间复杂度为O (ks) 。应用上, 这个复杂度是可接受的。
3 实例验证
为了验证方法的有效性, 本文采用了如表1所示的3组测试函数[1,5]来测试算法的性能。在每个测试实例中, 以图形化的方式给出了此方法生成的Pareto前沿, 并对解的分布性能及散布范围[10]进行比较。
定义5 间距评估
其中:
n为算法获得的Pareto前沿上向量的个数, 当所获得的解越接近均匀散布时, 间距S的值越小。
定义6 最大散布范围评估
其定义了两个极值解的距离, 其值越大, 表明算法的解散布范围越广。
算法用MATLAB编程实现并进行了计算测试。测试中所用的参数为α=β=1, ρ=0. 7, Q=1。区域分割数为10, 则每个实例为100个区域。生长竞争机制中n=10, m=1。
表2给出第1组测试函数迭代200次后的求得的间距, 所有解绘制的Pareto曲线如图2;表3给出文献[1]和文献[6]中算法的间距。两者比较本文算法好于其它算法。
表4给出编号2测试函数迭代10次后的求解结果, 图3给出第5次所得的Pareto曲线图;表5给出文献[5]、文献[6]的结果。两者比较本文算法其结果优于文献[5]、文献[6]的结果, 很好地逼近了Pareto前沿。
表6给出编号3测试函数迭代100次后的求解结果, 第2次求得的解绘制的Pareto曲线如图4; 表7给出文献[5]、文献[6]的结果。本文算法其结果优于文献[5]、文献[6]的结果。
4 结束语
本文基于生长竞争机制, 提出了用于求解多目标优化的生长竞争蚁群算法。通过将生长竞争与信息素释放相结合, 引导蚂蚁的行走方向。通过算例求解与测试, 效果良好, 可以很好地逼近Pareto前沿, 同时有一定的散布广度。算法的收敛性的理论分析是今后研究的重点。
摘要：提出一种求解多目标优化的生长竞争蚁群算法。该方法将生长竞争规则引入蚁群算法, 给出了在连续空间多目标函数优化的算法描述, 定义了生长竞争规则及蚁群邻域的转移概率, 并提出了实现算法的具体步骤。算法在MATLAB环境下, 对一些典型的测试函数进行了求解和验证, 实验结果表明该方法具有向真实的Pareto前沿逼近的效果, 是一种求解多目标优化的有效方法。
关键词：蚁群算法,生长竞争,多目标优化
参考文献
[1]Coello C A, et al.Multiobjective optimization usinga micro-genetic algorithm[C]//Proceedings of theGenetic and Evolutionary Computation Conference (GECCO2001) .San Francisco:Morgan KaufmannPublishers, 2001:274~282.
[2]Mu S J, et al.An efficient evolutionary multi-objective optimization algorithm[C]//Proceedingsof the IEEE Congress on EvolutionaryComputation (CEC2003) .Canberra:IEEE Press, 2003:914~920.
[3]王跃宣等.处理带约束的多目标优化进化算法[J].清华大学学报 (自然科学版) , 2005, 45 (1) :103~106.
[4]张利彪等.求解多目标优化问题的一种多子群体进化算法[J].控制与决策, 2007, 22 (11) :1313~1316, 1320.
[5]张勇德, 黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策, 2005, 20 (2) :170~173.
[6]朱刚, 马良.多目标函数优化的生长竞争蚁群算法[J].控制与决策, 2007, 22 (11) :1317~1320.
[7]Colorni A, Dorigo M, Maniezzo V.Distributedoptimization by ant colonies[C]//Proc.of the FirstEuropean Conf.on Artificial Life.Paris:ElsevierPublishing, 1991:134~142.
[8]《运筹学》教材编写组.运筹学[M].北京:清华大学出版社, 2005:440~447.
[9]李彤等.求解整数规划的一种仿生类全局优化算法[J].系统工程理论与实践, 2005, 25 (1) :76~85.
蚁群优化算法 篇11
[关键词] MAX-MIN蚁群算法时间窗车辆路径问题优化
一、VRPTW模型的建立
带有时间窗口的车辆路径问题是典型的多目标组合优化NP-hard问题,因此需要通过合理的构造数学模型来安排车辆配送路线，达到提高配送效率同时又能够产生巨大的社会和经济效益的目的。
VRPTW包括一些客户和仓库，每个客户有一定的需求和时间窗口。每个客户只能由一辆车一次服务完成，还要保证每个客户只能被精确的访问一次，同时不能违背时间窗口约束。其目的是要找到一个可行解使得车辆数最少并且总行程最小。
二、最大最小蚁群算法
为克服在Ant．Q中可能出现的停滞现象,Thomas Stutzle等提出了MMAS算法。该算法具有比基本蚁群算法更贪婪的搜索模式，其主要的改进有以下几点:首先,MMAS在运行期间更多的利用最优解信息，即每次迭代后仅允许一只最优的蚂蚁增加信息素。其次,该算法限定了信息素浓度的上下限，有效避免了在搜索中过早收敛于非全局最优解。
将m只蚂蚁随机放到n个客户中，为t时刻支路(i,j)上的信息素强度，每只蚂蚁都可认为是根据状态转移策略来选择下一个客户，并遵循信息素全局更新规则和信息素限制规则。
1.状态转移策略
针对VRPTW自身的特点，我们定义其状态转移概率为:
其中h∈allowedk={n-tabuk};ηij为启发信息;α(α≥0)代表信息素的权重，β(β≥0)代表启发信息的权重;μij=di0+dj0-dij为节约值; δij为紧迫性因子。
2.信息素更新规则
在MMAS中，只允许其中的最优路径更新信息素，其更新规则为:
其中，为该次迭代sib或全局最优路径sgb的目标函数。
3.信息素限制规则
为了降低算法搜索中的早期停滞问题，该算法限定了信息素浓度允许值的上下限，即
。若，则;若，则。
在搜索过程中,当得到最优解时,按下式便得到一个动态变化的:
为了提高算法的收敛性，我们一般先给定一个Pbest，然后根据下式来选定一个 ：
三、算例分析及结论
设某仓库使用完全相同的车辆把货物运往8个客户，车辆的载重能力为8吨，车速为50公里每小时，客户所需货物的重量，服务时间及访问时间窗口的具体要求由Tab.1给出。客户之间的距离如Tab.2所示。问题是寻找合适的路径，使得车辆运行总成本最小。
实验开始，将每个客户都放置一只蚂蚁，蚂蚁的个数与客户数相同。取α=1，β=3，γ=3，λ=1，ρ=0.8，θ=10。采用本文的算法，得到的最优解为:第一辆车：0-2-7-4-0;第二辆车：0-3-1-0;第三辆车：0-8-5-6-0。
将求解的结果与Clarke-Wright算法和遗传算法比较,从Tab.3中可以看出MMAS不失为带时间窗车辆路径问题的一个较优解。
四、结语
本文将MMAS算法应用于VRPTW问题中，充分发挥了其超强的贪婪搜索能力，获得了较为满意的实验效果。这次成功尝试再次表明了该算法在组合优化领域中是具有强大竞争力的，同时也证明了用这种方法解决具有一定的理论参考价值和实际意义。
参考文献:
[1]吴启迪汪 镭:智能蚁群算法及应用[M].上海科技出版社，2004，4
[2]刘云忠宣慧玉:动态蚁群算法在带时间窗车辆路径问题中的应用[J].中国科学工程,2005,12(7):35－40
基于蚁群算法的模糊控制规则优化 篇12
传统控制是建立在系统精确数学模型的基础上的,而实际系统常常存在复杂性、非线性、时变性、不确定性等问题,难以获得精确的数学模型。模糊控制作为一种新技术,不依赖于工业对象模型,他不是用数值变量而是用语言变量来描述系统特征,并根据系统的动态信息和模糊规则进行推理以获得合适的控制量,因而具有很强的鲁棒性,在诸多的复杂系统控制领域得到了广泛的应用。在模糊控制器的设计过程中,模糊规则通常是由专家经验来确定的,在专家经验难以获取的情况下,模糊控制器的设计将无法进行。为了解决这个问题,人们提出了很多种优化,例如粒子群算法、遗传算法等[1,2,3,4]。模糊规则的设计相当于一个组合优化问题,文章利用蚁群算法来优化模糊规则,并将其用于链梯速度控制系统中来验证该方法的有效性及优越性。
1蚁群算法分析
蚁群算法是由意大利学者Dorigo等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法。它是一种通用的启发式算法,可用来解决各种不同的组合优化问题。该算法最早成功地用于解决著名的旅行商问题(TSP)。它采用分布式并行计算机制,易于与其他方法结合,具有较强的鲁棒性。
蚁群算法的基本思想是:用蚂蚁的行走路线表示待求解问题的可行解,每只蚂蚁在解空间中独立地搜索可行解,解的质量越高,在“行走路线”上留下的信息素也就越多;随着算法的推进,代表较好解的路线上的信息素逐渐增多,选择它的蚂蚁也逐渐增多,最终整个蚁群在正反馈作用下集中到代表最优解的路线上,也就找到了最优解。而且蚂蚁还能够适应环境的变化。当蚁群的运动路径上突然出现障碍物时,蚂蚁亦能够很快重新找到最优路径。可见在整个寻优的过程中,虽然单个蚂蚁的选择能力有限,但是通过信息素的作用使整个蚁群的行为具有非常高的自组织性,蚂蚁之间交换着路径信息,最终通过蚁群的集体自催化行为找出最优路径。蚁群算法便是基于这种正反馈自催化(autocatalytic)行为产生的[5,6]。
蚁群算法通过候选解组成的群体的进化过程来寻求最优解,该过程包含两个基本阶段:适应阶段和协作阶段。在适应阶段,各候选解根据积累的信息不断调整自身结构;在协作阶段,候选解之间通过信息交流,以期望产生性能更好的解。
2蚁群算法优化模糊控制器
典型的模糊控制器的结构如图1所示,其中模糊规则库是需要优化的,优化前给定一个初始值,在优化过程中根据优化标准调整模糊规则库的值,最终将规则库确定下来[1]。
此处的模糊控制器采用双输入单输出,模糊规则采用传统形式如下:
IF A=ai AND B=bj THEN C=ck
其中A,B为输入,C为输出。
设每一个输入变量有S,M-,M,M+,B这5个模糊语言值可取,这样整个模糊系统最多可有5×5=25条模糊规则,即为最大规则基。规则辨识算法就是要确定这25条规则的后件(THEN的部分),也就是输出模糊值。
为了简化计算,隶属度函数采用等腰三角形,对于每条规则的后件可取S,M-,M,M+,B这5个模糊值,而当此条规则不存在时算法规定规则的后件取Z(Zero)。这样,整个25条模糊规则后件最优解的寻优空间为25×6的矩阵。在这里,用一维数组Rules[25]表示得到的规则,为了编写程序方便,将6个模糊集Z,S,M-,M,M+,B相应定义为0,1,2,3,4,5,设系统的25条模糊规则如表1所示。
为了实现对规则的辨识,算法先保持隶属度函数的初始参数不变。而初始的25规则的后件在(0～6)中随机选取,这样就基本建立了一个完整的初始模糊系统,这个系统对于给定的输入数据对将会有相应的输出。然后再利用蚁群算法对25条模糊规则的后件进行优化辨识。
利用已知的代表实际系统特性的输入输出数据对,对模糊规则进行训练学习,使得模糊系统对应于样本输入数据对的输出数据最大程度接近实际系统的样本输出。这样,训练过程完成后所得到的25条规则后件Rules[25]就是算法所辨识出的规则[5,6,7,8]。
为模拟实际蚂蚁的行为,首先引进如下记号:设m为蚂蚁的总数,τj(t)为t时刻在j规则节点上残留的信息素量。初始时刻,各条规则上信息素相等。蚂蚁k(k=1,2,…,m)在运动过程中,根据各条规则节点上的信息素量决定转移方向,p
其中,allowedk={n-tabuk}表示第k只蚂蚁下一步允许选择的规则的集合。这里用tabuk(k=1,2,…,m)表示已经选择过的规则。随着时间的推移,所经过路径上的信息素不断蒸发,经过l个时刻,l是规则总数,每经过一次循环,蚁群中的每一只蚂蚁都完成了一次符合规则的旅行,此时,各路径上信息素浓度要按下式修正,即:
τj(t+l)=ρ×τj(t)+Δτj (2)
式中ρ(0<ρ<1)表示在时间t和t+l之间经过路径上信息素的蒸发系数,系数ρ必须规定为小于l,是为了避免各路径上信息素量无限制地累积。(1-ρ)为信息素残留因子,而Δτj可表示为本次迭代中第k只蚂蚁释放在规则j上的信息素量。
经过n次迭代后,所有蚂蚁都将完成一次旅行,它们的禁忌表已被填满,此时,对每只蚂蚁k计算fitness(b),并且将其Δτj值按式(3)修正。然后,将这些蚂蚁所找到的最有规则储存下来,并将每只蚂蚁的禁忌表清空。
上述过程不断循环重复,直到达到最大收敛次数Ncmax。至此,可认为蚁群已找到最优的模糊规则[5]。算法流程图如图2所示。
3 仿真结果与分析
将设计的模糊控制器用于链梯速度控制系统中,系统的模型如图3所示[9]。
系统中的参数分别为:φf=1.02Wb;pn=2;J=1.954kg·m2;ne=1500r·min-1;v=0.5m·s-1;Kz=1;τz=0.3;k1=1;
通过MATLAB仿真得到系统使用蚁群算法优化前与优化后的响应曲线,如图4所示。图中虚线表示优化前的响应曲线,实线表示优化后的响应曲线。由图可以看出,采用蚁群算法优化后的模糊规则控制效果明显优于优化前,优化后系统的动态响应速度明显加快,过渡时间大大缩短,超调量有所减小,极大地改善了系统的性能。
4 结束语
本文成功地将蚁群算法应用到模糊规则的优化中,为解决无法获得专家经验的情况下设计模糊控制器的问题给出了一种可行的方法,仿真结果表明所得模糊控制器具有良好的性能。但是由于本文所采用的蚁群算法,在每次循环后,都会对所走过的路径进行信息素增强,所以搜索效率较低,下一步的研究重点是采用改进的蚁群算法来提高优化效率。
参考文献
[1]徐开军,朱伟兴.基于遗传算法的模糊控制器的优化设计——采用模糊数据挖掘技术[J].计算机工程与应用,2006,42(29):97-99.
[2]徐开军,张春艳.基于SCEA的模糊控制器的优化设计研究[J].微计算机信息,2010,26(2):39-41.
[3]Boubertakh H,Tadjine M,Glorennec P Y,et al.Comparisonbetween fuzzy PI,PD and PID controllers and classical PI,PD and PID controllers[J].International Review of Auto-matic Control,2008,1(4):175-183.
[4]Ko C N,Lee T L,Fan H T,et al.Genetic auto tuning andrule reduction of fuzzy PID controllers[J].IEEE Trans Sys-tems,Man,and Cybernetics,2006,41(5):291-297.
[5]师黎,陈铁军,李晓媛.智能控制理论及应用[M].北京:清华大学出版社,2009:317-320.
[6]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002:129-136.
[7]Kowalska T O,Szabat K.Control of the drive system withstiff and elastic couplings using adaptive neuro-fuzzy ap-proach[J].IEEE Trans Ind Electron,2007,54(1):228-240.
[8]Clerc M,Kennedy J.The particle swarm explosion,atability,and convergence in a multidimentional complex space[J].IEEE Trans,Evolutionary Computation,2002,6(1):58-73.