多智能体差分进化算法

1、2011年7月Jul. 2011第26卷第7期Vol. 26 No. 7控制与决策Control and Decision文童编号：1001 -0920 (2011) 07-0961 -06多智能体差分进化算法何大阔，高广宇，王福利，刘阳(东北大学a教育部暨辽宁省流程工业综合自动化重点实验室,b.信息科学与工程学院,沈阳110819)摘 要：基丁乡种能体与基分进化算法的乞门优势，充分地将对多种能休环境的感知和反作用丁环境的能力与圣分 进化速度和全局寻优能力有机结合，提出一种多种能体左分进化算法.引入泾分进化算子以提高押能体更新速度并 保持眸体多样性，同时应川止交交义炸以改善智能体协作特性他保仃

2、效竟争，并通过局部优算/提岛算法的J 优粽度.对几种典型测试函数进行了测试,实验结果表明所提出的伴法具冇较强的全局寻优能力.关键词：多舒能体：左分进化：疋交交义算子：垦分进化算子：财部寻优算子中图分类号：TP273文献标识码：AMulti-agent differential evolution algorithmHE Da-kuo. GAO Guang-yu, WANG Fu-li. LIU Yang(a. Key Laboratory of Process Industry Automation of Ministry of Education b College of Informati

3、on Science and Engineering. Northeastern University. Shenyang 110819. China Correspondent： HE Da-kuo. E-mail： hedakuo )Abstract： Based on the respective strengths of multi-agent and differential evolution algorithm, multi-agentability of sensing the environment and reacting to the environment and di

4、fferential evolutions capacity of the speed and good global optimization are fully combined and multi-agent differential evolution algorithm is proposed The proposed differential evolution operator is introduced to improve the update speed of agent, and the diversity of the population is kept. The o

5、rthogonal crossover operator is imported to ameliorate cooperation characteristic and compete with their neighbors effectively. The local optimization operator is applied to improve searching precision. Several classic test functions are tested. and the results show that the proposed algorithm can i

6、mprove the global convergence ability.2011年7月Jul. 2011收稿日期：2010-06-03：修回日期：2010-08-23.基金项目：国家fl然科学战金项H(6077406&61004083)：中央高校肚本科研业务费专项资金项11.作者简介：何人阔(1975-),男，制教授，从事复朵I.业过程刖能建模、控制、优化的研究：王福利(1957-)，男，教授，购I：生导师，从M父杂工业过程建模与优化、故障诊断等研究.Key words： multi-agent： differential evolution： orthogonal searching o

7、perator1引言函数优化问题貝有广泛的应用背駅，几乎在科 学、商业和1程等领域的各个分支都存在这类问题. 签分进化算法作为i种智能随机捜索算法，以其快速 性和对搜索空间形状、函数类型等无任何限制等优 势，已成为求解函数优化问题的有效方法I.但是， 肖函数的维数增高时，搜索空间变大，变呈间耦介度 增强,从而会&致基分进化算法的全局搜索能力下降. 多智能体进化计算以其感知环境并反作用于环境的 特点表现出较大的智能特性，在对复杂问题尤其在高 维问题的求解中表现出色，已经广泛应用于各个学科 领域冋本文针对高维函数优化问题，仃机地将智能体对crossover operator： differenti

