鱼群算法

鱼群算法（共8篇）

鱼群算法 篇1

摘要：人工鱼群算法是一种新型的群体智能随机全局优化算法。在阐述鱼群算法的基本原理的同时,综述了近年来鱼群算法的发展历程及其改进算法,分析了其应用领域,并提出了今后的研究方向。

关键词：鱼群算法,基本原理,改进算法,发展应用,研究趋势

近年来,人工智能学科飞速发展,学者们通过研究动物群体和人类社会的智能行为,提出了群体智能(Swarm Intelligence)算法。它具备天然的分布式和自组织特征[1],是通过模拟自然界生物群体行为来实现人工智能的一种方法。典型的群体智能算法主要有粒子群算法、蚁群算法、等。

2002年,李晓磊等[2]成功地将动物自治体的概念引入优化算法,提出了人工鱼群算法(Artificial Fish Swarm Algorithm,AFSA)。它采用自下而上的思路,应用了基于行为的人工智能方法,因为是从分析鱼类的活动出发进行寻优,故称为人工鱼群算法。目前,关于AFSA算法的研究已经渗透到多个应用领域,并且得到了很好的应用效果,成为群智能计算领域的研究热点之一。

1 人工鱼群算法的基本原理

在一片水域中,鱼生存数目最多的地方一般就是本水域中富含营养物质最多的地方,依据这一特点来模仿鱼群的觅食等行为,从而实现全局寻优,这就是AFSA的基本思想[2]。基本人工鱼群算法是用来解决连续值域内不受约束的优化问题,在离散域内将行为定义稍加改动也同样适用。

假设有条人工鱼,当前状态为Xi,随机选择人工鱼另一状态为Xj;其中,xi=[xid](i=1,2,L,SN,d=1,2,L,D)是一个D维向量,xi=[xid](i=1,2,L,SN,d=1,2,L,D)同为一个D维向量;状态Xi的食物浓度(适应度函数)为Yi=f(Xi),其中f(.)为目标函数;人工鱼个体之间的距离表示为di,j=‖Xi-Xj‖,其感知距离(视野范围)为Visual,移动步长为step,拥挤度因子为δ。算法中,几种行为与寻优命题的解决有着较密切的关系。

(1) 觅食行为

设人工鱼当前状态为Xi,在其感知范围内随机选择一个状态Xj,在求极大值问题时,若Yi

undefined

式中,Rand为一个(0,1)的随机数。

(2) 聚群行为

