多目标遗传算法

第六图书馆

针对非劣分层多目标遗传(NSGA)本身所存在的局部搜索能力和易早熟的问题,鉴于模拟退火算法的局部搜索能力强和在解决易早熟问题上的优势,提出了加入局部搜索的多目标遗传算法及适用于多目标优化的模拟退火局部搜索算法和跳转准则,即在NSGA的每一代个体中的1层、2层非劣解附近进行模拟退火局部搜索.该算法能够提高非劣分层多目标遗传算法的效率,弥补了遗传算法中局部搜索能力差、易早熟的缺点.最后给出的仿真结果表明了这种算法的有效性.针对非劣分层多目标遗传(NSGA)本身所存在的局部搜索能力和易早熟的问题,鉴于模拟退火算法的局部搜索能力强和在解决易早熟问题上的优势,提出了加入局部搜索的多目标遗传算法及适用于多目标优化的模拟退火局部搜索算法和跳转准则,即在NSGA的每一代个体中的1层、2层非劣解附近进行模拟退火局部搜索.该算法能够提高非劣分层多目标遗传算法的效率,弥补了遗传算法中局部搜索能力差、易早熟的缺点.最后给出的仿真结果表明了这种算法的有效性.遗传算法 多目标优化 模拟退火 小生境算子 非劣分层东北大学学报:自然科学版王小刚 梁仕贤 王福利东北大学信息科学与工程学院,辽宁沈阳1100042007第六图书馆

第六图书馆

www.6lib.com

第２８卷第７期　东北大学学报（　自然科学版）　Ｖｏ１．２８．Ｎｏ．７　２００７年７月　Ｊｏｕｒｎａｌ　ｏｆ　Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　Ｊｕ１．２　００　７　加入局部搜索的非劣分层多目标遗传算法　王小刚，梁仕贤，王福利　（东ｊＥ大学信息科学与工程学院，辽宁沈阳１１０００４）　摘　要：针对非劣分层多目标遗传（ＮＳＧＡ）本身所存在的局部搜索能力和易早熟的问题，鉴于模拟退火　算法的局部搜索能力强和在解决易早熟问题上的优势，提出了加入局部搜索的多目标遗传算法及适用于多　目标优化的模拟退火局部搜索算法和跳转准则，即在ＮＳＧＡ的每一代个体中的１层、２层非劣解附近进行模　拟退火局部搜索．该算法能够提高非劣分层多目标遗传算法的效率，弥补了遗传算法中局部搜索能力差、易早　熟的缺点．最后给出的仿真结果表明了这种算法的有效性．　关键词：遗传算法；多目标优化；模拟退火；小生境算子；非劣分层　中图分类号：ＴＰ　２７３．１　文献标识码：Ａ　文章编号：１００５．３０２６（２００７）０７．０９２１．０４　Ａ　Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　Ｎｏｎ－ｄｏｍｉｎａｔｅｄ　Ｓｏｒｔｉｎｇ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　Ｌｏｃａｌ　Ｓｅａｒｃｈｉｎｇ　Ｗ：Ａ　ＮＧ．）（　ｏ－ｇａｎｇ，Ｌ　４『、ｆＧ　Ｓｈ　—ｘｉａｎ，Ｖ　４『、『（；ｊ　一Ｚ　（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｏｒｔｈｅａｓｔｅｎｒ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ　１　１０００４，Ｃｈｉｎａ．　Ｃｏｒｒｅｓｐｏｎｄｅｎｔ：ＷＡＮＧＸｉａｏ－ｇａｎｇ，ａｓｓｏｃｉａｔｅ　ｐｒｏｆｅｓｓｏｒ，Ｅ—ｍａｉｌ：ｗｘｇ—ｎｅｕ一８００＠１２６．ｃｏｍ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｎｏｎ—ｄｏｍｉｎａｔｅｄ　ｓｏｒｔｉ第六图书馆