8、al evolution operator： local环境的感知和反作用的能力9棊分进化算法的快速 性和全局寻优能力相结合，提出一种多智能体差分进 化算法(MADE),设计了差分进化算子、局部寻优算 (等进化算子来实现智能体间的竞争、合作、自学习 等行为，其收敛速度远远烏于传统算法.仿真实验结 果显示，本文方法对高维函数优化问题具有较好的寻 优性能.2多智能体差分进化算法用于函数优化的智能体定义如卜： 一个智能体a 农示待优化函数的个候选解，其能虽为其I标函数 值的相反数(极小问题)，即a S, Energy (a) = -/(a).(1)帮能体的ri的足尽可能地増大n”能武所冇智第7期何大

9、周等：多智能体差分进化算法963能体均生存在一个网格环境中，称为押能体网格，记 为乙网格的大小为Lg x Lg,其中厶心为非零正 整数.每个智能体固定在一个格点上，记处F第讥亍.第j列的智能体为=则智能体厶的邻域为硏ghbor3Ec，J, Ly、厶”,Lj， 其中 y =(7W； j厶size,彳=1；3 一 1 1； 厶size： j = 1；j + l J / 厶size；1, j =厶size-每个智能体不能移动，只能号其邻域发生相互作 用.智能体网格可表示成图1所示的形式，每个恻圈 表示一个智能体,圈中的数字表示该智能体在网格中 所处的位置，只仃心在连线的两个郢能体才能发生相 互作用.

10、i1L-6-LL/A_/5JY；L0-4图1智能体网格何个和能体一般通过竞争与合作行为达到增加 口身能量的目的.除了竞争、合作行为外，智能体还可 以利用知识増加门身能虽.根据这些行为，除邻域竞 争算子外，本文还设计了 Jt他相应算f,其中邻域竞 争舁子和止交交叉算子实现智能体的竞争与合作行 为，差分进化算子和局部寻优算子实现智能体利用知 识的行为.邻域竞争算产为多智能体算法常规算F, 在此不再累述.下而主要介绍正交交叉算于、差分进 化算子和局部寻优算子.2.1正交交叉算子止交交叉算子是利用止交设计产生新的个体，即 利用正交设计信息对解空间的代表性,通过正交设计 矩阵确定较小数虽:并在搜索空间中

11、均匀分布的个体, 从而产生具冇代表性的个体.因此，将正交交叉算子 作用Litj与厶跻 上，以形成疋仝交义个体.止交表一般有矩阵苴积、特征旳数构造哈达马 姬阵两种产生方式，当求解函数的维数増加时，搜索 空间的大小打局部极值的个数也随看问题维数的增 尚而增长，能就函数求取时间増加I,函数备维数的耦 合11：増大，这些都给髙维问题的求解带來用难.当然, 耍应用止交交叉算子必须解决高维止交表的构造问 题，为此，本文设计了-种近似止交衣构造方法：假i殳待优化的岛维函数为n维，现在有-个zn维 的正交表，求取S,这里S = EVENO，其中EVEN表示向上収整.111 Lq(2m)组成如下矩阵：Hsl =

12、 Lg(2m)1,.,Lg(2-)s.x(Sxm).在进行正交交叉之询，随机从岛维正交表中选収 前n列组成正交交叉表.为了减少计算就，世交交义只取iE交交艾表中的 P(2vPWg)行进行交义，即按交更率R在所有智 能体中选择进行交叉操作的智能体厶小将厶，和 E赏依据正交交叉表产生P个智能体，并计算所产 生的P个智能体能戢，利用包括Lij在内的P十1个 智能体中能量垠大的智能体取代厶止交交叉算了的作用：多智能体在竞争和介作 时，正交交叉算了可以以最小的代价，获紂在多智能 体竞争中产生的有利于增加多押能体能戢的所有I人1 素，増加多智能体口身的优良因素,从而保证多智能 体之间的竞争全部为有效竞争,

13、使得影智能体的陡屋 不断增大.2.2差分进化算子羞分进化足利用父代个体的羞并性产生新个体, 保留优良个体，淘汰劣质的个体，从而引导搜索过程 向最优解逼近【.其优点是鲁棒性好、速度快、在实 数域上的搜寮能力强.为r提高幺智能本V?法的件 能，引入差分进化算法以利用其快速性等特点，同时 加速秤能体交流以实现能就増加.构建差分进化畀 子，即以智能体为种群进行一代差分进化.羌分进化 算了叮以实现快速更新等智能体的作用，1L鲁棒性 好、筝样性较强，从而提岛了算法的寻优性能.2.3局部寻优算子S*能体几冇号所求解问题相关的知识，因此它可 以利用这些知识进行局部寻优來提高其性能,而对智 能体进行局部搜索便可

14、实现其局部寻优的行为.本文 根据当询最优个体Agent, max _cG的信息构建小规 模多智能体网络实现局部搜索，即局部寻优算r.在局部寻优算子中，沖先产生一个智能体子网格 8厶其大小为sLxsLaL为非零止整数)，其上 的所仔智能体bS，(/,j = l,2,，&厶ze)均根据卜 式产生：J Agent-max上。,/ = 1JZ = 1;&Lii9 = “.I N八 otherwise式中=(刃旳几2厂，8卩知5)由 卜式产生：1xk,人火十 & X randn(l, n) Xk； ( 4jt + g x randn(l,n), otherwise.其中:Xk和班为第上维变量:的上下限,

15、randn(l,n)为 高斯分布的随机数,G为进化代数变就8的均 值为去，即Agent, max _cG的第上维变量值，标准羌 为1/G.由于局部寻优算f的作用是在蝕优解附近搜 索更优的解，而岛斯变并冇利丁在厳优点附近快速向 最优点无限靠近，同时随希进化代数G的増加，烏斯 变异的标准差变小，从而实现由粗到细的搜索过程. 局部寻优算子流程如图2所示.初始化务押能体子网络图2局部寻优算子流程2.4多智能体差分进化算法步骤与实现在多智能体羞分进化算法中，邻域竞争算孑起 优胜劣汰的作用；止交交叉舁了通过交叉保留优势 信息;差分进化算子和变并算子则将产牛和更新优势 *智能体;局部寻优算J进-步提高算法精

16、度当主 网格迭代一定代数后加入局部寻优算f操作,可降低 计算时间，迥冇效地发挥局部寻优算子的局部搜索能 力.而当主网格运行到一定代数时，它所找到的授优 点是全局极值点的可能性增大,这时再运用局部寻优 算亍可以达到事半功倍的效果.为防止早敛现象,由 随机更新率H)控制并进行秤能体随机更新，保持多 智能体网格的多样性，即依据R),利用高斯变异更新 多智能体主网格.等智能体星分进化算法的详细流程 如下：LG表示第G代的智能体网格,H+1/3和H+2/3 是“与/+1之间的中间代智能体网格.Agent.maxc是乙D,，乙中最优的智能体, Agent, max _cG是LG *|1垠优的智能体.Ste