设人工鱼探索当前邻域内(di,jδYi,表明伙伴中心有较多的食物且其周围不太拥挤,则朝伙伴中心位置方向前进一步;否则执行觅食行为。其数学表达式为:

undefined

(3) 追尾行为

设邻域内(di,jδY,表明Xmax状态具有较高的食物浓度且其周围不太拥挤,则朝Xmax的方向前进一步;否则执行觅食行为。其数学表达式为:

undefined

(4) 公告板

用来记录最优人工鱼个体的状态。

2 基本人工鱼群算法的改进

2.1 初始化的改进

初始化种群是算法进行搜索的起点。AFSA算法的初始种群生成是随机的,通常情况下可以保证初始鱼群分布均匀,但对于个体的质量不能保证,解群中有一部分远离最优解。

宋潇潇等[3]提出了基于极坐标编码的改进人工鱼群算法。它通过设定编码规则,并将此编码方式运用到三种行为当中,计算出每一个编码母体获得的人工鱼的概率,选择大概率的母体作为算法初始化的起点,有效提高算法的收敛性。宋志宇等[4]利用混沌系统产生混沌变量,并在参数允许范围内随机产生各个人工鱼个体的初始状态。陈广洲等[5]引入了免疫算法中的消亡算子,经算子运算更新,相互比较,摒弃非优个体,将其重新初始化,以此保持种群的多样性。

2.2 算法参数的改进

AFSA算法参数较多,且通常情况下是固定的,δ设置不合理,收敛效果不明显。在算法后期,随着人工鱼个体逐渐靠近最优点,这时当前较好的解只有一两位元素与最优解不同,所以在其附近仍采用在Visual与step范围内觅食的方式寻优是不合理的。

王冬冬等[6]提出了分段优化的思想,令食物浓度η为分界线,大于η时,为前期过程,采用较大的step和Visual,能使算法较快地得到一个相对较优的解;小于η时为后期过程,采用较小的step和Visual,得到一个精度更高的解。黄华娟等[7]通过公式(4)和公式(5)自适应减小了步长和拥挤度因子。

undefined

δk+1=αδk . (5)

其中,k为当前迭代的代数,α∈[0,1]为衰减因子。俞洋等[8]通过公式(6)逐渐减小视野。

Visualk+1=αVisualk . (6)

Xiao J M等[9]运用最优适应值变化率K和变化方差σ2作为是否进行参数变化的衡量标准,从而避免算法的退化。

2.3 与其它算法相结合的改进

算法一般在优化初期具有较快的收敛性,而在后期却往往收敛较慢。虽然通过对参数的改进可以解决此问题,但是从计算复杂度、收敛效果及速率等因素来考虑,仅从算法自身改进不足难以达到更高的要求。因此,在AFSA算法中引入其它算法,综合二者的优点,成为AFSA改进的一个主流趋势。

(1) 与粒子群算法相结合

罗德相等[10]将种群分为两部分,一部分运用粒子群算法,一部分运用鱼群算法,将二者比较后的最优值赋予公告板,以此提高收敛速度。

(2) 与遗传算法相结合

张梅凤等[11]将变异算子引入鱼群算法,实现人工鱼个体的跳变,从而调整优化群体。曲良东等[12]引入高斯变异和差分进化两种变异算子,通过变异使得劣解得以更新,确保了算法的寻优性。

(3) 与禁忌搜索算法相结合

李亮等[13]通过邻域禁忌搜索,构造两点禁忌寻优算子对解空间进行无重复的搜索,以此来跳出局部最优点,确保算法的高效性。

(4) 与其它算法相结合

高德芳等[14]提出鱼群-蚁群算法的概念,将蚁群算法融入ASFA中。

3 鱼群算法的应用

基于鱼群算法的优点,其在很多领域得到广泛应用。如对连续函数进行优化;将算法运用到多用户检测;解决旅行商问题及约束优化问题等。综上所述,AFSA算法在很多领域都展现出了其良好的解决问题能力。

4 总结与展望

目前针对鱼群算法的研究已逐渐趋于成熟,但许多问题仍有待进一步的研究:

首先,AFSA算法的基础理论研究尚待完善。例如算法参数较多,且参数设置也缺乏确切的理论依据,通常依靠经验来设定。

其次,算法在后期收敛速度明显降低,仅仅通过AFSA算法的计算很难得到满意解。如何将其它智能算法与AFSA算法融合,减小甚至克服各自的缺点,构造出创新性并具备实用价值的混合算法是当前研究的热点趋势。

浮在空中的鱼群 篇2

云是树林的披肩，风是碎石路的纱帕，而刚走入文学国度的人，总喜欢用散文做短衫，拿小说裁百褶裙，诗是纽扣。

【缁衣】

如果有人认为文学是不着尘色的白裳，那是因为他遗忘了“现实”这件缁衣。崇拜杜甫的人，不见得读得懂杜诗，但我们不难想象，当杜甫访友归来，一进门问他的老妻的第一句话，也许是：“尚有油盐否？”

【伏流】

文学如同溪涧，允许不同姿势的浏览与品味。好寻思的人，临流自伤，说人生也是不可眉批的东逝水。自诩清高的人，水清濯缨，水浊濯足，一向自在。至于率然天真的人，俯身溪岸，一咕噜一咕噜地畅饮，把自己喝成一条支流。

【参商】

不必观天象，你的指掌自能屈算人事。若有酒，何不空杯？若有驿车，何不共游？人生动如脱兔，静如处子，一旦扬镳分道，若要相见，须问参商。

【唱晚】

所有的笙歌琴音收束于一个指势，繁华之后，只剩空夜里的上弦。歌偏阳春，你的知音再给你一次热切的掌声，下一曲呢？依稀，生命到达了彼岸，你收起琴弦，站起，深深一揖：“我倦欲眠君可去。”

【雄浑】

当女娲炼石补天，单单剩下一块未用之时，雄浑之气已然锻炼，自行游历于人间世事，等待崩裂。

赶着驴子去市集摆摊的民家，只急着拿这块彩石，压住铺在地上的布，好让生意顺当，怀兜里的银两愈进愈重才妙。

河畔浣洗衣裳的姑娘家，抓着石块打得脏衣服流汁，好似逮住薄情郎，搓洗一阵，随手把石头丢入江河，想的全是驭夫训子。

那一日，江水滔滔，行吟泽畔的楚国屈大夫，揽身一跃入水，忽然江底的石头崩裂，鱼龙四奔。

从此，玄黄之地有了补不完的龟伤。

【冲淡】

好比一滴泪掉入江河，才会懂淡而不化的心情！

在古远的、兵荒马乱的年代，女人的心好似唐装襟上的盤扣，一个布环紧扣着一个布锁，就这样背着孩子抱薪举爨。思夫与望乡的眼神，如烟，散得快。

在晚近的、寻常日子的岁月里，女人的心好似一根穿了线的针，把温情缝给远游不归的子女，一针一线地将异乡的风雪挡住。线尽针钝，女人也老了。

打了一个死结，女人将自己咬断，唾到窗外，好比一滴泪掉入江河。

【秾纤】

采采流水，蓬蓬远春，啊！这是个多雨的地方，心情好似青苔。雨滴沿着屋檐而落，更漏声声;夜，是给人覆盖在心事之瓮上的，拿着芳龄的红麻绳一勒，久而久之，便是春醋。

雨似牛毛，也碍不了我要出巡的意兴。发髻上布满雨的碎珠，眉睫之间，好似雾湿楼台。山风清沁，野林苍翠，好吧，我来采荇。采不盈袖，正要拔起银簪搔一个湿意，却眼见深林处奔出快蹄，好一个骏马吉士！

鱼群算法 篇3

在工程技术和科学计算中,经常会遇到求解数值积分∫${}_a^b$f(x)dx,除了几种有限类型外,被积函数f(x)往往很难甚至无法求出它的原函数,即使有的原函数能求出来,但是也相当麻烦不适宜于计算,这时常常需要借助近似方法求解近似数值解。数值积分虽然计算方法很多,如梯形求积方法[1]、抛物线求积方法[1]、Newton-Cotes方法、Romberg 方法、Gauss 方法等[2],但这些传统方法都有一定的局限性。其中梯形求积方法和抛物线求积方法适用于光滑性较差的被积函数,但是对于其它被积函数精度较低;Newton-Cotes方法是一种利用插值多项式来构造数值积分的常用方法,但高阶Newton-Cotes方法的收敛性没有保证;Romberg方法虽然收敛速度快,计算精度较高,但是计算量较大;Gauss方法积分精度高、数值稳定、收敛速度较快,但节点与系数的计算较困难。针对这些问题,本文基于对基本人工鱼群算法进行改进提出一种基于人工鱼群算法的优化分割数值积分算法。通过仿真实验与传统的数值积分方法比较表明新算法十分有效,可以看作是传统方法的补充和拓展,在工程中有较大的应用价值。

1 人工鱼群算法

1.1 基本人工鱼群算法

在一片水域中,鱼往往能自行或尾随其它鱼找到营养物质多的地方,因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方。人工鱼群算法AFSA(Artificial Fish-school Algorithm)[3]就是根据鱼群上述特点提出的一种新型仿生优化算法,通过构造人工鱼来模仿鱼群的觅食、聚群、追尾及随机行为,从而实现寻优,是群体智能思想[4]的一个具体应用。它的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣的比较,通过各人工鱼个体的局部寻优行为,最终使全局最优值突现出来。作为一种新型的全局寻优策略,它已应用于时变系统的在线辩识、鲁棒PID的参数整定和优化前向神经网络中,取得了较好的效果。

然而随着优化问题的复杂性,基本AFSA在应用中也存在不足:当寻优的空间维数高或区域较大或处于变化平坦的区域时收敛于全局最优解的速度减慢,搜索性能劣化,甚至会陷入局部极小;算法一般在优化初期收敛快,后期却往往较慢;得到的解是满意解,精度不高。因此在具体应用中常常要对它进行改进。

1.2 柯西变异人工鱼群算法

Gunter[5]通过理论分析表明柯西变异算子具有较强的局部逃逸能力。为了增强人工鱼群算法在高维复杂环境下的全局搜索能力和提高搜索效率,本文在基本人工鱼群算法中引入柯西变异算子来对人工鱼的状态Xi=(xi1,xi2,...,xin)进行变异,定义如下:

X′i=Xi·[1+k·Cauchy(0,1)] (1)

其中Cauchy(0,1)的一维概率密度函数为$f(x)=\frac{1}{\pi }\cdot \frac{1}{1+x{}^2},-\infty <x<+\infty$,k是随迭代由1线性减为0的变量,迭代前期变异幅度大,后期变异幅度小。

设ξ是[0, 1]上的服从均匀分布的随机变量,由随机变量生成函数定理[6],Cauchy(0,1)的柯西分布的随机变量生成函数为 η=tan[(ξ-0.5)π]。

为判断随迭代次数增加搜索结果是否有改进,种群迭代后将种群中最优鱼的状态的函数值与公告板[7]进行比较,如果优于公告板,则取代公告板状态。当在连续两次迭代过程中公告板没有改变或变化极小时,此时我们看作鱼群迭代停滞,则启用变异操作。此算法CMAFSA(Artificial Fish-school Algorithm Based on Cauchy Mutation)流程如下:

Step1 初始化群体:在控制变量可行域内随机生成Np条人工鱼,形成初始鱼群。

Step2 公告板赋初值:计算初始鱼群各人工鱼当前状态的函数值y,取y为最小值者进入公告板,并将此鱼位置状态也赋值给公告板。

Step3 行为选择:各人工鱼分别模拟追尾行为和聚群行为,评价行动后的值,选择y值较小的行为实际执行,缺省行为方式为觅食行为。

Step4 公告板更新:种群迭代后,如果种群最优鱼状态的y优于公告板的y,则更新公告板。

Step5 变异条件判断:若公告板在连续两次迭代过程没有改变或变化极小(<η),则执行Step6;否则执行Step7。

Step6 变异操作:用历史最优鱼替换当前群体的最差鱼形成中间种群,对中间种群的人工鱼按式(1)变异,计算变异后各状态的函数值与公告板比较,若优,更新公告板。

Step7 终止条件判断:判断是否已达到预置的最大迭代次数MaxIteration或判断最优值是否达到了满意的误差界内(<ε),若不满足,执行Step3,进行下一代鱼群优化过程;否则执行Step8。

Step8 算法终止:输出最优解(即公告板中人工鱼状态和函数值)。

1.3 CMAFSA性能测试

本文用一个典型的高维(30维)、多峰函数Ackley来测试CMAFSA的性能。算法参数设置如下:Np=100,Try_number=30,δ=0.618, η=10-4,最大迭代次数200次, Visual=5,Step=0.5。独立测试5次(随机生成5个初始群体分别用AFSA和CMAFSA运行), 运行结果如表1和图1(为了便于比较, 图中纵坐标是5次的每代最优值的平均值的常用对数)所示。

从表1和图1可以看出AFSA在优化高维、多峰问题时效果很差,而CMAFSA的精度、收敛速度、稳定性有了非常明显的提高,实际上5次实验中CMAFSA最差的一次是在第114(从图1也可看出)代达到了理论最优值。

2基于人工鱼群算法的优化分割数值积分算法

在数值积分${\displaystyle {\int }_a^{b}f}(x)dx\approx {\displaystyle \sum _{i=1}^{n}f}(\xi {}_i)\Delta x{}_i$的近似计算中,分割的优劣和f(ξi)的替代对求解结果的精度有很大的影响。我们的基本思想是在积分区间[a,b]上用柯西变异人工鱼群算法搜到一个最优的分割,考虑到函数值的变化关系和曲线的弯曲情况,在得到的最优分割对应的小区间上用一个合适的值代替f(ξi)来达到近似计算,算法步骤如下:

Step1 确定人工鱼个体的表达式:Xi=(x1,x2,...,xn),其中xi为积分区间[a,b]内的随机n个节点。

Step2 鱼群初始化:在[a,b]内随机生成Np条人工鱼, 形成初始鱼群。实际上就是在[a,b]上产生Np个随机分割。

Step3 公告板赋初值:计算初始鱼群各人工鱼当前状态的函数值y,取y为最小值者进入公告板,并将此鱼位置状态也赋值给公告板。其中函数值是这样计算的:将人工鱼的状态值置于积分区间的左端点和右端点之间,各自按照升序排好顺序。这样,积分区间[a,b]总共有n+2个节点和n+1个小区间,然后分别计算这n+2个节点相邻节点之间的长度Δxi,i=1, 2, …,n+1。再计算出这n+2个节点对应的函数值和每个小区间中点的函数值。找出每个小区间左端点、中点和右端点的函数值中的最小值wi和最大值Wi,i=1,2,…,n+1,则该个体所对应的函数值$y={\displaystyle \sum _{i=1}^{n+1}|}W{}_i-w{}_i|\Delta x{}_i$。

Step4 行为选择:各人工鱼分别模拟追尾行为和聚群行为,评价行动后的值,选择y值较小的行为实际执行,缺省行为方式为觅食行为。

Step5 公告板更新:种群迭代后,如果种群最优鱼状态的y优于公告板的y,则更新公告板。

Step6 变异条件判断:若公告板在连续两次迭代过程没有改变或变化极小(<η),则执行Step7;否则执行Step8。

Step7 变异操作:用历史最优鱼替换当前群体的最差鱼形成中间种群,对中间种群的人工鱼按式(1)变异,计算变异后各状态的函数值与公告板比较,若优,更新公告板。

Step8 鱼群算法终止条件判断:判断是否已达到预置的最大迭代次数MaxIteration或判断y的最优值是否达到了满意的误差界内(<ε),若不满足,执行Step4,进行下一代鱼群优化过程;否则执行Step9。

Step9 得到最优人工鱼个体状态(xbest1,xbest2,...,xbestn),这n个数同a,b一起排序,从而得到最优分割。

Step10 输出积分${\displaystyle {\int }_a^{b}f}(x)dx\approx {\displaystyle \sum _{i=1}^{n+1}\overline{f}}{}_i\cdot \Delta x{}_{best{}_i}$。其中$\overline{f}{}_i$是最优分割所得到的n+1个小区间每个区间左、右端点和三点对应的函数值的加权平均$\overline{f}{}_i=\frac{f{}_{i\text{左}}+4f{}_{\text{中}}+f{}_{i\text{右}}}{6}$,Δxbesti是最优分割所对应小区间的长度。

3 积分仿真实验与分析

为了检验本文提出的数值积分算法的有效性和正确性,本文给出的一些实例,以下仿真均在Matlab 7.0下编程运行。参数设置如下:Np=50,Try_number=20,δ=0.618, η=10-4,ε=10-4,最大迭代次数200次,Visual=0.1,Step=0.01, n=100。每个函数独立运行5次,并与传统的梯形法、Simpson方法、Composite Simpson方法、Romberg方法和神经网络等比较。

例1 分别计算被积函数$x{}^2,x{}^4,\sqrt{1+x{}^2},\frac{1}{1+x},\sin (x),e{}^x$六个函数在[0,2]上的积分。与文献[8,9]的结果统计比较如表2所示。

由表2看出传统方法中只有Simpson法在求解函数x2时的结果优外,其他的在这6个函数上效果都不好,而本文的算法对每个函数均独立运行5次皆是精确值,可见精度高且很稳定。

例2 计算积分:

∫${}_0^1$e-x2dx

被积函数的原函数不是初等函数,本文算法(参数设置同前)5次运算与文献[9]分别用矩形法、梯形法、Simpson法给出结果统计如表3所示。

由表3看出对于被积函数的原函数不是初等函数的函数,本文的算法也是相当有效的。

例3 计算积分:

${\displaystyle {\int }_0^{48}\sqrt{1+(\text{c}\text{o}\text{s}x){}^2}}dx$

用传统的方法Romberg比较麻烦,不易处理,文献[9]用神经网络算法得到的结果是58.5205,文献[10]用Composite Simpson rule计算的结果是58.47082,而此积分的精确值是58.4704691。由于此被积函数是一个以π为周期的函数,48=15π+(48-15π),此积分可化为:

${\displaystyle {\int }_0^{48}\sqrt{1+(\text{c}\text{o}\text{s}x){}^2}}dx=15{\displaystyle {\int }_0^{\pi }\sqrt{1+(\text{c}\text{o}\text{s}x){}^2}}dx+{\displaystyle {\int }_0^{48-15\pi }\sqrt{1+(\text{c}\text{o}\text{s}x){}^2}}dx$

用本文的算法(参数设置同前)运行5次求得的积分值的最差值是58.47046674929646,最佳值是58.47046909676099,平均值是58.47046871265326,由此看出对于Romberg方法不易处理的函数积分,本文的算法也是很优的。

例4 计算奇异函数:

$f(x)=\{\begin{array}{l}e{}^{-x}0\le x<1\\ e{}^{-\frac{x}{2}}1\le x<2\\ e{}^{-\frac{x}{3}}2\le x\le 3\end{array}$

在[0,3]上的积分该函数的积分精确值是1.546036,文献[9]用神经网络算法算得的结果是1.5467。用本文的算法(参数设置同前)运行5次求得的积分值的最差值是1.54554025335573,最佳值是1.54606116448507,平均值是1.54600370898978,可见本文算法也可求解奇异函数的积分。

4 结 论

本文在分析传统数值积分和人工鱼群算法的基础上提出了一种求解定积分数值解的新算法,此算法对被积函数没有太多的限制,通过四组积分算例实验表明此方法十分有效,此方法可以看作是传统方法的补充和拓展。在优化区间的每一段上如何再处理以及用此算法计算重积分是我们下一段要做的工作。

摘要：在分析传统求数值积分和基本人工鱼群算法不足的基础上,提出了一种基于人工鱼群算法的优化分割数值积分算法,该算法不仅能求解通常意义下函数的数值积分,还能计算奇异函数的数值积分。通过算例与传统数值积分方法比较,实验结果表明该算法是可行的和有效的。

关键词：人工鱼群算法,柯西变异,优化分割,数值积分

参考文献

[1]华东师范大学数学系.数学分析[M].北京:高等教育出版社,2001.

[2]薛密.数值数学和计算[M].上海:复旦大学出版社,1991.

[3]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.

[4]Bonabeau E,Theraulaz G.SwarmSmarts[J].Scientific American,2000,282(3):72-79.

[5]Gunter R.Local convergence rates of simple evolutionary algorithms withCauchy mutation[J].IEEE Transactions on Evolutionary computation,1997,4(1):249-258.

[6]王梓坤.概率论基础及其应用[M].北京:科技出版社,1979.

[7]李晓磊,路飞,田国会,等.组合优化问题的人工鱼群算法应用[J].山东大学学报:工学版,2004,34(5):64-67.

[8]Burden R L,Faires J D.Numerical Analysis[M].7th Edition.Brooks/Cole,Thomson Learning,Inc,2001:190.

[9]王小华,何怡刚,曾喆昭.三角基函数神经网络算法在数值积分中的应用[J].电子与信息学报,2004,26(3).

基于人工鱼群算法的输电网络规划 篇4

输电网规划是电力系统规划的重要组成部分,其任务是根据规划期间的负荷增长及电源规划方案确定相应的最佳电网结构,以满足经济可靠地输送电能的要求[1]。目前进行输电网规划的方法分为数学优化方法和启发式方法两类。数学优化方法在理论上更为优越,一般可以保证解的最优性,但通常计算量过大,实际应用中有许多困难。启发式方法是以直观分析为依据的方法,通常是基于系统某一性能指标对可行路径上的一些参数作灵敏度分析,并根据一定的原则选择要架设的线路。启发式方法的优点是直观、灵活、计算量小、应用方便;缺点是无法从理论上证明其解的最优性,并且各启发式方法的收敛性也值得进行进一步的研究。

近年来应用于输电网规划的启发式方法主要有:遗传算法[2,3,4]、粒子群算法[5,6]、模拟退火算法等。这些方法的提出丰富了输电网规划的解法,也为更好地进行电网规划工作打下了基础。

人工鱼群算法(AFSA)是近年来提出一种模拟鱼类行为的优化方法,是集群智能思路的一个具体应用,它能很好地解决非线性函数优化等问题。人工鱼群算法的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣的比较,有着较快的收敛速度[7]。

本文首次将人工鱼群算法应用于输电网规划,希望起到抛砖引玉的作用,毕竟作为一种新的方法,算法本身还有许多值得研究和改进的问题。

2 输电网络规划的数学模型

单阶段输电网络规划就是在规划水平年的负荷预测和电源规划已知的条件下,基于现有的网络结构和给定的待选线路,确定出满足运行要求的最经济的网络扩展方案。在计及建设投资费用时,不考虑政策、地形复杂度等实际因素的影响,认为规划方案的投资费用只与新建线路长度和运行费用有关,网络潮流采用直流潮流计算。

在上述的假设条件下,输电网规划的数学模型可以表述为:

$\begin{array}{l}\text{m}\text{i}\text{n}Y={\displaystyle \sum _{j\in \Omega {}_1}c}{}_{j}x{}_j+k{\displaystyle \sum _{j\in \Omega {}_2}r}{}_{j}p{}_j^2(1)\\ \text{s}.\text{t}.B\theta +{\rm P}{}_{\text{L}}={\rm P}{}_{\text{G}}(2)\\ |B{}_{l}A\theta |\le {\rm P}{}_{\max }(3)\\ 0\le x{}_j\le x{}_{j\text{m}\text{a}\text{x}}(4)\end{array}$

Y为年费用,包括建设费用和运行费用;cj为支路j中扩建一回新建线路的投资费用;xj为支路j中新建线路回路数;k为年网损费用系数;rj为支路j的电阻;pj为正常运行情况下支路j输送的有功功率;B为系统节点导纳矩阵;Bl为由各支路导纳组成的对角矩阵;θ为节点相角矢量;PL为负荷矢量;PG为发电机出力矢量;A为系统关联矩阵;xjmax为支路j可以新增线路的上限。

作为初步研究,本文采用简化的数学模型,考虑稳态运行方式下不出现过负荷作为约束,认为规划方案的投资费用只与新建线路长度有关,同时使规划方案的建设投资费用最小。

$\max Y({\rm Z})={\rm Z}{}_0-\left({\displaystyle \sum _{i=1}^{{\rm N}}L}{}_{i}z{}_i+C{\rm P}{}_{\text{e}\text{x}}\right)(5)$

式中Z是表示规划方案的N维向量。N是所有待选线路的数目,zi是Z的第i个元素,表示第i条待选线路在规划方案中是否被加入系统,取值为0或1(1代表加入,0代表不加入);Li是第i条待选线路的长度;Pex为网络过负荷量,可以通过直流潮流或最大网流法得到;C是过负荷惩罚系数;Z0为一常数,为避免目标函数值为负,可取一较大的正数。

3 人工鱼群算法 (AFSA)

3.1 人工鱼群简介

在一片水域中,鱼生存数目最多的地方一般就是本水域中富含营养物质最多的地方,因此,本算法就依据这一特点来模仿鱼群的觅食行为从而实现寻优。以下给出三种典型的鱼类行为:

(1) 鱼的觅食行为:当发现食物时,会向食物或食物浓度高的水域快速游过去;若没有发现食物或周围食物浓度都较低,则自由随机游动。

(2) 鱼的尾随行为:在鱼群的游动过程中,当其中一条或几条发现食物时,其邻近的伙伴会尾随至附近。

(3) 鱼的聚群行为:鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群。鱼聚群时所遵守的规则有:分隔规则,尽量避免与邻近伙伴过于拥挤;对准规则,尽量与邻近伙伴的平均方向一致;内聚规则,尽量朝邻近伙伴的中心移动。

3.2 人工鱼群相关概念说明

人工鱼个体位置表示为向量Z = (z1,z2,…zn),其中zi(i=1,2,…n)为欲寻优的控制变量,也代表人工鱼位置的坐标,本文中控制变量取值仅为0或1。

$z{}_i=\{\begin{array}{l}1‚\text{第}i\text{条}\text{线}\text{路}\text{加}\text{入}\text{了}\text{网}\text{络}。\\ 0‚\text{第}i\text{条}\text{线}\text{路}\text{未}\text{加}\text{入}\text{网}\text{络}。\end{array}(6)$

式(5)作为目标函数,即食物浓度,人工鱼的每一个位置都对应一个食物浓度Y(Z)。

人工鱼的视野为Visual,表示人工鱼一次可以移动的最远范围。在其视野范围内,人工鱼可以执行觅食、追尾等行为。

人工鱼的移动是其进行觅食、追尾的前提。规定人工鱼的移动只能在其视野内进行,移动的方式为改变自身位置的坐标。例如某人工鱼的视野为m(m≤n),表示它可以通过改变自身位置Z = (z1,z2,…zn)中不多于m个坐标来改变自身位置从而实现移动。

4 AFSA在输电网规划中的应用

4.1 人工鱼群算法描述

人工鱼的行为描述:

(1) 人工鱼的觅食行为:假设人工鱼当前位置为Zi,在视野Visual内随机选择一个新位置Zj,如果Yi<Yj,则向该方向前进一步;反之,则重新随机选择位置Zj,判断是否满足前进条件;反复trytimes次后,如果仍不满足前进条件,则随机移动一步。公式表述如下:

$\begin{array}{l}\text{i}\text{f}(Y{}_j\ge Y{}_i)\\ \begin{array}{l}{\rm Z}{}_{\text{i}\text{n}\text{e}\text{x}\text{t}}={\rm Z}{}_i+\text{R}\text{a}\text{n}\text{d}\text{o}\text{m}(\text{v}\text{i}\text{s}\text{u}\text{a}\text{l});\\ \text{e}\text{l}\text{s}\text{e}\\ {\rm Z}{}_{\text{i}\text{n}\text{e}\text{x}\text{t}}={\rm Z}{}_i+\text{R}\text{a}\text{n}\text{d}\text{o}\text{m}(1)；\end{array}(7)\end{array}$

其中:Zi——人工鱼当前所处位置;

Zinext——人工鱼随机移动后所处的位置;

Yi——当前状态下的目标函数值;

Yj——随机移动后的目标函数值;

Zi+Random(1)——当前所在位置的坐标随机1位取反。

Zi+Random(visual)——当前所在位置的坐标随机visual位取反。

(2) 人工鱼的追尾行为:假设人工鱼当前位置为Zi,探索当前邻域内的伙伴中Y为最大的伙伴位置Zmax,若Yi < Y,且邻域内伙伴的数目nf满足:

$\frac{n{}_{\text{f}}}{{\rm N}}\le \delta (8)$

式中:N——人工鱼总数;

δ——拥挤度, 0<δ<1;

表明伙伴Zmax处食物浓度较高且不太拥挤,则立刻移动至该伙伴处。公式表述如下:

$\begin{array}{l}\text{i}\text{f}(n{}_{\text{f}}/{\rm N}＜\delta ＆＆Y{}_j＞Y{}_i)\\ {\rm Z}{}_{\text{i}\text{n}\text{e}\text{x}\text{t}}={\rm Z}{}_{\max }；\\ \text{e}\text{l}\text{s}\text{e}\\ \text{c}\text{o}\text{n}\text{d}\text{u}\text{c}\text{t}\text{p}\text{r}\text{e}\text{y}\end{array}(9)$

(3) 人工鱼的聚群行为:在文献[8,9,10]中,介绍了人工鱼群在控制变量连续时的聚群行为,由于电网规划的控制变量为离散的0、1变量,无法描述鱼群中心位置,故本文算法不考虑人工鱼的聚群行为。

(4) 公告板:算法中设一个公告板,用以记录最优人工鱼个体位置及该人工鱼位置的食物浓度值。每条人工鱼在进行一次行动后就将自身当前状态与公告板进行比较,如果优于公告板则用自身状态取代公告板状态。这样就使公告板记录下了所有人工鱼在整个寻优过程中的最优食物浓度Ymax及其对应的人工鱼状态位置Zmax。公告板不光可以保留一个最优解,根据需要,还可以保留多个较优解,这也可以为实际的规划问题提供更多的选择。

4.2 应用于输电网规划的AFSA算法流程

人工鱼群算法解决输电网规划的基本过程为:

(1) 输入初始数据,如人工鱼条数、最大迭代次数、视野、觅食尝试次数等。

(2) 利用随机数发生器在控制变量可行域内随机生成个人工鱼个体,形成初始鱼群。鱼群中的每个人工鱼个体都代表一个初始方案。计算初始鱼群个体当前位置的食物浓度,并比较大小,取食物浓度最大者进入公告板,保存其位置及食物浓度值。即在初始方案中选择最优方案,为寻优过程提供一个供比较的基准值。

(3) 各人工鱼分别执行觅食行为、追尾行为;选择行为后食物浓度较大者实际执行,缺省方式为觅食。这是以通过最有效的行动方式搜寻更优的规划方案。

(4) 各人工鱼行动一次后,检验自身位置的食物浓度与公告板比较,如果优于公告板,则取代之。即每条人工鱼检查自己是否搜索到此时最合理的规划方案。

(5) 判断是否达到预置的最大迭代次数,若是则输出计算结果;否则转步骤(4)。

各条人工鱼通过不断改变自身的位置,并将对应位置的食物浓度与公告板比较,在经过一系列的反复搜索寻优过程后,可能包含最优解的最佳的结果将最终被留在公告板上。

以上基本过程见图1所示。

5 算例分析

5.1 算例1

对广泛采用的IEEE Garver-6系统进行试验,该算例原有6个独立节点,6条输电线路,待选线路共22条。受篇幅所限,IEEE Garver-6节点系统网络图及相关参数参见文献[4]。根据人工鱼群算法和分析调试的经验,人工鱼条数一般可取为待选线路的0.5～1倍,最大觅食次数一般取近似等于待选线路条数,其余参数可按问题复杂程度参考选择。

参数设置时考虑了文献[10]的意见,经调试,可取人工鱼条数N = 12,最大迭代次数Gmax = 15,最大觅食尝试次数trytimes = 30,觅食视野Visual = 2, Z0 = 10000,C = 2.4,过负荷的检验采用直流潮流,公告板最终保留2个最优结果。

应用数学软件MATLAB编制人工鱼群算法的程序并求解,得到两个相同的最优食物浓度Y = 9635,人工鱼状态(位置)所代表的网络结构如图2所示,这也与最优的网络规划结果相吻合。

同样应用MATLAB软件编制遗传算法的程序,其适应度函数与人工鱼群算法的食物浓度函数相同,程序所用部分参数参考文献[2],染色体域为60,交叉率取为0.5,变异率取为0.027,最终保留2个最优染色体。计算得到与人工鱼群算法相同的结果,网络结构如图2所示。

与遗传算法相比,人工鱼群算法不仅继承了其模型简单直观、适合解决电网规划问题的优点,并且具有更快的收敛速度,每次迭代食物浓度(目标函数)都有显著的改善,如图3所示,同时不需要人为确定交叉率、变异率这样的经验参数。

5.2 算例2

对18节点系统进行试验,该系统共有18个独立节点,9条现有输电线路及32条待选输电线路,网络结构及相关参数请参见文献[1]。

根据人工鱼群算法,参数设置时考虑了文献[10]的意见,经调试,取人工鱼条数(N = 25),最大迭代次数Gmax = 35,最大觅食尝试次数trytimes = 45,觅食视野Visual = 3,过负荷的检验采用直流潮流,规划结果如图4所示,与文献[1]中所得结果相同。

以下分析各参数的变化对计算结果的影响:

(1) 人工鱼条数对计算结果的影响。表1给出了最大迭代次数Gmax = 15,觅食视野Visual = 3时人工鱼条数的变化对计算结果的影响。人工鱼条数的增长使得搜索个体更加稠密地分布在解空间,更加有利于最优解或较优解的产生;但同时,人工鱼条数的增长加大了计算量,从表1可以看出人工鱼条数的增长与计算时间的增长近似呈现出线性关系。

(2) 觅食视野对计算结果的影响。表2给出了最大迭代次数Gmax = 15,人工鱼条数N = 30时,觅食视野的变化对计算结果的影响。从表2可以看出,人工鱼的觅食视野在某一个合理的范围内时,对结果影响不明显,但超出这个范围后,对迭代收敛的速度有一定的影响;觅食视野对计算时间的影响较小。

6 结论

人工鱼群算法是一种新的随机搜索优化算法,它具有并行性、全局性、跟踪性等特点,为解决一些非线性及离散的优化问题提供了一条新的思路。人工鱼群算法在电力系统输电网规划中具有潜在的实用前景。通过上述的理论分析和实践计算得到以下结论:

(1) 人工鱼群算法应用于电网规划问题,模型简单直观,收敛较快。

(2) 全局寻优能力强,最终还可以生成一系列较优方案,供规划人员参考比较。

(3) 新方案的生成是随机完成,在一定程度上避免了陷入局部极值;在随机生成新方案后,立刻与现方案进行比较,及时否定和修改欠佳的方案,加快收敛速度。

(4) 人工鱼算法应用于输电网网络扩展规划是可行的有效的。

作为初步尝试,本文只是采用较简单的模型来描述输电网规划问题,没有考虑稳定性的影响、N-1校验以及多阶段规划的过渡等问题,进一步的工作还需要在这些方面进行改进和完善。

摘要：人工鱼群算法是一种基于动物自治体模型的优化算法。各人工鱼通过各种行为不断改变自身的位置,并将对应位置的食物浓度与公告板最优食物浓度比较,在经过一系列的反复搜索寻优过程后,可能包含最优解的最佳结果将最终被保留在公告板上。针对输电网络网架的扩展规划这样一个复杂的组合优化问题,建立相应的数学模型,首次尝试采用人工鱼群算法求解。该算法用于IEEE Garver-6系统和18节点系统的计算结果表明,人工鱼群算法用于电力系统输电网规划是可行的,有效的。

关键词：电力系统,电网规划,人工鱼群算法

参考文献

[1]王锡凡(Wang Xifan).电力系统优化规划(Optimizationof power system planning)[M].北京:水利电力出版社(Beijing:Hydraulic and Elec.Power Press),1990.

[2]王秀丽,王锡凡(Wang Xiuli,Wang Xifan).遗传算法在输电系统规划中的应用(Transmission system planningwith genetic algorithm)[J].西安交通大学学报(J Xi anJiaotong Univ.),1995,29(8):1-9.

[3]王秀丽,陈皓勇,王锡凡,等(Wang Xiuli,Chen Haoyong,Wang Xifan,et al.).基于非支配遗传算法及协同进化算法的多目标多区域电网规划(Multi-objective andmulti-district transmission planning based on NSGA-II andcooperative co-evolutionary algorithm)[J].中国电机工程学报(Proc.CSEE),2006,26(12):11-15

[4]刘可真,陈勇(Liu Kezhen,Chen Yong).基于改进遗传算法的输电网优化规划(Transmission network planningbased on improved genetic algorithm)[J].昆明理工大学学报(J Kunming Univ.of S&T),2007,32(1):32-35.

[5]金义雄,程浩忠(Jin Yixiong,Cheng Haozhong).改进粒子群算法及其在输电网规划的应用(Improved particleswarm optimization method and its application in powertransmission network planning)[J].中国电机工程学报(Proc.CSEE),2005,25(4):46-50.

[6]金义雄,程浩忠(Jin Yixiong,Cheng Haozhong).计及阻塞管理及剩余容量的并行粒子群电网规划方法(Parallel particle swarm optimization on power transmissionnetwork planning taking account of congestion managementand residual capacity)[J].电网技术(Power SystemTech.),2005,29(23):18-23.

[7]刘耀年,庞松岭,刘岱(Liu Yaonian,Pang Songling,LiuDai).基于人工鱼群算法神经网络的电力系统短期负荷预测(Short-term load forecasting method based onartificial fish-swarm algorithm of neural network)[J].电工电能新技术(Adv.Tech.of Elec.Eng.&Energy),2005,24(4):5-8.

[8]王锡淮,郑晓鸣(Wang Xihuai,Zheng Xiaoming).求解约束优化问题的人工鱼群算法(Artificial fish schoolalgorithm for solving constrained optimization problems)[J].计算机工程与应用(Computer engineering andapplications),2007,43(3):40-42.

[9]李晓磊,冯少辉,钱积新,等(Li Xiaolei,Feng Shaohui,Qian Jixin,et al.).基于人工鱼群算法的鲁棒PID控制器参数整定方法研究(Parameter tuning method of robustPID controller based on artificial fish school algorithm)[J].信息与控制(Information and Control),2004,33(1):112-115.

[10]刘耀年,李迎新,张冰冰,等(Liu Yaonian,Li Yinxin,Zhang Bingbing,et al.).基于人工鱼群算法的最优潮流计算(Artificial fish school algorithm for optimal power flowproblems)[J].电工电能新技术(Adv.Tech.of Elec.Eng.&energy),2006,25(4):30-33.

改进人工鱼群算法及其收敛性分析 篇5

作为一种新颖的群体智能算法,人工鱼群[1—8]AFS(Artificial Fish Swarm)算法由文献[1]于2002年首次提出,很快便受到国内外学者的重视,并针对该算法展开了相关的研究。相关研究表明,该算法具有较快的收敛速度,以及不需要相关的先验知识,对参数初始值不敏感等特点[1]。

在文献[1]中,作者对AFS算法的原理进行了相关说明以及设计原理,并应用该算法求解属于NP-Hard的组合优化问题,获得较好的求解效果,证明了该算法的有效性;在文献[2]中,作者在鱼群算法的后期每隔一定的代数,引入一次单纯形算子,替换掉原来大量聚集在非极值点附近的人工鱼个体,有效提高了局部搜索精度,提高了解质量;在文献[3]中作者针对鱼群算法中的两个主要参数视野、步长进行了改进,使两个参数在进化过程中逐步减小,提出了一种简化的自适应鱼群算法,实验证明该算法的收敛速度比原始鱼群算法有较大提高;文献[4]则提出了一种多鱼群协同的人工鱼群算法,并用于实现对连续空间变量的分类规则提取问题[4];文献[5]将模糊理论与人工鱼群算法融合提出了一种模糊自适应的人工鱼群算法;文献[6]针对人工鱼群算法求解多峰函数时难以发现全部最优的弱点,将小生境技术和模拟退火技术融入人工鱼群算法之中,同时加入变异算子和小生境半径自动生成机制,实验结果表明算法在求解多峰函数时非常有效;文献[7]应用人工鱼群算法解决支持ABC的QOS单播路由机制,取得了不错的效果。文献[8]利用有限马尔科夫链理论分析了鱼群算法的进化过程,得出结论鱼群算法是全局渐进收敛的。

与众多的群体智能算法一样,人工鱼群算法通过模拟自然界中具有生命的群体行为协作求解,缺少严格的数学理论支撑,所以群体多样性的保持能力成为了限制该算法求解能力的关键因素。鱼群算法前期收敛速度较快,能够迅速靠近最优解,但是后期往往容易陷入局部极值,存在求解精度低等问题。为了克服此缺点,在算法的后期依据种群拥挤度引进小生境排挤机制,提出一种小生境自适应人工鱼群算法(NAFS)。

1 小生境人工鱼群算法

1.1 小生境算法

源于生物学中的小生境[6]指的是具有同类特征的生物聚集在一起,形成一个相似的生活环境。该技术应用于计算科学中,可以将具有相同特征的数据划归一类、不同特征的数据分离开,避免大量数据在局部最优点附近聚集。

在小生境技术中有三种种群选择策略。分别是基于预选择机制、基于排挤机制、基于共享机制。这里主要应用基于排挤机制选择策略。

基于排挤机制的选择策略如下:

(1)设置排挤因子CF(2 or 3);

(2)在群体中随机选择1/CF个群体参与排挤运算;

(3)产生新个体成员,计算新个体与排挤成员之间的海明距离;

(4)利用新产生的个体排挤掉一些与排挤成员相类似的个体。

1.2 原始AFS算法

人工鱼群算法通过模拟鱼群的觅食、聚群、追尾等行为,利用鱼群间的相互协作来达到求取问题最优解。算法分为三个步骤:觅食行为、聚群行为、追尾行为。算法的主要参数如下:

visual—鱼的视野范围;

λ—拥挤因子(0<λ<1);

step—移动步长;

try_number—尝试次数。

将鱼所处位置的食物浓度设为f(X),即待求解目标函数,当前鱼个体的状态表示为X=(X1,X2,…,Xn)。以求解minf(X)为例,鱼群算法的流程描述如下。

1.2.1 自由游动

设鱼的当前状态为Xi,在没有执行其它任何行为的时候,鱼个体在自己视野范围visual内随机游动。

1.2.2 觅食行为

设鱼的当前状态为Xi,在其视野范围visual之内随机选择一新状态Xj,如果f(Xj)<f(Xi),则鱼向该状态移动一步;否则,重新选择一个新的Xj,进行尝试。如果尝试try_number次后仍然不能移动,则将鱼随机移动一步。

1.2.3 聚群行为

设鱼的当前状态为Xi,在其视野范围visual内搜索聚集鱼群的中心位置Xc,并探测附近的同伴个数s。如果s/N<λ,表示该中心位置不拥挤,如果此时f(Xc)<f(Xi)则鱼向该方向前进一步,否则执行觅食行为。

1.2.4 追尾行为

设鱼的当前状态为Xi,在其视野范围visual内搜索最优的鱼个体Xmin。设Xmin视野领域内的伙伴数为s',如果f(Xi)>f(Xmin)并且s'/N<λ,表明该位置食物较多,并且不够拥挤,则当前鱼向该位置前进一步,否则继续执行觅食行为。

1.2.5更新公告板

设置一个公告板,用于记录鱼群内历史最佳鱼的状态Xgbest。各人工鱼每迭代一次都检查自身状态,如果f(Xi)<f(Xgbest)成立,则将Xgbest修改为Xi。

1.3 AFS算法改进

AFS早期收敛速度较快,能够迅速找到问题的粗略解,而在算法的后期由于鱼群大量的聚集,鱼群多样性降低,容易出现鱼群聚集于局部最优解的现象。源于此,引入公式2描述鱼个体之间的聚集程度,并根据鱼群的聚集程度来决定是否执行小生境算法排挤。

式(2)中,fk是鱼个体的适应度函数值,favg是鱼个体的适应度平均值。显然,α2的值越小,说明鱼的聚集程度越高;当其为0时,则算法要么是已经全局收敛完毕,要么收敛于局部最优。

设阈值β为较小的一个值,当α2<=β时,引入小生境机制,随机生成现有鱼个体数目20%的新鱼个体,将不符合条件的20%鱼个体排挤掉,以维持种群的多样性。

算法标记为NAFS,描述如下:

算法1.NAFS算法

1.在解空间内随机初始化鱼群个体;

2.参数初始化;

3.While(终止条件不满足)

4.do begin

5.自由游动;

6.觅食操作;

7.聚群操作;

8.追尾操作;

9.if(α2≤β)then执行小生境排挤算法;

10.endwhile

11.cout<<求解结果。

2 NAFS的全局收敛性证明

为了证明群体智能算法的全局收敛性,主要采用的方法包括有限马尔科夫链技术[8—11]和随机泛函理论[12—14]等。通过分析1.3节中的NAFS算法,可知该算法采用精英保留策略,以个体鱼所在位置食物浓度评价鱼个体状态的优劣,鱼个体的进化序列必然是一个单调非递增的序列。

另外,鱼群算法中的鱼个体均通过随机游动产生新状态,该操作类似于遗传算法中的变异操作,而这种变异的目的是为了产生更加优异的新状态,保证算法向全局最优解进化,故应用随机泛函理证明NAFS的收敛性。

不失一般性,现假定使用f(x)为最小优化函数,解空间则表示为:

Ω={X|X=(x1,x2,…,xk)}∧Li≤xi≤Ui,i=1,2,…,k},是一个k维欧式空间Rk的有界子集,其中Li<Ui,令,则。

定义1[13]设X是一个非空集合,d是一个X×X到R的映射,当且仅当X集合中任意的元素x,y,z,满足如下要求:

(1)d(x,y)≥0(其中d(x,y)=0,当且仅当x=y);

(2)d(x,y)=d(y,x);

(3)d(x,y)≤d(x,z)+d(z,y)。

则称为d为X上的度量(或称为距离函数),称为(X,d)为度量空间。

定理1[13]若(X,d)为一个度量空间,x,y,z,x1,y1为X中的任意元素,则具有如下性质。

(1)|d(x,z)-d(y,z)|≤d(x,y);

(2)|d(x,y)-d(x1,y1)|≤d(x,x1)+d(y,y1)。

定义2[13] 若(X,d)是度量空间,{xn}是(X,d)中的任一序列,对于任意的ε>0,存在正整数N,使得对于n>N有d(xn,x)<ε成立,则称序列{xn}在(X,d)中收敛于x。

定义3[13] 若(X,d)是度量空间,{xn}是{X,d}中的任一序列。若对于任意的ε>0,存在正整数N,使得一切m,n>N,有d(xm,xn)<ε,则称序列{xn}是(X,d)中的cauchy序列。若{X,d}中的每一个cauchy序列都收敛,则称(X,d)为完备度量空间。

定义4[13] 设(X,d)是完备度量空间,对于映射f:X->X,若存在任意的ε∈(0,1),使得对于任意的x,y满足d(f(x),f(y))≤ε*d(x,y),则称f为压缩映射。

定理2[13] 设(X,d)为完备度量空间,f:X→X为一压缩映射,则f有且仅有一个不动点x*属于X,并且对于任意的x0∈X,满足:

其中f0(x0)=x0,fk+1(x0)=f[fk(x0)]。

定理3 当t→$时,NAFS算法是渐进全局收敛的。

(1)鱼群个体通过觅食操作来调整自身的状态向最优解靠近,即以概率β产生新的状态集合Ω'。(Ω',B,μ)表示一个完全概率测度空间,B是非空抽象集合Ω'上的某些子集构成的σ-代数,μ为B上的概率测度,Xj是随机生成的visual内的新状态,则应用如下公式描述这一过程:

显然,该映射是一个随机映射。

(2)算法通过聚群操作、追尾操作和排挤操作,生成下一代种群,为简便操作,称之为选择算子SO,可以看做是解空间上的映射,如下描述:

σ2:G2→G。(注:因为上述这些操作中均存在两两比较,所以原始状态标记为G2)

对于鱼群中任意的两个个体鱼存在:

(3)NAFS进化过程实质就是一个通过上述(1)、(2)两个算子映射过程的逆序合成,即是一个作用于当前种群P的映射过程,表示如下:

g是产生新状态的一个基本操作。

各代群体中的最优个体的适应值序列{f[Xbest(t)]}(1≤t≤Tmax)必是一个单调非递增序列。

通过上述关于鱼群的算子定义、分析可知,NAFS算法每一次迭代均使新种群在总体上较上一次种群更加趋优,故对于随机映射σ=(σ1°σ2):Ω'×G→G,存在一个非负随机变量ε∈(0,1)使得下式成立:

NAFS的映射σ=(σ1°σ2):Ω'×G->G是一个随机压缩映射。

根据定理2可知,必然存在一个唯一的随机不动点x*满足σ(g,x*)=x*,即:成立,说明NAFS是渐进全局收敛的,定理得证。

3 仿真实验

计算机硬件配置为AMD TL—6双核CPU,主频为2.0 G,内存为2 G。软件配置操作系统windows xp sp3,编程环境为开源免费的code::block。参与对比的算法包括AFS、差异演化算法(DE)、粒子群算法(PSO)等算法。对比的项目包括:最大值、最小值、平均值、标准差。AFS、NAFS算法均单独运行30次,实验结果列于表2中,其中DE和PSO的数据来自于文献[15]。测试用的Benchmark函数如下:

Rosenbrock function

从表1中提供的NAFS算法的测试数据可以看出,NAFS算法在求解能力上明显要较原始AFS算法提高了很多,也比DE和PSO算法优越许多。这充分说明,针对该算法的改进是卓有成效的。加入小生境排挤机制,在算法后期提高了种群的多样性,使得算法能够进行比较全面的解空间搜索,求解精度得以提高。从均方差的数据可以看出,NAFS算法较AFS等算法有更强的鲁棒性。

4 结论

针对人工鱼群算法容易陷入局部最优、求解精度低的缺点,在鱼群算法的后期根据鱼群的聚集程度引入小生境排挤机制,排挤掉一部分状态相近的个体鱼,同时随机增加一部分新个体,保持了种群的多样性。通过应用理论分析和在Benchmark函数上的实验,证明该算法具有较好的全局收敛能力、较高的求解精度和较强的鲁棒性,可以应用于求解高维优化问题。如何解决小生境算法的执行随机性,将是进一步的研究方向。

鱼群算法 篇6

声纳视觉感知属于计算机视觉和人工智能的重要分支, 在水下潜水器系统中具有不可替代的作用。近年来, 水下声纳技术被广泛应用到鱼群探测、资源勘探、水下管道探测以及水底天然气监测等领域。声纳图像由于声信息传输的复杂性, 在多数情况下目标信息会淹没在信道、背景等噪声中。随着信息技术的飞速发展, 声纳数据处理的方法也随着科学技术的发展而不断改进。鱼群统计对于水下养殖以及珍贵鱼类保护具有重要的应用价[2,3]。2003年Moursud[4]等利用双频识别声纳观测了鱼群游过水电站鱼道的情况, 2004年Maxwell[5]等验证了用双频识别声纳在浑浊水域中评估洄游大马哈鱼的数量, 2006年Everitt[6]等利用双频识别声纳对密苏里河渔业进行管理。Han[7]等用双频识别声纳做了洄游鱼类以及养殖的大型鱼类的尾数、体长自动计数、测量的研究, 能够自动精确地计算出鱼的尾数和体长。董剑锋[8,9]等对双频识别声纳图像处理进行了初步研究, 并运用到香鱼计数上。上述方法主要是针对鱼群进行大致的统计分析, 缺乏较为准确的定量分析。已有研究表明, 利用DIDSON视频进行鱼群各种应用, 其关键是鱼群检测方法的精度[10]。

1 传统目标检测算法鱼群检测结果

与光学图像相比, 声纳图像本身的信息小于随机噪声信息, 因此将光学图像的目标检测算法直接应用于声纳图像目标检测时效果不理想。图1分别为帧间差模型、平均背景法模型、高斯混合模型、Code Book背景模型、背景差分法直接用于声纳图像目标检测的效果图。

由图可知, 由于声纳图像随机高斯噪声含量大, 帧间差模型检测结果最差;平均背景模型、高斯混合模型和Code Bool背景模型的检测结果含有大量孤立噪声点且鱼体轮廓含有大量毛刺;背景差分法检测结果中含有鬼影。

2 本文鱼群检测算法

本文充分利用声纳图像噪声特性和鱼体亮度统计特性, 在背景差分法基础上提出了一种DIDSON鱼群目标检测及鬼影抑制方法。具体思路:首先采用背景差分法初步寻找可能出现的鱼体目标点;利用声纳特性, 对初步检测的鱼体目标点进行鬼影判断去除鬼影;最后采用形态学开闭运算去除孤立噪声点。

2.1 背景差分理论

背景差分工作原理:设背景模型为M (x) ={v1, v2, …, vN}, 其中N个样本值均为已被判断为背景的像素值。记v (x) 为x点处的像素值, 设定阈值R, 计算{v (x) -R, v (x) +R}区间内与样本模型M (x) 相交的样本值个数, 若数值大于预设的某个最小值, 则将当前像素点x的像素值v (x) 判断为背景, 否则为前景。

初始化:利用相近像素点具有相近的时空分布特性, 用一帧图像填充样本集。其优点在于:对噪声比较灵敏、计算量小、速度快, 可以很快的进行运动物体检测。更新策略:每一个背景点有1/φ的概率更新背景模型样本集, 同时也有1/φ的概率去更新其它的邻居点的背景模型样本集。当前景点计数达到临界值时, 将其变为背景, 并有1/φ的概率背景模型样本值。

由于背景差分采用一帧建模, 如果模型初始化时出现目标, 会将前景目标点误判为背景。当前景目标点离开后, 当前像素值无法与背景样本集匹配, 导致背景像素点被错误地检测为前景点形成鬼影, 严重影响后续的跟踪或识别。

2.2 鬼影抑制

通过对DIDSON数据图像的特性分析可知声纳图像中的鱼体目标属于高亮区域, 且背景区域中仅有少量的波纹信息是属于高亮区域的。因此本文基于此特性提出了鬼影抑制方法。其基本思想:对已预处理的视频采用背景差分法初步寻找出当前帧中的前景目标;然后对这些前目标景的像素值作进一步判断, 若此像素点的像素值大于阈值T, 即判断为前景, 否则认为是鬼影并判断为背景, 同时更新背景模型。

2.3 实验结果分析

本实验将本文的目标检测方法与其它经典检测算法, 针对小鱼群和大鱼群检测性能进行对比分析。实验环境配置为matlab2009a, 内存8GB, 处理器为Intel Core i5-3470 3.20GHz、声纳视频帧率为8 fps。大鱼群检测结果如图2所示。

如图2, Code Book算法检测出的目标边缘模糊, 且存在大量的误检像素。背景差分法存在严重的鬼影现象 (图2中第3行白色椭圆标记的鱼体为鬼影) , 鬼影在第139帧以后也未消失。而本文提出的算法在第28帧之前, 鬼影已消失, 整体检测性能明显优于Code Book算法和背景差分算法。同时本文算法在鱼体较小的情况下, 其检测效果同样较好。

3 鱼群数量统计

3.1 鱼群数量统计方法

本文单帧鱼群数量统计流程:鱼群目标检测后的图像中任然还有一个小面积的连通域, 这些小面积的连通域并不是鱼体而是一些干扰物, 因此在进行单帧数量统计之前需要消除面积较小的连通域。首先去除面积较小的连通域, 然后统计这一帧图像中连通区域的个数, 既可以得到一帧中的鱼体个数。

假设在图像中有n帧图像检测到鱼体, 每帧鱼体数量记为Nm, 对每m帧求一次平均, 即将视频分成k个部分, 其中k=floor (n/m) ;再对k部分的鱼体数量分别求均值, 最后将k个部分的均值累计即得到整个图像序列的鱼群数量, 其公式表达式如下:

3.2 实验结果与分析

采用本文所示方法对many fish.avi图像序列进行单帧鱼体数量统计, 其结果如图所示。

从图中可以看出, 本文算法对单帧鱼体数量统计基本准确, 但是对于即将消失的鱼体和即将出现在声纳视野中的鱼体检测结果较差、不够精确。由于将消失的鱼体其回波较弱, 在图像上反应忽明忽暗, 容易被漏检。其次大鱼在游动的过程中会产生大量水波, 剧烈的水波也会被误检成鱼体。

采用本文所示方法对many fish.avi图像序列进行鱼群数量统计, 整个视频一共有162帧, 目测整个图像序列一共游过了16条鱼。通过本文的检测结果N=16, 其中m取得40;通过DIDSON二次开发软件检测的结果如图4所示;本文单帧检测结果见表1。

如图4所示, DIDSON二次开发软件检测出的鱼群数量为9。通过本文算法检测出的鱼体数量为16, 与DIDSON二次开发软件检测的结果更准确。其中表1展示了本文算法在many fish.avi图像序列从第1帧到第27帧的单帧检测结果。

采用本文提出的方法对Kenai3-12manyfishnoshad.avi图像序列进行鱼群数量统计, 整个视频一共有790帧, 目测整个图像序列一共游过了87条鱼。通过本文的检测结果N=72条, 其中m取得40;通过DIDSON二次开发软件检测的结果如图5所示。

如图5所示, DIDSON二次开发软件统计的鱼群数量为42条。由此可以看出DIDSON二次开发软件在对体长较小的鱼统计数量效果较差。本文的统计结果更接近真实结果。

4 结论

由于声纳图像的含有大量噪声信息, 采用光学图像的目标检测算法不能满足声纳图像目标检测的要求。针对这个问题, 本文提出的目标检测方法在保留背景差分法优势的同时能快速抑制鬼影。其次再鱼群统计算法上, 本文提出了一种简单的统计方法:在基于精确的鱼群检测上, 统计鱼群数量;实验结果表明, 本文提出的鱼群数量统计结果比DIDSON二次开发软件的统计结果更准确, 且满足实时性需求。

摘要：双频识别声纳 (DIDSON) 可以在黑暗浑浊的水下获得清晰的视频影像。对双频识别声纳的鱼群视频进行基于智能视觉的鱼群数量统计, 可高效、准确的评估该水域的渔业资源[1]。提出了一种简单可靠的统计方法:首先通过改进的目标检测算法检测鱼体并统计每帧鱼体数量;其次将视频分成多个部分并对各部分的鱼体数量进行统计;最后将各个部分的统计值累计得到整个图像序列的鱼群数量。实验结果表明本文提出的鱼群数量统计结果比DIDSON二次开发软件的统计结果更准确, 且满足实时性需求。

关键词：双频识别声纳,鱼群检测,鬼影抑制,背景差分

参考文献

[1]张进.基于双频识别声纳DIDSON的鱼群定量评估技术[D].上海:上海海洋大学, 2012.

[2]SHEN W, YANG L, ZHANG J, et al.The survey of fishery resources and spatial distribution using DIDSON imaging sonar data[C]//IFIP 2013:International conference on the Advances in Information and Communication Technology.New York, US:Springer Press, 2013:366-375

[3]谭细畅, 史建全, 张宏.EY60回声探测仪在青海湖鱼类资源量评估中的应用[J].湖泊科学, 2009, 21 (6) :865-872.

[4]Melvin, G, Li.Y.Mayer, L and Clay, A.The development of an automated sounder soanr acoustic logging system for deployment on commercial fishing vessel[Z].ICES CM, 1998:14.

[5]Misund, O.A.Aglen, AandFronaes, E.Mappingtheshape, size and density of fishs chools by echo integration and a highresolution sonar[J].ICES J.Mar.Sci, 1995, 52:11-20.

[6]Maxwell, S.and Gove, N.The Feasibility of Estimating Migrating Salmon Passage Rates in Turbid Rivers using a Dual-Frequency Identification Sonar (DIDSON) .Regional Information Report No.2A04-05[R].Alaska Department of Fish and Game, March 2004.

[7]Everitt, D.Adams, J.and Mestl, G.Using DIDSON technology to observe the ecology and behavior of Missouri River fishes[C]//Proceedings of the 67th Midwest Fish and Wildlife Conference.Omaha.Nebraska, Dec 6-10, 2006.

[8]童剑锋, 韩军, 沈蔚.声学摄像仪图像处理的初步研究及在渔业上的应用[J].湖南农业科学, 2010, 17.

[9]童剑锋, 韩军, 浅田昭, 溝口雅彦.基于声学摄像仪的溯河洄游幼香鱼计数[J].渔业现代化, 2009, 36.

鱼群算法 篇7

近20年来,基于混沌搜索路径的集中优化算法有了很大的发展,出现了混沌神经网络[1],混沌模拟退火[2],混沌禁忌搜索[3]和混沌搜索[4]等相关算法,这些只是一些确定的优化算法例子。基于混沌的搜寻策略可以获得很好的性能并且避免了局部最优,该方法比任意搜寻更有效率。

在混沌控制及同步问题中,如何获得混沌动态系统的不确定参数是一个很重要的问题。近几年,人们提出了很多不同的方法来解决混沌系统的参数识别问题。基于卡尔曼滤波,Annan和Hargreaves介绍了一种有效识别混沌系统参数的方法;基于Lyapunov函数理论,Parlitz和Chen etal通过同步方法来估计混沌系统的参数[5],Lietal对该方法进行了相关讨论。

现给出了一种称作CFS的搜索算法,通过构造一个合适的适应度函数,将混沌系统的参数估计问题转化为参数优化问题来解决参数辨识问题。在CFS算法中,引进组织变量得到鱼群的组织自律过程。在算法中,有两种选择邻居的途径。Lorenz系统和Logistic系统的仿真结果表明了所提出算法对于混沌系统参数优化的有效性。

1混沌鱼群优化算法

受到鱼天性行为的启发,提出了一种称为CFS(混沌鱼群)的优化方法。该算法从混乱视角来描述:单个鱼的混沌行为和鱼群的智能组织行为的适应性,从而解决优化问题。假设:鱼能够找到食物来源,并能记住最好食物来源的信息。鱼之间交换信息。在自我组织搜寻过程中,有如下两个连续过程发生:(1)鱼混乱行走导致的不协调过程,鱼的组织能力很弱,单个鱼在混乱行走时拥有信息素或者可视标志作为间接联系的形式去帮助其它鱼获得适合的食物来源,这一阶段持续到单个行为导致的组织影响足够大时;(2)产生协调阶段。纵观整个自我组织过程,鱼间交换信息且进行比较并记住这种信息。

鱼的搜索区域对应于问题的搜索空间。所提算法搜寻最优所在的搜索空间通常记做Rl,l为连续空间的实际数目。假设有K只鱼,它们位于搜索区域S且它们试图记住S→R的函数关系。在S中的每个s对于所考虑的问题都是有效的解决办法。由于仅考虑搜索空间为连续空间的情况(S=Rl)。第i个鱼的位置记为数学变量si=(zi1,…,zil),其中i=1,2,…,K。显然,每个变量可为任意有限维。在行动过程中,每个鱼单个受到群体的有组织过程的影响。从数学角度看,单个鱼的运动策略假设为当前位置、由该鱼找到的最佳位置、相邻的其他成员,组织变量函数如下表示:

zid(n)=g[zid(n-1),pid(n-1),yi(n)] (1)

式(1)中:n表示当前步数,n-1表示先前步数;

zid(n)表示鱼单个i的第d维的当前状态;

pid(n-1)表示有第i个鱼和相邻的鱼在n-1步之前找到的最佳位置;yi(n)表示组织变量的当前状态;g表示非线性函数。

问题的焦点是定义规则:一只鱼可以移动的期望方式。期望的单个鱼的搜索行为最初是混乱的,最初的组织变量行为对单个鱼的影响相当小。伴随组织变量不断的改变,最终,该组织变量行为对单个鱼的影响越来越强烈。当组织变量的影响足够大时,鱼的无序行为就消失了。然后鱼在它们能找到在搜索空间内做进一步的搜索和移动。在整个过程当中,它们和周边不断地交换着信息。

为了获得最初的混沌搜索,Sole[7]介绍的混沌系统方程xn+1=xn+1eu(1-xn)被介绍进入本文的准启发式方程。由于成功消耗组织变量yi(n)的引入导致单个鱼混沌行为的调整,并引领单个移动到新的位置最终获得最好的状态。为了实现个体之间的信息交换和以最好的状态到达新的位置,提出(pid(n-1)-zid(n-1))。pid(n-1)是根据广泛应用于诸如遗传算法和禁忌搜索的最优化理论来选择的。因此,获得了混沌鱼群的动态优化系统如下:

$\{\begin{array}{l}y{}_i(n)=y{}_i(n-1){}^{(1+r{}_i)}\\ z{}_{id}(n)=z{}_{id}(n-1)e{}^{(1-ay{}_i(n))(3-\psi {}_{d}z{}_{id}(n-1))}+\\ (p{}_{id}(n-1)-z{}_{id}(n-1))e{}^{-2ay{}_i(n)+b}\end{array}(2)$

式(2)中,a是一个足够大的正常量并可以选择a=200,b是一个常量并0≤b≤1/3,ψd决定了在d元空间内的选择搜索范围,ri>0是一个正常数并小1,由受组织因素作用的鱼i所确定, yi(n)=0.999,其他变量的定义同方程(1)。

前文提到,鱼经常通过一些直接或间接的方式交换信息,它们之间的组织就随着时间逐渐变强,最终所有的鱼走到食物源头。方程(2)描述搜索过程中的混沌鱼群,yi(n)是用来控制混乱过程中鱼的行走方式,并且它最初对鱼行为的影响是非常微弱的。这就是说,yi(n)对状态混沌系统的影响较小。随着时间的发展,组织变量yi(n)通过ri的影响变得越来越大。而pid和yi(n)的影响使得混沌系统最终趋于最优或近似最优状态。

ri和ψd在算法中是两个重要的参数。ri作用于混沌鱼群的收敛速度。如果组织因素ri非常大,且“混乱”搜索的时间较小,则系统收敛较快。因此,不能达到预期的最优或近似最优状态。如果组织因素ri非常小,且“混乱”搜索的时间较长,则系统收敛慢并且运行时间会很长。随着时间的发展,小的改变是必须的, ri的取值通常是选择0≤ri≤0.5,ri的格式可以根据具体的问题和运行时间来设计。

为了表示每只鱼都有不同的ri,现设置ri=0.1+0.2·rand(),这里rand()是一个在[0,1]均匀分布的随机数。在“混乱”的搜索后,收敛速度将主要通过

zid(n)=zid(n-1)+eb[pid(n-1)-zid(n-1)]

决定。ψd主要影响了该方法的搜索范围。通过分析方程(2),得知,如果参数ψd很小,则算法的搜索范围较大,反之亦然。如果间隔的搜索是[0,ωd],便可以获得一个近似公式ωd=7.5/ψd。ψd的值应该根据具体的优化问题适当地选择。

通过各种模拟,发现上述模型的混沌鱼群方程(2)在约束搜索寻优积极或消极的间隔。也就是说,如果ψd>0,方程(2)可用于实现在所有zid≥0时间间隔内的搜索过程。如果ψd<0,方程(2)可用于所有zid≤0的时间间隔内的搜索过程。当所有最优值位于积极的间隔(或消极的间隔),方程(2)能够有效地解决数值优化问题。然而,最优值可以位于整个实数范围内。为了解决这一问题的搜索区域,现给出了比方程(2)更加完美的CFS模型:

式(3)中0≤Vi≤1决定鱼i的搜索区域,且拥有在不同问题空间搜索的优势。如果Vi=1/2,这意味着和方程(2)相比,鱼i的混沌吸引子向负的方向移动一半。Vi应该按照具体的优化问题适当取值。方程(3)为一般的混沌鱼群算法模型。在这个模型中可以选择单个鱼的zid(0)=(7.5/ψd)(1-Vi)rand(),ψd>0作为初始位置。

原则上, 一个区域可以是任何有限指令集。在它们附近的参数空间内, 这些邻居不一定是单个个体, 而是拓扑空间内单个个体。该方法中, 相邻鱼是根据它们有限的距离空间定义的。这是一种动态的邻居。当然,在空间中可以使用任意距离的定义, 例如拓扑距离和规范距离。这里, 假设有两个鱼的位置(zi1, …, zil)和(zj1, …, zjl),而i, j=1, 2, …, K并且i≠j; i, j意味着第i和j个鱼,那么两只鱼之间的距离为$\sqrt{(z{}_{i1}-z{}_{j1}){}^2+(z{}_{i2}-z{}_{j2}){}^2+\cdots (z{}_{il}-z{}_{jl}){}^2}$。

现定义了两种方法的邻居选择。第一种是最近的固定数量的邻居,定义最近的m个鱼作为鱼i的邻居。例如,定义最近的3条鱼作为邻居,一条鱼的邻居可能会随着时间的变化而改变;第二种是邻居的数量选择是考虑到随着迭代的步骤,邻居数量会增加的情况。这是由于鱼行为的自组性的影响。组织的影响将变得比以前更加强且邻里之间的鱼会增加。也就是说,最近邻居的数量是随着时间的推移或迭代步骤增加而动态改变的。这里定义q为伴随迭代步骤增加的单个鱼数量。由于每个单独的轨迹是调整向邻居,鱼群收敛或集群在搜索空间中的最优区域。如果单个鱼不能从它们的邻居获得最好的食物来源的信息,搜索的一些鱼便会失败。

2混沌系统的参数识别

将描述通过混沌鱼群算法混沌系统的参数估计过程:

$\dot{\overrightarrow{x}}=G(\overrightarrow{x},\theta )(4)$

让式(4)作为一个持续的非线性混沌系统,$\overrightarrow{x}=(x{}_1,\cdots ,x{}_{{\rm N}}){}^{\text{Τ}}$为混沌系统的状态向量,$\dot{\overrightarrow{x}}$是$\overrightarrow{x}$的导数,θ=(θ1,…,θt)是混沌系统的未知参数向量。

下面给出持续混沌系统参数识别过程。在搜索空间中随机生成所有鱼的最初位置,鱼$\overrightarrow{x}$的初始位置为$\widehat{\theta }{}_i^0=(\widehat{\theta }{}_{il}^0‚\cdots ‚\widehat{\theta }{}_{il}^0){}^{\text{Τ}}$;i=1,2,…,K这里$\widehat{\theta }$是θ的估计。未知参数的搜索范围是通过ψd选择的,其中d指的是搜索范围dth元素的搜索空间变量。基于可衡量的状态向量

定义如式(5)目标函数。

$f(\overrightarrow{e})={\displaystyle \sum _{t=0}^W[}(x{}_1(t)-x{}_{i1}^n(t)]{}^2+\cdots +$

[xN(t)-xniN(t)2] (5)

式(5)中t=0,1,2…,W。因此,把参数估计的问题转化为用CFS算法寻找$\widehat{\theta }{}_i^0=(\widehat{\theta }{}_{il}^0‚\cdots ‚\widehat{\theta }{}_{il}^0){}^{\text{Τ}}$的最优值,所以未知变量f在整体上被缩小。对于每一步,公式(4)中$\widehat{\theta }{}_i^n$将会被取代。利用非线性方程(4),将会得到状态向量$\overrightarrow{x}{}_i^n(t)=[x{}_{i1}(t),\cdots ,x{}_{il}(t)]{}^{\text{Τ}}$。在每一个重复步骤中,由公式(5)衡量的已辨识出参数的性能。如果所有的鱼达到最终的状态,参数估计的过程将结束并输出结果。

现在讨论如何获得状态向量$\overrightarrow{x}(t)$,仿真是用未知的四阶龙格-库塔矩阵在Matlab的环境下运行。任意选择一个点作为初始状态,并且初始时刻设为0。让混沌系统从初始时刻运行到Wh。那么可以得到在时刻0h,1h,2h,…,Mh下的状态向量$\overrightarrow{x}(t)=[x{}_1(t),\cdots ,x{}_{{\rm N}}(t)]{}^{\text{Τ}}$,这里步长h=0.01和上述连续混沌系统的辨识过程是相似的,由此可以解决在非线性混沌系统匹配上的参数估计问题。

3仿真实例

通过数值仿真证实了CFS算法对混沌系统参数估计的作用。CFS的参数选择是基于快速收敛率,达到了预期的结果。由于篇幅有限,这里仅选择著名的Logistic系统和Lorenz系统[8]为代表[9]验证本文算法。系统描述为:

xn+1=λ(1-xn)xn (6)

$\{\begin{array}{l}\stackrel{\cdot }{{\displaystyle x{}_1}}=\theta {}_1(x{}_2-x{}_1)\\ \stackrel{\cdot }{{\displaystyle x{}_2}}=(\theta {}_2-x{}_3)x{}_1-x{}_2\\ \stackrel{\cdot }{{\displaystyle x{}_3}}=x{}_{1}x{}_2-\theta {}_{3}x{}_3\end{array}(7)$

在(6)式、(7)式分别所示的Logistic和Lorenz系统里x1、x2、x3、xn是状态变量,θ1、θ2、θ3、λ是未知的正常数参数。在模拟中设置参数值为θ1=10、θ2=28、θ3=8/3,λ=4此时该系统处于混沌状态。设置方程(2)中的混沌鱼群参数y(0)=0.999,a=200,b=2/3,K=20, ψ1=0.5,ψ2=0.15,ψ3=0.75,ri=0.1+0.2·rand()。W=30是目标函数(5)的参数。邻居的数量是19,这是第一个类邻居形式。

为了观察鱼群的非线性动态搜索过程作为一个整体,分别绘制Logistic和Lorenz系统的所有鱼的搜索值如图1—图3和图4。从图4中,可以看到经过本文鱼群算法的处理,最终算法收敛到了Lorenz系统相应的参数值上,所以说该混沌鱼群模型可以作为一个有效的优化模型,是混沌系统参数参数辨识的有效工具。

4总结

利用仿生学搜索算法—CFS(混沌鱼群)算法,成功的研究了混沌系统参数辨识问题。CFS是一个确定性混沌优化方法,它的灵感来自大自然真正的鱼行为,它有别于传统鱼群算法。是一个通过混乱的视角来描述单个鱼的自适应混沌行为和智能组织行动鱼群优化问题的解决方法。该方法包括混沌动态学和swarm-based搜索。Lorenz系统和Logisti系统仿真结果表明了该算法的有效性和可行性。此方法可以解决工程上的许多优化问题。

参考文献

[1] Aihara K,Takabe T,Toyoda M.Chaotic neural networks.Phys LettA,1990;44:333—340

[2] Chen L,Aihara K.Chaotic simulated annealing by a neural networkmodel with transient chaos.Neurl Networks,1995;8:15—30

[3] Hasegawa M,Ikeguchi T,Aihara K,et al.A novel chaotic search forquadratic assignment problems.Eur J Operat Res,2002;139:543—56

[4] Li B,Jiang W.Optimizing complex functions by chaos search.Int JCybernet Syst,1998;29:409—419

[5] Lie J,Chen S,Xie J.Parameter identificat and control of uncertainunifie chaotic system via adaptive extending equilibrium manifold ap-proach.Chaos,Solitons&Fractals,2004;19:533—540

[6]杨万利,王铁宁.非线性动力学理论及应用.北京:国防工业出版社,2007

[7]彭书华,李邓化,苏中,等.一类不确定混沌系统的模糊滑模控制与同步.计算机工程与设计,2010;31(6):1291—1293

[8] Kehui Sun,J.Sprott C.Dynamics of simplified Lorenz system.Int JBifurcat Chaos,2009;19:1357—1366

鱼群算法 篇8

关键词：电网建设,物资需求预测,支持向量机,鱼群算法,混沌搜索

电网建设项目所需的物资是电力企业物资需求的主体,其需求量的合理预测,对于加强物资计划和采购,提高物资计划及时性、准确性,节约物资成本具有重要意义。以往由于物资需求预测所需支持数据的缺乏,预测结果往往不佳,使用效果也不理想。国家电网公司的企业资源计划(ERP)系统已于2010年全面正式上线,为电网建设物资的需求预测提供了一个难得的数据平台,能够为物资需求预测提供初步的数据支撑。使得利用系统数据资源,依据工程建设里程碑计划中的基本工程指标如电压等级、线路长度、变电容量等,构建合理有效的模型,进行物资需求预测成为可能。

目前电网建设项目的物资需求预测分析刚刚起步,邬斌弢和张玉鑫针对以物资信息提前储备为基础的电网企业物资需求进行了研究[1]。相似的研究中,张斌、陈建国、吴金生等提出了基于精细网格的台风灾损空间模型及相应的台风应急物资需求定性预测模型[2],傅志妍和陈坚从案例推理所确定关键因素出发构建了灾害应急物资需求预测模型[3],蔡开龙、姚武文、孙云帆等利用RBF神经网络技术对飞机战伤抢修备件需求预测进行了研究[4], 张晓磊、杨西龙和展丽潇提出了基于模糊相似推理的应急物资需求预测模型[5]。

电网建设项目物资需求影响因素(如设计方案、工程实际情况等)复杂多变,所需物资的种类繁多,物资需求呈现明显的随机性和非线性特征,而支持向量机模型能够在此类问题中表现出较强的优势。在现有利用支持向量机进行预测分析的研究中,鲍永胜和吴振升应用支持向量机对短期风速进行了预测计算[6],沈梁玉和于欣针对夏季电力负荷采用支持向量机进行预测分析[7], 祝金荣、何永秀和Furong Li结合混沌理论和支持向量机提出了一个新的电价预测模型[8]。本文则基于支持向量机模型,结合加入混沌搜索因子的人工鱼群算法,提出用于电网建设项目物资需求的预测模型,并通过实例数据测试模型性能。

1.理论基础

1.1 支持向量机

支持向量机(support vector machines, SVM)是由Vapnik提出的一个机器学习算法[9],以统计学习理论为基础,数学基础完善,几何解释直观,在分类问题、回归分析、图象识别等领域有着广泛应用。其核心思想是将数据实现非线性变换, 映射到特征空间,寻找支持向量,确定最优分离超平面(如图1)。

支持向量机通过将函数集的子集按照一定规则排列,使得在相同的置信范围子集中,实现风险的最小化。现有的SVM通常有C -支持向量分类机、υ - 支持向量分类机、ε -支持向量回归机、υ - 支持向量回归机。其中υ - 支持向量回归机的数学形式为:

而能否较好地求解问题,支持向量机的关键在于满足维数限制的前提下采用合适的核函数,不同的核函数对于不同的SVM算法。常用的SVM的非线性核函数有三种:

1.2 人工鱼群算法

人工鱼群算法是我国学者李晓磊等提出的一种群智能优化算法[10],该算法具有并行搜索、收敛速度快、能够跳出局部最优、对初值不敏感、鲁棒性强等优点,在参数计算、数据拟合、组合问题和优化调度等领域得到了良好应用。

人工鱼群算法以自然界鱼群的行为学研究为基础,提出人工鱼的概念,定义了人工鱼的四种行为:觅食行为、聚群行为、追尾行为和随机行为,其中随机行为是前三种行为的缺省行为。人工鱼个体对四种行为方式所引起的求解函数值的变化进行分析, 择优执行。通过不断模拟和迭代计算,人工鱼群体能够表现出对函数优化的群体智慧,从而使问题得到优化。

2.预测模型构建

2.1问题特性分析

电网建设项目以输变电工程、配网工程为主。对于各个不同的电网建设项目而言,物资需求有其个体性和共性。有因工程自身特殊情况而进行的个别设计,也有按照设计规范可以采用的标准设计图集。共性因素作用下的物资需求,可以通过区分不同工程类别,构建恰当的预测模型和算法,取得满意的预测结果。个体性因素作用下的物资需求,往往单体预测模型无法满足精度要求,需采用多项目汇总的方式,控制总体预测误差,使预测结果满足实际使用要求。

由于工程建设的特殊性、设计方案的灵活性,电网建设项目的物资需求非线性明显。物资种类繁多,样本数据矩阵呈现的稀疏性特征,预测难度较大。因此建立的预测模型不仅要适用,而且要通过对比真实值和预测值的差异,逐步修正预测模型参数, 才能提高预测质量。

2.2 模型构建思路

对于单体工程预测,选取在非线性问题预测中性能变现良好的支持向量回归机模型。因为选取不同的核函数或设定不同的参数取值,都会影响预测精度,所以需要借助寻优算法优化核函数的选取和支持向量机参数的设置。本文利用对初值不敏感、收敛速度快并且全局搜索能力强的人工鱼群算法进行模型优化。先利用较低精度的预测计算,逐步优化核函数选取和参数设置,结果满意后再进行高精度的正式预测。同时针对预测中不确定性因素较多,核函数选择和参数设置规律性差的特点,在基本的人工鱼群算法中,增加混沌搜索算子,利用其随机不重复遍历的特点, 提高算法的搜索性能。采用的混沌搜索算子为:

当μ =4时,系统将处于完全的混沌状态。

2.3 模型代码描述

以增加了混沌搜索算子的人工鱼群算法,优化υ -支持向量回归机,所构建的电网建设项目物资需求预测模型,用C++语言伪代码描述如下。

3.预测效果分析

3.1测试数据整理

测试数据采用河南省电力公司自2010年1月至2012年8月间ERP系统中的全部物资需用数据记录。共约42万条,包括224种物资小类,涵盖10kV以上级输变电项目、技改项目和配网项目。按照项目个体对原始数据进行整理和分析,采用数据完整、项目代表性强的数据样本,从中随机抽取训练集数据和测试集数据, 检验模型预测性能。

3.2 结果分析

以控制电缆和钢芯铝绞线两类物资为例对模型预测结果进行说明,见图2、图3所示。图中横轴代表电网建设项目的项目样本编号,纵轴表示物资的需求量。若需求量为0,则表示该项目不使用此项物资。对比预测值和真实值可以看出,在多数情况下, 预测值较为准确,但也有个别点预测值与真实值相差较大,如图2中的项目7、项目12,图3中的项目22和项目27。

分析其产生的原因,由于工程建设项目的个体性和设计方案的灵活性,使得是否使用此类物资成为影响预测精度的首要问题。然而在项目施工图最终完稿前,依靠主要工程建设指标对物资需求预测,此问题又是无法回避的。因此使用模型进行需求预测时,必须通过增加预测项目数量,控制总体预测误差的办法, 减小物资使用的随机性,提高预测判断的准确性。

电网建设项目的物资需求预测实践结果表明,除个别特定条件下才使用的少数物资不具备预测条件外,大多数物资可以得到满足使用要求的预测值,且所预测物资的总值占到项目实际所需物资总价值的80%以上。

4.结论