ｎｇ　ｉｎ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ（ＮＳＧＡ）ｈａｓ　ｓｏｍｅ　ｄｅｆｉｃｉｅｎｃｉｅｓ　ｓｕｃｈ　ａｓ　ｔｈｅ　ｐｏｏｒ　ｌｏｃａｌ　ｓｅａｒｃｈ　ａｎｄ　ｐｒｅｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ．Ａｎ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ａｄｖａｎｔａｇｅ　ｏｆ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ｉｓ　ｐｒｅｓｅｎｔｅｄ　ｔｏ　ｏｖｅｒｏｃｍｅ　ｔｈｅｓｅ　ｓｈｏｒｔｏｃｍｉｎｇｓ．　Ｔｈｅ　ｌｏｃａｌ　ｓｅａｒｃｈ　ｏｐｅｒａｔｏｒ　ｏｆ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ｆｏｒ　ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｎｄ　ｔｈｅ　ｊｕｍｐ　ｃｒｉｔｅｒｉａ　ａｒｅ　ｔａｋｅｎ　ｐａｒｔ　ｉｎｔｏ　ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ｌwww.6lib.com

ｏｃａｌ　ｓｅａｒｃｈ　ｓｈｏｕｌｄ　ｂｅ　ｃａｒｒｉｅｄ　ｏｕｔ　ｂｙ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｇｎ　ｉｎ　ｔｈｅ　ｖｉｃｉｎｉｔｙ　ｏｆ　ｔｈｅ　１ｓｔ　ａｎｄ　２ｎｄ　ｒａｎｋ　ｏｆ　ｎｏｎ—ｄｏｍｉｎａｎｔ　ｏｓｌｕｔｉｏｎｓ．Ｔｈｉｓ　ａｐｐｒｏａｃｈ　ｃａｎ　ｉｍｐｒｏｖｅ　ｏｐｅｒａｔｉｏｎａｌ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ｍａｋｅ　ｕｐ　ｆｏｒ　ｔｈｅ　ｄｅｆｉｃｉｅｎｃｉｅｓ　ｏｆ　ＮＳＧＡ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｓｉｍｕｌａｔｄｅ　ａｎｎｅａｌｉｎｇ；ｎｉｃｈｅ　ｏｐｅｒａｔｏｒ；　ｎｏｎ．ｄｏｍｉｎａｔｅｄ　ｏｓｒｔｉｎｇ　现实世界中，存在大量的多目标优化问题，即　的非劣解．基于Ｐａｒｅｔｏ的优化方法一般将多个目　多于一个目标函数的最优化问题．由于多个目标　标值直接映射到适应度函数中，通过比较函数值　函数之间可能存在的冲突，多个目标函数不可能　的占优关系来搜索问题的有效解集，可以得到一　同时达到各自的最优解，因此多目标优化就是找　系列的非劣解，是一类很有效的方法．由于遗传算　出互相协调满意解，而不是完全意义上的最优　法隐含的并行性、随机性和高度的鲁棒性，所以在　解［卜２１．　基于Ｐａｒｅｔｏ优化方法的实现上应用最为广泛，先　目前求解多目标优化的方法主要分为三类：　后出现了一系列经典的算法【３－８　Ｊ，并得到成功的　多目标聚合成单目标的方法，非Ｐａｒｅｔｏ方法和　应用．然而，这些算法仍存在一些问题，如局部搜　Ｐａｒｅｔｏ方法．其中，将多目标转化为单目标的方法　索能力差，易产生早熟现象，即陷入局部最优，从　设计简单，运行效率高，但最终却只能得到一个有　而导致算法收敛性能差，无法找到全局最优解或　效解．非Ｐａｒｅｔｏ方法可以求出多个有效解，但这　需要很长时间才能找到全局最优解．而模拟退火　些解往往集中在有效界面的端点上，丢失了太多　算法不仅具有局部搜索能力强，而且采用了以一　收稿日期：２ｏ０６—０８—０４　基金项目：国家自然科学基金资助项目（６０３７４ｏ０３）．　作者简介：王小刚（１９６ｏ一），男，辽宁沈阳人，东ｊＥ大学副教授；王福利（１９５７一），男，辽宁辽阳人，东ｊＥ大学教授，博士生导师．　http://www.6lib.com 第六图书馆