17、p 1:初始化厶,更新 Agent, max0, Energymax0, G = 0.Step2:对中的每个智能体执行邻域竞争算 子，得到H+1/3.Step3:对于1G+1/3中的每个智能体，将止交交 叉算子作用其上，得到H+2/3.Step4:依据&对厶G+2/3中的每个智能体进行 差分进化和更新操作，得到LG+1.Step 5:从 LG+1 中找出 Agent.max _cG,并将局 部寻优算子作用其上.Step 6:如果Energy (Agent_ max _cG+1) Energy (Agent _maxG), 则有Agent_maxG+1 = Agent_max_cG,Energy

18、 _maxG+i = Energy (Agent _maxG+1); 否则Agent _maxG+1 = Agent _ max.Energy _maxG+1 = Energy (Agent _maxG).Step 7:如果满足终止条件，则输出Agent_maxG, 并停止；否则，令G = G十1,转Step2.多智能体差分进化算法流程如图3所示.图3多智能体差分进化算法流程3测试函数及仿真结果与分析3.1测试函数及仿真结果为了测试本文提出的MAD E算法的性能，本文 针对8个标准测试函数进行了测试，并将测试结果与 以往文献算法【绚进行了比较.测试肉数中多为多峰 函数，特别是歯数尺)8拥何9.

