新的混合智能优化算法及其多目标优化应用

1、1292计算机应用第30卷文章编号:1(X)1- 9081(2010) ()5- 1290- 03新的混合智能优化算法及其多目标优化应用张汉强，卢建刚，陈金水(浙江人学匸业控制技术M家巫点实验空，杭州310027)(1 叩han輕 i|)c zjl hIu rn)摘 要：针对人工鱼髀算法后期收效速度较慢、解精度不商的不足，按照分阶段寻优和变参數寻优的改进策略， 并结合禁忌搜索算法中的相关规则提出I种新的混合智能优化算法。该算法将寻优过程分为饋定最优解或者局部 解邻域和求得高精度最优解两 饰段，每 饰段设置不同的参数并结合禁忌搜索算法以提高收敛速度和最优解精 度。典型函数验证表明，该算法收敛速度

2、快、精度爲；同时，对于多目标优化问题.该算法可以提离Pan-bit优解集质 量扩大决炭分布范围，维持决我多样性，有利于决罠者作出决策。关键词：人工鱼群算法；分阶段寻优和变参数寻优：禁忌搜索：多目标优化中图分类号：TP273J 5文献标志码：ANew hybrid intelligoit optim izatbn algorithmand its applicatbn h multi-objective optim izatimZANG II aii-q iing IE Jiaif-gaiig CH EN Jui-sliui(StileKey Labomt>ryr of Industria

3、lCm trolTerhnolcgy Zhejiang Unwtrsity IIangsiiM Zhejiaig 310027 China)Abstract A fter aiiakz iig ie didvantages of lie sl(w er cciiveigtiice proiMTty and er a(x-ura(y h A rtifk'ial F islt- Sw am Algorihn (AFSA a new hybrid nte Urgent oplin izatkn a(goritlni was p»|)osed based on phased op t

4、in izatbn and varial) le paran eteroptm eat bn as well as sone relevait mlrs h talxi search aoriiiin In th k a lg> ritlin. tie optm izatbn process was(I K iinl iito bvo phases mew as b lock die neiiborfiood of the opt in al so b tbn or partul sohtbix die oiierw as to obtain ir qilinal solutim of

5、h glbprecbidi Ea(h phase set (lifffivnt )araneteis and c(m binl lie talxi s<*anh algorillin to in prove cxinvcigence s|)ee<l aixl ac(n racy of opt in al solutbiix The s inu h tioti results slxis that tlx* profMistl algor ilin cin great k in pmve tie ability of seek hg the g blxi 1 ex cel bn t

6、wsu It convergeiuv speed and acai rary. A s f>r the mu h4-ol>jrctke <j|> tin izatidi pn)b Inu tie pn)|M)seil a ritlin can ak) in pn)ve ie <ualit)of Paretoal sohlimn en brge die <1 is trim ti>n ar<!a of(l(x#isi)ns aixl mail tain(I kersity ii(l(!cibi)irtnak iigKey words .Artifi

7、 ud Fisl>-Swarn A ritlin (AFSA); |>l)as(tl (ptin izaticii ami variiblr paran optin izatim Tabu Searth (IS); mu It+obclke optin izatbn1292计算机应用第30卷1292计算机应用第30卷收稿日期：20)9. 11- 19修回日期：1)10- 01- 11 基金项目：国彖门然科学基金资助项U ( 60736021);国家863计划以U (2D06AA(MZ184 2007AA041406);浙江省科技计划资助项目(20)6611066 2OO6C3105

8、1);浙江省fl然科学基金资助项冃(Y4080339).作者简介：帐汉强(1982-)，黑浙江义乌人，硕上研究生，主要研究方向：复杂系统优化计算机智能控制;卢建刚(1968-),男浙江杭 州人教授匸要研究方向：复杂匸程系统的建模.控制与优化：陈金水(1970-)臥福建福州人制研究员】浚研究方向：嵌入式系统的软件 模卑柑再弊2()I2 China Academic Journal Electronic Publishing House. AH rights reserved, http:/ 0引言人们根處牛物系统的特征和一些物埋现彖构适设计出 许多仿生优化算法来解决复杂的实际问题，例如模拟退火算

9、 法M、粒子非算法宀和遗传算法E等.虽然这些优化算法具 有某些共同的机制和原理但由于不同的优化算法表现出不 同的行为特征和优缺点叫因而算法间的相互促进与补足逐 渐成为i种改进算法特性的H然途径。人工鱼 群算法(ArtiTbalF ish Schoo I A 如 ritlin. A FSA)是 李晓需等人21于2002年提出的一种垄于模拟饥群觅食、聚胖 和追尾行为的仿生型优化算法该算法具仃口好的克服局部 极伉、取得全局极值的能力，并FL该算法还貝有对初伉不敏 感、鲁棒性强、简单(只使用H标函数值)、易实现等诸多优 点。但足随着优化问題的不断父杂化，AFS在大规模父杂 优化间题的求解和应用中存在着

10、不足，匸要表现为算法得到 的解将度不高，优化就期收敛速度快但后期收敛速度慢等。 针对人工鱼胖算法的这些不足,本文提出基于分阶段3优和 变参数寻优的改进策略，并结合禁忌搜索(Talm Search TS) 算法® !>的禁总规则、解禁规则和终止规则提出一种新的 混介智能优化算 ii ( H ybril Intelligent Optin izatioi A Igorilin. HDA),将此优化算法应用在多目标优化问题中，取得了良好 的效果.1多目标优化问题描述在多目标优化问题中，以个目标通常是相互制约的关系， 对兀中一个目标进行优化往往以Jt他II标的性能降低为代 价因而全局敲

11、优值通过各日标平衡达到，其数学表达式如 下：in nF (X ) -(J( X ) f; i = 1,2 mh t S(X) = (a(X) )T 0 j = L 2 , kA <X < B其中:X = x.(i = L 2，n)为“维决策向St; F(X)= (f,(x)T为多口标优化函数向M；s(X)=为约束条件.表示S.(X) > (¥；= L 2，k);边界条件A<X<B表 示毎个决策分量须满足© < X. < bj i = L 2，n)c2人工鱼群算法概述2 1人工鱼个体相关定义人工鱼个体的状态X = (xlt x2t ,

12、 x ),其中Xj(i= L 2 ，n)为欲寻优的变昼；人工鱼当前食物浓度表示为Y = f(X);人工血个体之间的距离为心，=II X. - X II;人工血毎 次移动垠大试探次数为人匸血的感知距离为 9rvisua I人工鱼移动的加人步氏为.$坤,拥挤度因了为d2 2行为描述觅食行为 设人工血当前状态为X。在其感知距离内随 机选择状态X户求极小值问题中(因为极小值与极大值问题 类似，下面均以极小值问题讨论丿，当岭 > 片时,Xw二X, + Rg|QS®(X厂否则.重新随机选择状态X户判 断Y, >片反复尝试try num her次后,仍不满足询进条件，则随 机移动一步。

13、聚群行为 设人工仇当前状态为X,搜索当前邻域内 (即J, .< visable)的伙伴数目兮及中心位置X“如果Y丹< 丹；表明伙伴中心冇ft物较少且不太拥挤，则X,2 = X. + RmMQS"“ (Xt. -XJ /IIX. - X,ll;否则执行觅食行为。追尾行为 役人工鱼当询状态为X,探索当前邻域内伙 件小£为垠小的伙伴X,如果Ynt < 6人表明£伙伴的状态 具有较低的食物浓度并且其周围不太拥挤,则xl/nal = xl + 丿S(epX - A,/II X厂X；否则执行觅食行为。随机行为 随机行为是觅食行为的一个缺省行为.公告板用以记求

14、垠优人工血个体状态及该人工鱼位置 的食物浓度。2 3行为选择根据所要解决问题的性质.对人丁饥当询所处的环境进 行评价，从而选择一种介适的行为，-般按照进步显快脈则。2 4参数对算法的影响tnnunber越小,人工鱼摆脱丿部极值的能力越强，收敛 效率高.山硼/越大.越容易发现全局极值点 、切越大初始收 敛速度快.后期速度降低.而H.将度卞降；&较大时.觅食行为 和随机行为突出，有利于全烏搜索，提髙收敛速度.同样粘度 会降低，人工鱼数H A越多，收敛速度快，但足计算量加大。3禁忌搜索算法禁忌搜索算法足-种应用广泛的解决组介优化问题的启 发式全局优化算法.禁忌搜索算法的上要规则有:禁忌规则、

15、 特赦规则和终止规则等。所谓禁忌就是重复前面的匸作，提 髙算法的搜索效率.禁忌搜索算法通过引入一个灵活的存储 结构和相应的禁忌准则来避免辻冋搜索.并通过特赦准则来 赦免一些被禁忌的优良状态，保证幺样性的仃效捜索。同时， 为了使算法具冇优良的优化性能或时间性能，必须设置-个 合理的终止准则来结束整个搜索过程。4新的混合智能优化算法4 1人工鱼群算法改进策略为了提髙人工鱼聊算法搜索速度以及解粘度，本文结介 分阶段寻优和变参数寻优的思想对人工鱼群算法进行改进. 具体改进策略如下.将人匸鱼群算法寻优分成两个阶段，分别设置不同的参 数。第一阶段为锁怎最优解或局部解邻域阶段.人丁鱼群算 法参数设置规则如下

16、：川“山、£他、©较大值以及规模较大 的人工鱼群N f但足相对较小try mtn仏q,此时该算法具有良 好的全局探索俾花屈以姐快算法搜霹速度，很佛锁産最优解© 1994-2(112 C hina Academic Journal nrecfromc Pu 或扃部解所在的邻域。第：阶段为得到垃优解阶段，参数设置 相对较小的visua /2» slep2和Q,同时较大的trxnitn ber2用此 时的参数对第一讦段锁是邻应内人匸血重新初始化.忌现信 息交换这样即维持了询-阶段人匸血的何利特性，乂赋其 新的特性。此时人工鱼的参数设迓冇利于算法进行将密3 优可

17、以在显优解或局部解邻域内找到高裕度眾优解或局部 解。该策略充分发挥了人工血胖算法前期收敛速度快以及比 较容易确定最优解或局部解所在邻域的特点同时克服r ft 群算法荷期收敛速度慢、不能紂到粘确值的缺点。仿真研究 也表明这是一种比较好的人工鱼群算法改进策略。42新的混合智能优化算法人工鱼个体在7优的过程中，存在着较多的漫无目的的 蘆机行为,而且人工血会反父搜索全局显优解或者局部最优 解所在的邻域，尽管追尾行为能促使陷入局部垠优人I W!向 趋于全前极值的更优人工鱼方向迅随而逃离罔部极值域.但 是随着优化过程的不断进行,必然会有其他的人工色继续陷 入局部最优.这样的反复搜索寻优，降低了算法寻优的效

18、率。 为了解决这些问题，将TS灯法的相关规则与人工鱼群算法结 介起來，一冃发现满足禁忌规则的邻域就将此邻域移入禁忌 表中禁戌使得剩卜的人1M.无法搜索此邻域迫使共上搜索 没仃被禁忌的区域；同时重新初始化一定数星的人工鱼，碓保 没冇被禁忌的区域内冇足够的人T血來保持搜索速度；'”1禁 总表不耳发生变化或者达到设宦迭代次数时将剩卜的IX域 移入禁忌农屮禁忌.但足此区域不得待赦，这样可以有效解决 搜索效率的问题。定义禁忌算法的相关规则如下.禁忌规则 设人工伯当前状态为X*搜索当前邻域内的 伙伴数目少及中心位置X*如果Y丹 > 函表明伙伴中心有 作物较少但已拥挤.则此邻域中存在全局最优或

19、者局部最优. 那么就将/所在的邻域移入禁忌表禁忌。转故规則 如果禁忌农中召在满总解的邻域.则特赦该 满意解的所在邻域.终止规則如果算法达到设定的最大迭代次数或者一定 迭代次数内禁忌表不变，则算法终止。4 3多目标应用中H DA的步骤力多H标优化咸用中满足禁总规则的邻域必然存徃非 劣皿优解，那么就可以川II DA公获取pareloJd优解集。算 法步骤如下。步骤1初始化H【)A参数。人工血群算法两个阶段的 参数组分别为 £|； (visual sftpr uynumber、, 6)/, Ly (visual step? trnnnber7 6J,初始化公告板以及禁忌表.步辣2初j始花人

20、工血群心其参数为"设置此阶段最 大迭代次数。步陳3运行HK)第一阶段算法，搜索非劣最优解所在 的邻域.步辣4按照禁忌规则，将非劣瑕优解所在的邻域移入 禁忌表中禁忌，并在未禁忌的可行解域内乘新初始化足数 量的人工鱼。步曝5根据终止规则，判断是否可以终止，如果不可 以跳到步骤$否则，执行步骤&步骤6将不存在非劣最优解的可行解域移入禁总表禁 忌,并不得解禁。步猱7根据解禁规则，解禁存在1F劣最优解所在的邻 域并重新设置各个邻域内人工血参数.其参数为g步辣8运行II I)A第二阶段算法。L.伞楙9猶笛个邻域内满足备件旳II：劣最优解放入公管 ningl louse. AU right

21、s reserved. nnp:/板。步朦10刿断公吿板上的非劣眾优解数就是否琏木稳 定或者迭代次数达到设怎值如果没有跳到步骤&否则执 行下一步。步探11输出公告板上所冇的非劣嚴优解，作为“1. 最优解集。5仿真计算研究 5 1 H K)A性能验证木仿貞实验采川以下的非线性函数:数呈为甌则分布性能可用垠近解欧氏距离代的标准差s來表示:$ =d -(I, )2,其中 </, = m in (力 fk (AJ - fL(Af) I ；= I 2."丿为决策i到所冇决策的最短距 离L 2 .» M )为决策向就 7为对短距离的期琨，即 d=令工九。从农达式$可以看出

22、Mfi越小人小决策分竹越 均匀.=2丿决策散布范围评价函数。用目标空间中2个极值解的欧氏距离來表示敬布范围：1292计算机应用第30卷max/% y)北 - io 10/y - 10 10/该函数的极值点位于(0 0丿,极值为L设置AF从参数如下D =£ ( ”品(A.) - m 陆 S 丿，值越大表示仍的敬布范囤越广。表I AF从与HDA所彳I!实验结果比较1292计算机应用第30卷人工鱼数量 N = 5Q visua I = 2 5= 0 7 8 = 0 618 tnnmi her = 2设W H I)A参数如卜.人工仮数量他=50禁 zI忌表长度为 20 L< f vif

23、ualx =38 step、= L 5 Uy number、= L 8, = 0 25/< L2: i isual2 = 1. 2 step2 = 02 In mtn ber2 = a 5> = 0 8/oMathl>7环境下仿真结果如图1所示。通过仿真结果分析得出.H DA开始时的寻优速度明显算法解的个数标准差s散布范国78(1 0062L 26II DA86Q 00343 57仿实实验结果表明.新的混介智能优化算法II DA能够 获取PaietoAi优解集足一种比较好的求解多H标问题的方 法。山实验数据分析得出，号基本人工鱼群算法比较.H K)A 不仅得到较多Pan t,

24、®优解集解数就而J1决策的分布更加 均匀、散布范围更加广，显著提高了 Pareto ft优解集的质量, 维持了决策的等样性何利于决策者作出决策。因此.H K)A 在多口标优化过程中效果明显优于AF%6结语针对人工鱼群算法的不足之处.运用分阶段3优和变参 数寻优的策略.对人丁血群粥法进行改进并结合禁忌搜索算 法中的禁忌规则、解禁规则和终止规则提出一种新的混合智1292计算机应用第30卷快丁龙本人工鱼群算法,后期的7优速度也比准本人工鱼胖能优化算法。该算法充分发挥了人工鱼非算法前期收敛速度1292计算机应用第30卷算法快，并H H DA得到的全局最优解梢度较之有了显*的 提高基本上可以达

25、到理论最优值.由此可以看出,HDA的 收敛速度更快、精度更离。5 2 H KH在多目标优化中的验证本仿貞所用实例说数如下：n ifx(x) = xb g(x) = 1 1 + x? - 10 cos ( 2H.r2 )fi(x) = g(x)(切虫"Ds t e(x ) = cos( 0)If2(x) - e/ - sin (0)/)(x)-a | sh (bsin(0)(x) - e) + cosfO (x)e J | > 00=0 2H. a - 026= 10 c = 1, J = 6 e = 1oC Xj C L 0 x 2 C 1以下仿貞均Mai hb 7环境下编程运

26、行。为了衷明 HDA在解决多Fl标优化问题时具冇优越性，且便于与AFSA 作出对比将HDA参数设置如下:禁忌表长度为12Q人工鱼 群规模= 12(1算法第-阶段/人迭代次数为50Q算法第 二阶段放大迭代次数为600 L、: f visual =02 siep t = 0 1 trynifn ber = I 6, = 4 5/. L、: (vutial2 = 0 05 $师2 = Q 025 trymun ber = 2 S, = L 98/ aAFSX参数设置如下：人工鱼数呈N = 120 visual = Q 15 sltp = 0 075 8 = 2 85 trynum her = 2 最大迭代次数为 I lOOu 在仿貞实例中.将从解的数星、决策分布均匀性和决策散布范 围三个方而作出比较。快、容易确定最优解或局部解所在邻域的特点.克服了英后期 收敛速度慢、解将度不高的缺点。仿貞研究也表明H I)A比 AFSA收敛速度更快，垃优解粘度更髙，总体性能也更加突 出在多n标优化过程中.也取得了比较理想的效果。参考文献：11 | MURRA、A T CHURCH R L Appng