９２２　东北大学学报（自然科学版）　第２８卷　定概率接受扰动；跳到比当前解还劣的解的方法，　分层，并对处于一级和二级的非劣解进行局部搜　这就一定程度上避免了陷入局部最优的问题［　．　索．根据个体所处的层数和小生境数来确定选择　另外，在函数连续变化的情况下，在１层、２层非　概率，然后进行传统的选择、交叉、变异［。　．本文　劣解附近进行局部搜索可以提高找到全局非劣解　引进精英保持策略得到新一代个体．　的概率．因此，本文提出一种新的方法，即在遗传　算法每一代个体中，对１层、２层非劣解进行模拟　退火的局部搜索，提高非劣分层多目标遗传算法　的效率，仿真结果验证了该方法的有效性．　１多目标优化问题　多目标优化就是在由决策变量、多个目标函　数和约束条件组成的函数关系下，在决策变量的　可行域中，确定由决策变量组成的向量，使得各目　标函数值尽量同时达到最小．　多目标优化的数学模型的一般形式：　ｍｉｎＦ（ｘ）＝［ｆ１（Ｘ），ｆ２（ｘ），…，　（Ｘ）ＩＴ，　ｓ．ｔ．　ｇ　（Ｘ）≤０（Ｕ＝１，…，ｑ），　（１）　ｈ　（Ｘ）＝０（　＝１，…，户）．　式中，ｍ是目标个数；ｑ是不等式约束的个数；Ｐ　是等式约束的个数；Ｘ＝［ｚ１，ｚ２，…，ｚ　］是决策　向量；ｋ是决策向量个数．　图１算法基本流程图　Ｆｉｇ．１　Ｂａｓｉｃ　ｆｌｏｗ　ｃｈａｒｔ　ｏｆ　ａｎ　ａｌｇｏｒｉｔｌｒｎ　ｐｒｏｐｏｓｅｄ　２　Ｐａｒｅｔｏ最优概念　在多目标优化中Ｐａｒｅｔｏ最优解是一个很关　第六图书馆

３．２非劣分层方法　非劣分层就是根据Ｐａｒｅｔｏ占优的思想，对种　键的概念．　群中的个体优劣进行评判的一种方法．其步骤如　定义１　Ｐａｒｅｔｏ占优　下：　对于向量比＝（Ｕ】，…，Ｕ　）和www.6lib.com

ｌ，＝（　】，…，　Ｓｔｅｐ　１设置初始序号ｒ＝１；　＂Ｏｋ），当且仅当Ｖ　ｉ∈｛１，…，ｋ｝，　≤　，并且　ｉ∈　Ｓｔｅｐ　２求出群体中的Ｐａｒｅｔｏ最优个体，定　｛１，…，ｋ｝使得Ｕｆ＜　，则称为向量比优于向量ｌ，，　义这些个体序号是ｒ；　记作：比＜ｌ，．　Ｓｔｅｐ　３从群体中去掉Ｐａｒｅｔｏ最优个体，并　定义２　Ｐａｒｅｔｏ最优集　更改序号ｒ＝ｒ＋１．转到Ｓｔｅｐ　２，直到处理完群体　对于给定的多目标问题Ｆ（Ｘ），Ｐａｒｅｔｏ最优　中的所有个体．　集Ｘ　定义为　３．３对１层和２层非劣个体进行局部搜索　Ｘ　＝（Ｘ∈　Ｉ　Ｘ　∈　，Ｘ≠Ｘ　使得　对于函数连续变化的问题，１层和２层非劣　厂（Ｘ）＜Ｆ（Ｘ　）），　解是最有可能达到全局非劣解．所以，只对１层、２　即如果一个解向量在整个决策空间是非劣的，则　层非劣解进行局部寻优而不对整个种群的所有个　称此向量为对应多目标优化问题的Ｐａｒｅｔｏ最优　体进行局部寻优，可以大大提高搜索效率．因此，　解［４１．　可以在每一代种群中都进行以下局部搜索：　３加入模拟退火局部搜索的非劣分　Ｓｔｅｐ　１初始化退火温度Ｔｏ；　层遗传算法　Ｓｔｅｐ　２分别将１层非劣解和２层非劣解作　为初始ｘ　进行以下操作；　３．１算法的基本流程　Ｓｔｅｐ　３在解的邻域内产生新的可行解ｘ　，　算法的基本流程如图１所示，首先初始化种　产生方法：　群得到一定规模的个体，终止条件一般采用一定　的代数限制，如果超出代数则输出优化结果，否则　Ｘ　＝Ｉｌｉａｘ［ｍｉｎ（ｘ。±　，ｘ一）　］．　计算出目标函数值．再根据目标函数值进行非劣　本文提出的这个算子是针对实数编码，Ｒ是１×ｋ　http://www.6lib.com 第六图书馆