19、33 x 10157个局部极值 点，搜索过程容易陷入局部址优，以检验算法的多峰 搜索能力测试函数如下：耳)1 : min/(x)=刀诰a=lh =(0,0,. ,0), /(z*) = 0.n用)2 : min/(x) =2(-Hjsin(/Ri), 1=1S = 一500,500几 /(x*) = -12 569.5.nF03 : min/(x)= 10 cos(27trj 十 10, t=lS = -5.12,5.12n, h(0,，0), /(xe) = 0.Fg : min/(x)=焉丈诸 _ cos (为十 1, t=l t=l VS = -600,600n, ar，= (0,，0)

20、, /(z*) = 0.甩:min/(x)=-10sm2(7t2/t) + (yn 一 l)2+nn刀(5 一 1)21 + 10sin2(7t+i)+ i=ln$211(,10,100,4),i=lS = -50,50n, X = (1,. ,1), /(!*) = 0.其中u(xi,a, k、m)=k(xi a)m, Xi a;0, a W 毛 W a,炊=1 十-(z + 1)；斤(一窃a)m, n a.屉：min/(x)=籾 sin2(37tj：i)H-2(xt -1)21 + sin2(37tXj+i)i- t=ln(xn-l)2l+sin2(27txn)J+2 0(,5,100,4

21、),i=ls = -50,50”，h = (1, , 1), /(”)=0.i n07 : min/(z) = - (讨-16诡十 5切，i=lS = 5,5f,=(-2.903 53, -2.903 53,，-2.903 53), f(x9) = -78.33236n2甩:mm/(z) = - sin(Xj) sin20爲兀),=1S = 0,7tn,垠优解未知.f07和局8为100维测试幣数，其余测试函数为 30维.本文MADE算法利用MATLAB 7.1实现(定义 小于1.0 x 10-308为0),在奔腾IV电脑独立运行50次 (以往文献算法均在奔瞻1【1电脑独立运行50次). MAD

22、E参数设置如卜： Laize = 9, CR = 0.4, Po = 0.3, P =4,凡= 0.3, F = 2.5 2 x rand(l,0), sL = 3, Aj部 寻优算子最大迭代代数为10.测试结果如表1所示.其中NA表示文献未给出 该伯息.山表1可知，MADE算法无论是最优值还是 标准垦肉优于其他算法，从而验证了 MADE算法的 粘砸性和收敛性，尤其对测试函数&7和片8的7优 性能较好另外，在对100维测试函数刑8的优化计見 中，MADE算法得到f更优的优化结果(-99.620194, 见衣2),验证了 MADE算法对于解决多峰问题的优 越性能.第7期何大周等：多智能体差分进化

23、算法#第7期何大周等：多智能体差分进化算法965表1各种算法结果比较FunctionAlgorithmsGenerationsM-bestStdOpt-FALEP15006.32 x 1047.6 x 105FEP15005.7 x 10-41.3 x 104CEP/best50003.09G10-7NAOGA/QlOOOf00尺HHTGANA000HPSO-TVAC30000.01NAMLNA3.191230.29463LEA1000+4.727 x IO-166.218 x 10-17MADE10002.67 x IO183.5 x nrALEP1500-11469.25&2FEP9000

24、一 12 554.552.6OGA/QlOOOf-12 569.453 76.447 x IO-41ITGANA-12 5C9.4GO02EDA/L30+-12 569.48NA-12569.5M丄NA-5461.826275.15LEA1000+-12 569.4S4 24831 x 104MADE1000-12 569.4866180续表1各种算法结果比较FunctionAlgorithmsGenerationsM-bestStdOp(-FALEP15005.852.07FEP50000.0460.012CEP/best50004.73NAOGA/Q1000+00HTGANA00M)3HP

25、SO-TVAC50000.0440.1960CPSO-H6100000.778NAEDA/L30+0NAM-LNA121.757 57.7573LEA1000+2.103 x 1()783.359 X 1018MADE100003.221 X 1()76ALEP15000.0240.028FEP20000.0160.022CEP/best50002.52 x IO7NAOGA/Q10004-00HTGANA00HPSO-TVAC50000.010.0010CPSO-H6100000.052 4NAEDA/L304-0NAM-LNA0.118940.010404LEA1000+6.104 x U

26、r2.513 x IO17MADE10004.44 x 10161.02 x 10-16ALEP15000.0240.028FEP20000.0160.022OGA/Q1000+00HTGANA00只)50EDA/L30+0NAM-LNA0.118 940.010404LEA1000+6.104 x Ur2.513 x IO17MADE10004.602 2 x 10-223.821 X 10-aiALEP15009.8 x 1051.2 x 105FEP20001.6 x 1047.3 x 105OGA/Q1000+1.869 x 1042.615 x 105HTGANA1.000 x IO

27、40/*060EDA/L304-3.485 x IO31NAM-LNA1.505 342.255 64LEA1000+1.734 X 1041.205 X 10-4MADE10006.164 4 x 10-194.1362 x IO10OGA/Q10004-一 78.300029 61.293 x 103HTGANA一78.30300EDA/L30+-78.31077NAF07-78.332 36M丄NA-35.809950.89146LEA1000+-78.3106.127 x 103MADE1000一 78.332 3310OGA/Q1000+-92.830.026 26HTGANA-92

28、.830EDA/L30+-94.375 TNAPob-99.278 4M-LNA一23.975 440.628 75LEA1000+-93.010.023 14MADE1000-96.018 8020.2618第7期何大周等：多智能体差分进化算法#第7期何大周等：多智能体差分进化算法#表2各种算法对甩的求解结果n法最小值iftft城优解赠伉个敎MADE-99.620194 0F08 文献H42未知100-99.278 49.33 x 10159文献1刃一 99.616 303 65HSOGA1201-99.618 03.2计算复杂度分析MADEJ?法的寻优操作主耍曲邻域克算/、 正交交叉算子、

29、差分进化算子和局部寻优算子构成. 在一个进化代内，邻域竞争算f、正交 I f、 分进化算了和局部寻优s?rn标函数计算数量分别 为 % E益，X 尺 X 必如 8% + PxPcx 8% 则算法在一个进化代内H标函数计算数I我为FmADE =8ize 十 Bizo + P X 匕 X 厶fizo +（忆鑰+ PxPcX曲J控 制 与 决 氣第26卷966由 0 = 8L$讼Lizc fjFmADE =Le十Llize十P X R X厶紀十 OEfize十尸X尺X心= (2+*P几+ 0 + 0PR)x 厶?可见,MADE算法的汁算父杂度与0, P, Lsize相关,0, P, E心和Pc的数值

30、越大,MADE算法的计算复杂度 越高.另外，以只有邻域竞争算子和世交交义算子的基 本务智能体遗传算法为例，基本箸智能体遗传算法在 一个进化代内目标函数计算数量为AlAGA = size + 2size = 3size- 可见,MADE算法的il-ffli杂度与基本多智能体遗传 算法呈.线性关系，因为多和能体遗传算法呈现多项式 的渐进计算复杂度，所以MADE算法也呈现多项式 的渐进计算复朵度.4结论针对复杂高维函数优化问题，本文将多科能体算 法与签分进化算法和结合，充分利用多智能体模拟门 然环境、类似小工境逐渐进行扩散的优点，以及签分 进化算法在快速性和件棒性方面的优势，提出r 一种 多智能体羌

31、分进化算法.该方法在提出高维正交表产 生方法的基础上引入了正交交叉算子，同时利用局部 竞争算r等/优策略改进了多智能体算法性能.最后 通过函数优化仿真测试，验证了所提出方法的冇效性.参考文献(References)1 Brest J, Greiner S, Bokovi B. et al. Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problemsJ IEEE Trans on Evolutionary Computation, 2

32、006, 10(6): 646-6572 Kaelo R Ali M M. Differential evolution algorithms using hybrid mutationJ. Computational Optimization and Applications. 2007, 37(2): 231-2463 Brest J. Boskovic B Greiner S, et al. Performance comparison of self-adaptive and adaptive differential evolution algorithmsJ. Soft Compu

33、ting. 2007. 11(7): 617-629.4 Noman N, Iba H Accelerating differential evolution using an adaptive local searchJ. IEEE Trans on Evolutionary Computation. 200& 12(1): 107-125.5 Qin AIG Huang V L Suganthan P N. Differential evolution algorithm with strategy adaptation for global numerical optimization!

34、J. IEEE Trans on Evolutionary Computation, 2009, 13(2): 398417 6 潘晓英，刘芳，焦李成.基种能体的多忖标社会进化克法卩软件学报,2009, 20(7): 1703-1711(Pan X Y, Liu F, Jiao L C Multiobjective social evolutionary algorithm based on multi-agentJ. J of Software, 2009, 20(7): 1703-1713.)7 闫畅,汪定伟，王大志，等.求解动态苗包问题的多智能 体进化算法J东北大学学报：白然科学版,20

35、09, 30(7): 948-951 (Yan Y. Wang D W, Wang D 乙 et al. Multiagent-based evolutionary algorithm for dynamic knapsack problem|J. J of Northeastern University: Natural Science, 2009, 30(7): 948-951.)8 黄水青，陆青,梁昌勇，等.交互式多押能体进化算法及 其应用卩系统仿真学报,2006. 18(7): 2030-3032.(Huang Y Q. Lu Q. Liang C Y. et al. Interact

36、ive multi-agent evolutionary algorithm and its applicationJ J of System Simulation, 2006 18(7): 2030-3032.)9 钟伟才，薛明志，刘静.等.名种能休遗传篦法用超高 维函数优化J1.自然科学进展,2003,13(10): 1078-1083. (Zhong W C, Xue M Z9 Liu J9 et al. Multi-agent genetic algorithm for high-dimensional optimizationJ. Progress in Natural Science, 2003,13(10): 1078-1083.)10 Stom R. Price K V. Differential evolution A simple and efficient heuristic for global optimization over continuous spacesJJ. J of Global Optimization, 1997, 11(4): 341-359.11 Yiu-Wing Leun