蚂蚁群算法（共7篇）
蚂蚁群算法 篇1
0 引 言
移动机器人路径规划属于研究机器人控制系统的重要应用基础问题,也是机器人研究领域中的一个重要分支。它是指在有障碍物的工作环境中,如何寻找一条从给定起始点到终止点的较优的运动路径,使机器人在运动过程中能安全无碰撞地绕过障碍物,且所走路线最短。对这一问题已有大量的研究,其中包括神经网络[1]、人工势场[2]、粒子群算法[3]、RRT算法[4]、遗传算法[5]等等,这些方法都在不同程度上提高了机器人路径规划的效率,但都存在一定的局限性。为了进一步改善性能,近几年,不少学者提出了路径规划蚁群算法[6,7],对此研究取得了不少成果,但其共同的问题是:所应用的算法基本是在原始蚁群算法基础上对单种群的改进,特别是传统蚂蚁算法及其改进算法中都是用充分利用正反馈机制,用信息素的浓度指导搜索方向,信息素浓度越高,路径被选择的概率大,使得算法在搜索过程中早期就能发现较优解,以至于陷入局部最优,算法出现停滞现象。作者在分析了导致传统蚁群算法早熟原因的基础上并依据对真实蚂蚁的最新研究成果[8],据此提出了一种多种群蚂蚁的全新机器人路径规划算法。该方法首先用栅格法对机器人运动环境进行建模,在此基础上,两组蚂蚁进行相向搜索,每组中都包含一定数量的分流蚁,当某路径被多只蚂蚁选择时,信息素浓度过高,此时分流蚁选择信息素较少的路径,实现了自动分流;针对凹形障碍物容易停滞死锁的情况,本算法引入了回退策略来跳出死锁;在搜索过程中采用了目标导引启发函数,有利于获得最优解和加快收敛。计算机仿真实验表明,即使在复杂的环境下,用本算法也可以较迅速地规划出一条全局优化的路径。
1 环境建模
本文采用栅格法建模,如图1所示,其中黑色表示障碍物,白色表示自由空间。
为了叙述方便,本文建立坐标系(图1),并作如下约定:
(1) 机器人Rob在二维平面上的有限运动区域记为AS。
(2) 机器人在水平方向上的行走步长为δ,并且AS在X、Y方向的最大值分别为Xmax和Ymax。以δ为步长形成一个栅格。则每行的栅格数Nx=Xmax/δ,每列的栅格数Ny=Ymax/δ。
(3) 记g∈AS为任意栅格,A为AS中g的集合,记OS={b1,b2,…,bn}⊆A为静态障碍集,其中b1 ,b2 ,…, bn为静态障碍物。
(4) ∀g∈A在坐标系中都有确定的坐标(x ,y),记为g(x ,y),x为g所在的行号,y为g所在的列号。令C={1,2,…,M}为栅格序号集,g(1,1)的序号为1,g(1,2)序号为2,g(2,1)序号为Nx+1…,如图1所示。gi∈A的坐标(xi,yi)与序号i∈C构成互为映射关系,序号i的坐标为:
xi=((i-1) mod Nx)+1 yi=(int)((i-1)/Nx)+1 (1)
式中,int为舍余取整运算,mod为求余运算。
规划的目的就是要机器人从给定栅格出发,绕过障碍,找出通往终点的路线,且要求极小化该路线所经过的栅格数。
2 多种群蚂蚁算法
2.1 算法的总体思路及问题定义
对真实蚂蚁的最新研究表明:蚂蚁具有自动分流功能,即出行的蚂蚁就像高速公路上的汽车一样,如果该路上蚂蚁过多,交通拥挤,后来的蚂蚁会自动选择另外的可行通道行走[8]。受此启发,在分析了导致传统蚁群算法早熟原因的基础上,提出了一种新的多种群蚂蚁机器人路径规划算法。本算法引入了分流蚁,当某节点已被多只蚂蚁选择时,后来的分流蚁则自动分流到其它节点。这样可以扩大搜索范围,增加解的多样性,能以较大概率搜索解空间的各个地方,找到更优路径。为了加快收敛,动态调节分流蚁的个数,随着迭代次数的增加,分流蚁的个数减少。当蚂蚁走进凹形障碍物时,采用回退策略解决算法的停滞,增强了算法对环境的适应性。本算法采用两组数量相等(均含有一定数量的分流蚁)的蚁群分别从机器人的起点和终点同时出发,对任意一只蚂蚁,在移动过程中如果在规定的最大步数内未到达终点,又未和另外一组蚂蚁中的任何一只蚂蚁相遇,则令其死亡,即将该蚂蚁从系统中删除,并重新初始化一只蚂蚁。
为模拟实际蚂蚁的行为,本文采用下列符号:Anti ={1,2,… k ,…,m} 表示一个蚂蚁家族所有蚂蚁的集合(本文中i=1,2),其中m为第i个蚂蚁家族的蚂蚁总数。用k 表示某一个蚂蚁且k∈Anti。为避免生成无效路径,任意一个蚂蚁k都有一个禁忌表,记为tabuk,它记录该蚂蚁k已经选择并行走过的所有路径点,它随着蚂蚁的行走动态调整。蚂蚁k任意时刻所处的位置为P,∀P 在∑0都有确定的坐标(x, y) ,记k在ti 时刻处于某栅格的位置为P(xi(ti),(yi(ti ))简记为Pi 或P(ti)。
定义1 任意栅格间的距离指两栅格间的连线长度,记作d(gi,gh)或d(Pi,Ph), i,h∈C,由式(2)计算,特别的,若有d(gi, gj),i,j∈C,满足|j-i|=1或|j-i|=Nx,(gi, gj) 在AS中的连线则称一个边eij,简称边ij,d(gi, gj)则为边长,记作dl。
定义2 在t时刻蚂蚁由栅格gi选择gj时,在栅格gi与gj连线上留下一定的信息量,记为τij(t)。它具有上限值τmax和下限值τmin。
定义3 ∀g∈A,g∉OS,则称g为可行节点,所有可行节点的集合称可行域,记为FS。
定义4
图1中的粗线示出了按本定义算出的g(4,4)的邻域。
定义5 设ti时刻,k处于gi,FSkBRi(gi(xi,yi))={g|g∈BRi(gi(xi,yi)),g∉Os,i∈C}称ti时刻k在BRi的可行域。
定义6 假设tabuk={ P(t0), P(t1), …, P(ti)}且有t0<t1<,…,<ti,为k从t0到ti时刻已走栅格位置的集合, ti+1时刻,∀P(ti+1)∈FSkBRi 且∀P(ti+1)∉ tabuk,则称∀P(ti+1)为ti+1时刻的可行点,可行点的集合用FPS表示,显然,根据图1,|FPS|≤8且|FPS|≤|FSkBRi|。
定义
η1i(gi)、η2j(gj)分别称Ant家族1、Ant家族2的第k个蚂蚁选择栅格gi或gj的启发函数,D为权重常系数,gbegin为出发点,gend为要到达的目标点。
定义8k1∈Ant1,k2∈Ant2,k1从gbegin出发,k2从gend出发,经过n个时刻,k1、k2的位置为分别为Pk1、Pk2,若有|d(Pk1,Pk2)|=0,则称k1与k2相遇。
定义9tabuk中各位置点在AS中的连线称P0到Pe的路径其长度记作L,由下式计算:
定义10 当分流蚂蚁的个数不为零时,依据公式(4)调节分流蚂蚁的个数
antma=ma-b×n (4)
其中antma是剩余分流蚂蚁的个数,n是已迭代次数,b是递减系数,ma是最初的分流蚂蚁的个数。
2.2 算法步骤
算法将两个蚂蚁家族的各m个蚂蚁分别放置在gbegin和gend,其中蚂蚁家族1的m个蚂蚁以gbegin为出发点,以gend为目标;蚂蚁家族2则相反,两个蚂蚁家族相向搜索,从而协作完成规划工作。对于两个蚂蚁家族中的每一个蚂蚁,以当前节点为中心,按一定策略选择并行走到下一可行节点。由于两个蚂蚁家族除了采用的启发函数不同、出发点不同外,算法完全相同,为了减少变量的下标,下面以蚂蚁家族1的搜索算法为例进行说明,并将表示蚂蚁家族1的所有下标省略 。本文算法如下:
Step1 将m只蚂蚁(其中包含ma个分流蚁)放置在出发点gbegin,并设置到禁忌表tabuk中(k=1,2,…,m)。令τij(0)=τ0 (τ0为常数)。设置迭代计数器n=0,最大代数为 MAX。
Step2
(1) 常规蚂蚁∀k,以当前节点gi∈FS为中心,按式(5)或式(6)选择并行走到下一节点gj,且有gj∈FSkBRi(gi),gj∉tabuk。节点选择算法如下:
式中,j— j∈C,蚂蚁k所选gj的节点序号,在此省略了上标k;S —由式(6)决定的随变量;q — 随机数(0<q≤1);q0 — 初始化时给定的阈值;ηj(gj)— 由定义7给出的启发信息;β —在边 eij上残留信息的重要程度;p
q和q0是为了防止出现停滞而设的随机搜索策略所需参数,以增加搜索的多样性。当 q> q0 时,计算|FPS|个节点的转移概率p
将j加入禁忌表tabuk。
(2) 分流蚁∀k,以当前节点gi∈FS为中心,按式(7)或式(8)选择并行走到下一节点gj,且有gj∈FSkBRi(gi),gj∉tabuk。
式中:SS由式(8)计算,其他参数同上。
将j加入禁忌表tabuk。
(3) 若在选择的过程中,发现|FPSi|=0,此时,蚂蚁执行回退策略,蚂蚁回退到gi,同时将gj标记为障碍格,回退路径上的信息素清零;再执行Step2,直到有可选节点为止。
Step3 局部信息素更新
用参数1-ρ表示信息消逝程度,每一只蚂蚁选择完一个节点后, 按式(9)进行局部信息更新:
τij(n+1)=(1-ρ)τij(n)+ρ Δτ
式中:
当τij(n+1)<τmin时,令τij(n+1)=τmin。
其中,Q1为常数,τmin是设定的最小值;dl是蚂蚁k已走过边的边长,可 由(2)式计算。w是蚂蚁k在本次搜索中已走过的边数; ljb是k在本次搜索中到当前时刻为止已走过的路程(边的累加总长)。
Step4 ∀k, k=1,2, …,m,选择完第j个节点后,按定义8定义的条件,检查两族蚂蚁中的所有蚂蚁是否已有蚂蚁相遇,若有,则转step5;否则,令i=j,返Step2开始选择下一个节点,直到有蚂蚁相遇或所有节点选择完毕,若重复多次仍无蚂蚁相遇,则可以判断起点与终点间无可行通道。
Step5 当两族中的两只蚂蚁或多只蚂蚁满足定义8的相遇条件时,将相遇蚂蚁所走通道连接,并用式(3)计算其路程L。并保存最短路程Lkmin(Lkmin=min Lk )。
将本次搜索得到的Lkmin与已得到的历史最优长度Ld比较,若有Lkmin<Ld 则用Lkmin替换Ld,并记忆最佳通道的节点集合。
Step6 全局信息素更新
本次搜索相遇并完成通道连接后,将本次搜索最短通道上的信息素按式(10)调整:
τ
式中,α— 全局信息素挥发系数;Lkmin— 本次搜索最佳通道的长度;ij∈global-best-tour表示蚂蚁k所走的边ij属于最佳通道。
Step7 当分流蚂蚁的个数不为零时,依据公式(4)减少分流蚂蚁的个数;令迭代次数n加1,若不等于MAX,则清空禁忌表,重复上述搜索过程,直到n=MAX为止。最终记忆的最佳通道即为规划出的最优路径。
3 试验仿真及与其他算法的比较
本文实验环境为:CPU赛扬2.66G,内存为 512M, 编译工具VC++6.0。
首先对30×30的较复杂环境进行了测试,对于如图2所示的复杂地形,黑色表示障碍格,图2示给出了用本文算法得到的从出发点到右下角目标点的一条路径,很显然该路径长度基本最优。这是目前大多数算法做不到的。运行参数设定如下:蚂蚁数为20,ma=5、β=2、α=1、ρ=0.1、MAX=50、Movemax=50。运行时间为9.218s。
接着又在栅格规模为30×30的环境下和文献[9]的算法进行了对比,所得到的路径如图3黑线所示。运行参数设定如下:蚂蚁数为20,ma=5、β=2、α=1、ρ=0.1、MAX=80、Movemax=50。在图3环境下文献[9]中的算法(ACO-grid)运行时间为41.7s,得到的长度为58,路径如图3红线所示,而本文算法用时9.586s,得到的长度为49.2,路经如图3黑线所示。
为了进一步说明本文算法的优越性,本文在同一环境中与RRT [10]算法进行了性能对比。每种算法求解时各执行20次,性能对比如表1所示。
当环境信息未知时,可以借鉴文献[7]的思想,首先将全局目标点映射到机器人视野域内作为子目标点,机器人用传感器探测视野域内的环境信息;然后利用本文算法迅速规划出一条从当前位置到局部子目标点的最短路径,沿此路径,机器人向前一步;机器人每前进一步,都进行上述规划过程。因此规划出的局部路径是实时动态修改的。
4 结 论
本文在分析了导致传统蚁群算法早熟原因的基础上,提出了一种新的多种群蚂蚁算法,算法模拟真实蚂蚁的觅食行为和拥挤分流行为,本质上的优势在于发挥了群体智能的作用。用两组智能体分头协作搜索,更加提高了搜索效率。算法设有随机搜索策略,保证了搜索的多样性,使搜索不易陷于停滞。设有回退策略,防止在有凹形障碍物时算法死锁停滞。实验结果也表明,只要有可行通道客观存在,即使在异常复杂的地形环境,本文算法也能迅速找到一条优化路径。
参考文献
[1]Janglov D.Neural Networks in Mobile Robot Motion[J].International Journal of Advanced Robotic Systems,2004,1(1):15-22.
[2]Josu Agirrebeitia,Rafael Aviles,Igor F De Bustos,et al.A new APF strategy for path planning in environments with obstacles[J].Mecha-nism and Machine Theory,2005(40):645-658.
[3]孙波,陈卫东,席裕庚.基于粒子群优化算法的移动机器人全局路径规划[J].控制与决策,2005,20(9):1052-1060.
[4]Lindemann SR,Lavalle SM.Steps toward de randomizing RRTs[C]//IEEE/RSJInt.l Confon Intelligent Robots and Systems,2003.
[5]Yanrong Hu,Simon X Yang.A Knowledge Based Genetic A1gorithm for Path Planning of a Mobile Robot[C]//Proceedings of the2004IEEE in-ternational Conference on Robotics&Automation New Orleans,LA April,2004:4350-4355.
[6]Mohamad M M.Ant Colony Robot Motion Planning[C]//Proceeding of IEEE EUROCON International Conference on Computer as a Tool,(EUROCON2005),Belgrade,Serbia and Montenegro,November:2005:213-216.
[7]朱庆保.复杂环境下的机器人路径规划蚂蚁算法[J].自动化学报,2006,32(4):586-593.
[8]Dussutour A,Fourcassie V,Helbing D,et al.Optimal traffic organiza-tion in ants under crowded conditions[J].Nature,2004,428:70-73.
[9]张美玉,黄翰,郝志峰,等.基于蚁群算法的机器人路径规划[J].计算机工程与应用,2005,41(9):34-37.
[10]国海涛,朱庆保,徐守江.基于栅格法的机器人路径规划快速搜索随机树算法[J].南京师范大学学报:工程技术版,2007,7(2):58-61.
蚁群算法与粒子群算法的比较研究 篇2
由简单个体组成的群落与环境以及个体之间的互动行为称群智能(swarm intelligence)。群智能算法作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点,群智能在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题求解方案提供了基础。目前,群智能理论研究领域主要有两种算法:蚁群算法(Ant Colony Optimization,ACO)和粒子群算法(Particle Swarm Algorithm,PSO),前者是蚂蚁群落食物采集过程的模拟,后者是鸟群觅食过程的模拟。本文对这两种算法的原理、模型、应用等方面进行比较分析,并对这两种算法的改进以及与其它算法的混合做出总结。
一、蚁群算法
蚁群算法是由Colorni、Dorigo和Maniezzo通过对蚁群觅食行为的研究,于1991年提出的一种仿生进化算法[1],利用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些离散系统优化中的问题。蚂蚁是一种社会性昆虫,通过一种特有的通信机制,其群体行为展现出高度协作性,能够完成复杂的任务,并且,蚂蚁还能够适应环境变化随时调整搜索路径。作为一种随机搜索处算法,与其他模型进化算法一样,ACO也是通过侯选解组成的群体的进化过程来寻求最优解。
蚁群算法首先被成功应用于旅行商问题(TSP)上,以此为例算法的寻优过程[2]:设有m只蚂蚁,每只蚂蚁根据信息素浓度选择下一个城市(tij(t)为t时刻城市i和j之间路径上残留的信息素浓度,dij(i,j=1,2,...,n)表示城市i和j之间的距离),规定蚂蚁走合法路线,除非周游完成,不允许转到已访问城市。完成周游后,更新蚂蚁访问过的每一条边上的信息素。
初始时刻,各路径的信息量tij(0)相等,m只蚂蚁被放置到不同的城市上。蚂蚁k(k=1,2...,m)在运动过程中,根据各条路径上信息量决定转移方向,表示在t时刻蚂蚁k由位置i转移到j的概率。
其中,allowedk表示蚂蚁k下一步允许转移到的城市集合,随k的行进而改变;信息量τij(t)随时间的推移会逐步衰减,用1-ρ表示它的衰减程度;α,β分别表示蚂蚁在运动过程中积累信息量及启发式因子在蚂蚁选择路径中所起的不同作用;ηij为由城市i转到j的期望程度,可根据某种启发算法而定。
经过n个时刻,蚂蚁k走完所有城市,完成一次循环。此时,根据式(2)一(4)更新各路径的信息素:
其中:ρ表示信息素挥发系数,Δtij表示本次循环中路径ij上的信息量增量,表示蚂蚁k在本次循环中在城市i和j之间留下的信息量,其计算方法根据不同模型而定,最常用的是ant-cycle system:
其中:Lk表示蚂蚁k环游一周的路径长度,Q为常数。
算法流程如图1所示:
二、粒子群算法
Kennedy和Eberhart于1995年受鸟群觅食行为的启发提出了粒子群优化算法(Particle Swarm Optimization,PSO)[3]。PSO中,每个优化问题的解视为d维搜索空间中的一个粒子,粒子在搜索空间中以一定速度飞行,所有的粒子都有一个由被目标函数决定的适应值,并且知道自己到目前为止发现的最好位置,每个粒子利用个体和全局最好位置更新位置和速度。
假设m个粒子组成一个种群并在D维空间搜索,第i个粒子在第t代的位置表示为一个D维的向量Xi(t)=(xi1,,xi2,…,xD),飞翔速度为Vi(t)=(vi1,vi2,...,vD),粒子本身历史最佳位置为Pi(t)=(pi1,pi2,...,pD),群体历史最佳位置为Pg(t)=(pg1,pg2,...,pD)。PSO算法迭代公式如下:
其中,w为惯性权重,使粒子保持运动的惯性,使其有扩展搜索空间的趋势;c1和c2为加速系数,代表了将每个粒子拉向Pi和Pg的随机加速项的权重;r1和r2是两个独立的介于[0,1]之间的随机数,t为进化代数。
算法流程如图2所示:
三、两种算法的比较分析
1算法各自优缺点
(1)由于群智能算法采用的是概率搜索算法,ACO和PSO具有共同的优点[4]:
①鲁棒性:由于算法无集中控制约束,不会因个别个体的故障而影响整个问题的求解。
②扩展性:信息交流方式是非直接的,通信开销少。
③并行分布性:可充分利用多处理器,适合于网络环境下的工作状态。
④优化过程无需依赖具体问题的数学特性,例如可微、线性等。
⑤算法简单容易实现:系统中个体能力简单,执行时间短。
另外,PSO还具有如下优点:
①群体搜索,并具有记忆功能,保留个体和全局的最优信息;
②协同搜索,同时利用个体和全局的最优信息指导进一步搜索。
(2)ACO和PSO也存在着局限性:
①优化性能在很大程度上依赖于参数设定,受初始值影响较大。
②容易产生早熟收敛。
另外,ACO收敛速度慢,只有小部分的ACO算法能够被证明是值收敛的,并且在实际应用中常常出现一种有害的搜索偏向现象,即二级欺骗现象。
PSO局部搜索能力差,搜索精度不高,并在理论研究上尚未完善,缺少算法设计的指导原则。
2应用领域
●ACO本质上适合于求解离散组合优化问题,在旅行商问题上取得成功应用后陆续渗透到其它领域。在指派、调度、子集、带约束满足等组合优化问题时达到了高效的优化性能。并在图着色、电路设计、二次分配问题、数据聚类分析、武器攻击目标分配和优化、大规模集成电路设计、网络路由优化、数据挖掘、车辆路径规划、区域性无线电频率自动分配、集合覆盖等优化领域得到了成功应用。
●PSO本质上适合于处理连续优化问题,但如果对求解问题进行变形或修正速度和位置更新公式也能将其应用于离散优化问题上。并且,鉴于其通用性和有效性,在解决一些典型优化问题时,其性能甚至超过了遗传算法,已成功应用于训练人工神经网络、函数优化、约束优化、多目标优化、动态优化、参数优化、组合优化、模糊系统控制、电力系统、信号处理、模式识别、生物医学等领域中。
3与其它算法混合
由于ACO与PSO具有容易与其它算法结合的特点,根据各算法的优缺点,在算法中结合其它优化技术,以提高算法的优化性能。
①蚁群算法与差分演化结合:针对蚁群算法对参数控制的依赖性、早熟和停滞等现象,以及易与其他算法结合的特点,将差分演化算法应用到蚁群算法的参数选取中,将蚁群算法的参数作为差分演化算法解空间的向量元素,自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。
②蚁群算法与粒子群算法结合:针对蚁群算法容易出现早熟现象以及算法执行时间过长的缺点,将粒子群算法引入到蚁群算法中,让蚂蚁也具有粒子的特性。
③粒子群算法与模拟退火结合:先利用PSO算法的快速搜索能力得到一个较优的群体,然后利用SA的突跳能力对部分较好的个体进行优化。
④粒子群算法与遗传算法结合:针对PSO容易早熟的缺点,在PSO中引入启发性变异机制,以扩展了算法的搜索区域,提高了算法的速度和精度且不容易陷入局部最优。
⑤粒子群算法与差分演化结合:针对粒子群算法易陷入局部极小点、搜索精度不高等缺点,在算法改进方面引用差分演化算法的变异操作,从而避免算法收敛到局部。
四、展望
群智能算法采用分布式计算机制、鲁棒性强、可扩充性好、优化效率高、并且简单易于实现,为解决实际优化问题提供了新的途径和方法。除了本文提出的ACO和PSO,群智能算法还包括研究蜜蜂通过与环境之间的信息交互实现安排工作的蜂群算法[5]、李晓磊博士通过模拟鱼群觅食行为和生存活动提出的鱼群算法[6]。作为一门新兴领域,群智能算法尚缺乏系统的分析和坚实的数学基础,实现技术不规范,在适应度函数选取、参数设置、收敛理论等方面还需要做进一步研究与探索。在此基础上,对算法加以改进或混合其他技术,以提高算法优化性能也是值得深入研究的一个方向。并且需不断拓宽其应用领域,以进一步推广群智能算法的应用。
参考文献
[1]A.Colorni,M.Dorigo,G.Theraulaz.Swarm intelligence: From natural to artificial systems[M].New York:Oxford Universyty Press,1999.
[2]宋雪梅,李兵.蚁群算法及其应用[J].河北理工学院学报,2006年2月,第28卷第1期:42-45.
[3]Kennedy J,Eberhart R.Particle Swarm Optimization[R].In:IEEE International Conference on Neural Networks,perth,Australia 1995:1942-1948.
多种群粒子群分层进化优化算法 篇3
粒子群优化算法 (Partical Swarm Optimization Algorithm, PSO) 是由美国学者Kenndy和Eberhart于1995年提出的一种群体智能优化算法[1], 现已广泛应用于科学和工程领域。但它存在收敛速度慢、容易陷入局部最优值的缺陷。本文介绍的多种群粒子群分层进化算法, 对具有不同适应度值的粒子采取不同的进化方式, 加快了算法收敛的速度和精度。
2 多种群粒子群分层进化优化算法
2.1 标准PSO
用标准PSO求解时, 先初始化一群随机粒子, 通过让粒子不断更新自己的位置, 来找到函数的最优解。在每次更新中, 粒子通过两个“极值”来调整自己的位置:粒子本身取到的最优值Pbest和粒子群找到的最优值Gbest。更新公式为:
其中, c为加速因子, rand () 是0-1之间的随机函数。
2.2 算法改进
美国的Shi和Eberhart引入惯性权重的概念[2], 将更新公式变为:
通过惯性权重w来控制前一速度对当前速度的影响。文献[3,4]基于控制理论分层控制的思想, 把PSO用于多种群2层优化, 文献[5]提出把粒子群分成两部分, 让粒子分别朝向最好最坏方向飞行。本文提出的分层进化让适应度值优的粒子采取较小的w值, 增加其局部搜索能力;让适应度值差的粒子采取较大w值, 增加其全局搜索能力, 并让适应度值特别差的用好的粒子代替, 便于粒子更快更好的找到最优值。
2.3 算法流程
Step 1.初始化n个种群, 每个种群m个粒子, 每个粒子记为Xij, 即第i个子群的第j个粒子;
Step 2.计算粒子的适应度值, 找出个体最优Xijbest、子群最优Li和种群最优G;
Step 3.根据不同适应度值将粒子分成不同层次, 对不同层次的粒子分别采取不同的惯性权重ωi, 将适应度值特别差的粒子用好的粒子替换;
Step 4.按如下公式逐个更新粒子:
Step 5.达到迭代次数或误差要求结束, 否则转Step2。
3 算法验证
为了比较算法的性能, 取Sphere、Ackley、Rastrigin、Griewank四个基准函数进行测试, 并与粒子群算法进行比较。四个函数形式为:
实例中取3个粒子群, 每群30个粒子, 每个粒子设定为3维, c1, c2, c3均取2, w按分层取得
对于适应度值与最优值差值大于10000的用最优粒子代替, 基本PSO中取w=0.7, 其他参数一样, 让每个函数分别运行100遍, 迭代90000次, 两种算法最优适应度值的平均值分别为[0.045064 0.68787 0.24894 0.14151], [0.259410.69659 0.26889 0.12891]。四个函数里边三个比基本粒子群寻到的结果要优, 两个算法的结果图像如图1、图2所示。
4 结论
本文提出的粒子群分层进化方法让具有不同适应度值的粒子取不同的惯性权重, 独立的改变自己的速度和位置, 这比基本粒子群对所有粒子采取相同操作更具针对性, 能让粒子更快更好的收敛到最优值, 通过对测试函数进行计算的结果图像很好地显示了粒子朝最优值逼近的趋势。但用来进行划分的适应度值的区间还有待进一步研究, 本文只是根据经验提出, 希望以后能有一种更好的划分适应度值的理论方法。
参考文献
[1]Kennedy J, Eberhart R C.Particle Swarm Optimization[C].IEEE International Conference on Neural Networks, Piscataway:IEEE Service Center, 1995:1942-1948.
[2]Shi Y, Eberhart R C.A Modified Particle Swarm Optimizer[C].IEEE World Congress on Computational Intelligence, 1998:69-73
[3]吕林, 罗绮, 刘俊勇等.一种基于多种群分层的粒子群优化算法[J].四川大学学报 (工程科学版) .2008;40 (5) :171-176
[4]吕林, 罗绮, 刘俊勇等.基于多种群分层粒子群优化的配电网络重构[J].电网技术.2008;2 (32) :42-45
粒子群算法的改进算法研究 篇4
基本PSO算法虽然比较简单,实现相对容易,不需要调整太多的参数,同时算法的早期收敛速度也比较快；但算法后期会受到随机振荡现象的影响,导致算法搜索到全局最优解的时间比较长,减慢了收敛速度;并且在一定程度上使其局部搜索能力表现较差,极易陷入局部最小值,精度降低,易发散[2]。针对基本粒子群算法的收敛精度问题,该文提出了一种新的改进粒子群优化算法—LPSO。
1 改进PSO算法研究
1.1 基本PSO算法
随机初始一群粒子,每个粒子均不包括体积和质量信息,将每个粒子都看作为优化过程中的一个可行解,粒子的好坏通过一个事先设定好的适应度函数来进行确定。优化过程中,每个粒子都将在可行解空间中进行运动,由一个速度变量决定其方向和距离。通常情况下粒子将追随当前的最优粒子,并经过不断的迭代搜索最后得到全局最优解。在每一次迭代过程中,粒子都将会跟踪两个最优值:一个是粒子本身迄今为止找到的最优解,即局部最优解;另一个是整个粒子群体到目前为止找到的最优解,即全局最优解[3]。
假设一个由n个粒子组成的粒子种群在d维的搜索空间中按照一定的速度进行飞行。粒子i在t时刻的状态属性设置如下:
位置:
Xi(t)=(xi1(t),xi2(t),…,xid(t)
xid (t)∈[Ld,Ud]
其中Ld为搜索空间的下限,Ud为搜索空间的上限;
速度:
其中:vmin为最小速度,vmax为最大速度;
个体最优值位置:
Pi(t)=(pit(t),pi2(t),…,piD(t))
全局最优值位置:
pg(t)=(Pgt(t)pg2(t)…,pgD(t))其中:1≤d,1≤i≤M。
那么粒子在t+1时刻的位置可以通过下式来得到:
式中,r1、r2都为均匀分布在(0,1)区间的随机数;c1、c2是学习因子,一般取2。
基本的PSO算法尽管比较简单,实现也相对容易,并且不需要调整太多的参数,早期收敛速度快;但同时也存在其局限性,由于粒子在移动时没有选择性,即使下一个粒子位置的评价函数值较差,粒子还是利用逐个位置来代替当前位置,这样就使得粒子很容易跳出最优解附近的某一邻域,因此在一定程度上表现出较差的局部搜索能力,比较容易陷入局部最小值,降低了精度,也易发散[4]。鉴于基本粒子群算法还存在一些不足之处,该文提出了一种新的改进的粒子群算法,下面将对其做具体介绍。
1.2 粒子群算法的改进算法研究
该文所提出的改进的粒子群算法主要是在基本粒子群算法基础上,对以下几个方面做了改进:
(1)惯性权重模型。
由于惯性权重w较大时,算法具有较强的全局搜索能力;w较小时,则算法局部搜索能力较强。所以本文中采用线性模型,随着迭代次数的增加,将w由初始的0.9线性递减至0.4,以达到期望的优化目的。权重函数w由下式确定:
式中Wmax为最大惯性权重,一般取0.9,wmin为最小惯性权重,一般取0.4。
(2)学习因子模型。
学习因子c1、c2表示粒子向个体最优值和全局最优值进化的随机加速权值。当c1、c2都等于0时,粒子会按照当前速度进行飞行,直到运动至边界处。当学习因子较小时,粒子将会在远离最优值区域内发生振荡现象;较大的学习因子则可以促使粒子快速向最优解区域内移动。所以该文中采用自适应模型,如下式所示:
式中cmax为最大学习因子,Cmin为最小学习因子,MaxDT为最大迭代次数,t为当前迭代次数。
(3)粒子位置更新方程的改进。
基本PSO算法前期,精度较低,易发散。如果参数较大的话,在后期收敛速度会变慢,从而无法继续进行优化。在进化规划中,算法中若带有高斯变异和柯西变异算子时,算法都会取得较好的收敛效果,因此,该文中对个体最优解加入了高斯算子,每次找到一个个体最优值时,将在其周围利用高斯算子进行局部搜索。这样不仅可以提高算法前期的收敛精度,还可以改进算法后期的收敛速度,可以有效避免后期在最优解附近发生振荡。所以该文中的粒子位置通过下式来进行更新:
是均值为0,方差为1的高斯变量,fmin是n个粒子中的最小适应函数值,即当前最优值,β是尺度因子,通常取0.6。
(4)早熟收敛的改进策略。
PSO运行过程中,如果其中一个粒子发现一个当前最优位置,此时其他的粒子会快速向其聚集。如果该最优位置是个局部极值点,或者两个粒子均处于局部极值点,此时整个粒子种群将不可能在解空间内重新进行寻优,导致算法失去了搜索能力,陷入局部最优,这一现象就称为早熟收敛。该文对会与当前最优解重叠的粒子加入交叉操作过程,这样可以使该粒子状态重新更新,寻找新的搜索区域,从而跳出函数的局部极值点。首先给定一个阈值,如果其中一个粒子与当前最优粒子的位置距离小于之前设定的阈值,则对其进行交叉操作。具体的交叉公式如下:
式中x是粒子位置,x为粒子速度,pi是介于[0,1]之间的一个随机数,x'ibest为局部最优解。
2 仿真实验
(1)粒子群算法性能比较仿真。
为了验证改进粒子群算法的有效性,该文中选取标准的测试函数,分别利用基本粒子群算法和改进后的粒子群算法对函数进行优化,寻找适应度函数的最优解。
测试函数:Griewank函数
式(6)中的X表示一个粒子,xi为粒子的每个分量,d为每个粒子的维数[3]。
首先在[-10,10]的区间内均匀生成两组数,作为初始的粒子种群,数的个数为生成粒子的个数,每个粒子都是二维的,则该函数的三维图形如图1所示。由图可以看出:该函数存在多个局部极值点,但只存在唯一的全局最优点在(0,0)处。
该文在进行仿真实验过程中的相关参数设置如下:学习因子cimin=2,cimax=5,粒子个数n=100,粒子维数D=10,粒子位置范围xi∈[-100,100],最大迭代次数选取为100次,交叉操作过程中的阈值g取0.5,尺度因子β取0.6。仿真结果如下,图2中描述的是函数的最优适应值与迭代次数之间的关系。
由上述仿真结果可以看出,改进的粒子群算法(LPSO)较基本粒子群算法,不管是收敛精度还是循环迭代次数,都有所提高,验证了改进算法的有效性。
3 结语
该文在基本PSO的基础上,对参数的选择进行了调整,同时引入高斯算子及交叉操作过程。仿真结果证明,改进后的算法收敛效果较好。
参考文献
[1]张必兰.改进的粒子群优化算法及应用研究[D].重庆:重庆大学,2007.
[2]李丽,牛奔.粒子群优化算法[M].北京:冶金工业出版社,2009.
[3]吴进华,吴华丽,周仕.基于模拟退火的粒子群算法[J].仪器仪表学报,2008.
[4]Yumao Li.Particle swarm optimization algorithm research and improvement[D].Northwestern university master degree thesis,2009.
[5]任小波,杨忠秀.一种动态扩散粒子群算法[D].银川:宁夏工程学院,2010.
蚁群算法概述 篇5
1、蚁群算法的基本原理
在自然界真实的蚁群觅食过程中, 蚁群在没有视觉的情况下通过个体之间交换信息素, 能够在较短的时间内找到食物和蚁巢之间的最短路径。生物学家的研究已经表明, 一只蚂蚁的记忆和智能是非常有限的, 但是, 由于蚂蚁之间可以通过一些信息素进行协同作用, 实现蚂蚁之间的信息交流和传递, 可以共同做出令人惊讶的行为。
为了阐述蚁群算法的机理[2], 下面以蚂蚁搜索食物的过程为例, 分析蚂蚁是如何通过上述的信息交流和传递的协同作用, 最终找到从蚁穴到食物源的最短路径的。
图1.1中, A为蚁穴, E为食物源, 从A到E有两条路径可走, ABE是长路径, ACE是短路径。蚂蚁走过一条线路以后, 在其路径上会留下信息素气味, 后来的蚂蚁就是根据留在各路径上的这种气味的强度选择应该移动的方向。图1.1 (a) 表示起始时的情况, 假定蚁穴中有4只蚂蚁, 分别用1, 2, 3, 4表示。开始时蚁穴中蚂蚁1, 2向食物源E移动, 由于线路ABE和ACE均没有蚂蚁通过, 在这两条路径上都没有原始的信息素气味, 因此蚂蚁1和2选择这两条线路的机会均等。假设蚂蚁1选择ABE线路, 蚂蚁2选择ACE线路, 并且假定各个蚂蚁行走的速度相同, 当蚂蚁2到达食物源E时, 蚂蚁1还在途中, 如图1.1 (b) 所示。蚂蚁2到达食物源以后就返回, 这时从B点返回也有两条线路的选择, 而哪一条线路上的信息素气味重, 就选择哪一条。因为蚂蚁1还在途中, 没有到达终点, 即此时在EBA线路上靠近B端处, 蚂蚁1还没有留下信息素气味, 所以蚂蚁2返回蚁穴的路径只有一个选择, 就是由原路返回。当蚂蚁2返回到A端时, 蚂蚁3开始出发, 蚂蚁3的线路选择将必定是ACE, 因这时ACE线路上信息素的气味比ABE线路上重 (ACE路径上已有蚂蚁两次通过) , 如图1.1 (c) 所示。当蚂蚁1到达食物源B点时, 由于同样的理由, 蚂蚁1所选择的返回线路必将是ECA, 如图1.1 (d) 所示。如此继续下去, 由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:沿路径ACE移动的蚂蚁越多, 则后来者选择该路径的概率就越大, 这正是蚁穴到食物源的最短路径。蚂蚁个体之间就是通过这种信息的交流达到最佳食物搜索的目的[3]。
在自然界中, 蚁群的这种寻找路径的过程表现为正反馈的过程, 与人工蚁群的寻优算法极为一致。如果我们将在优化求解中那些只具备简单功能的单元看作"蚂蚁", 那么上述寻找路径的过程可以用于解释人工蚂蚁的寻优过程。[4]
由以上分析可知, 人工蚁群和自然界蚁群的相似之处在于:两者优先选择的都是含"信息素"浓度较大的路径;人工蚁群和自然界蚁群的区别在于:
(1) 人工蚂蚁具有记忆或智能功能, 它能够记忆已经访问过的节点。
(2) 人工蚂蚁具有一定的视觉, 人工蚁群在选择下一条路径的时候, 并不是完全盲目的, 而是按一定的算法规律有意识得寻找最短路径。
(3) 人工蚂蚁的生活环境是时域离散的。
2、蚁群算法的特点
从蚁群算法的原理不难看出, 蚁群的觅食行为实际上是一种分布式的协同优化机制。单只蚂蚁虽然能够找到从蚁巢到食物源的一条路径, 但找到最短路径的可能性极小, 只有当多只蚂蚁组成蚁群时, 其集体行为才表现出蚂蚁的智能 (发现最短路径的能力) 。在寻找最短路径的过程中, 蚁群使用了一种间接的通信方式, 即通过向所经过的路径上释放一定量的外激素, 其它蚂蚁通过感知这种物质的强弱来选择下一条要走的路。
在蚁群的觅食行为中, 另一个重要的方面是自催化机制和解的隐式评估。自催化机制实际上是一种正反馈机制, 解的隐式评估指蚁群将先走完较短的路径。自催化机制和解的隐式评估相结合, 极大地提高了问题的求解效率。即对于越短的路径, 蚂蚁将越早走完, 从而使更多的蚂蚁将会选择该路径。当然在使用自催化机制时, 要努力避免早熟现象。在蚁群算法中, 使用外激素蒸发和随机状态转移来弥补自催化机制的缺陷。蚁群算法的主要特点概括如下:
(1) 采用分布式控制, 不存在中心控制。
(2) 每个个体只能感知局部的信息, 不能直接使用全局信息。
(3) 个体可改变环境, 并通过环境来进行间接通讯。
(4) 具有自组织性, 即群体的复杂行为是通过个体的交互过程中突现出来的。
(5) 是一类概率型的全局搜索方法, 这种非确定性使算法能够有更多的机会求得全局最优解。
(6) 其优化过程不依赖于优化问题本身的严格数学性质, 诸如连续性、可导性, 及目标函数和约束函数的精确数学描述。
(7) 是一类基于多主体的智能算法, 各主体间通过相互协作来更好的适应环境。
(8) 具有潜在的并行性, 其搜索过程不是从一点出发, 而是同时从多个点同时进行。这种分布式多智能体的协作过程是异步并发进行的, 分布并行模式将大大提高整个算法的运行效率和快速反应能力。
3、蚁群算法的应用
对蚁群算法的应用研究一直非常活跃。由于蚁群算法不依赖于问题的具体领域, 所以在很多学科有广泛的应用。
(l) 组合优化
继M.Dorigo首先将蚁群算法应用于TSP问题之后, V Maniezzo[5]等人将蚁群算法应用于QAP。最近几年, Gambardella[6], Taillard[7]和Stutzle[8]也发表了一些用蚁群算法求解QAP问题的文章。目前, ACO己是求解QAP问题最有效的算法之一。A Colomi[9]等人首先将蚁群算法应用于车间作业调度问题 (Jobshop Scheduling Problem, 简称JSP) 。Costa和Herz[10]提出增强的蚁群算法, 并将其应用于分配类型的问题。该算法在求解图的作色问题时, 得到了完全可以和其它启发式算法相媲美的结果。
(2) 通讯领域
蚁群算法在通讯网络领域 (特别是解决网络路由问题) 方面的应用研究受到越来越多学者的关注。由于网络中信息的分布式性、动态性、随机性和异步性与蚁群算法一非常相似, 如利用局部信息发现解, 间接的通讯方式和随机状态的转换。Di Caro和Dorigo己在相关的文献中将蚁群算法应用于网络路由问题, 并称这种算法为Ant Net[11]。
(3) 大规模集成电路的线网布局
在大规模集成电路的线网布局中, 需要根据电路和工艺的要求完成芯片上单元或功能模块的布局, 然后实现它们之间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个Agent根据启发策略, 像蚂蚁一样在开关盒网格上爬行, 所经之处便设置一条金属线, 历经一个线网的所有引脚之后, 线网便布通了[12]。应用蚁群算法, 可以找到成本最低、最合理的线网布局, 而且由于其本身的并行性, 比较适合于解决此类问题。
(4) 函数优化
虽然蚁群算法在离散空间的寻优能力十分突出, 但是对于连续空间的优化也是蚁群算法应用的领域之一, 也是评价蚁群算法性能的主要方法[13,14]。
此外, 蚁群算法在计算机领域、机器人设计与控制领域、数据挖掘、系统辨识、化工领域等方面也有广泛应用。特别需要指出的是:由于蚁群算法在求解复杂组合优化问题方面具有并行化、正反馈、鲁棒性强等先天优越性, 所以在解决一些组合优化问题时所取得的结果无论是在解的质量上, 还是在收敛速度上都要优于或至少等效于模拟退火以及其它一些启发式算法[2]。
摘要：本世纪50年代中期创立了仿生学, 人们从生物进化的机理中受到启发, 提出了许多用于解决复杂优化问题的新方法, 如遗传算法、蚁群算法、进化规划、进化策略等。研究成果已经显示出这些算法在求解复杂优化问题 (特别是离散优化问题) 方面的具有很强的优越性。本文将对蚁群算法做详细的介绍。
多种群蚁群算法解机组组合优化 篇6
关键词：机组组合,多种群蚁群算法,启发式算法
0 引言
机组组合问题(UC)又称开停机计划,其研究的是在满足各类机组运行条件约束的情况下,如何合理安排未来一定时期内的机组开、停机状态,调节各时段机组出力,以使系统总的运行费用达到最小。机组组合问题具有高维数、非凸、离散、非线性的特点,在数学上为NP-Hard问题。因此,在大型电力系统调度中,在可以接受的时间内得到一个可行的精确解是相当困难的。在实际系统中应用于解此类问题的经典算法有优先级表法[1]、动态规划法[2]、拉格朗日松弛法[3]、混合整数规划法[4]等。还有基于人工智能的一些方法,包括模拟退火算法[5]、蚁群算法[6]、遗传算法[7]、粒子群算法[8]、禁忌算法[9]等。
蚁群算法(ACO)是20世纪90年代提出的一种新型的分布式智能优化算法,具有高度并行性、合作性和鲁棒性,已经成功运用于求解多种组合优化问题当中。在电力系统中的应用领域包括机组组合[10,11,12]、经济调度[13]、配电网规划[14]等。与其他智能算法一样,计算速度慢、易陷入局部最优是其突出的缺点。针对这些特点,国内外学者对蚁群算法计算效率和准确度的提高做了大量的研究。文献[10]通过将蚁群算法与鱼群算法想结合的方式,加强了收敛速度和搜索能力。文献[11]提出了倒指数扰动因子,并设计了通过随机选择策略和随机扰动策略来处理蚁群算法的停滞现象。文献[12]通过改进蚁群运动方式来改进路径上信息素的积累方式,这种处理方式减少了对计算机内存的占用,并且加快了计算的速度和提高了结果的准确度。
多种群蚁群算法(MCAO)是一种新型的蚁群算法,基本思想是把原先单独的一种蚁群分类,通过各类蚁群之间的信息交流与合作来提高算法的计算效率以及解的质量。现阶段这种算法在电力系统中的研究应用还很少。文献[14]针对旅行商问题对多种群蚁群算法的信息交换机制作了研究;文献[15]提出了一种文化蚁群算法,并给出了群体空间和信仰空间的概念。
笔者受上述文献的启发,提出一种针对求解机组组合问题的多种群蚁群算法。该算法把蚁群分为搜索蚁、侦察蚁和工蚁。通过种群之间信息交流和合作加快搜索最优解的效率;针对各种群的不同作用设置不同的信息素调节机制,使蚁群在路径寻优上极大地避免了陷入局部最优解,从而提高优化效果。
1 机组组合问题描述
机组组合问题的约束条件一般包括机组功率平衡约束、旋转备用约束、出力上下限约束、机组爬坡速率约束、最小开机时间约束和最小停机时间约束等。机组组合的目标函数通常为系统运行成本F最小,其表达式如下:
式中:Uit—第i台机组在t时段的开关机状态;Pit—第i台机组在t时段的出力;Ci—开机费用;PDt—时段t系统负荷;SDt—时段t的备用要求;Pˉi,-Pi—机组i的出力上/下限;Rui,Rdi—机组i每个时段允许可调的出力上/下限;T1i,T2i—机组i的最小开机时间和最小关机时间。
上述约束条件可以分为系统约束和机组特性约束。式(2,3)分别为系统功率平衡约束、备用约束,式(4～7)分别为机组输出功率约束、机组爬坡速率约束、最小开停机时间约束。
2 基本蚁群算法简介
基本蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。本研究在某一个时段把机组的一种随机组合状态当作蚂蚁在这一时段内候选的一条路径,基本蚁群算法在解决组合问题时选择转移路径的概率公式为:
式中:ij—在k时段里从i到j的一条路径;is—在k时段里从i出发的任意一条候选路径;τij(t)—t时刻路径ij上的信息素量;ηij—与解决问题相关的启发式信息,在机组组合优化中可选为t时刻运行费用的倒数;T(k)—k时段的候选路径表集合,在机组组合优化中为通过开停机时间约束和爬坡约束筛选后的可选机组组合办法所组成的集合;α,β—蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径过程中所起作用的重要程度。
蚂蚁按照上述转移概率规则完成对候选机组组合路径的选择。当所有的蚂蚁完成了它们的路径选择后,即一次迭代结束,本研究利用全局信息素更新规则来更新路径上的信息素量,重复以上过程,直至达到最大迭代次数或最大停滞次数。全局信息素更新规则为:
式中:ρ—信息素的挥发因子,以减少历史记忆对选择的影响,0<ρ<1;Q—常数,表示信息素强度。
通过分析以上公式可以看出,在所有候选路径中,某条路径上的信息素越多且路径越短,则蚂蚁选择该路径的概率也越大。
3 多种群蚁群算法解机组组合优化
3.1 作用原理描述
笔者提出的多种群蚁群算法是在基本的蚁群算法的基础上,另外设定了侦察蚁和工蚁两种不同作用的蚁群,通过3种蚁群的相互协调配合来达到避免解陷入局部最优、提高解的质量等目的。3种蚁群之间的信息交换机制如图1所示。
3.2 信息素更新算法的设定
搜索蚁采用基本蚁群算法,它的任务是寻找最优解。搜索蚁在选择一条路径之后,会在这条路径上留下信息素,越短的路径信息素含量越高。需要说明的是各条路径上信息素含量的多少会直接影响到后代蚁群对路径的选择:越短的路径被选中的概率越大,信息素积累也越多,这样被后代选择的机会进一步增大,如此反复,最后达到找到最优路径的目的。
笔者设定侦察蚁的任务是扫描搜索蚁未选择过的路径,最大程度地发现搜索蚁未能发现的最优路径解,帮助搜索蚁避免陷入局部最优。根据这个设定,侦察蚁采用最优路径上信息减少的更新办法,表达式如下:
式中:μ—恢复因子,μ>1。
从式(8)容易看出,这样的信息素更新方法简单有效,可以很好地避免对已知路径的反复搜索而使蚁群有更多机会搜索搜索蚁未能选用的路径,进而避免所得解落入局部最优。
3.3 最优解记忆库及最优逼近变异算法
多种群蚁群算法中,工蚁是整个蚁群算法的核心。工蚁为得到的最优解创建最优解记忆库,并对这些解进行最优解逼近变异,进行最优解的进一步更新,最终对搜索蚁和侦察蚁路径上的信息素进行调整。具体处理过程为:
(1)接收搜索蚁和侦察蚁每次寻优得到的各自前n个最优解。本研究将这2n个结果再排序,找到前n个最优,将这n个最优解归入最优解记忆库Tbest0。
(2)受2-opt算法的启发,笔者针对Tbest0里的最优解采用最优逼近的变异方法进行进一步的局部寻优。具体做法为:在Tbest0中找到最优解Ubest,将Ubest和其他n-1个最优解进行对比。以Ubest和Ubesti为例,对比最优解如图2(a)所示。本研究以每一个时段的机组组合状态为单位,对比Ubest和Ubesti的几个连续时段里的机组组合状态。假设Ubest和Ubesti的段落2的这些时段里所选择的机组组合状态是一样的,而在段落1里Ubesti的费用小于Ubest的费用,在段落3里Ubest的费用小于Ubesti的费用,那么新的最优解U′best结构如图2(b)所示。
(3)检验U′best是否可行,如果可行且计算所得费用小于Tbest0中最大值,则将U′best也归入Tbest0中。
(4)将最优解复制m份,其中m=λn(0<λ<1)。
(5)将Tbest0中最优解重新排序,找到最优的n个解,更新记忆库。
(6)为搜索蚁和侦察蚁更新信息素。搜索蚁的信息素更新方法采用式(9～11)基本蚁群全局信息素更新的算法。侦察蚁与搜索蚁的信息素更新处理不同之处在于信息素的累积办法为式(10～12)。
3.4 多种群蚁群算法流程
多种群蚁群算法流程(如图3所示)如下:
(1)初始化。读取系统信息,初始化各参数,计迭代次数Nt=0。
(2)Nt=Nt+1,搜索蚁和侦查蚁按照各自的信息素信息寻优。每组蚁群得到n个最优解。
(3)工蚁接收这2n个最优解,作3.1节的处理。
(4)判断是否已经到达收敛要求。如果是,则输出最优解;如果不是,则返回(2)。
4 算例分析
仿真在P4-3.0 GHz的PC机下进行,本研究采用Matlab 2008编写多种群蚁群算法程序,并调用CPLEX11.0进行经济调度,算例采用修正的IEEE30[16]节点系统。搜索蚁5只,侦察蚁25只,最优集合取最优解的个数为n=10,最优解加权值m=2,即λ=0.2,最大迭代次数为100次,ρ=0.8,μ=1.05,α=6,β=1。算法的终止条件为达到最大迭代次数或最优解集合中只有一种解,即所有蚂蚁聚敛到一条路径上时计算终止。
基本蚁群算法和多种群蚁群算法以及没有经过局部寻优的多种群蚁群算法的计算效果如图4所示(其中,实线表示基本蚁群算法解,短划线为笔者提出的多种群蚁群算法解,虚线表示不做局部寻优的多种群蚁群算法解)。从图4中可以明显看出,笔者所提出的多种群蚁群算法,在收敛速度和结果的准确度上都远远优于基本蚁群算法。从图4也可以看出,通过在最优解集中做局部寻优可以在很大程度上加快最优解的搜索效率。
最优解加权和不做最优解加权时的解的情况如图5所示。实线为最优解加权后得到的解的情况,短划线为没有做加权的解的情况,短线点线表示最优解没有加权时得到的最优解集里最优解的平均值。从图5中可以看出,不做最优解加权时,解的收敛速度会比做最优加权时慢很多。这是因为当最优解集里的次最优解已经占一定规模时,即使侦察蚁找到了最优解,由于信息素的积累不够,蚁群在做下一次寻找时,很难向最优解靠拢,造成时间的浪费。最优解的适当加权在一定程度上克服了这样的缺陷,使得蚁群尽快地找到最优值。
各种算法所得出的最优解值以及迭代次数如表1所示。结果表明笔者提出的多种群蚁群算法在效率和解的质量上比基本蚁群算法有很大的提高。
5 结束语
国内外研究表明,蚁群算法在解决组合问题上有其突出的优点,但蚁群算法在计算速度和解的准确度上仍不能够令人满意。笔者提出的多种群蚁群算法对基本蚁群算法做了改进,在基本蚁群(搜索蚁)的基础上引入了侦察蚁和工蚁两种蚁群。
侦察蚁与搜索蚁做反方向的路径寻优计算,这样做使得蚁群可以最大可能地搜索各种未知路径,从而在很大程度上防止了搜索蚁陷入局部最优。
工蚁为整个蚁群系统提供信息处理:形成最优解集,进行最优解局部寻优,为搜索蚁和侦察蚁做信息素更新。工蚁是多种群蚁群算法的核心。它相当于鱼群算法的公告板,在解的处理过程中吸收了遗传算法的交叉寻优过程,也集合了免疫算法的最优解加权寻优等优点,使得多种群蚁群算法在计算效率和最优解质量上都有明显的提高。
群智能算法发展研究 篇7
群智能算法是近几十年发展起来的一类基于生物群体行为规律的全局概率搜索算法。这些算法将搜索空间中的每一个可行解视为生物个体, 解的搜索和优化过程视为个体的进化或觅食过程。生物个体适应环境的能力用来度量待求解问题的目标函数, 生物个体的进化或觅食过程用来模拟优化中较差的可行解被具有优势的可行解替代的迭代过程。下文将对几种典型的群智能算法进行简要的介绍。
2 典型群智能优化算法
2.1 蚁群算法
1991年意大利学者Dorigo M等受到自然界中蚁群觅食行为启发而提出了蚁群算法 (Ant Colony Optimization, ACO) 。
蚁群算法的思想是:在最短路径的找寻过程中, 每只蚂蚁只可以根据局部信息调整路径上的信息素, 一轮循环结束后, 采取全局信息对路径上的信息量再进行一次调整, 且只对寻优过程中发现的最好路径上的信息素进行加强。在蚁群算法中, 蚂蚁逐步地构造问题的可行解, 在解的构造期间, 每只蚂蚁使用概率方式向下一个节点跳转, 这个节点是具有较强信息素和较高启发式因子的方向, 直至无法进一步移动。此时, 蚂蚁所走路径对应于待求解问题的一个可行解。
蚁群算法目前已成功地用于解决旅行商TSP问题、数据挖掘、二次指派问题、网络路由优化、机器人路径规划、图着色、物流配送车辆调度、PID控制参数优化及无线传感器网络等问题。
2.2 粒子群算法
1995年美国的Kennedy等受鸟群捕食行为的启发而提出了粒子群算法 (Particle Swarm Optimization, PSO) 。
粒子群算法的思想是:将群体中的任一个个体, 即每个可行解, 视为D维搜索空间的一个有飞行方向和速度的粒子。所有的粒子都有一个被目标函数决定的适应值, 且记忆了自身曾经获得的最好位置及当前位置, 视为自身的飞行经验。同时每个粒子还知道整个群体所有粒子已获得的最优位置, 视为群体的飞行经验。在迭代过程中, 所有的粒子将不断地统计个体的飞行经验和整个群体的飞行经验, 以此动态调整本身飞行的方向和速度。在此过程中, 个体逐步迁移到较优的区域, 使群体最终搜索到问题的最优解。
粒子群算法的应用领域众多, 如模式识别与图像处理、工程应用、神经网络训练、模糊系统控制、化工系统处理、滤波器设计、仿人智能控制参数优化、数据聚类等。
2.3 人工鱼算法
2002年由我国的李晓磊等受鱼群运动行为的启发而提出了人工鱼群算法 (Artificial Fish-Swarm Algorithm, AFSA) 。
人工鱼群算法的思想是:将人工鱼随机地分布于解空间中, 解空间中包含着若干局部最优值和一个全局最优值。可将最优值视为食物的浓度, 而全局最优值为最大的食物浓度, 且人工鱼将移动聚集到食物浓度较大的区域, 通过移动策略来控制人工鱼个体的四种行为 (觅食、聚群、追尾和随机) , 用视野来限制个体的邻域, 用步长来控制个体探索的进度, 用拥挤度来控制群体的过度密集。寻优期间, 每次迭代执行完, 人工鱼都将对比自身状态和公告板状态, 如自身具有优势, 则更新公告板状态, 确保公告板为最优状态。
人工鱼群算法已在参数估计、组合优化、前向神经网络优化、电力系统无功优化、输电网规划、边坡稳定、非线性方程求解等方面得到应用, 且取得了较好的效果。
2.4 混合蛙跳算法
2003年Eusuff等人受青蛙觅食特征的启发而提出了混合蛙跳算法[4] (Shuffled Frog Leaping Algorithm, SFLA) 。
混合蛙跳算法的思想是:将青蛙个体随机地分布于解空间中, 每只青蛙表示解空间的一个解。在进化更新的过程中既有全局性的信息交流, 还有内部的信息交流。根据青蛙个体的适应度值的优劣进行排序和分组, 组内只有适应度最差的青蛙更新, 元进化并混合各组, 在各组一轮元进化后, 将组中的青蛙重新排序、分组并记录全局最优解, 之后再继续局部搜索的过程。青蛙更新的学习对象首先是组内最优, 其次是群体最优, 若两次都未能进步, 则随机初始化。
混合蛙跳算法已经应用于多个领域, 如水资源网络优化、数据聚类、桥面修复、风电场电力系统动态优化、装配线排序、流水车间调度、PID控制器参数调节等。
2.5 人工蜂算法
2005年由土耳其的Karaboga等受蜜蜂采蜜行为的启发而提出了人工蜂群算法 (Artificial Bee Colony, ABC) 。
人工蜂群算法的思想是:将虚拟蜜蜂群初始时随机分布在解空间中, 将食物源的位置抽象成解空间中的点 (可行解) 。通过三种蜜蜂对食物源位置 (解) 修正, 进行一次循环搜索过程。引领蜂通过对比附近食物源的花蜜量 (适应度) , 来对现有食物源位置 (解) 进行修正。如果新食物源的花蜜量 (适应度) 比现有的高, 那么引领蜂记忆新食物源 (解) , 放弃现有的。在引领蜂的搜索过程完成后, 它们通过跳舞与跟随蜂传递食物源信息。跟随蜂通过汇总和评估所有食物源信息, 计算出一个关于花蜜量的概率值, 通过比较概率选取食物源。跟随蜂也是根据贪婪选择策略来更新当前食物源的位置。利用侦察蜂来使得陷入局部搜索停滞的蜜蜂跳出。
人工蜂群算法已经应用于多个领域, 如车辆路径问题、人工神经网络训练、作业车间调度问题、数据聚类以及各类连续优化问题等。
2.6 萤火虫算法
2009年由剑桥大学的Xin-She Yang受萤火虫发光行为的启发而提出了萤火虫算法 (Firefly Algorithm, FA) 。
萤火虫算法的思想是:将萤火虫个体作为解随机地分布于解空间中。解的搜索和优化过程视为每只萤火虫的移动和吸引过程。个体所在位置的优劣用来度量所求问题目标函数。个体进化的过程用来模拟优化中较差的可行解被具有优势的可行解替代的迭代过程。萤火虫根据自身亮度和吸引度两个要素来更新自己的位置。萤火虫所在位置的目标值决定其能产生的荧光亮度, 所处位置 (目标值) 越好其亮度越高。萤火虫的亮度与吸引力成正比, 视线范围内, 亮度稍弱的萤火虫将被吸引, 朝着较亮萤火虫的方向移动, 以完成的位置进化。当亮度相同时, 萤火虫则随机地进行位置移动。萤火虫之间的距离与亮度和吸引度成反比, 也即距离越大, 亮度和吸引度越小。
目前萤火虫算法已应用在生产调度、路径规划、神经网络训练、天线阵列设计优化、图像处理、机械结构设计优化、负载经济均衡分配问题、复杂函数优化等方面。
3 结论
本文在简述群智能算法的基础上, 对近年来发展的几种典型的群智能算法的生物原理、算法思想和应用进行了阐述和研究, 为群智能算法的深入研究奠定了基础。
摘要：最优化技术的应用日渐广泛, 传统的优化方法对于解决复杂问题变得无能为力。群智能算法在这种背景下产生并迅速发展。目前已研究出许多种类的群智能优化算法, 包括蚁群、粒子群、人工鱼群、混合蛙跳、人工蜂、萤火虫算法等。本文主要介绍群智能算法的发展, 阐述上述典型算法产生的生物原理、算法思想和应用。
关键词：群智能算法,ACO,PSO,AFSA,SFLA,ABC,FA
参考文献
[1]Colomi A, Dorigo M, Maniezzo V.The Ant System:An autocatalytic optimization process, Technical Report 91-016, Dept.of Electronics, Politecnicco di Milano, Italy, 1991.
[2]Kennedy J, Eberhart RC.Particle swarm optimization[C].IEEE International Conference on Neural Networks, Perth, Piscataway, NJ, Australia:IEEE Service Center, 1995, 1942-1948.
[3]李晓磊, 邵之江, 钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践, 2002, 11, 32-38.
[4]Eusuff, M.M., Lansey.K.E.Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J].Water Resources Planning and Management, 2003, 129 (3) :210-225.
[5]Karaboga D.An Idea Based On Honey Bee Swarm for Numerical Optimization[R].Erciyes Uiversity, Technical Report:TR06, 2005.