第７期　王小刚等：加入局部搜索的非劣分层多目标遗传算法　９２３　的随机矩阵；　是退火温度；走是调节系数；　是　３．５适应度计算和精英保持　种群规模；ｘ　，ｘ　ｉ　分别为决策变量的上下限．　本文采用ｆ，－　计算适应度函数，　在寻优的初级阶段，　大，搜索半径就大，在寻优　后期阶段，　小，搜索半径就小．　越大则要求搜　是个体的小生境数，走　是个体ｉ所处的层数．精英　索半径越小，走是振动调节系数，可以通过调节它　保持采用的是在每一代种群中，找出Ｐａｒｅｔｏ最优　的大小来调节搜索半径；　解集，即一层非劣解，将最优解集中的解保持到下　Ｓｔｅｐ　４计算新解的目标函数值并找出１层　代种群中．　非劣解中比新解优的个数，假设有ｍ个解比新解　４仿真分析　占优．　若ｍ＝０，说明新解不劣于最优解集中的解，　本文为了验证方法的有效性，采用文献［１０］　将新解作为新的初始解．有两种情况，一是新解比　中的一个例子：　２　１层非劣解中的某些解更优，则用新解替换最优　ｍｉｎｉｌ　１　，　解集中的劣于新解的解；二是新解和１层非劣解　ｍｉｎｆ２＝　ｌ（１一Ｘ２）＋５．　互相非劣，则将此新解追加到最优解集中．　Ｓ．ｔ．　１≤　１≤４，　若ｍ≠０，则说明新解劣于最优解集中的解．　１≤Ｘ２≤２．　以概率　＝ｅｘｐ（一　）作为新的初始解，即产生　仿真程序采用Ｍａｔｌａｂ实现，编码方式是实数　、　上正　Ｉ　个随机数，若此随机数小于ｔ，则将新解作为初　编码，种群规模２００，交叉概率０．９，变异概率　始解．　越大，则说明新解越劣，作为初始解的概　０．０２，小生境半径０．０５，初始退火温度１　０００℃，　率越小．随着　的降低，以劣于当前解的解作为　震动调节系数３　０００，温度降低比例０．８，概率调　初始解的概率越小．走，是概率调节系数．　节系数５００，ＣＰＵ采用Ｉｎｔｅｌ　Ｐｅｎｔｉｕｍ　４，主频３．０　Ｓｔｅｐ　５如果连续三次找不到非劣解，则转　ＧＨｚ．　到Ｓｔｅｐ　２，进行下一个１层、２层非劣解的局部搜　索．否则跳到Ｓｔｅｐ　３，继续做此非劣解的局部搜　第六图书馆

由图２～图４可以看到，未加人局部搜索时　索．　Ｓｔｅｐ　６所有ｌ层、２层非劣解都进行了局部　搜索，则跳出局部搜索，降低温度．www.6lib.com

