求解约束优化问题M-精英协同进化算法

2010年10月 第37卷第5期 西安电子科技大学学报(自然科学版) JOURNALOFXIDIANUNIVERSITY oct．2010 V01．37NO．5 doi：10．3969／j．issn．1001—2400．2010．05．014 求解约束优化问题M一精英协同进化算法 慕彩红1，焦李成1，刘 逸2’3 (1．西安电子科技大学智能感知与图像理解教育部重点实验室，陕西西安710071；2．西安电子科技 大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071；3．西安电子科技大学电子工 程学院，陕西西安710071) 摘要：提出了一种适用于约束优化问题的协同进化算法．该算法旨在模拟人类社会中团队的组建及其 协作方式，并强调精英人才对团队建设的推动作用．算法将整个种群分为精英种群和普通种群，围绕各 个精英来组建团队，使精英种群带动普通种群，进而带动整个种群不断进化．组建团队过程中，不同精英 之间采用协作操作。精英对普通种群成员进行引导操作，其中协作操作和引导操作由若干交叉或变异算 子的组合所定义．使用静态罚函数法将约束优化转化为无约束优化，利用13个约束优化测试函数对算 法进行了测试．仿真实验和参数 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 结果表明，该算法寻优精度高，算法稳定，运行时间少，其性能优于 组织进化算法，能够有效解决复杂的约束优化问题． 关键词：优化算法；约束优化；进化算法；协同进化算法 中图分类号：TPl8 文献标识码：A 文章编号：1001—2400(2010)05一0852—10 M—ElitecOeVolutiOnaryalgorithmforconstrainedoptimization MUCai—hon91，JIAOLi—chen91，LJUⅥ2·3 (1．MinistryofEducationKeyLab．ofIntelligentPerceptionandImageUnderstanding，XidianUniv． Xi’an710071，China；2．StateKeyLab．ofIntegratedServiceNetworks，XidianUniv．，Xi’an 710071，China；3．SehoolofElectronicEngineering，XidianUniv．，Xi’an710071，China) Abstract：AnalgorithmnamedtheM—EliteCoevolutionaryAlgorithm(MECA)isproposedfor constrainedoptimizationproblems．Thealgorithmsimulatestheestablishmentandcooperationofteams inthehumansocietywithemphasisontheimportantroleofelitesinteams．Thewholepopulationis dividedintotwosubpopulations，i．e．，elitepopulationandcommonpopulation，withtheformerleading thelattertoevolveSOastoacceleratetheevolutionofthewholepopulation．Duringthisprocessseveral teamsareestablished，eacheliteindividualactingasthecoreofeachteam．Thecooperatingoperationis implementedbetweenthedifferenteliteindividuals．andthecommonindividualsareledbytheelite individualsintheleadingoperationduringtheprocessofteamestablishment．Theabovecooperating operationandtheleadingoperationaredefinedbythedifferentcombinationsofseveralcrossover operatorsormutationoperators．Staticpenaltyfunctionsareusedtotransformaconstrainedoptimization problemintoanunconstrainedone，andtestsaremadeon13benchmarkproblems．Experimentalresults andparameteranalysisshowthattheMECAcanobtainahighsolutionqualitywithlessruntimeandis robustandthatitobtainsbetterperformancesthanOrganizationalEvolutionaryAlgorithm。andcansolve difficultconstrainedoptimizationproblem． KeyWords：optimizationalgorithms；constrainedoptimization；evolutionaryalgorithms；coevolutionary algorithms 传统进化算法非常适合于求解无约束优化问题，但当求解约束优化问题时会面临一些问题，即如何处理 收稿日期：2009—10—08 基金项目：国家自然科学基金资助项目(61003199，60703108)；国家863资助项目(2007AAl22223)；博士点基金资助项目(20070701022) 作者简介：慕彩红(1978一)，女．讲师，博士，E-mail：caihongm@mail．xidian．edu．cn． 万方数据 第5期 慕彩红等：求解约束优化问题M一精英协同进化算法 853 进化过程中出现的不可行解．目前已有的方法包括罚函数法(具体又可分为静态罚函数[1]、动态罚函数、自适 应罚函数[2_3)、使用特殊的表示及算子的方法、将约束与目标分离的方法以及各种混和方法．Coello等对各 种常见约束处理技术进行了系统的分类及分析Ⅱ]．在以上各种方法中，罚函数方法是根据某个解违背约束的 程度给其目标函数加上或减去一个值，从而将约束优化问题转换为无约束优化问题，可以很方便地应用于进 化算法中．但对于约束优化问题，给目标函数引入惩罚项后，适应度曲面会变得非常复杂．这使得算法非常容 易陷入局部极值，因而许多学者将注意力放在开发新的处理约束的方法上．笔者基于协同进化和精英策略的 思想提出一种求解约束优化问题的算法，并着力于算法模型及算子的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ，在约束处理技术上使用的是静态 罚函数方法． 协同进化算法是在协同进化论基础上提出的一类新的进化算法。其在进化算法的基础上，考虑了种群与 环境之间、种群与种群之间在进化过程中的协调．自然界以及人类社会普遍存在协同的现象．目前协同进化 算法已经成为当前进化计算的一个热点问题{6。8]．最近，Liujing等提出了一种协同进化算法即组织进化算法 (OEA)[1]，该算法使用分裂算子、吞并算子以及合作算子对种群在组织的基础上进行进化操作，在求解约束 优化问题时，使用大规模的种群，取得了很好的效果． 精英策略通常是指在进化算法中，使种群中适应度最大的个体不经过遗传操作直接进入下一代，采用精 英策略的进化算法可以较快地收敛到最优解[9]．这说明适应度较高的个体(以后称作精英个体)对于种群的 进化有着重要的推动作用．这与人类社会中精英人才对于其所在团队的发展会起到重要作用的现象十分相 似．基于这一思想并结合协同进化的思想，笔者提出了一种M～精英协同进化算法(M—EliteCoevolutionary Algorithm，缩写MECA)，主要模拟人类社会中团队的构建与协作方式，并且强调精英人才对团队建设起到 的推动作用．在之前的工作中，笔者将该算法用于求解高维无约束优化问题，取得了很好的效果¨0|，之后将 该算法简化后应用于V—BI。AST系统的信号检测，也获得了理想的结果[11]，表明M一精英协同进化思想具有 较好的理论及应用价值．笔者将M一精英协同进化算法进一步扩展用于求解复杂的约束优化问题，算法的基 本思想描述如下：将整个种群划分为精英种群(含M个精英个体)和普通种群两个子种群，并以M个精英为 核心(称为核心精英)来组建M个团队，当选中的团队成员是其他精英时，该成员与核心精英利用文中定义 的协作操作来交换信息，产生新个体；当团队成员选自普通种群时，则由核心精英对其进行引导操作产生新 个体，其中协作操作和引导操作分别由若干不同类型的交叉或变异算子的组合所定义．这些算子包括长方体 交叉算子工(CuboidCrossoverOperatorI，缩写CCOI)，离散交叉算子(DiscreteCrossoverOperator，缩 写DCO)，翻转交叉算子(FlipCrossoverOperator，缩写FCO)，长方体交叉算子1I(CuboidCrossover OperatorII，缩写CCOII)，正交交叉算子(OrthogonalCrossoverOperator，缩写OCO)以及变异算子 (MutationOperator，缩写MO)，用于个体间信息的交换，产生新个体，从而促使种群进化． MECA算法通过精英个体之间，以及精英个体与普通个体之间的交叉实现全局搜索，并通过在精英个 体附近搜索实现局部搜索，全局搜索与局部搜索的有效结合使算法具有更强的搜索能力．仿真实验和参数分 析结果表明。MECA寻优能力很强，对于13个约束优化测试函数，算法能够找到高质量的解，不易陷入局部 最优，并且计算代价较低． 1 MECA算法 约束优化问题的数学模型一般可描述为 min，(x)， z一(z1，⋯，z。)∈SnF ， (1) 其中S∈R”为搜索空间，其范围为：互≤z。≤z，，i=1，2，⋯，咒． 可行域F为 F={X∈R”Ig，(工)≤0，VJ∈{1，2，⋯，m))， (2) 其中g，(x)，歹∈{1，⋯，Tn)是约束条件． 由于笔者旨在通过算法模型及算子的设计来提高算法的搜索能力，为直观显示算法本身的优势，在处理 约束条件时，仅使用了一个简单的静态惩罚项，把约束优化转化为无约束优化，即 万方数据 854 西安电子科技大学学报(自然科学版) 第37卷 驴(x)=．厂(工)+A>：max{0，g，(x)}， (3) 篇 其中A是一个静态惩罚系数． 文中个体用实值向量工=(z，，z。，⋯，z。)来表示．只考虑最小化问题，则个体的适应度Fitness(x)定义 为一妒(x)．设种群规模为N，种群pop为{而，工。，⋯，工N}，MECA算法在每代的初始阶段将整个种群pop划 分为两个子种群：父代精英种群E和父代普通种群C，，规模分别为M和N。=N—M，其中，父代精英种群 为当前种群中M个适应度最高的个体，其余个体构成普通种群，同时生成初始的子代精英种群E和子代普 通种群C，，并且满足E，与E，相同，C，与C，相同．MECA算法充分发挥精英种群在种群进化中的推动作用， 在每代进化中以当前代M个精英作为进化操作的核心，依次利用M个精英E，；(i—l，2，⋯，M)作为团队核 心来组建M个团队，每个团队的成员数为G=10．8(N—M)／Ml(其中Iz陵示对z向上取整)，各个团队中每 个成员等概率地从精英种群和普通种群中选取，若成员来自精英种群，则与E，进行协作操作，否则利用E丸 对其进行引导操作．通过各个团队的精英与其团队成员进行协作操作或引导操作来产生新个体，并不断更新 子代精英种群E，和子代普通种群C，．当M个团队组建完毕，子代精英种群E。和子代普通种群C。也同时更 新完毕，将E和C。合并，构成下一代的种群pop． 1．1 M一精英协同进化算法种群演化示意图及算法流程 M一精英协同进化算法种群演化示意图见图1． 图1 M’精英协同进化算法种群演化示意图 M一精英协同进化算法算法流程： Stepl设置算法初始参数t=0，随机产生初始种群pop(t)； Step2将整个种群pop(t)依据适应度划分为精英种群(含M个精英)和普通种群，并生成子代精英种 群和子代普通种群； Step3依次以M个精英为核心组建M个团队，团队成员等概率地从精英种群和普通种群选取，若选中 的团队成员是其他精英，该成员与核心精英进行协作操作，若团队成员选自普通种群，则由核心精英对其进 行引导操作； Step4更新子代精英种群或子代普通种群； Step5当M个团队组建完毕，合并子代精英种群和子代普通种群作为pop(￡)，t----￡+1； Step6若满足算法终止条件，则输出pop(t)中适应度最大的可行解，否则转Step2． 1．2协作操作 在协作操作中，用工和y表示两个父代个体，用H和v表示利用某个算子最终产生的两个新个体．若产生 新个体时存在中间状态，则用w和z表示． 设当前团队的核心为精英个体Ep；：工=(z。，z。，⋯，z。)，i∈{l，2，⋯，M)，E，．所选择的当前成员个体 万方数据 第5期 慕彩红等：求解约束优化问题M一精英协同进化算法 855 为来自精英种群的精英个体E∥Y=(3，，，Y：，．．·，Y。)，歹∈{1，2。⋯，M}，且歹≠i． 协作操作是指对等地利用两个精英父代个体的信息以产生两个新个体，文中为协作操作定义了如下3 种算子：CCOI，DCO，FCO．如果U(O，1)3时，新个体的搜索空间将是一个 高维长方体，因其几何意义将式(4)称为长方体交叉算子J．由于新个体是在两个父代精英个体的附近产生， 因而更容易产生高质量的解；同时该算子将搜索空间扩展到了一个包含了两个父代精英个体的长方体空间 内，从而增加了解的多样性，将更有利于种群的进化． 由式(4)可以看出，利用CCOI算子所产生的新个体’．，，z可能会超出解空间的约束范围，需要进行出界 判别 一层： ：妻兰： lWk， 其他 ， ， fy^ ， ％Y ，^ lz。 ， 其他 ， 1．2．2DCO算子及FCO算子 在DCO算子中，新个体为 』H一‘z1’z2，⋯，zf-一l，Yf-’Yf-+1，⋯’yfz9X12-4-1，zfz+2'⋯，zH’’ (6) 【'，2(Yl，Yz’⋯'Yll—l，zfl，zfl+1’⋯，Xt2，Ytz+1，Y12+2，⋯，Y日J， 其中，1 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 测试函数(Go。～G。。)来测试MECA解决约束优化问题的能力，这些测试函数包含着对于 进化算法而言是”困难”的全局优化问题的典型特征，已被广泛地用来测试优化算法的性能，文献[2—3]给出 了这些函数，其中函数G。z的可行域由93个不相交的、半径为0．25的球构成．G。。，Go；，G，，和G。。中包含等式 约束．以下实验中将等式约束转化为不等式约柬，即 I^(z)一艿I≤0， (13) 其中，占=10一．与文献[1]一致．式(3)中惩罚系数A对每个函数的取值为 万方数据 第5期 慕彩红等：求解约束优化问题M一精英协同进化算法857 f A01=0．5，A02=100，A03=105，A04=104，A05=10，A06—5000，A07=1000，⋯、 【A08—1000，A09—500，A10=5×106，A11=10，A12=100，A】3—0．05． 在下面将比较MECA与同类型算法OEAt¨在不同种群规模下的解的质量和运行时间，并以标准遗传算法 SGA作为时间参照，并进行参数分析．以下实验的仿真环境为：CPU，AMDAthlon2．6GHz；内存为 1．93GB；操作系统为WindowsXPProfessional；开发工具为MicrosoftVisualC++2005． 2．1 MEOA与0EA及SGA的比较 OEA算法是一个较新的且性能优良的算法E,J，文献[1]显示OEA算法的解要优于RY[z]，SMES[33等经 典的约束优化算法，且在运行时间上占有优势．由于OEA算法和MECA算法均可归属于协同进化算法，且 OEA算法处理约束的方法与文中一致，因而作者严格参照文献[1]实现了OEA算法，实验数据有效，数字 位数也与原文献保持一致，以便于与MECA算法进行比较．为公平起见，其仿真环境与MECA的完全一致． 文献Eli中求解约束优化时，OEA算法的种群规模为1500，该文献中有实验表明，当种群规模较小(如N= 150)时，对于多个函数OEA算法都容易陷入局部最优解．为比较算法受种群规模的影响，作者将每个算法 都分别在两个种群规模下进行实现，即N。=1500，Nz=150．为直观地比较运行时间，还给出了标准遗传 算法SGA关于部分函数的结果． 表1 N。=1500时MECA与OEA的比较 ，'／厂mI。 方法 最优解 中值 ‘ 平均值 方差 最差解 运行时问／s G01／ 一15．000 Goz／ ——0．803619 G03／ ——1．000 G04／ 一30665．539 G05／ 5126．498 G06／ 一6961．814 G07／ 24．306 Gos／ ——0．095825 G09／ 680．630 G10／ 7049．331 G1l／ 0．750 612／ ——1．000 G13／ MECA oEA MECA oEA MECA oEA MECA 0EA MECA oEA<43> MECA OEA MECA 0EA MECA oEA MECA OEA MECA OEA MECA OEA MECA 0EA MECA ——15．000 —15．000 ——0．803608 —0．803591 ——0．967 —·1．000 —30665．539 —30665．539 5126．497 5126．497 —6961．814 —6961．814 24．307 24．308 ——0．095825 ——0．095825 680．630 680．630 7049．391 7064．727 0．750 0．750 ——I．000 ——1．000 0．053942 一15．000 —15．000 ——0．803567 —0．778192 ——0．777 ——0．498 —30665．539 —30665．539 5129．594 5128．208 —6961．814 —6961．814 24．39l 24．422 ——0．095825 ——0．095825 680．637 680．633 7337．220 7307．100 0．750 0．750 —1．000 ——1．000 0．053985 —15．000 —15．000 —0．801357 ——0．775574 一O．713 —0．45l 一30665．539 —30665．539 5132．972 5128．936 —6961．814 —6961．814 24．446 24．482 ——0．095825 ——0．095825 680．639 680．636 7347．151 7422．246 0．750 0．750 ——1．000 ——I．000 0．054049 8．702×10—16 2．512×10—16 4．384×10—3 1．75l×10—2 2．090×10一l 3．780×10一l 1．455×10—11 1．444×10—ll 10．401 2．700 1．819X10—1z 1．819×10—12 1．642×10—1 2．046×10—1 7．664×10—17 7．120×10—17 6．385×10—3 7．409X10—3 120．000 336．466 1．002X10一j 2．074×10一6 0 O 1．708×10—4 —15．000 —15．000 —0．792581 —0．723271 —0．157 0．000 —30665．539 —30665．539 5173．03l 5138．322 —6961．814 —6961．814 24．961 25．151 —0．095825 ——0．095825 680．656 680．668 7636．869 8412．988 0．750 0．750 —1．000 ——I．000 0．054764 0．968 12．596 2．260 14．400 O．998 12．290 0．897 12．087 0．998 12．024 1．185 11．825 0．994 12．485 1．046 11．537 1．024 12．326 0．950 12．237 1．001 11．503 7．922 18．452 0．954 0．0539498 OEA<40>0．053942 0．053972 0．053974 2．263×10—0．054020 12．163 所有算法的终止条件与文献[1]一致，即当函数评价次数超过240000次时算法终止．种群规模取Nt= 1500时，MECA的其他参数设置为：精英个数M=50，长方体交叉概率P。=0．8，Po=0．7，对每个测试 函数独立运行50次．MECA与OEA的对比实验结果见表1．种群规模取Nz=150时，MECA算法的精英 个数按比例缩小即M=5，其他参数保持不变．实验结果见表2．SGA的约束处理方法与文中一致，采用十 进制编码、精英策略、算术交叉，算法中交叉概率为0．8、变异概率为0．01，其他步骤均与标准遗传算法保持 万方数据 858 西安电子科技大学学报(自然科学版) 第37卷 一致．关于SGA的实验结果在表3给出．各表中，“空格”表示50次运行未找到一个可行解．方法一栏中“”表示当某方法50次运行中不是每次都能找到可行解时，给出其实际找到的可行解个数z，此时的数据统 计仅基于实际找到的可行解． 从表1可以看到，当N。一1500时，MECA算法位于第一梯队(即MECA结果不差于OEA结果)的函 数有Go。，Go。，G⋯G。。，G。，，G0s，Gn，G。z共8个．其中G0。的优势格外显著．MECA找到的最差解为 --0．792581，比OEA的中值和均值(分别为一o．778192，一O．775574)还要好，MECA的中值和均值分别 为一0．803567和一O．801357，表明50次运行中有多半的最终解都非常接近于理论最优值，此外MECA找 到的G0。的最优解也非常接近于理论最优值．文献[2]曾指出，G。：具有非常复杂的适应度曲面，一般来说是 这些测试函数中最难求解的，因而该函数的结果表明，MECA算法具有非常优良的搜索性能．此外，MECA 对于所有函数50次运行均能找到可行解，而OEA对于函数G0。和G。。，则仅找到43和40个可行解．以上结 果表明，MECA的求解质量更高，算法更稳定． 当N：=150时，MECA对于函数Go。和G，。，找到32和31个可行解，其他11个函数则均能找到50个 可行解，且解的质量变化不大，而OEA算法则有G0，，G。。，G。。，Go，，G。。，G，。等6个函数不能找到50个可 行解，表2给出了两种方法关于这6个函数的结果． 表2 N2=150时MECA与OEA的比较 ∥厂m．。 方法 最优解 中值 平均值 方差 最差解 运行时间／s Gol／ 一15．000 G05／ 5126．498 G06／ 一6961．814 G07／ 24．306 G10／ 7049．331 G13／ MECA) 0EA<43> MECA<32> 0EA<32> MECA 0EA<42> MECA OEA<49> MECA oEA)<49> MECA<31> ——15．000 —15．000 5126．886 5126．876 —6961．814 —6961．814 24．414 24．318 7052．037 7103．496 0．053943 —15．000 —15．000 5138．687 5141．783 —6961．814 —6961．814 25．425 25．182 7482．425 7469．046 0．057857 —15．000 一15．000 5154．758 5152．901 —6961．814 —6961．814 25．753 25．640 7699．943 7717．661 0．057466 O 1．756X10—15 41．709 27．699 5．207×10—12 2．487×10—12 1．117 1．818 755．370 533．567 2．80l×10—3 —15．000 —15．000 5342．710 5228．599 —6961．814 —6961．814 29．390 36．914 10859．986 9105．688 0．063393 0．399 2．476 0．380 2．349 0．371 2．397 0．374 2．467 0．305 2．372 O．355 0．0539498 ()EA<6>0．053958 0．054170 0．0541891．808×10～0．054436 2．375 以上结果表明MECA算法受种群规模的影响较小，在小种群规模下，对于多数函数仍然有效，而0EA 则必须使用大种群才能达到比较理想的结果；从运行时间上看，无论哪个种群规模，MECA的时间都远少 于0EA． 表3 SGA在不同种群规模下的运行结果 厂／凡。 方法 最优解 平均值 方差 最差解 运行时间／s G)2} 一0．803619 G05／ 5126．498 G∞l 680．630 G13 SGA(NJ) SGA(N2) SGA(N1) SGA(N2)<0> SGA(N，) SGA(N2) SGA(N1) ～O．358269 ～O．511419 709．759 690．058 ——0．234112 一O．364112 746．376 706．005 3．583×10—2 5．566×10—2 20．977 6．658 —0．192706 一O．272914 797．765 718．957 7．246 2．455 5．905 O．994 6．016 1．002 5．972 0．0539498 SGA(N2)0．969 表3给出了SGA关于4个典型函数在种群规模N。=1500和Nz=150时的运行结果，可以看到SGA 对于这些复杂的约束优化问题显得无能为力．除结果不理想外，还可以看出，SGA的运行时间也比MECA 长．这是由于在轮盘赌选择中，种群的所有个体都要计算出选择概率，此外判断选择哪些个体的次数也与种 群规模相等，这些操作都增加了SGA算法的运行时间；MECA算法的操作算子虽然看起来比较多，但各算 子处于算法的不同分支中，每次产生新个体时，只会使用其中的一到两个算子；算子类型多，增加了种群多样 万方数据 第5期 慕彩红等：求解约束优化问题M一精英协同进化算法 859 性，但并没有因此而增加算法的时间复杂度，此外在为各个精英个体选取成员以产生新个体时，采取了比较 简单的选择机制，也节省了算法的运行时间． 2．2 MECA算法的参数分析 MECA算法使用的参数有P。，Po和M，其中P。是指执行长方体交叉的概率，Po是指执行正交交叉 的概率，M是指精英子种群规模．以下选择G0：，G⋯G。。和G。。4个方差较大的函数作为代表，对于P。进行 参数分析，考虑到篇幅限制，对于参数P，，和M，仅选择G。z和G。。进行分析．G。。和G。。含有等式约束，其可行 域小，很难产生可行解，因而当算法参数选择不合适时，容易出现最终结果中没有可行解的情况，故这里定义 成功率R，，用于参数分析． 定义1 如果一次运行后最终结果中含有可行解，则此次运行称为成功的，否则称为失败的．设y次运 行中有y，次成功，则成功率为R，=Y；／V． 成功率是对算法在规定条件下搜索可行解能力的概率估计，其值为1时，表明算法在当前参数设置下每 次都能够找到可行解．当测试函数对于不同的参数设置均能达到为1的成功率时，则使用成功率将无法判断 参数对算法性能的影响，此时将使用目标函数均值MeanFV和目标函数最优值BestFV来衡量参数对算法 性能的影响，以下各实验均按照该原则进行． 2．2．1参数P。对MECA性能的影响 长方体交叉概率P。在区间(o，1)内以步长0．1采样，得到9个P。参数，在每个P。参数下进行50次实 验(其他参数及终止条件与2．1节N，一1500时相同)．对于函数Go。和G⋯计算不同P。参数下的成功率 R；，如此便得到R，与P。的关系，如图2(a)和图2(b)所示．对于函数G。：和G。。，由于在不同参数下成功率R， 均为1，故计算该参数对应的目标函数均值MeanFV和目标函数最优值BestFV，如此便得到MeanFV， BestFV与P。的关系，如图2(c)和图2(d)所示． 尸。 (a)函数G。，的成功率胄，随一的变化情况 1 0 茸0 0 0 680．7 680．7 > ‰ 680．6 680．6 Pn (b)函数G，，的成功率尺，随气的变化情况 —导—MeanFV(G") L—．_电cstFV(G0)＼，。二。 }。P。 (c)函数G。的函数值FV鲫。．的变化情况 (d)函数G。的函数值FV随L的变化情况 图2 P。对MECA的影响 从图2中可以看出，对于G。。和G∽当P。取0．6～0．9时，成功率为l，相应地，P。在该范围时，G。。的 目标函数均值也更小，因而P。的理想取值范围是0．6～0．9．而Go。受该参数的影响较小，在整个范围内都 可以取得理想的目标函数均值．另外，对于G。。和G0。，其目标函数最优值受参数P。的影响不大，始终处于最 优解附近．这表明算法具有比较稳定的寻优性能，在较大的参数范围内均可求得好的解． 2．2．2参数Po对MECA性能的影响 文中算法引入了正交交叉算子OCO以进一步改善算法的精度，这里研究正交交叉概率Po对算法性能 的影响．Po在区间[o，1]内以步长0．1采样，得到11个Po参数，在每个Po参数下进行50次实验(其他参数 及终止条件与2．1节N，=1500时相同)，与2．2．1节类似，可得到不同Po对应的G。。和G，。的目标函数均 值MeanFV以及目标函数最优值BestFV，分别如图3(a)和图3(b)所示．从图3(a)可以看到，对于G02来 说，当Po从0增加至l时，G0：的函数均值呈下降趋势，但变化幅度并不大，这表明OCO算子能够提高搜索 精度，但其提高的程度是有限的，特别注意当Po取0时，即完全不执行正交交叉时，所得的均值结果仍然与 1 0 0 0 7 7 8 8 n 地>函n n 万方数据 860 西安电子科技大学学报(自然科学版) 第37卷 -0． ．0． >‘0· ‰．0． ·0· ．0． 0．054 0．054 主0．054 0．054 (a)函数G。的函数值FV随P。的变化情况 (b)函数G，，的函数值FV两Po的变化情况 图3 P。对MECA的影响 理论最优相差不多，这表明文中算法的优越性能是由算法机制保证的，并不依赖于0C0算子．从图3(b)可 观察到类似的结果，但其曲线下降幅度很小，这表明OCO算子对可行区域小的这类函数的改善效果比较有 限．综上，Po可在[o，1]内取值，值越高，对算法的改善程度也越大，但考虑到OCO具有一定的计算复杂度， Po的取值也不宜太高． -0 ·0 乏一0 -0 ．0 l·O 0．8 O．6 《O．4 0．2 0．0 l (a)函数瓯的函数值FV随枷g变化情况 (b)函数G。，的成功率月．随．|‘，的受化情况 图4 M对MECA的影响 2．2．3参数M对MECA性能的影响 M在区间(o，1500)内进行非均匀采样，具体取值为[5，10，25，50，80，90，100，150，300，6003，得到10个 M参数，在每个M参数下进行50次实验(其他参数及终止条件与2．1节N。=1500时相同)，与2．2．1节类 似，可得到不同M对应的G。。的目标函数均值MeanFV和目标函数最优值BestFV，如图4(a)所示，以及不 同M对应的G。。的成功率R，，如图4(b)所示．从图4(a)可以看到，对于G。：来说，当M在25～150之间时，函 数均值及最优值性能较好，特别在50-～90这一区间时，效果更好，而从图4(b)也可看出，此区间内G，。的成 功率都为1，因而要兼顾各类函数，M的理想取值范围为50～90． 文中算法的主要思想是以精英个体为核心进行搜索，精英个体所在的区域就是有希望的区域，因而M 的取值即精英的个数，实际上代表的是算法在每代进行搜索时所划定的将要重点搜索的区域的数目，该数值 若太小，则算法仅在有限的几个区域进行搜索，可能陷入局部最优；而该数值若过大，则会使算法”分散精 力”，但缺乏重点，因而在评价次数受限时，会使搜索具有广度但缺乏深度，因而会影响搜索的精度．所以M 的取值应当适中，本节的仿真实验结果恰恰证实了以上分析． 3结束语 提出了一种可以很好解决约束优化问题的M一精英协同进化算法，通过两个子种群间的协作交流实现更 加有效的优化．实验中对13个约束优化问题的测试以及与OEA，SGA算法的比较结果表明，MECA算法具 有较强的寻优能力，在评价次数相同时，总体的求解质量优于所对比的方法，且运行时间最少．此外，算法受 种群规模的影响较小，无论种群规模大小，都能够达到比较理想的优化效果． 参考文献： E1]LiuJing，ZhongWeicai，JiaoLicheng．AnOrganizationalEvolutionaryAlgorithmforNumericalOptimization口]．IEEE TransonSystems，Man，andCybernetics--PartB：Cybernetics，2007，37(4)：1052-1064． [2]RunarssonTP，YaoXin．StochasticRankingforConstrainedEvolutionaryOptimization[J]．IEEETranson EvolutionaryComputation。2000，4(3)：284—294． [3]MontesEM，CoelloCAC．ASimpleMultimemberedEvolutionStrategytoSolveConstrainedOptimizationProblems [J]．IEEETransonEvolutionaryComputation，2005，9(1)：1-17． 万方数据 第5期 慕彩红等：求解约束优化问题M一精英协同进化算法 86l 1-43TessemaB。YenGG．ASelfAdaptivePenaltyFunctionBasedAlgorithmforConstrainedOptimization[c]／／IEEE CongressonEvolutionaryComputation．Vancouver：IEEE，2006：246—253． [5]CarlosC．Constraint—HandlingTechniquesUsedwithEvolutionaryAlgorithmsEC／OL3．[2009—7—15]．http：／／doi．acm org／10．1145／1274000．1274105 [6] [7] [8] [9] [10] GobCK，TanKC．ACompetitive-CooperativeCoevolutionaryParadigmforDynamicMultiobjectiveOptimizationEJ]． IEEETransonEvolutionaryComputation，2009，13(1)：103一127． HuZhihua，DingYongsheng，Shaoqing．ImmuneCo-evolutionaryAlgorithmBasedPartitionBalancingOptimizationfor TobaccoDistributionSystem口]．ExpertSystemswithApplications，2009，36(3)：5248-5255． 潘晓英．焦李成．社会协作的多智能体进化[J]．西安电子科技大学学报，2009，36(2)：274—280． PanXiaoying，JiaoLicheng．SocialCooperationBasedMulti—agentEvolutionaryAlgorithm[J]．JournalofXidian University，2009，36(2)：274—280． ChangWA，RamakrishnaRS．Elitism—BasedCompactGeneticAlgorithms[J]．IEEETransonEvolutionarv Computation，2003。7(4)：367—385． 慕彩红，焦李成，刘逸．M一精英协同进化数值优化算法D]．软件学报．2009，20(11)：2925—2938． MuCaihong，JiaoLicheng，LiuYi．M—eliteCoevolutionaryAlgorithmforNumericalOptimization[J]．Journalof Software，2009，20(11)：2925—2938． [11]慕彩红，焦李成，刘逸．M一精英进化算法及其在V—BLAST系统中的应用[J]．电子与信息学报，2009，31(10)： 2443—2448． MuCaihong，JiaoI．icheng，LiuYi．M-elitistEvolutionaryAlgorithmandItsApplicationinV-BI。ASTSystem[J]． JournalofElectronics&InformationTechnology，2009．31(10)：2443—2448． [123LeungYW，WangYuping．AnOrthogonalGeneticAlgorithmwithQuantizationforGlobalNumericalOptimization[J]． IEEETransonEvolutionaryComputation。2001，5(I)：41-53． 1-13]丛琳，沙宇恒，焦李成．采用正交免疫克隆粒子群算法求解SAT问题[J]．西安电子科技大学学报，2007，34(4)：616— 621． CongLin，ShaYuheng，JiaoLicheng．OrthogonalImmuneCloneParticleSwarmOptimizationfortheSATProblem口]． JournalofXidianUniversity，2007，34(4)：616—621． (编辑：齐淑娟) (上接第812页) [5]MesserH，SigalG，BialyL．OntheAchievableDFAccuracyofTwoKindsofActiveInterferometersI-J-I．IEEETrans onAerospaceElectron，1996(32)：1158—1164． [63NielsenRO．PerformanceofCombinationsofProjectorsandReceivers[J]．IEEEJOceanEng，2002，27(3)：753—759． [7]LehmannNH，FishierE。HaimovichA，eta1．EvaluationofTransmitDiversityinMIMO-RadarDirectionFinding[J]． IEEETransonSignalProcessing，2007，55(5)：2215—2225． [83FishlerE，HaimovichA。BlumR，eta1．MIMORadar：anIdeaWhoseTimeHasCome[C]／／RadarConference， ProceedingsoftheIEEE2004RadarConference．NewJerseyInst．ofTechnol，Newark：IEEE，2004：71—78． [9]FishierE，HaimovichA，BlumR，eta1．SpatialDiversityinRadars—modelsandDetectionPerformance[J]．IEEETrans onSignalProcessing，2006，54(3)：823-838． [10]曲毅，廖桂生，朱圣棋，等．MIMO雷达的目标运动方向及速度估计[J]．西安电子科技大学学报，2008，35(5)： 78l一784． QuYi，LiaoGuisheng，ZhuShengqi，eta1．EstimationofMovingAngleandVelocityofTargetinMIMORadarEJ]． JournalofXidianUniversity，2008，35(5)：78卜784． [11]KrimH，VibergM．TwoDecadesofArraySignalProcessingResearchEJ]．IEEESignalProcessMagazine，1996，13 (4)：67-94． [12]StoicaP，NehoraiA．MUSIC，MaximumLikelihood，andCramer-RaoBound[J]．IEEETransonA