基于差分进化与NSGA-Ⅱ的多目标优化算法

第４２卷　第１１期　Ｖｏ１．４２　ＮＯ．１１　计算机工程　２０１６年１１月　Ｎｏｖｅｍｂｅｒ　２０１６　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　・人工智能及识别技术・　文章编号：１０００．３４２８｛２０１６）１１－０２１９－０６　文献标志码：Ａ　中图分类号：ＴＰ１８　基于差分进化与ＮＳＧＡ．ＩＩ的多目标优化算法　陶文华，刘洪涛　（辽宁石油化工大学信息与控制工程学院，辽宁抚顺１１３００１）　摘　要：为避免多目标优化过程中子目标相互冲突，提高Ｐａｒｅｔｏ最优解的质量，提出一种基于差分进化（ＤＥ）和第　二代非支配遗传算法（ＮＳＧＡ—ｌＩ）的混合算法。采用带有自适应参数的ＤＥ算法对初始种群进行变异和交叉操作，　以提高种群的多样性。应用新种群标记策略对ＤＥ的初始种群和测试种群进行支配得到新种群，并标记其中每个　个体，使ＤＥ能够处理多目标问题。将新种群作为ＮＳＧＡ．Ｉ１的初始种群，通过ＮＳＧＡ—ＩＩ产生下一代种群，进一步提　升Ｐａｒｅｔｏ最优解的质量。使用４个基准多目标函数进行测试，结果表明，与ＮＳＧＡ－Ⅱ和ＳＡＤＥ算法相比，该算法的　收敛速度更快，Ｐａｒｅｔｏ最优解集空间分布更均匀。　关键词：多目标优化；混合算法；自适应参数；Ｐａｒｅｔｏ最优解；收敛速度；空间分布　中文引用格式：陶文华，刘洪涛．基于差分进化与ＮＳＧＡ一Ⅱ的多目标优化算法［Ｊ］．计算机工程，２０１６，４２（１１）：２１９—２２４．　英文引用格式：Ｔａｏ　Ｗｅｎｈｕａ，Ｌｉｕ　Ｈｏｎｇｔａｏ．Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　ａｎｄ　ＮＳＧＡ一１１［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１６，４２（１　１）：２１９—２２４．　Ｍｕｌｔｉ・ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　ａｎｄ　ＮＳＧＡ．ＩＩ　ＴＡＯ　Ｗｅｎｈｕａ，ＬＩＵ　Ｈｏｎｇｔａｏ　（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｃｏｎｔｒｏｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｌｉａｏｎｉｎｇ　Ｓｈｉｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ，Ｆｕｓｈｕｎ，Ｌｉａｏｎｉｎｇ　１　１　３００　１，Ｃｈｉｎａ）　【Ａｂｓｔｒａｃｔ】Ｉｎ　ｏｒｄｅｒ　ｔｏ　ａｖｏｉｄ　ｃｏｎｆｌｉｃｔ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｓｕｂ　ｏｂｊｅｃｔｉｖｅｓ　ａｎｄ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｑｕａｌｉｔｙ　ｏｆ　Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ｆｏｒ　ｔｈｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍ，ａ　Ｈｙｂｒｉｄ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ（ＤＥ）ａｎｄ　Ｎｏｎ—ｄｏｍｉｎａｔｅｄ　Ｓｏｒｔｉｎｇ　Ｇｅｎｅｔｉｃ　ＡｌｇｏｒｉｔｈｍⅡ（ＨＤＥ－ＮＳＧＡ－ＩＩ）ｉｓ　ｐｒｏｐｏｓｅｄ．Ｆｉｒｓｔ　ｏｆ　ａｌｌ，ＤＥ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｓｅｌｆ—ａｄａｐｔｉｖｅ　ｐａｒａｍｅｔｅｒｓ　ｉｓ　ｕｓｅｄ　ｆｏｒ　ｍｕｔａｔｉｏｎ　ａｎｄ　ｃｒｏｓｓｏｖｅｒ　ｏｐｅｒａｔｉｏｎｓ　ｏｆ　ｉｎｉｔｉａｌ　ｐｏｐｕｌａｔｉｏｎ，ＳＯ　ｔｈａｔ　ｐｏｐｕｌａｔｉｏｎ　ｄｉｖｅｒｓｉｔｙ　ｉｓ　ｉｍｐｒｏｖｅｄ．Ｓｅｃｏｎｄｌｙ，ａ　ｎｅｗ　ｐｏｐｕｌａｔｉｏｎ　ｍａｒｋｉｎｇ　ｓｔｒａｔｅｇｙ　ｉｓ　ａｄｏｐｔｅｄ　ｔｏ　ｄｏｍｉｎａｔｅ　ｔｈｅ　ｉｎｉｔｉａｌ　ｐｏｐｕｌａｔｉｏｎ　ａｎｄ　ｔｅｓｔｉｎｇ　ｐｏｐｕｌａｔｉｏｎ　ｏｆ　ＤＥ　ｔｏ　ｏｂｔａｉｎ　ａ　ｎｅｗ　ｐｏｐｕｌａｔｉｏｎ　ｗｈｏｓｅ　ｉｎｄｉｖｉｄｕａｌｓ　ａｒｅ　ｍａｒｋｅｄ．Ｔｈｅ　ｓｔｒａｔｅｇｙ　ｅｎａｂｌｅｓ　ＤＥ　ｔＯ　ｄｉｓｐｏｓｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｐｒｏｂｌｅｍ．Ｆｉｎａｌｌｙ，ｔｈｅ　ｎｅｗ　ｐｏｐｕｌａｔｉｏｎ，ａｓ　ｔｈｅ　ｉｎｉｔｉａｌ　ｐｏｐｕｌａｔｉｏｎ　ｏｆ　ＮＳＧＡ－１Ｉ，ｗｉｌｌ　ｇｅｎｅｒａｔｅ　ｔｈｅ　ｎｅｘｔ　ｇｅｎｅｒａｔｉｏｎ　ｐｏｐｕｌａｔｉｏｎ　ｂｙ　ＮＳＧＡ—ＩＩ．Ｔｈｅ　ｑｕａｌｉｔｙ　ｏｆ　Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎｓ　ｗｉｌｌ　ｂｅ　ｆｕｒｔｈｅｒ　ｐｒｏｍｏｔｅｄ　ｂｙ　ｔｈｉｓ　ｓｔｅｐ．Ｆｏｕｒ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｂｅｎｃｈｍａｒｋ　ｆｕｎｃｔｉｏｎｓ　ａｒｅ　ｔｅｓｔｅｄ　ｂｙ　ＨＤＥ－ＮＳＧＡ—ＩＩ，ＮＳＧＡ—ＩＩ　ａｎｄ　ＳＡＤＥ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｒａｔｅ　ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｆａｓｔｅｒ　ａｎｄ　ｔｈｅ　ｓｐａｔｉａｌ　ｄｉｓｔｒｉｂｕｔｉｏｎｓ　ｏｆ　Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ｓｅｔ　ｉｓ　ｍｏｒｅ　ｕｎｉｆｏｒｍ　ｔｈａｎ　ｔｈｅ　ｏｔｈｅｒ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ．　【Ｋｅｙ　ｗｏｒｄｓ】ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｈｙｂｒｉｄ　ａｌｇｏｒｉｔｈｍ；ｓｅｌｆ—ａｄａｐｔａｔｉｖｅ　ｐａｒａｍｅｔｅｒ；Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ；　ｃｏｎｖｅｒｇｅｎｃｅ　ｒａｔｅ；ｓｐａｔｉａｌ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１６．１　１．０３６　０概述　差分进化（Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ，ＤＥ）算法…是　种新兴进化计算技术，它由美国Ｂｅｒｋｅｌｅｙ大学的　Ｓｔｏｒｅ和Ｐｒｉｃｅ于１９９５年提出。经研究发现ＤＥ算法　能有效解决复杂非线性优化问题。ＤＥ采用实数编　一码，能够实现全局搜索，简单易行，其特有的记忆种　群最优个体的能力，使得算法有较好的鲁棒性和较　强的收敛性。近年来，ＤＥ得到了较大发展。文　献［２］提出的算法采用ＤＥ进行全局搜索，增强了整　个算法的鲁棒性。文献［１，３］通过改进ＤＥ的变异　或交叉参数增强算法的自适应性。文献［４］提出　基金项目：国家自然科学基金（６１４７３１４０，６１２０３０２１）。　作者简介：陶文华（１９７２一），女，教授，主研方向为生产过程建模与先进控制、智能算法；刘洪涛，硕士研究生。　收稿日期：２０１５一ｌ１．１６　修回日期：２０１６－０１—１１　Ｅ－ｍａｉｌ：ｔａｏｗｅｎｈｕａ２０１５＠１６３．ｃｏｒｎ　２２０　计算机一种基于多维灰度熵理论和改进混沌ＤＥ算法的飞　机机体损伤区域划分方法。文献［５］将混沌序列加　入到ＤＥ中，以增强其局部搜索能力。文献［６］将粗　糙集合理论与多目标ＤＥ结合，增强算法的局部搜　索能力。文献［１，３］采用加权法处理多目标优化问　题，但其缺点是加权系数难以确定。　第二代非支配遗传算法（Ｎｏｎ—ｄｏｍｉｎａｔｅｄ　Ｓｏｒｔｉｎｇ　Ｇｅｎｅｔｉｃ　ＡｌｇｏｒｉｔｈｍⅡ，ＮＳＧＡ－ｌＩ）　由ＮＳＧＡ改进而　来，其采用精英保留策略保证了算法的收敛性和　Ｐａｒｅｔｏ最优解的质量。目前ＮＳＧＡ一Ⅱ已得到了广泛　的应用。文献［８］采用ＮＳＧＡ—ＩＩ优化多目标纤维复　合板问题。文献［９］采用ＮＳＧＡ—ＩＩ解决多目标发电　扩建计划问题。文献［１０—１２］采用ＮＳＧＡ一１１或改进　的ＮＳＧＡ．ＩＩ有效解决了多目标无功功率补偿优化问　题。ＮＳＧＡ．Ⅱ具有解决多目标问题的能力且能保证　Ｐａｒｅｔｏ最优解的质量，所以，在保证ＤＥ解决多目标　问题的基础上，如何利用ＮＳＧＡ，１１进一步提升　Ｐａｒｅｔｏ最优解的质量是本文研究的主要内容。　目前，国内外也有一些关于ＤＥ和ＮＳＧＡ一Ⅱ的　研究，其主要内容是采用ＮＳＧＡ－Ⅱ算法中的快速非　支配排序法协助ＤＥ算法处理多目标问题。文　献［１３－１５］均采用了这种思想。但这种方法仅仅是　在ＤＥ基础上能够求解多目标问题，Ｐａｒｅｔｏ最优解的　质量并没有得到实质性的提高。　为使多目标问题整体最优，需要求得能够权衡每　个子目标的高质量Ｐａｒｅｔｏ最优解。因此，在文　献［１３－ｌ５］的基础上，本文提出一种基于ＤＥ和ＮＳＧＡ．ＩＩ　的混合算法（Ｈｙｂｒｉｄ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　ＤＥ　ａｎｄ　ＮＳＧＡ一１１，ＨＤＥ—ＮＳＧＡ－ＩＩ）。首先采用ＤＥ和快速非　支配排序法进行一次搜索寻优，然后将一次寻优结果　传递给ＮＳＧＡ—ＩＩ进行二次搜索寻优，从而提高算法的　局部搜索能力和Ｐａｒｅｔｏ最优解的质量。　１　预备知识　以目标函数最小化为例，一个具有Ｍ维目标函数、　维控制变量的多目标优化问题的数学模型如下：　ｍｉｎｆ（Ｘ）＝［　（Ｘ），，２（Ｘ），…，　（　），…，　（　）］　Ｘ：　，…，　，…，　］　（１）　・　ｉ　≤　≤　其中，，（ｘ）为目标向量；　（Ｘ）（ｉ：１，２…，Ｍ）为　第ｉ个目标函数；　是控制向量；　（　＝ｌ，２，…，　）为　第　个控制变量；　，　为　，的上下限。　多目标优化问题常用到以下定义：　定义１（Ｐａｒｅｔｏ支配关系）　Ｖ　，Ｘ２∈　，若　（Ｘ１）≤　（　２），Ｕ∈（１，２，…，　）且ｊ　１，∈（１，２，…，　），使　（　）＜ｆｖ（　：），则称　。支配　，用符号表　示为　＞　，　是非支配的，　：是支配的。如果ｘ，　工程　２０１６年１１月１５日　和　不存在支配关系，则称两者是不相关的。　定义２（Ｐａｒｅｔｏ最优解）　可行点（控制向量）　，Ｘ∈［　，　，…，Ｘ　，…，Ｘ　］，满足　ｊ　＞　，则　被称为Ｐａｒｅｔｏ最优解。　定义３（Ｐａｒｅｔｏ最优解集）　所有的Ｐａｒｅｔｏ最优　解组成的集合被称为Ｐａｒｅｔｏ最优解集。　２　ＨＤＥ－ＮＳＧＡ－Ⅱ算法　２．１　ＤＥ算法　２．１．１　ＤＥ种群初始化　ＤＥ的初始种群也是整个混合算法初始种群。　首先随机产生规模为ＮＰ的初始种群Ｘ。＝［　，　…，，ｘ？，…，　，］（ｆ－１，２，…，ⅣＰ），个体（向量）　＝Ｌ＝［　？　ｆ，，１　２　？　ｌ，，…，　　ｆ．ｐ…，，，…，　ｆ，　］（Ｊ　Ｌ　＝１，　＝　，，…，２，…，　～Ｖ）中各个变　备　ｒ　量表示可行解空间初始解。可行解空间初始变量计　算公式如下：　：　．　。　＋ｒａｎｄ×（　一　）　（２）　其中，　和　。　分别为　维变量的搜索上下界；ｒａｎｄ　为均匀分布的随机数，ｒａｎｄ∈［０，１］。　２．１．２　ＤＥ变异和交叉操作　变异和交叉操作是为了满足种群的多样性，使　Ｐａｒｅｔｏ最优解空间分布均匀化。　变异操作公式如下：　（Ｇ）＝Ｘ　（Ｇ）＋Ｆ×［　（Ｇ）一Ｘ　（Ｇ）］（３）　其中，Ｔ　（Ｇ）为变异目标个体；Ｇ为种群进化代数；　，。（Ｇ），Ｘ　（Ｇ），Ｘ　（Ｇ）为从种群中随机选取的　３个个体；Ｆ为缩放比例因子，Ｆ∈［０，１］；ｒｌ≠ｒ２≠ｒ３　≠ｉ，ｉＥ　１，２，…，ⅣＰ。　交叉操作：　Ｐｗ：一　ｆｔｉ，ｊ‘，　：　或√一ｄ　（４）　ｆ（Ｇ），其他　其中，ｒ　为变异目标个体　的第　个变量；Ｐ　为测　试个体Ｐ　的第　个变量；ｒｉ为个体，ｊ　ｉ　第　个变量对应的均匀分布的一个随机数，ｒｊ．　［０，１］；ｒｎｄ为均匀　分布的整数，ｒｎｄ∈［１，ＮＰ］；ｃｒ为交叉概率，　ｃｒ∈［０，１］。　Ｆ，ｃｒ这２个参数存在难调性，为了使参数具有　自适应性，本文采用参数自适应策略，如式（５）和　式（６）所示　。　Ｆ　（Ｇ＋１）＝Ｆｔ＋ｒＦ　（Ｇ＋１）＝　ａｎｄ￣ｘ　Ｆ“＇“　　ｎｄ２＜　‘　（（５）５）　（　ｒａｎｄ３，）　（６）　其中，Ｆ　（Ｇ）表示第Ｇ代个体ｉ的自适应缩放比例　因子；ｃｒ　（Ｇ）表示第Ｇ代个体ｉ的自适应交叉概率；　第４２卷第１１期　陶文华，刘洪涛：基于差分进化与ＮＳＧＡ．Ⅱ的多目标优化算法　２２１　由于　在区间［０．５，１）以及ｃｒ在区间（０，０．５］取值　对算法比较有利，因此Ｆ和ｃ，．的初始值均赋给０．５。　Ｆ　分别为Ｆ的上下界，本文取Ｆ　＝０．３，Ｆ　＝０．５；　，作为ＮＳＧＡ—ＩＩ的初始种群，其目的是利用ＮＳＧＡ．ＩＩ　对ＤＥ求得的解进行二次寻优，进一步提高Ｐａｒｅｔｏ最　优解的质量。因此，Ｎ　是ＤＥ和ＮＳＧＡ－Ｕ结合的关　键部分。　２．３．２二元锦标赛选择法　ｒａｎｄ　为均匀分布的随机数，ｒａｎｄ　∈［０，１］，ａ∈（１，　２，…，４）；　，ｆ：∈［０，１］为自适应调节因子。　２．１．３　ＤＥ选择操作　对测试个体Ｐ　（Ｇ）和当代个体　（Ｇ）进行比　较，选择较优者进入下一代，采用这种方式可保证下　代种群个体　（Ｇ＋１）优于当代种群个体　（Ｇ），　一从　。　中任意选取２个不同的个体。对两者等级　进行比较，等级小的个体进入交配池，若两者等级相　同，则空间拥挤距离大的个体进人交配池。直到达到　交配池数量（一般为Ⅳ脚规模的一半取整）为止。　这是一种贪婪选择方式。即：　＋１）＝　；　（７）　显然，式（７）只能解决单目标问题，为了解决多目标　问题，需要对当代个体和测试个体进行支配处理。　为此，本文应用新种群标记策略Ⅳ　。　２．２新种群标记策略　如果个体　＞Ｐ　，则把　『力Ⅱ入Ⅳ　中，如果个体　Ｐ　＞Ｘ　，则把Ｐ　加入Ⅳ。。。中，否则，把ｘ　，Ｐ　同时加　入Ⅳ　中。Ⅳ脚的规模为ＮＰ～２ＮＰ。Ｎ脚的标记策　略依靠ＮＳＧＡ一１１算法中的快速非支配排序法和空间　拥挤距离实现。　１）分级快速非支配排序法　个体ｉ的２个参数为支配个体ｆ的个体数目ｎ　和个体ｉ支配的个体集合Ｓ，。　首先，定义２个空集合Ａ和Ｂ，找到所有ｎ　＝０　的个体并将其放人集合Ａ中，Ａ中个体等级为１；然　后，Ａ中每个个体ｉ对应的Ｓ　中每个个体Ｊ的ｎ，减　１。如果支配　的ｎ　＝０，则把这样的个体．，放入集合　Ｂ，Ｂ中个体等级为２。依次类推，直至所有个体都有　自己的等级。　２）空间拥挤距离　空间拥挤距离能够预防个体在局部堆积，保持目　标向量空间分布均匀，空间拥挤距离的计算公式如下：　沙（ｉ）＝∑　（ｉ，　）　（８）　ｆｉ　—ｆｉ　（ｉ，　）＝　（９）　一　其中，　（ｉ）为个体ｉ的空间拥挤距离；ｌｆ，（ｉ，．『）为个　体ｉ在第　个目标的空间拥挤距离；　，　分别　为　（个体ｉ在第＿，个目标的函数值）的前后相邻　值；　，　为第．『个目标的极大极小值。　通过以上２个步骤，新种群中每个个体具备自　己的标记，即等级和空间拥挤距离。　２．３　ＮＳＧＡ－ＩＩ算法　２．３．１　ＮＳＧＡ一Ⅱ种群初始化　ＮＳＧＡ－Ｉ１种群初始化与ＤＥ算法种群初始化方　式一样，此处不再重复。但是本文采用新种群＾，…　２．３．３　ＮＳＧＡ－Ⅱ交叉和变异操作　ＮＳＧＡ—ＩＩ的交叉和变异操作是为了增强算法的　局部搜索能力，使得Ｐａｒｅｔｏ最优解的质量得到提升。　交叉操作公式如下：　ｒ（２　ｘ　ｎ　）　，　ｎ　≤０・５　｛【　（一×２　２　ｄ　）　而　　Ｉ＇…一　其中，Ｏｌ　为交叉参数；　为交叉分布指数。　变异操作公式如下：　｛ｒ　ｆ２×ｒａｎｄ）　．’（２—２　ｘ　ｒａｎ　．１，＂￣ｌ／ｅｍ＋ＩＦａｎｄ≤０其他．５　（１１）　一，其中，卢　为变异参数；　为变异分布指数。　２．３．４精英保留策略　将交配池中的个体作为亲代种群通过交叉　（９０％的发生概率）和变异（１０％的发生概率）产生　子代种群。　当交叉发生时，从亲代种群中随机选取２个亲代　个体　．，（１），　（２），按式（１２）和式（１３）产生子代个　体ｘ　（１），Ｘ　（２），并将子代个体加人子代种群中。　．　（１）＝０．５×［（１＋Ｏｔ　）×　．　（１）］　＋［（１一　）×　（２）］　（１２）　ｘ　　．（２）＝０．５×［（１一　）×　．　（１）］　＋［（１＋Ｏｔ　）×　．　（２）］　（１３）　当变异发生时，从亲代种群中随机选取一个亲　代个体ｘ　（３），按下式产生子代个体ｘ　（３），将其　加入子代种群中。　（３）＝　（３）＋／３　（１４）　精英保留策略潜在地把优秀个体保留下来，将　亲代种群和子代种群合并为一个大种群日，并对　中个体划分等级和计算空间拥挤距离。　２．３．５　ＮＳＧＡ一Ⅱ选择操作　选择操作需要从日中选出规模为Ⅳ｜Ｐ的种群作　为下一代的初始种群。该操作按等级选取个体，等　级小的个体优先选出，当规模超过ＮＰ，等级越大、空　间拥挤、距离越小的个体容易被淘汰，直到选出ＮＰ　个最优秀的个体为止。　综上，ＨＤＥ—ＮＳＧＡ一Ⅱ算法流程如图１所示。　２２２　计算机图１　ＨＤＥ－ＮＳＧＡ－ＩＩ算法流程　ＨＤＥ—ＮＳＧＡ－１１算法的具体步骤如下：　步骤１　ＤＥ种群初始化，确定参数ⅣＰ，Ｇ…得　到初始种群且初始化Ｇ＝１。　步骤２按式（３）和式（４）完成ＤＥ变异和交叉　操作。　步骤３　按２．２节支配当代初始种群和测试种　群，产生新种群Ⅳ　并对其中的个体标记。　步骤４　Ｎ　成为ＮＳＧＡ—ＩＩ的初始种群。　步骤５依次按照二元锦标赛选择法、式（１０）　和式（１１）、精英保留策略以及ＮＳＧＡ－Ⅱ选择操作得　到下一代初始种群。　步骤６　如果Ｇ≤Ｇ…，则Ｇ＝Ｇ＋１，返回步　骤２，直到满足条件为止。　混合算法的意义在于利用ＤＥ和ＮＳＧＡ．１Ｉ对多　目标问题的解分别进行２次寻优，此过程ＨＤＥ－　ＮＳＧＡ—ＩＩ算法的局部寻优能力不断得到增强，同时　算法的全局寻优能力也得到了提高。　３实验与结果分析　多目标优化算法性能评估标准主要包括Ｐａｒｅｔｏ　最优解集空间分布性和收敛性。Ｐａｒｅｔｏ最优解集空　间分布性用以衡量Ｐａｒｅｔｏ最优解的质量，收敛性用　以测试算法寻优能力。本文采用多目标自适应差分　进化算法　（ＳＡＤＥ）、ＮＳＧＡ—ＩＩ　以及本文算法对　４个基准多目标函数（ＭＯＰ１一ＭＯＰ４）进行测试，通　过实验验证本文算法在２个性能评估标准方面相比　其他算法具有的优势。所有实验程序均用Ｍａｔｌａｂ　编写，在Ｍａｆｌａｂ　２０１０环境下运行，ＰＣ机主频为　２．３０　ＧＨｚ，内存２　ＧＢ。　工程　２０１６年１１月１５日　ＭＯＰ１～ＭＯＰ４函数如式（１５）一式（１８）所示。　ＭＯＰ１：　｛ｆｍｒｎｉｉｎ，　，（（２１））＝：１１－一ｐｅＸｐ（（‘一　（　毫（　１矿１　　）　）　（１５）　ＩＸｉ　Ｅ［一４，４］，ｆ＝１，２，３　ｆｍｉｎ厂（１）＝Ｘ１　　ｌｍｉｎ，（２）＝ｇ（１一　）　ｊｌ　６　（１６）　ｇ（　）＝１０＋∑［　２　一１０ｃｏｓ（４，１ｒｘ　）］　ｌ　ｌ　ｚ　【０≤　１≤１；－５≤　≤５，ｉ＝２，３，…，６　ＭＯＰ３：　ｆｍｉｎ，（１）＝ｇ（ｘ）ｅ　勺　Ｉ　ｎｆｉｎ，（２）＝ｇ（ｘ）＋ｓｉｎ（４￣ｘ２　６）　Ｉ　ｍｉｎ，（３）＝ｇ（ｘ）一ｃｏｓ　Ｅ６￣ｒ（ｘ４＋　５）］　１ｊ　．　（１７）　ｇ（　）＝２＋　（　＋２）　／８　ｌ【　０≤　ｆ≤１，ｉ＝１，２，…，６　…　Ｍ０Ｐ４：　，（１）＝叶　Ｈ　［１＋　］　，血，（２）＝ｃｏｓ（詈　）ｓｉＩｌ（詈　）Ｅｌ＋ｇ（　）］　ｍ，（３）＝　［１＋　）］　８　ｇ（　）＝　毛１２（　一０．５）　０≤　≤Ｉ，ｉ：１，２，…，１２　设置种群规模ＮＰ＝２００，最大进化代数Ｇ　＝１００，ＳＡＤＥ算法中自适应调节因子７Ｉ　＝７－　＝０．９，　ＮＳＧＡ—ＩＩ中　。＝　＝２０。　表１和表２展示了３种算法时间和空间方面的　性能比较结果。　表１　３种算法的运行时间比较　Ｓ　表２　３种算法的运行时ＣＰＵ占用率ＥＥ较　％　第４２卷第１　１期　陶文华，刘洪涛：基于差分进化与ＮＳＧＡ。ＩＩ的多目标优化算法　２２３　比较表ｌ中运行时间可知，ＨＤＥ．ＮＳＧＡ—ＩＩ算法　比其他２个算法都要长，即在时问复杂度方面ＨＤＥ—　ＮＳＧＡ—ＩＩ不如其他２个算法。因为ＨＤＥ—ＮＳＧＡ—ｌＩ　是由ＤＥ和ＮＳＧＡ一１／以串联方式混合而成，其执行　一次循环相当于对ＤＥ和ＮＳＧＡ一１Ｉ各执行一次，所　以其运行时间落后其他算法属于正常现象。　比较表２中空间复杂度（运行时ＣＰＵ占用率）　可知，ＨＤＥ—ＮＳＧＡ一／／与其他２个算法相当。　图２～图４分别展示了３种算法对ＭＯＰＩ～　ＭＯＰ４多目标函数的测试结果，即函数的Ｐａｒｅｔｏ最　优解集空间分布。图５展示了ＭＯＰ１～ＭＯＰ４的收　敛性测试结果，其中纵轴Ｃ，～Ｃ　分别表示ＭＯＰＩ～　ＭＯＰ４收敛性能测试指标，采用文献［１６］方法求得；　横轴表示进化代数。　Ｅ　Ｏ　５Ｏ　ｌＯ０　进化代数　（ｂ）ＭＯＰ２　≤　。　ＨＤＥ—ＮＳＧＡ－１１算法　Ｉ　…一ＮＳＧＡ—ＩＩ算法　ＳＡＤＥ算法　一一Ｉ　Ｉ．、一一　Ｉ．　一’１　０　５０　５０　ＩＯＯ　进化代数　（ｃ）ＭＯＰ３　进化代数　（ｄ）ＭＯＰ４　图５收敛性测试结果　通过图２（ａ）、图３（ａ）、图４（ａ）之间的Ｐａｒｅｔｏ最　２　优解集空问分布比较可知，３种算法优化ＭＯＰ１，　ＭＯＰ３得到Ｐａｒｅｔｏ最优解集空间分布均匀的能力相　当。通过图２（ｂ）、图３（ｂ）、图４（ｂ）和图２（Ｃ）、　图３（Ｃ）、图４（Ｃ）以及图２（ｄ）、图３（ｄ）、图４（ｄ）之间　的Ｐａｒｅｔｏ最优解集空间分布比较明显看出，ＨＤＥ—　ＮＳＧＡ．ＩＩ算法求解ＭＯＰ２～ＭＯＰ４得到的Ｐａｒｅｔｏ最优　解集空间分布要比ＮＳＧＡ．１１和ＳＡＤＥ的均匀很多，即　喜　。　ＨＤＥ—ＮＳＧＡ一Ⅱ能够求得高质量的Ｐａｒｅｔｏ最优解。　由图５收敛性测试结果可知，ＨＤＥ—ＮＳＧＡ一１Ｉ的收　敛速度比ＮＳＧＡ一Ⅱ和ＳＡＤＥ快一些。由图５（ｂ）和　图５（Ｃ）可以看出，ＨＤＥ—ＮＳＧＡ—ＩＩ不仅收敛速度快而且　不易陷入局部最优。ＮＳＧＡ一１１和ＳＡＤＥ在全局最优方　（ｄ）ＭＯＰ４　（ｃ）ＭＯＰ３面与本文算法相比还存在差距。综上，ＨＤＥ—ＮＳＧＡ一Ⅱ　算法在空间Ｐａｒｅｔｏ最优解集空间分布和收敛性两方　图３　ＮＳＧＡ－ＩＩ测试结果　２２４　计算机面与ＮＳＧＡ—ＩＩ和ＳＡＤＥ算法相比具有优越性。　４　结束语　本文以多目标优化问题为研究对象，提出一种　基于ＤＥ和ＮＳＧＡ—ｌＩ的｝昆合算法，并将其与ＳＡＤＥ，　ＮＳＧＡ．１１对多个多目标函数进行测试。经过２项测　试标准的比较，充分证明了本文算法在空间分布性　和收敛性方面存在优势。同时，通过空间分布性比　较也间接证明了本文算法能够求得较好的Ｐａｒｅｔｏ最　优解集，其中的每个Ｐａｒｅｔｏ最优解能够权衡每个子　目标函数，使得多目标函数整体最优。但本文算法　尚存不足，即运行时间稍慢。因此，在保证求解质量　的前提下，提高运算效率是下一步研究的重点。　参考文献　Ｚｏｕ　Ｄｅｘｕａｎ，Ｌｉｕ　Ｈａｉｋｕａｎ，Ｇａｏ　Ｌｉｑｕｎ，ｅｔ　ａ１．Ａｎ　Ｉｍｐｒｏｖｅｄ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　Ｔａｓｋ　Ａｓｓｉｇｎｍｅｎｔ　Ｐｒｏｂｌｅｍ［Ｊ］．Ｅｎｇｉｎｅｅｒｉｎｇ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　Ａｒｔｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２０１１，２４（４）：６１６－６２４．　［２］　Ｍｏｒｅｎｏ　Ｌ．Ｇａｒｒｉｄｏ　Ｓ，Ｂｌａｎｃｏ　Ｄ，ｅｔ　ａ１．Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ｓｏｌｕｔｉｏｎ　ｔｏ　ｔｈｅ　ＳＬＡＭ　Ｐｒｏｂｌｅｍ［Ｊ］．Ｒｏｂｏｔｉｃｓ　ａｎｄ　Ａｕｔｏｎｏｍｏｕｓ　Ｓｙｓｔｅｍｓ，２００９，５７（４）：４４１—４５０．　［３］　Ｌａｉ　Ｍｉｎｇｙｏｎｇ，Ｃａｏ　Ｅｒｂａｏ．Ａｎ　Ｉｍｐｒｏｖｅｄ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｖｅｈｉｃｌｅ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ　ｗｉｍ　Ｓｉｍｕｌｔａｎｅｏｕｓ　Ｐｉｃｋｕｐｓ　ａｎｄ　Ｄｅｌｉｖｅｒｉｅｓ　ａｎｄ　Ｔｉｍｅ　Ｗｉｎｄｏｗｓ『Ｊ］．　Ｅｎｇｉｎｅｅｒｉｎｇ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　Ａｒｔｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２０１０，　２３（２）：１８８—１９５．　［４］　蔡舒妤，师利中．基于改进混沌差分进化算法的机体　损伤区域划分［Ｊ］．计算机工程，２０１５，４１（１１）：２３９．　２４４，２５２．　［５］　Ｌｕ　Ｙｏｕｌｉｎ，Ｚｈｏｕ　Ｊｉａｎｚｈｏｎｇ，Ｑｉｎ　Ｈｕｉ，ｅｔ　ａ１．Ｃｈａｏｔｉｃ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ｍｅｔｈｏｄｓ　ｆｏｒ　Ｄｙｎａｍｉｃ　Ｅｃｏｎｏｍｉｃ　Ｄｉｓｐａｔｃｈ　ｗｉｔｈ　Ｖａｌｖｅ—ｐｏｉｎｔ　Ｅｆｆｅｃｔｓ［Ｊ］．Ｅｎｇｉｎｅｅｒｉｎｇ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　Ａｒｔｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２０　１　１，２４（２）：　３７８—３８７．　［６］　Ｓａｎｔａｎａ—Ｑｕｉｎｔｅｒｏ　Ｌ　Ｖ，Ｈｅｒｎｄｎｄｅｚ—Ｄｆａｚ　Ａ　Ｇ，Ｍｏｌｉｎａ　Ｊ，　ｅｔ　ａ１．ＤＥＭ０ＲＳ：Ａ　Ｈｙｂｒｉｄ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　Ｕｓｉｎｇ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　ａｎｄ　Ｒｏｕｇｈ　Ｓｅｔ　工程　２０１６年１１月１５日　Ｔｈｅｏｒｙ　ｆｏｒ　Ｃｏｎｓｔｒａｉｎｅｄ　Ｐｒｏｂｌｅｍｓ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆　Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，２０１０，３７（３）：４７０－４８０．　［７］Ｄｅｂ　Ｋ，Ｐｒａｔａｐ　Ａ，Ａｇａｒｗａｌ　Ｓ，ｅｔ　ａ１．Ａ　Ｆａｓｔ　ａｎｄ　Ｅｌｉｔｉｓｔ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ：ＮＳＧＡ—ＩＩ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（２）：　１８２—１９７．　［８］Ｈｏｎｄａ　Ｓ，ｌｇａｒａｓｈｉ　Ｔ，Ｎａｒｉｔａ　Ｙ．　Ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　Ｃｕｒｖｉｌｉｎｅａｒ　Ｆｉｂｅｒ　Ｓｈａｐｅｓ　ｆｏｒ　Ｌａｍｉｎａｔｅｄ　Ｃｏｍｐｏｓｉｔｅ　Ｐｌａｔｅｓ　ｂｙ　Ｕｓｉｎｇ　ＮＳＧＡ—ＩＩ［Ｊ］．Ｃｏｍｐｏｓｉｔｅｓ　Ｐａｒｔ　Ｂ：Ｅｎｇｉｎｅｅｒｉｎｇ，２０１３，４５（１）：１０７１・１０７８．　［９］　Ｍｕｒｕｇａｎ　Ｐ，Ｋａｎｎａｎ　Ｓ，Ｂａｓｋａｒ　Ｓ．ＮＳＧＡ—Ｕ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｇｅｎｅｒａｔｉｏｎ　Ｅｘｐａｎｓｉｏｎ　Ｐｌａｎｎｉｎｇ　Ｐｒｏｂｌｅｍ［Ｊ］．Ｅｌｅｃｔｒｉｃ　Ｐｏｗｅｒ　Ｓｙｓｔｅｍｓ　Ｒｅｓｅａｒｃｈ，２００９，　７９（４）：６２２・６２８．　ｆ１０］Ｐｉｒｅｓ　Ｄ　Ｆ，Ａｎｔｕｎｅｓ　Ｃ　Ｈ，Ｍａｒｔｉｎｓ　Ａ　Ｇ．ＮＳＧＡ．１１　ｗｉｔｈ　Ｌｏｃａｌ　Ｓｅａｒｃｈ　ｆｏｒ　ａ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｒｅａｃｔｉｖｅ　Ｐｏｗｅｒ　Ｃｏｍｐｅｎｓａｔｉｏｎ　Ｐｒｏｂｌｅｍ［Ｊ］．Ｅｌｅｃｔｒｉｃａｌ　Ｐｏｗｅｒ　ａｎｄ　Ｅｎｅｒｇｙ　Ｓｙｓｔｅｍｓ，２０１２，４３（１）：３１３—３２４．　［１　１］Ｒａｍｅｓｈ　Ｓ，Ｋａｎｎａｎｖ　Ｓ，Ｂａｓｋａｒ　Ｓ．Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｍｏｄｉｆｉｅｄ　ＮＳＧＡ一ⅡＡｌｇｏｒｉｔｈｍ　ｔｏ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｒｅａｃｔｉｖｅ　Ｐｏｗｅｒ　Ｐｌａｎｎｉｎｇ［Ｊ］．Ａｐｐｌｉｅｄ　Ｓｏｆｔ　Ｃｏｍｐｕｔｉｎｇ，２０１２，１２（２）：７４１—　７５３．　［１２］Ｊｅｙａｄｅｖｉ　Ｓ，Ｂａｓｌｃａｒ　Ｓ，Ｂａｂｕｌａｌ　Ｃ　Ｋ，ｅｔ　ａ１．Ｓｏｌｖｉｎｇ　Ｍｕｌｔｉ—　ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍａｌ　Ｒｅａｃｔｉｖｅ　Ｐｏｗｅｒ　Ｄｉｓｐａｔｃｈ　Ｕｓｉｎｇ　Ｍｏｄｉｉｆｅｄ　ＮＳＧＡ一Ⅱ［Ｊ］．Ｅｌｅｃｔｒｉｃａｌ　Ｐｏｗｅｒ　ａｎｄ　Ｅｎｅｒｇｙ　Ｓｙｓｔｅｍｓ，２０１１，３３（２）：２７９—２２８．　［１３］牛大鹏，王福利，何大阔，等．多目标混沌差分进化算　法［Ｊ］．控制与决策，２００９，２４（３）：３６１－３７０．　［１４］王林，陈璨．一种基于ＤＥ算法和ＮＳＧＡ一１Ｉ的多　目标混合进化算法［Ｊ］．运筹与管理，２０１０，１９（６）：　５８—６４．　［１５］Ｘｕ　Ｂｉｎ，Ｑｉ　Ｒｏｎｇｂｉｎ，Ｚｈｏｎｇ　Ｗｅｉｍｉｎ，ｅｔ　ａ１．Ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　Ｐ－・Ｘｙｌｅｎｅ　Ｏｘｉｄａｔｉｏｎ　Ｒｅａｃｔｉｏｎ　Ｐｒｏｃｅｓｓ　Ｂａｓｅｄ　ｏｎ　Ｓｅｌｆ・　－ａｄａｐｔｉｖｅ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｄｉｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ［Ｊ］．　Ｃｈｅｍｏｍｅｔｒｉｃｓ　ａｎｄ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｌａｂｏｒａｔｏｒｙ　Ｓｙｓｔｅｍｓ，２０　１　３，　１２７（１２）：５５—６２．　［１６］Ｄｅｂ　Ｋ，Ｊａｉｎ　Ｓ．Ｒｕｎｎｉｎｇ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｍｅｔｒｉｃｓ　ｏｆｒ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ：２００２００４［Ｒ］．Ｋａｎｐｕｒ，Ｉｎｄｉａｎ：　Ｉｎｄｉｎａ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ　Ｋａｎｐｕｒ，２Ｏ０２．　编辑金胡考