　３．４小生境的计算　为了保持非劣解中解的多样性，本文还在每　个等级的个体中引人小生境数．先按式（２）计算共　享函数．　ｆ　／　．、ａ　Ｊｌ　１０，卜Ｉ　　）　否则．　（２）　图２未加入局部搜索时２０代的Ｐａｒｅｔｏ边界　Ｆｉｇ．２　Ｐａｒｅｔｏ　ｆｒｏｎｔ　ｏｆ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｔｈｅ　２０ｔｈ　ｇｅｎｅｒａｔｉｏｎ　ｗｉｔｈｏｕｔ　ｌｏｃａｌ　ｓｅａｒｃｈ　这里ｄ　是同一个等级内的任意两个个体ｉ和Ｊ之　间的标准化距离，按式（３）计算．　为小生境半径．　ｄｏ＝　（３）　然后按Ｎｉ＝　ａ（ｄ　）计算小生境数．　Ｊ＝Ｉ　Ｐａｒｅｔｏ最优解的稠密程度可以由　来调节，　当　较小时，相似抗体相应增多，Ｐａｒｅｔｏ最优解　变稠，分布会出现不均匀；而当　较大时，Ｐａｒｅｔｏ　图３未加入局部搜索时６０代的Ｐａｒｅｔｏ边界　最优解变稀．只有　大小合适时，才能得到分别　Ｆｉｇ．３　Ｐａｒｅｔｏ　ｆｒｏｎｔ　ｏｆ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｔｈｅ　６０ｔｈ　均匀的非劣解．　ｇｅｎｅｒａｔｉｏｎ　ｗｉｔｈｏｕｔ　ｌｏｃａｌ　ｓｅａｒｃｈ　http://www.6lib.com 第六图书馆

东北大学学报（自然科学版）　第２８卷　［２］　Ｓｒｉｎｉｖａｓ　Ｎ，Ｄｅｂ　Ｋ．Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｕｓｉｎｇ　ｎｏｎｄｏｍｉｎａｔｄ　ｓｅｏｒｔｉｎｇ　ｉｎ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ［Ｊ］．　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，１９９４，２（３）：２２１—２４８．　［３］　Ｓｅｈａｅｒ　Ｊ　Ｄ．Ｍｕｌｔｉｐｌｅ　ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｗｉｔｈ　ｖｅｃｍｒ　ｅｖａｌｕａｔｄｇｅｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１ｓｔ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ．Ｈｉｌｌｓｄａｌｅ：　Ｌａｗｒｅｎｃｅ　Ｅｄｂａｕｍ．１９８５：９３—１００．　［４］Ｆｏｎｓｅｃａ　Ｃ　Ｍ，Ｆｌｅｍｉｇ　Ｐ　Ｊ．Ｇｅｎｅｔｎｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｍｕｌｔｉ．　ｏｂｊｃｔｉｅｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ．　ｆｏｒｍｕｌａｔｉｏｎ，ｄｉｓｃｕｓｓｉｏｎ　ａｎｄ　ｇｅｎｅｒａｌｉｚａｔｉｏｎ［ｃ］／／Ｐｒｏｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎｌａ　Ｃｏｎｆｅｒｅｎｃｅ　Ｏｉｌ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ．Ｓａｎ　Ｍａｔｅｏ：Ｍｏｒｇａｎ　图４加入局部搜索时２０代的Ｐａｒｅｔｏ边界　Ｋａｕｆｍａｎｎ，１９９３：４１６—４２３．　Ｆｉｇ．４　Ｐａｒｅｔｏ　ｆｒｏｎｔ　ｏｆ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｔｈｅ　２０ｔｈ　［５］Ｆｏｎｓｅｃａ　Ｃ　Ｍ，Ｆｌｅｍｉｇｎ　Ｐ　Ｊ．Ａｎ　ｏｖｅｒｖｉｅｗ　ｏｆ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｇｅｎｅｒ＝ｉｏｎ　ｗｉｔｈ　ｌｏｃａｌ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉａｚｔｍｎ［Ｊ］．Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，１９９５，２８（３）：１—１６．　候２０代不仅Ｐａｒｅｔｏ最优解的个数比较少，分布不　［６］张延年，刘斌，郭鹏飞．基于混合遗传算法的建筑结构优　均匀，而且有些非劣解还不在Ｐａｒｅｔｏ边界上，加　化设计［Ｊ］．东北大学学报：自然科学版，２００３，２４（１０）：　入模拟退火局部搜索以后，２０代的Ｐａｒｅｔｏ边界明　９９Ｏ一９９３．　显改善，完全可以与不加局部搜索６０代的效果相　（Ｚｈａｎｇ　Ｙａｎ－ｎｉａｎ，Ｌｉｕ　Ｂｉｎ，Ｇｕｏ　Ｐｅｎｇ·ｆｅｉ．Ｈｙｂｒｉｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｏｐｔｉｍｕｍ　ｄｅｓｉｇｎ　ｏｆ　ｂｕｉｌｄｉｇｎ　ｓｔｒｕｃｔｕｒｅｓ［Ｊ］．　比．分别运行程序２０次，改进前２０代运算需要平　Ｊｏｕｒｎａｌ　ｏｆ　Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ：Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ，　均时间是１．２５　Ｓ，则６０代平均需要３．７５　Ｓ．而改进　２００３，２４（１０）：９９０—９９３．）　后２０代平均需要时间是１．６８　Ｓ，１．６８　Ｓ就可以得　［７］ＤｅｂＫ，ＰｒａｔａｐＡ，ＡｇｒａｗａｌＳ，ｅｔａ１．Ａｆａｓｔ　ａｎｄｄｉｔｉｓｔｍｕｌｔｉ—　到原来３．７５　Ｓ的效果，大大提高搜索效率．　ｏｂｊｅｃｔｉｖｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｍｈ：ＮＳＧＡ一Ⅱ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｌｌ　Ｅｖｏｌｕｔｏｉｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（２）：　５结　论　１８２—１９７．　［８］Ｆａｒｉｎａ　Ｍ，Ｄｅｂ　Ｋ，Ａｘｎａｔｏ　Ｐ．Ｄｙｎａｍｉｃ　ｍｕｌｔｉｏｂｊｃｅｔｉｖｅ　本文在非劣分层遗传算法的基础上，设计的　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ：ｔｅｓｔ　ｃ　髑，　ａｐｐｒｏｘｉｍａｔｉｏｎｓ，　ａｎｄ　模拟退火局部搜索算子，弥补了遗传算法中局部　第六图书馆

