一种基于DE算法和NSGA-Ⅱ的多目标混合进化算法

第１９卷　第６期　２０１０年ｌ２月　运　筹　与　管　理　ＯＰＥ１］Ａ　ＦＩＯＮＳ　ＲＥＳＥＡＲＣＨ　ＡＮＤ　ＭＡＮＡＧＥＭＥＮＴ　ＳＣＩＥＮＣＥ　Ｖｏ１．１９，Ｎｏ．６　Ｄｅｅ．２Ｏ１０　一种基于ＤＥ算法和ＮＳＧＡ一１Ｉ的多目标混合进化算法　王林，　陈璨　（　｝　科技大学管理学院，湖北武汉４３００７４）　摘　要：设计了一种新颖的暴于差分进化算法和ＮＳＧＡ．Ⅱ的混合进化算法用来解决多目标优化问题。在此算法　中，根据算法的搜索情况设汁相应的自适应变异算子．以便在突变操作中找到Ｐａｒｅｔｏ解。同时，选择操作将基于　ＮＳＧＡ—ＩＩ快速非优超排序和拥挤机制将父代与子代的双种群进行截短，确保最优解不会丢失并保证解的多样　性。三个经典测试函数的仿真结果表明，文中算法在实现多目标优化问题的两个目标（获得收敛于真实Ｐａｒｅｔｏ　前沿的解和解沿着前沿均匀扩展）方面表现出良好的综合性能。　关键词：运筹学；混合进化算法；自适应差分进化算法；ＮＳＧＡ—ＩＩ；多目标优化；仿真　中图分类号：Ｆ２２４；ＴＰ１　８　文章标识码：Ａ　文章编号：１００７—３２２ｌ（２０１０）０６—００５８—０７　Ａ　Ｈｙｂｒｉｄ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ　Ｕｓｅｄ　ｉｎ　Ｍｕｌｔｉ—Ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｐｒｏｂｌｅｍ　Ｂａｓｅｄ　ｏｎ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ａｎｄ　ＮＳＧＡ一Ⅱ　ＷＡＮＧ　Ｌｉｎ，ＣＨＥＮ　Ｃａｎ　（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｎａｇｅｍｅｎｔ，Ｈｕａｚｈｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ　４３００７４，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａ　Ｈｏｖｅ１　ｈｙｂｒｉｄ　ｄｉｉｆｅｒｅｎｔｉａ１叭ｒｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍ　ｎａｍｅｄ　ＤＥ・ＮＳ・　ＧＡ　ＩＩ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｂａｓｅｄ　Ｏ１１　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ａｎｄ　ＮＳＧＡ—ＩＩ．Ｉｎ　ＤＥ—ＮＳＧＡ　ＩＩ，ｔｈｅ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ　ｐａｒａｍｅ－　ｔｅｒ　ｉｓ　ａｄａｐｔｉｖｅ　ｆｏｒ　ｔｈｅ　ｓｅａｒｃｈｉｎｇ　ｅｆｆｅｃｔ　ｉｎ　ｅｖｅｒｙ　ｇｅｎｅｒａｔｉｏｎ　ｔｏ　ｆｉｎｄ　Ｐａｒｅｔｏ　ｓｏｌｕｔｉｏｎｓ．Ｔｈｅ　ｓｅｌｅｃｔｉｖｅ　ｏｐｅｒａｔｏｒ　ｂａｓｅｄ　ｏｎ　ｆａｓｔ　ｒａｎｋｉｎｇ　ｍｅｃｈａｎｉｓｍｓ　ａｎｄ　ｃｒｏｗｉｎｇ　ｄｉｓｔａｎｃｅ　ｓｏｒｔｉｎｇ　ｏｆ　ＮＳＧＡ一１Ｉ　ｔｒｕｎｃａｔｅｓ　ｔｈｅ　ｐｏｐｕｌａｔｉｏｎ　ｓｅｔ　ｆｏｒｍｅｄ　ｂｙ　ｔｈｅ　ｐａｒ—　ｅｎｔｓ　ａｎｄ　ｔｈｅ　ｎｅｗ　ｐｏｉｎｔｓ　ｔｏ　ｅｎｓｕｒｅ　ｔｈｅ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ｎｏｔ　ｂｅ　ｌｏｓｔ　ａｎｄ　ｔｏ　ｅｎｓｕｒｅ　ｔｈｅ　ｄｉｖｅｒｓｉｔｙ　ｏｆ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ．　ＤＥ—ＮＳＧＡ　ＩＩ　ｉｓ　ｉｍｐｌｅｍｅｎｔｅｄ　ｏｎ　ｔｈｒｅｅ　ｃｌａｓｓｉｃａｌ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ，ａｎｄ　ｔｈｅ　ｒｅｓｕｌｔｓ　ｉｌｌｕｓｔｒａｔｅ　ｔｈｅ　ｇｏｏｄ　ｃｏｍｐｒｅｈｅｎｓｉｖｅ　ｐｅｒｆｍ’ｍａｎｃｅ　ｏｆ　ＤＥ—ＮＳＧＡⅡｉｎ　ａｃｈｉｅｖｉｎｇ　ｔｗｏ　ｇｏａｌｓ：ｔｈｅｙ　ｆｉｎｄ　ｔｈｅ　ｓｏｌｕｔｉｏｎｓ　ｃｏｎｖｅｒｇｅ　ｔｏ　ｔｈｅ　ｔｒｕｅ　Ｐａｒｅｔｏ—ｆｒｏｎｔ　ａｎｄ　ｕｎｉｆｏｒｍ　ｓｐｒｅａｄ　ａｌｏｎｇ　ｔｈｅ　ｆｒｏｎｔ．　Ｋｅｙ　ｗｏｒｄｓ：ｏｐｅｒａｔｉｏｎｓ　ｒｅｓｅａｒｃｈ；ｈｙｂＩ’ｉｄ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍ；ａｄａｐｔｉｖｅ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ；　ＮＳＧＡ—ＩＩ；ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｓｉｍｕｌａｔｉｏｎ　０　引言　由几个相互冲突的目标函数构成的多目标优化问题（Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｐｒｏｂｌｅｍ，ＭＯＰ）经常　出现在现实世界中，这些目标需要同时优化，而且通常是高度复杂、非线性的。针对一个ＭＯＰ，由于子目　标互相冲突，往往没有唯一的最优解，而是一个Ｐａｒｅｔｏ最优集。传统求解ＭＯＰ的方法有加权法、约束法和　混合法等，这些求解算法按某种策略确定多种目标之间的权衡方式，将多目标问题转移为多个不同的单目　收稿日期：２００９—０９一Ｉ７　基金项目：国家自然科学基金资助项目（７０８０１０３０）；高校基本科研业务费专项资金项目（２０１０ＭＳＩ　３３）　作者简介：王林（ｊ９７４．），男，湖北枣阳人，副教授，博士，从事供物流管理和优化算法研究；陈璨（１９８７一），女，湖北武汉人，硕士生，从事　物流工程研究。　第６期　王林，等：一种基于ＤＥ算法和ＮＳＧＡ．Ⅱ的多目标混合进化算法　５９　标优化问题，并用这些单目标优化问题的最优解构成的解集近似ＭＯＰ的Ｐａｒｅｔｏ最优集…。近年来，许多　进化优化方法被用来解决ＭＯＰ，代表性的有强度值非劣进化算法　引（Ｓｔｒｅｎｇｔｈ　Ｐａｒｅｔｏ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏ—　ｒｉｔｈｍ，ＳＰＥＡ）、多目标遗传算法　。　（Ｍｕｌｔｉ—Ｏｂｊｅｃｔｉｖｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ＭＯＧＡ）、非劣存档进化策略　（Ｐａｒｅ—　ｔｏ　Ａｒｃｈｉｖｅｄ　Ｅｖｏｌｕｔｉｏｎ　Ｓｔｒａｔｅｇｙ，ＰＡＥＳ）、非支配排序遗传算法Ⅱ　（Ｎｏｎ—Ｄｏｍｉｎａｔｅｄ　Ｓｏｒｔｉｎｇ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　Ⅱ，ＮＳＧＡ一Ⅱ）和多目标差分算法（　ｄｔｉ—Ｏｂｊｅｃｔｉｖｅ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ，ＭＯＤＥＡ）　等。进化算　法采用一系列可能的解来得到可行区域，所以一个多目标问题的几个解可能运行一次就可以获得，这种强　大的搜索能力使得进化算法能很快的收敛于真实的Ｐａｒｅｔｏ前沿。　由于进化算法在研究多目标问题时表现出的突出优点，近年来关于多目标优化的进化算法受到了广　泛的关注。ＭＯＰ对进化算法的要求体现在两个方面：获得收敛于真实Ｐａｒｅｔｏ前沿的解和解沿着前沿均匀　扩展¨　。目前多目标进化算法也主要向这两个方面在发展，但都存在一些问题：ＳＰＥＡ和ＰＡＥＳ在解的均　匀性方面表现良好，但是仍然有改进空问，且计算复杂度很高；ＭＯＧＡ和ＭＯＤＥＡ效率较高，但Ｐａｒｅｔｏ最优　解分布不理想。ＮＳＧＡ—ＩＩ采用简洁明晰的非优超排序机制，使算法具有逼近Ｐａｒｅｔｏ最优前沿的能力，并采　用排挤机制保证得到的Ｐａｒｅｔｏ最优解具有良好的散布，表现出较好的综合性能。然而ＮＳＧＡ—ＩＩ在遇到高　维的问题算法的效果就明显变差，全局的寻优能力较弱，需要与其他算法混合进行改进。　差分进化（Ｄｉｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ，ＤＥ）算法是一种随机的并行直接搜索算法，它保留了基于种群的全　局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂　性　“　。同时ＤＥ特有的记忆能力使其可以动态跟踪当前的搜索情况，进而调整其搜索策略，具有较强的　全局收敛能力和鲁棒性，以其易用性、稳健性和强大的全局寻优能力在众多应用领域取得成功¨　。近年　来，一些基于ＤＥ算法的多目标优化进化算法相继被提出。Ａｂｂａｓｓ首次将ＤＥ用于解决ＭＯＰ，提出了　Ｐａｒｅｔｏ差分进化算法¨　；Ｑｉａｎ提出了自适应ＤＥ算法来解决多目标优化问题¨…，通过测试函数检验了算法　的性能；孟红云等设计了基于双群体搜索机制的求解约束ＭＯＰ的ＤＥ算法　，在求解约束ＭＯＰ方面具有　一定优势。但这些算法时问复杂度很高，这些研究同时表明仅仅简单利用ＤＥ算法求解ＭＯＰ无法保持　Ｐａｒｅｔｏ最优解的多样性，同样需要改进，因为良好的优化算法要求最优解集所对应的目标向量应尽可能均　匀的分布在Ｐａｒｅｔｏ前沿。　因此，本文设计了基于ＤＥ和ＮＳＧＡ一Ⅱ的混合智能算法（简记为ＤＥ—ＮＳＧＡｌＩ），它克服了ＤＥ算法单纯　的随机选择方法存在的不足，将更多优质的解被保留到下一代，提高了优化的效率，保证了解的多样性。　与ＮＳＧＡ．Ⅱ相比，ＤＥ—ＮＳＧＡⅡ的个体繁殖方法能够使目标向量在解空间中更有效的搜索最优解；在　ＤＥ—ＮＳＧＡ　ＩＩ算法中，进化操作中的变异和交叉操作采用ＤＥ算法，自适应变异算子将随着进化代数发生变　化，以便在突变操作中找到Ｐａｒｅｔｏ解；而选择操作则会根据ＮＳＧＡ一Ⅱ的快速非优超排序和拥挤机制，将拥　有父代和子代双种群进行截短操作，将相对最优的个体选人下一代。从而使算法加快收敛速度，并使得解　收敛于真实的Ｐａｒｅｔｏ前沿的解和解沿着前沿均匀扩展。同时，本文将利用三个标准的多目标测试函数对　ＤＥ—ＮＳＧＡ　ｌＩ算法进行性能测试，并与其他典型的进化算法进行对比。　１　多目标优化问题概述　在实际经济管理、工程应用领域中普遍存在着对多个目标的方案、计划以及设计的决策问题。在解决　这类问题时，决策者往往要综合考虑现实世界中各种因素的制约，寻求满足多个目标的最佳设计方案，这　就是所谓的ＭＯＰ。由于子目标间的冲突，最优解一般不可能是单一的解，而是一个解集，称作Ｐａｒｅｔｏ前　沿，相关的概念如下：　定义１多目标问题（ＭＯＰ）　ｍｉｎ（Ｆ（　）＝（　，（　），　（　），…，　（　））　（１）　其中，　＝［　。，　：，…，　称为决策变量，　ｎ且Ｑ＝｛川ｇ　（　）≤０，ｈ　（　）＝０｝（ｉ＝１，２，…，Ｐ，Ｊ．＝１，２，…，　ｍ）；　（　）表示ＭＯＰ的第２（　１，２，…，　）个优化目标。　运　筹　与　管　理　２０１０年第１９卷　定义２　Ｐａｒｅｔｏ占优　假设　，　是多目标优化问题的两个可行解，则称与　相比…Ｘ是Ｐａｒｅｔｏ占优的，当且仅当　Ｖ　ｉ：｛１，２，…，ｋ｝　（　）≤　（　），ｊ　＝｛１，２，…，ｋ｝　）＜　（　）记作　＜　，也称　支配　。　定义３　Ｐａｒｅｔｏ非劣最优解　‘∈ｎ是Ｐａｒｅｔｏ非劣最优解是指了　∈Ｑ使得Ｆ（　）＜（　）。　定义４　Ｐａｒｅｔｏ非劣最优解集　Ｐ　＝｛　∈Ｑ　　Ｉ∈Ｑ：Ｆ（　）＜Ｆ（　）｝　定义５　Ｐａｒｅｔｏ前沿（Ｐａｒｅｔｏ　Ｆｒｏｎｔ）　ＰＦ＝｛Ｆ（　）＝（　（　），　（　），…，　））１　∈Ｐ　｝　２基于ＤＥ和ＮＳＧＡ一Ⅱ的混合进化算法　２．１　差分进化算法流程　（１）初始化：建立优化搜索的初始点，首先需对种群初始化。ＤＥ利用Ⅳ个维数为Ｄ的实数值参数向　量作为每一代的种群，每个个体表示为：　（ｉ＝１，２，…，Ⅳ）　其中：ｉ为个体在种群中的序列；Ｇ为进化代数；Ｎ为种群规模。设参数变量的界限为　¨≤　≤　∽，则　通过式（２）生成初始种群个体。　　【＝ｒａｎｄ［０，１］・（　，Ｕ—　）＋　’　（２）　其中：ｉ：ｌ，２，…，Ｎ；　：Ｉ，２，．．，Ｄ。　（２）变异：对每个目标个体　，变异向量通过式（３）产生：　Ｇ＋ｌ＝　Ｇ＋Ｆ‘（　ｒ’Ｇ一　，　（３）　．，．．Ｇ）　．其中：下标ｒ。，ｒ　和ｒ，是随机选择的不相同的数，且与目标向量　的下标ｉ也不相同；变异算子　Ｆ　ｅ［０，２］常数，可用来控制偏差变量的放大程度。　（３）交叉：将目标向量　和变异向量Ｖｉ．Ｇ进行交叉操作，则可得到试验向量“　＋．。　ｒ　＋Ｉ　ｒａｎｄ≤ＣＲ）ｏｒ　Ｊ　ｑ　＇…　ｒａｎｄ＞ｃＲ）矾ｄ　≠ｇ　ＣＲ　Ｅ［０，１］是一个交叉算子，ｒａｎｄ是产生［０，１］之间的随机数，ｇ　｛１，２，…，Ｄ｝是一个随即产生的参　数，用来确保试验向量“　＋。至少能从变异向量　获得一个参数。　（４）选择：在选择操作中，通过比较试验向量的适应度值和目标向量的适应度值来决定谁进入下一　代。在选择过程中，试验向量只与相应的目标个体进行比较，而不是种群所有的个体　。　Ｉ厂（ｕ　＋　）≥厂（　）　…　Ｘｉ，Ｇ＋ｌ　。　２．２本文设计的ＤＥ－ＮＳＧＡⅡ算法　标准ＤＥ在单目标优化中选择操作简单，不能在多目标优化问题中直接套用，它存在着实验解和父代　不可比较的情况。在标准ＤＥ中，如果实验解不优于父代，将会被弃之并导致很多已经发现的最优解丢　失。同时，参数，的敏感度目前也没有被研究清楚，一般只是随机的选择它的值，，值对新产生点的影响　被忽视了。为克服上述缺点，本文提出了一个自适应参数Ｆ和一个新的选择方法，根据ＮＳＧＡ．Ⅱ的对种　群的选择过程，当一个实验点产生时我们不比较实验解和它的父代，而是将它保留在实验解集里。当种群　中所有成员都产生实验解后，我们得到一个新的种群，它包含了实验解集和父代解集种群规模为２Ｎ；然后　截短这个种群的规模带人算法的下一步计算。截取的步骤由两部分组成，一个是对个体进行非支配排序，　使种群中的每一个个体均分配相应的前沿，另一个是通过拥挤距离机制评估在同一个前沿里的个体，设　Ｆ　表示第ｉ个前沿的个体数量，如果前ｋ个前沿总的数量＜Ｎ，而前ｋ＋１个前沿的总数量＞Ｎ，则对于前后　个前沿的所有个个体均进入下一代种群，对于第ｋ＋１前沿的个体，从中选择拥挤距离最大的Ⅳ减去前ｋ　第６期　５－林，等：一种基于ＤＥ算法和ＮＳＧＡ一Ⅱ的多目标混合进化算法　６１　个前沿个体总数的个体进人下一代种群，从而将规模为２Ｎ的种群截短为规模为Ⅳ的种群。ＤＥ—ＮＳＧＡ　１Ｉ　算法采用了与ＮＳＧＡ—ｌＩ类似的但目前更有效的拥挤距离机制…，如图１所示，我们将只包含种群中点　的最大的立方体的对角线定义为种群密度的估计值。　图Ｊ　ＤＥ—ＮＳＧＡ　１Ｉ算法中的拥挤距离机制　在标准ＤＥ中，参数Ｆ的值是固定的，其敏感度也没有研究清楚，只是随机的选择他们的值，主要在０．　５到０．９之间。在ＤＥ中，新的点的产生主要靠变异操作。在变异时，参数Ｆ起到了很重要的作用，Ｆ影响　收敛的速度和解的多样性，Ｆ决定了搜索幅度。通常，优化算法在早期进行全局搜索得到可行域，找到全　局最优解，在后期进行局部搜索加速收敛。基于上述策略，将定义参数Ｆ如下　＾Ｍ　Ｆ：Ｆ　＋（Ｆ　一Ｆ　）・ｅ　丽而　（６）　其中Ｆ　表示变异参数的最小值；Ｆ…表示变异参数的最大值；ＧｅｎＭ表示最大的进化代数；Ｇ则表示当前　进化的代数。在算法开始时自适应变异算子为，…，具有较大值，在初期保持个体多样性，避免早熟；随着　算法进展变异算子逐步降低，到后期变异率接近Ｆ　，保留优良信息，避免最优解遭到破坏，增加搜索到全　局最优解的概率，ＤＥ　ＮＳＧＡ　ＩＩ的流程图如图２所示。　图２　ＤＥ—ＮＳＧＡ　ＩＩ流程图　３性能测试实验与结果　３．１　测试函数　为了检验改进后的ＤＥ—ＮＳＧＡ　１Ｉ算法的性能，选择Ｄｅｂ设计的多目标测试问题ＺＤＴ系列　进行寻　优，它们在多目标优化研究被广泛采用。　测试函数一（凸Ｐａｒｅｔｏ前沿）：ＺＤ３、ｌ　（　）＝　（　）＝ｇ（　）（１一￣／　．／ｇ（　））　）＝１＋　ｎ　ｎ—Ｉ　ｎ＝３０，　Ｅ［０，１］　测试函数二（非凸Ｐａｒｅｔｏ前沿）：ＺＤＴ２　６２　运　筹　与　管　理　（　）＝　。　２０１０年第１９卷　ｆ２（　）＝ｇ（　）（１一（　／ｇ（　））　）　）＝ｌ＋　ｎ＝３０，　，凡一　１　∈［０，１］　测试函数三（间断Ｐａｒｅｔｏ前沿）：ＺＤＴ３　（　）＝　（　）　＋　一厕一　ｓｉｎ（１０　））　芝　ｎ＝１０，　，∈［０，１］　以上三组测试函数的Ｐａｒｅｔｏ解集分别属于凸的、凹的以及不连续的，Ｐａｒｅｔｏ最优边界均为对应的ｇ（　）　＝１，因此可以将多目标进化算法的运行结果与ＭＯＰ最优解进行直接比较和分析。　３．２　性能指标　为了验证本文设计算法的优劣，我们将比较ＤＥ—ＮＳＧＡⅡ和某些优化算法的性能，将用到在多目标优　化算法的评价中广泛应用的二个性能指标。　（１）收敛度指标ｒ，定义如下　ｒ＝Ｙ　ｄ．’　／ｎ　其中ｎ为由算法得到的非支配向量的数量；ｄ，为获得的非支配前沿Ｑ和真实Ｐａｒｅｔｏ前沿中最近的成员间　的欧几里德距离（在目标空间衡量）。　（２）多样性指标△，△衡量沿着非支配解扩展的距离，定义如下　凸　＾　—＋ｄ　＋∑　’一　ｉ＝ｌ（ｄ　一　）　　．　其中，ｄ。为获得的非支配前沿Ｑ和真实Ｐａｒｅｔｏ前沿中最近的成员间的欧几里德距离（在目标空间衡量）；　参数ｄ，和ｄ．为真实Ｐａｒｅｔｏ前沿Ｐ的极值解和获得的前沿Ｑ的边界解之间的距离。　３．３测试结果和对比分析　在参数设置中，对于每个测试问题，为了使算法比较进行一致性比较，种群大小设为１００，算法迭代　２００次，ＤＥ—ＮＳＧＡ　ＩＩ的变异算子Ｆ　Ｆ　分别为０．２和０．６，交叉算子ＣＲ为０．２。我们将ＤＥ－ＮＳＧＡ　ｌＩ与　ＮＳＧＡ—ＩＩ在测试问题ＺＤＴ１．ＺＤＴ３中的性能进行了对比，如图３～５所示。可看出在实数编码的情况下，在　相同的种群大小和最大进化代数的情况下，ＤＥ—ＮＳＧＡⅡ比ＮＳＧＡ．Ⅱ的结果更优，最优解的质量和数量都　多于后者，说明混合的算法较有效地改善单个算法的不足，提高了算法的性能。　图３测试函数ＺＤＴＩ优化结果性能比较（左：ＤＥ—ＮＳＧＡｌＩ；右：ＮＳＧＡ—ＩＩ）　第６期　王林，等：一种基于ＤＥ算法和ＮＳＧＡ．１Ｉ的多目标混合进化算法　６３　ｒ　－　　＿－　＿　＼　　Ｌ　Ｉ　｝　Ｊ１　图４测试函数ＺＤＴ２优化结果性能比较（左：ＤＥ—ＮＳＧＡⅡ；右：ＮＳＧＡ—Ｕ）　图５测试函数ＺＤＴ３优化结果性能比较（左：ＤＥ—ＮＳＧＡⅡ；右：ＮＳＧＡ—ＩＩ）　表１　测试函数ＺＤＴ１的结果统计　算法　收敛度指标　排序　多样性指标　排序　ＮＳＧＡ一Ⅱ　０．０３３４８±０．００４７５　４　０．３９０３ｌ±０．００ｌ８７　３　ＳＰＥＡ　０　００ｌ８０±０．０００００　Ｉ　０．７８４５３±０．００４４４　４　ＰＡＥＳ　０．０８２０８±０．００８６８　５　１．２２９７９±０．０００７３　５　ＰＤＥＡ　Ｎ／Ａ　０．２９８５７±０．０００７４　２　Ｍ０ＤＥＡ　０．００５８０±０．００４００　２　Ｎ／Ａ　ＤＥ．ＮＳＣＡⅡ　０．０３０５３±０．０００３０　３　０．２０８５２±０．０００２０　ｌ　表２测试函数测ＺＤＴ２的结果统计　算法　收敛度指标　排序　多样性指标　排序　ＮＳＧＡ．Ⅱ　０．０７２３９　４－０．０３１６９　４　０．４３０７７　４－０．００４７２　３　ＳＰＥＡ　０．００ｌ３４±０．０００００　Ｉ　０．７５５ｌ８±Ｏ．ＯＯ４５２　４　ＰＡＥＳ　Ｏ．１２６２８±０．０３６８８　５　１．１６５９４　４－０．００７６８　５　ＰＤＥＡ　Ｎ／Ａ　０．３ｌ７９６±０．００１３９　２　ＭＯＤＥＡ　０．００５５０±０．（３００００　２　Ｎ／Ａ　ＤＥ．ＮＳＧＡⅡ　０　０３７６２±０．０００３０　３　０．２０４５９±０．００３５０　ｌ　表３测试函数ＺＤＴ３的结果统计　算法　收敛度指标　排序　多样性指标　排序　ＮＳＧＡ－Ⅱ　０．１ｌ４５０－．－ｉ０．００４９４　５　０．７３８５４±０．０１９７１　３　ＳＰＥＡ　０．０４７５２±０．００００５　４　０．６７２９４±０．００３５９　４　ＰＡＥＳ　０．０２３８７±０．００００ｌ　３　０．７８９９２±０．ＯＯｌ６５　５　ＰＤＥＡ　Ｎ／Ａ　０．６２３８１±０．０００２２　２　ＭＯＤＥＡ　０．Ｏ２ｌ５６±０．０００００　２　Ｎ／Ａ　ＤＥ．ＮＳＣＡ　１１　０．００ｌｌ０　４－０．０００ｌ０　ｌ　０．４０３４３　４－０．００５００　ｌ　运　筹　与　管　理　２０１０年第１９卷　同时我们将ＤＥ—ＮＳＧＡⅡ与其他五种算法（ＮＳＧＡ一１１，ＳＰＥＡ，ＰＡＥＳ，ＰＤＥＡ，ＭＯＤＥＡ）　在这３个测试问　题上的收敛度指标ｒ和多样性指标　进行了对比，结果如表１一表３所示，这些值是运行了２０次得到的平　均值。从表ｌ一表３中，＿ｊ『看到ＤＥ—ＮＳＧＡ　ＩＩ在所有测试问题中收敛和保持多样性方面都比较好，在ＺＤＴ３测　试中ＤＥ—ＮＳＧＡ　ＩＩ优于相比较的所有算法；ＺＤＴＩ和ＺＤＴ２测试中，Ｉ）Ｅ—ＮＳＧＡ　１１保持多样性的性能是最好　的，ＳＰＥＡ收敛的最好，ＤＥ—ＮＳＧＡ　１Ｉ优于ＮＳＧＡ—ｌＩ和ＰＡＥＳ。在三组测试函数中，ＤＥ—ＮＳＧＡ　１在实现了多目　标优化的两个目标（收敛于真实Ｐａｌｅｔｏ前沿和解沿着前沿均匀分布），这说明ＤＥ算法与ＮＳＧＡ—ｌＩ相结合　的混合智能算法能有效解决多目标优化难题，在此方面有很广的应用空间。　４　结论　本文属于新颖的智能优化算法与多日标优化问题的交叉研究，我们设计了一种简单可靠的、基于ＤＥ　算法和ＮＳＧＡ—ｉｉ的自适应混合差分进化算法用来解决ＭＯＰ问题。本文设计的ＤＥ—ＮＳＧＡ　１算法和其他多　目标优化进化算法不同之处在于综合了两种算法的优点，同时设汁了相应的自适应变异算子和选择操作　来改善混合算法的性能，标准的测酞函数测试以及与其它算法的对比分析结果表明ＤＥ—ＮＳＧＡ　１Ｉ算法在实　现多目标优化的两个目标（收敛于真实Ｐａ　ｒｅｔｏ前沿和解沿着前沿均匀分布）表现出良好的综合性能，并且　算法复杂度适中．在解决ＭＯＰ方面有一一定的优势。末来，我们将利用ＤＥ—ＮＳＧＡ　１算法来解决实际企业管　理中的多目标优化问题，扩大其应用范围并进行针对性的改进。　参考文献：　［１］　陈小庆，侯中喜．郭良民．罗文彩．基于ＮＳＧＡ—ＩＩ的改进多目标遗传算法［Ｊ］．计算机应用，２００６，２６（１Ｏ）：２４５３—２４５６．　［２］　Ｋｕｍａｒ　Ｒ，Ｉｚｕｉ　Ｋ，Ｙｏｓｈｉｎｍｒａ　Ｍ，Ｎｉｓｈｉｗａｋｉ　Ｓ．Ｍｎｈｉ—ｏｂｊｅｃｔｉｖｅ　ｈｉｅｒａｒｃｈｉｃａｌ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｍｕｈｉｌｅｖｅｌ　ｒｅｄｕｎｄａｎｃｙ　ａｌｌｏｅａ—　ｔｉｏｎ　ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．Ｒｅｌｉａｂｉｌｉｔｙ　Ｅｎｇｉｎｅｅｒｉｎｇ＆Ｓｙｓｔｅｍ　Ｓａｆｅｔｙ，２００９，９４（４）：８９１—９０４．　［３］　李中凯，谭建荣．冯毅雄，裘乐淼．基于强度Ｐａｒｅｔｏ进化的注塑机注射性能多目标优化［Ｊ］．计算机集成制造系统，２００７，　１３（１１）：２１６２—２ｌ６８．　［４］　Ｃｈａｎｇ　Ｐ　Ｃ，Ｈｓｉｅｂ　Ｊ　Ｃ．Ｗａｎｇ　Ｃ　Ｙ．Ａｄａｐｔｉｘ　ｅ　ｍｕｈｉ—ｏｂｊｅｃｔｉｖｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｓｃｈｅｄｕｌｉｎｇ　ｏｆ　ｄｒｉｌｌｉｎｇ　ｏｐｅｒａｔｉｏｎ　ｉｎ　ｐｒｉｎｔｅｄ　ｃｉｒｃｕｉｔ　ｂｏａｒｄ　ｉｎｄｕｓｔｒ）　［Ｊ］．Ａｐｐｌｉｅｄ　Ｓｏｆｔ　ｃ１）ｒｅｐｕｔｉｎｇ．２００７，７（３）：８００～８０６．　［５］蔡龙飞．基于改进遗传算法的多目标问题的研充［Ｊ］．计算机工程与科学，２００８，３０（３）：７５—７７．　［６］Ｋｎｏｗｌｅｓ　Ｊ，Ｃｏｒｎｅ　Ｄ．Ｔｈｅ　ｐａｒｅｔ￣）ａｒｃｈ／，，ｅｄ　ｅｖｏｌｕｔｉｏｎ　ｓｔｒａｔｅｇｙ：ａ　ｎｅｗ　ｂａｓｅｌｉｎｅ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ［Ａ］．　Ｄａｎｖｅｒｓ，Ｍ　Ａ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ［Ｃ］．ＮＹ：ＩＥＥＥ　Ｐｒｅｓｓ，１９９９．９８—１０５．　ｆ　７］Ｓｈｉ　Ｃ，Ｙａｎ　ｚ　Ｙ，Ｌｆｉ　Ｋ　Ｖ．Ｓｈｉ　ｚ　Ｚ，Ｗａｎｇ　Ｂ．Ａ　ｄｏｍｉｎａｎｃｅ　ｔｒｅｅ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，２００９，１７９（２０）：３５４０—３５６０．　［８］童晶，赵明旺．高效求解Ｐａｒｅｔｏ最优前沿的多目标进化算法［Ｊ］．计算机仿真，２００９，２６（６）：２１６—２１９．　［９］Ｘａｅ　Ｆ，Ｓａｎｄｅｒｓｏｎ　Ａ　Ｃ，Ｇｒａｖｅｓ　Ｒ　Ｊ．Ｐａｒｅｔｏ—ｂａｓｅｄ　ｍｕｈｉ—ｏｂｊｅｃｔｉｖｅ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ［Ａ］．Ｓａｒｋｅｒ　Ｒ，Ｒｅｙｎｏｌｄｓ　Ｒ，Ａｂｂａｓｓ　Ｈ　Ａ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｔ　ｔｈｅ　２００３　Ｃｏｎｇｒｅｓｓ¨ｎ　ｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ［Ｃ］．ＮＹ：ＩＥＥＥ　Ｐｒｅｓｓ，２００３．８６２—８６９．　［Ｊ０］Ｑｉａｎ　Ｗ　Ｙ．Ｌｉ　Ａ　Ｊ．Ａｄａｐｔｉｖｅ　ｄｉｆｅｒｅｏｔｉａｌ　ｏｌｕｌｉｎｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍｕｈｉｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ［Ｊ］．Ａｐｐｌｉｅｄ　Ｍａｔｈｅｍａｔ—　ｉｃｓ＆ＧｕｍｐｌＨａｌｉｏｎ，２００３，２０１（１—２）：４３ｌ一４４０．　［Ｊ１］Ｓｌｏｒｎ　Ｒ，Ｐｒｉｃｅ　Ｋ．Ｄｉｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉ￣｝ｆｌ：ａ　ｓｉｍｐｌｅ　ａｎｄ　ｅｆｆｉｃｉｅＩ１ｔ　ｈｅＬｔｒｉｓｔｌｅ　ｆｏ　ｇｌｏｂａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｖｅｒ　ｃｏｎｔｉｎｕｏｕｓ　ｓｐａｃｅｓ［Ｊ］．　Ｊｏｕｒｎａｌ　ｏｆ　Ｇｌｏｂａｌ　Ｏｐｔｉｍｉｚａｔｉｏｕ．１９９７．１１（４）：３４１—３５９．　【ｌ　２］Ｓａｌｍａｎ　Ａ，Ｅｎｇｅｌｂｒｅｃｈｔ　Ａ．Ｐ，Ｏｍｒａｎ　Ｍ　Ｇ　Ｈ．Ｅｍｐｉｒｉｃａｌ　ａｎａｌｙｓｉｓ　ｏｆ　ｓｅｌｆ—ａｄａｐｔｉｖｅ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ【Ｊ３．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ　２００７．１　８３（２）：７８５—８０４．　［１３］Ａｂｂａｓｓ　Ｈ　Ａ．Ｔｈｅ　ｓｅｌｌ＂一ａｄａｐｔｉｖｅ　Ｐａｒｅｔｏ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ［Ａ］．Ｙａｏ　Ｘ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎ—　ａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ［Ｃ］．ＮＹ：ＩＥＥＥ　Ｐｒｅｓｓ，２００２．８３ｌ一８３６．　［１４］　孟红云，张小华．刘三阳．用于约束多目标优化问题的双群体差分进化算法［Ｊ］．计算机学报，２００８，３１（２）：２２８—２３５．　［１５］　Ｄｅｂ　Ｋ．Ｍｕｌｔｉ’ｏｂｊｅｃｔｉｖｅ　ｇｅｎｅｔｉｃ　ｏｐｔｉｍｉｚａｔｉｏｎ：ｐｒｏｂｌｅｍ　ｄｉｆｆｉｃｕｌｔｉｅｓ　ａｎｄ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　ｔｅｓｔ　ｐｒｏｂｌｅｍｓ［Ｊ］．Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕ—　ｒａｔｉｏｎ，１９９９．７（３）：２０５—２３０．