ａｐｐｌｉｃａｔｉｏｎｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　０７ｌ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｎｏ，２００４，８（５）：４２５—４４２．）　搜索能力差、易早熟的缺点．而且这个改进算子可　［９］　Ｚｈａｎｇ　Ｑ，Ｓｕｎ　Ｊ，Ｔｓａｎｇ　Ｅ．Ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｍｈ　ｗｉｔｈ　ｔｈｅ　以应用于所有的基于Ｐａｒｅｔｏ最优解的多目标优　化算法．　www.6lib.com

ｇｕｉｄｅｄ　ｍｕｔａｔｉｏｎ　ｆｏｒ　ｔｈｅ　ｍａｘｉｍｕｍ　ｃｌｉｑｕｅ　ｐｍｂｌｅｍ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｎｏｓ　０１ｌ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，２００５，９（２）：　１９２—２００．　参考文献：　［１０］周明，孙树栋．遗传算法原理及应用［Ｍ］．北京：国防工业　出版社，１９９９：１５０—２００．　［１］Ｃｅｌｌｉ　Ｇ，Ｇｈｉａｎｉ　Ｅ，Ｐｉｌｏ　Ｆ．Ａ　ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　（Ｚｈｏｕ　Ｍｉｇｎ，ＳｕｎＳｈｕ·ｄｏｎｇ．Ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｍｈｓ：ｔｈｅｏｒｙａｎｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ｓｉｚｉｎｇ　ａｎｄ　ｓｉｔｉｎｇ　ｏｆ　ｄｉｓｔｒｉｂｕｔｅｄ　ｇｅｎｅｒａｔｉｏｎ　ａｐｐｌｉａｃｔｉｏｎｓ［Ｍ］．Ｂｅｉｊｉｇｎ：Ｎａｔｉｏｎａｌ　Ｄｅｆｅｎｃｅ　Ｉｎｄｕｓｔｙｒ　Ｐｒｅｓｓ，　［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　０７ｌ　Ｐｏ￣ｅｒ　Ｓｙｓｔｅｍｓ，２００５，２０（２）：　１９９９：１５０—２００．）　７５０—７５７．　http://www.6lib.com 第六图书馆