文摘

多目标优化问题(拖把)是一个重要的和具有挑战性的主题领域的工业设计和科学研究。多目标进化算法(MOEA)已被证明是最有效的算法解决多目标优化。在本文中,我们提出一个entropy-based多目标进化算法的增强精英机制(E-MOEA),提高了收敛性和多样性的有效解集在拖把。在该算法中,一个增强精英机制应用于指导的方向进化的人口。具体地说,它加快了人口接近真正的帕累托前的早期演化过程。策略基于熵是用来保持种群的多样性,当人口接近帕累托。上执行该算法广泛使用的测试问题,和模拟结果表明,该算法具有更好的或比较表演相比,收敛性和多样性的解决方案有两个先进的进化算法:NSGA-II, SPEA2 MOSADE。

1。介绍

优化问题存在于各种各样的工程和科学领域。当有多个目标的优化问题,它被称为多目标优化问题(拖)。由于这些目标通常是在彼此冲突,解决一个拖把的目标是找到一个妥协的解决方案对所有目标而不是最好的一个简略的优化问题。拖把的解决方案,也称为帕累托最优的解决方案,是最优的存在没有其他可行的解决方案,而不造成的增加会降低一些标准至少还有另一个标准。进化算法(EA)是一种基于种群的进化优化算法。因为它可以搜索多个并行的解决方案,它赢得了研究人员的极大关注。近年来,许多优秀的东亚峰会(1- - - - - -4提出了有效地解决拖把和MOEA被公认为最好的方法之一解决拖把。

一般来说,有两个绩效指标在评估MOEA获得的帕累托最优的解决方案。一个是收敛测量,评估帕累托解之间的邻近度和真正的最优。另一个是多样性的测量,评估解决方案在目标空间的分布。为了实现良好的性能,许多优秀的策略和方法已经提出了MOEA [1,2,5- - - - - -9]。收敛,精英机制已被证明是非常有用的加速进化的人口(6]。精英机制的基本思想是信息良好的解决方案,这发生在进化的进程,用于确保解集收敛于最优前尽快。它的惯例是一定数量的最佳解决方案是选择从人口作为父母产生良好的后代(1]。然而,在早期阶段算法的应用这一策略,因为有很多主导解决方案中存在人口选为父母,人口不能收敛速度快。为了保持nondominated的多样性的解决方案,应用两种主要方法。第一个是使用网格保持多样性[7]。它吸引了网格在目标空间和控制解决方案在一个网格的数量。尽管这种方式可以快速找到更好的解决方案,有时不能准确反映全球分布的解决方案,因为网格位置是固定的。第二个是基于密度的方式(2,8,9]。每个解决方案获得的值密度和一位杰出的密度分布计算可以帮助养成良好的解决方案。

自1948年以来,香农(10]介绍了信息熵理论来衡量随机过程的信息内容,导致信息理论领域的建立。然后,许多不同的应用程序给出了熵在各领域的合作。在解决多目标优化问题,Farhang-Mehr和Azarm [11谷纳温)和et al。12)应用熵维持解集在多目标问题的多样性和多层次多目标问题。王等人提出了MOSADE算法(13],它结合了自适应差分进化和拥挤entropy-based多样性度量获取nondominated解集。在该算法中,每一个解决方案可以计算其拥挤程度通过改善信息熵公式根据解决方案的分布。本质上,这个方法是类似于NSGA-II拥挤距离。因此,对于一些三个客观问题,该算法不能获得非常理想的解决方案。

在本文中,我们提出一种新的MOEA更有效地解决拖把,一个增强的精英主义使得nondominated解决方案更好的指导作用和entropy-based策略应用于保持种群的多样性。我们称之为一个entropy-based多目标进化算法增强的精英主义,即E-MOEA短暂。具体来说,我们使用增强的精英主义中只有nondominated解决方案联盟人口被选为父母确保解集更快地收敛于最优面前。与算法,nondominated解决方案联盟人口的数量会逐渐增加。为了保持精英人群的大小(精英人群的最大数量在我们的算法集N)和维护解决方案的多样性,基于熵的应用策略。在这个策略,一个区域是由以解决方案为中心和最拥挤的地区最不均匀分布的解决方案被发现通过应用熵;然后,在这些地区,最拥挤的解决方案是一个接一个地删除。与MOSADE相比,增强的精英主义可以使帕累托最优解集方法方面更容易在我们的算法,和帕累托解集的表面更均匀通过地区和熵的组合。实验结果在3-objective 2-objective问题和问题表明,新算法具有更好的性能在收敛性和多样性,与NSGA-II相比,SPEA2 MOSADE。

2。多目标优化问题

在本文中,我们考虑下面的连续多目标优化问题(连续拖把): 在哪里空间和决策是决策变量向量。由真正的价值目标函数,是客观的空间。

让,两个向量,据说主导,用,如果对所有,。

一个点如果没有被称为帕累托最优这样。所有的帕累托最优向量的集合被称为帕累托集,用PS。所有帕累托目标向量的集合,,被称为帕累托(2,9]。

3所示。的Entropy-Based多目标进化算法的增强精英机制

在本节中,我们首先提出一个增强的精英机制;然后一个entropy-based策略提出了保持种群的多样性。最后,entropy-based多目标进化算法与增强的精英主义。

3.1。增强的机制

最近的研究已经表明,精英机制是一个很好的方法来加速进化算法的收敛性。人口可以产生一个好的后代人口通过精英主义的指导作用,实现人口的快速发展。这个概念的基础上,提出了不同形式的精英机制在一些东亚峰会(1,14]。其中,最受欢迎和最有效的一个用于NSGA-II,然后父母和子女首先结合人口选择一定数量的解决方案将从欧盟人口作为下一次迭代的亲本种群根据nondominated排序和人群距离任务。正如上面提到的,算法的运行初期,主导解决方案的一部分可能会选择到精英人群,这样产生的后代都不够好。因此,我们做一些改进来提升良好的解决方案,当生产后代的指导作用,我们称之为增强精英机制。

根据精英机制,合理,更好的解决方案选择为父母,后代就越好解决方案,是由这些父母。因此,为了提高导游的精英主义在我们的算法,我们只是选择所有nondomination解决方案作为下一次迭代的父母而不是一定数量的相对良好的解决方案,其中可能包括主导解决方案由于nondominated解决方案在欧盟人口的数量小于N在早期的运行算法。这种增强的机制可以避免一些复杂的操作,比如分层nondominated排序和群众的距离计算。另一方面,所有后代nondominated人口产生的解决方案,这使得使用最好的解决方案来提高人口的演变的效率。当nondominated解决方案的数量超过N最差的,我们删除解决方案通过entropy-based策略分配一个接一个,而准确地考虑所有解决方案的分布信息获得更好的精英人口分布。

3.2。维持多样性Entropy-Based策略

在增强精英机制,nondominated解决方案联盟人口的数量会逐渐增加算法。让精英人群的最大大小N和维护人口的多样性,我们提出了entropy-based策略结合区域信息和知识熵。策略删除最拥挤的解决方案,和所有相关的值将被重新计算,然后再决定哪些解决方案应该从人口中删除,可以动态地、准确地反映的分布解决方案。很明显,关键的操作策略是最拥挤的解决方案如何选择nondominated人口。首先我们选择最拥挤的地区通过应用与最不均匀分布的信息熵,然后解决严重影响解集的分布在这个地区选择和清除的精英人群。前面的过程是循环直到nondominated人口减少的大小N形成了精英人群。这个策略详细描述如下。

为便于操作,我们点nondominated解决方案由一个目标,然后,该地区被定义为以每个解决方案为中心,在那里代表了解决方案的客观价值,是一个参数,用于控制区域的面积,然后呢的长度是客观的数值范围。显然,2-objective问题,该地区是一个广场;3-objective问题,该地区是一个立方体。因为这些地区的地区所有的解决方案都是一样的,毫无疑问,越多的总数现有解决方案在一个地区,该地区更加拥挤。因此,它很容易找到最拥挤的地区基于解决方案的数量在一个地区。如果只有一个地区最解决方案,包括本地区最拥挤的解决方案将被删除。然而,在大多数情况下,可能会有几个地区也包括和最大数量的解决方案。最多的地区分布不均的解决方案将从这些地区选择应用知识熵。

根据香农信息论(15),熵可以用来测量的概率分布的均匀性在一个标准化的系统。假设一个随机过程可能结果的概率th的结果是。这一过程的概率分布作为概率向量表示可以显示为 这个概率向量都有一个关联的香农熵,的形式 在哪里被假定为零当。这个函数的最大值。,当所有的可能性都有相同的值,并至少当一个组件的零向量是1,其余的条目矢量为零。灵感来自于这一点,我们计算的熵通过将该地区作为一个地区和查看每个之间的距离作为两个相邻的解决方案。如果一个地区有一个更加均匀分布,相邻的解决方案之间的距离大致相似,其熵将更大,当一个地区有更多的不均匀分布,相邻的解决方案之间的距离有很大区别,其熵将更小。

计算区域的熵的原理图如图1。有解决方案按客观排序在这个地区,两个相邻的解决方案之间的距离,和分别是,边缘距离两种极端的解决方案,,相应的边界地区的客观要求。为了获得一个规范化系统和更合理的采用熵公式,需要执行一些转换。让,,然后 根据(3),这些地区的熵与熵的大多数解决方案计算和该地区是最小的。不仅意味着这个地区包括大多数的解决方案,但也其分布解决方案在这个地区是最不均匀。接下来,我们将从这个区域删除选择最拥挤的解决方案。在这里,一个简单而有效的方法。在该地区,首先找到最小邻近距离的两个解决方案,然后我们比较他们和他们的其他相邻的解决方案之间的距离。最后,解决方案从人口规模较小的距离将被删除。一个简单的例子如图2。和被发现有最小的距离,然后我们比较的距离之间的和与距离之间的和。自,解决方案将被删除。我们的方法之间的主要区别和存档SPEA2截断方法是所有解决方案在我们的算法中排序和我们只执行一些比较相邻的距离。这种方法不仅可以减少计算,但也可以保持甚至分布合理的解决方案。

3.3。E-MOEA框架

梳理基本进化算法和传统的方法产生的后代在遗传算法(交叉和变异),我们提出了entropy-based多目标进化算法的增强精英机制(E-MOEA)。主要步骤如下所示。

参数
我们有以下:(数量),(最大数量的一代),(当前的人口),(精英人群),(后代人口)。

步骤1。生成初始种群并设置。

步骤2。复制所有的nondominated解决方案人口。

步骤3。如果,减少的大小由一个接一个,直到entropy-based策略。

步骤4。如果,然后去一步7。

第5步。执行重组和变异算子获得后代人口。

步骤6。 ,,去一步2,

步骤7。输出当前的精英人群。

4所示。实验设计和结果

在本节中,通过大量的实验进行测试的性能E-MOEA biobjective和3-objective问题。具体地说,我们的算法相对于其他高级MOEAs: NSGA-II和SPEA2构建精英人群的不同的策略。然后,提出的比较E-MOEA和MOSADE。

4.1。测试实例和性能指标

在我们的实验中,biobjective问题来自ZDT系列:ZDT1, ZDT2 ZDT3, ZDT6。3-objective问题我们选择由DTLZ家庭可伸缩测试问题[16]。

有几个指标提出了测量MOEAs获得的帕累托最优的性能。在我们的工作中,我们选择了GD指标(17和SP规18]。GD可以测量之间的距离nondominated解决方案获得真正的帕累托最优 在哪里代表之间的欧几里得距离的解决方案和最近的成员(是一个从真实的帕累托最优解集均匀取样前)。在我们的实验中,我们使用10000均匀间隔的帕累托最优解的近似真实的帕累托面前。

度规SP可以用来测量获得解决方案的多样性。在这里,是所有的平均值,是目标的数量:

通常使用的另一个指标来评估解决方案集的多样性(1]。然而,这个指标只适用于biobjective问题,不能直接用来评价以上两个目标的问题。基于提出的指标(19),指标被扩展以适应两个多目标问题通过计算给定的点的距离其最近的邻居。修改指标 在哪里是一组解决方案,是极端的解决方案集的帕累托最优解决方案,的数量目标,

4.2。比较E-MOEA和其他MOEAs

在这一部分中,我们将比较E-MOEA提议和两个先进的算法,NSGA-II SPEA2。所有三个算法给出了实值决策变量。模拟二进制交叉(墨)20.)和多项式变异(PM) (21)与分配指标的应用和,分别。交叉概率和变异概率(是决策变量的数量为测试问题)。在E-MOEA,不应该太大,以减少算法的计算;相反,我们的实验结果也表明,如果设置过小,算法也没有得到好的结果。所以对于2-objective问题,我们集3-objective问题,。在所有三个MOEAs,人口的规模是100和功能评价的最大数量是25000 2-objective问题。和3-objectives问题这两个数是200年和80000年,分别。

四个biobjective问题,ZDT1-3 ZDT6,三个3-objective问题DTLZ1-3。为每个测试问题,30倍执行。收敛指标GD和多样性度量SP是用来评估性能。结果在表1,平均和声波时差。dev,分别代表指标的平均值和标准偏差。GD指标而言,我们可以清楚地看到,E-MOEA接近帕累托最优方面比其他四个2-objective测试问题。原因是父母nondominated解决方案的解决方案都是由在当前人口E-MOEA。由于不使用解决方案为主,人口可以达到真正的帕累托最优前更快更有效率。的SP度量,ZDT1 ZDT2,和ZDT3 E-MOEA是最好的,SPEA2第二,NSGA-II是最后一个。ZDT6, SPEA2比E-MOEA好一点,他们比NSGA-II要好得多。可能的原因是,SPEA2使用有效的健身任务,然而,这花费了太多的时间。E-MOEA基于熵的策略适用于保护人口的多样性,可以评估分布的均匀性的解决方案更科学的精英人口的分布。

DTLZ串行测试Deb K,提出的问题都是可以设置的不同数量的目标。在这里,我们选择的设置一样22]。DTLZ1 DTLZ2,所有三个算法能收敛帕累托最优,但E-MOEA最近的真实方面,SPEA2是第二,NSGA-II是最后一个。的多样性,E-MOEA和SPEA2比NSGA-II更好。由于DTLZ3是最困难的测试问题,SPEA2和NSGA-II不能收敛于帕累托最优。原因是NSGA-II和SPEA2总是产生太多野生个体获得的数量。幸运的是,E-MOEA可以获得DTLZ3解决方案具有良好的收敛性和多样性。因此,表1由E-MOEA DTLZ3只给出了结果,“-”表示,相应的算法不能获得合理的结果。

数据3,4,5,6显示最后三个算法获得的四个biobjective测试问题的解决方案。显然,我们可以看到解决方案通过E-MOEA显示最广泛和最均匀分布,靠近真正的帕累托最优比NSGA-II和SPEA2前面。数据7和8显然现在最终的解决方案由三个算法DTLZ1和DTLZ2。图9通过E-MOEA DTLZ3显示了最终的解决方案。

4.3。比较E-MOEA MOSADE

E-MOEA和MOSADE利用熵维持解集的多样性。在E-MOEA,我们选择最严重地区分布保持解决方案通过应用信息熵公式。MOSADE,改善信息熵公式用于更新档案,保持解集的多样性。这两个算法,进行了进一步的实验来比较他们的表演。E-MOEA,所有的参数都是一样的的参数E-MOEA节中描述4.2除了人口规模是100的测试问题。MOSADE,人口规模和外部精英档案大小是100,突变体的上下极限常数和交叉概率,,,。ZDT1-3 biobjective问题和ZDT6 DTLZ1-7 3-objective问题考虑。GD和在这个实验中,作为评价指标和结果展示在表吗2。

从表中获得的结果2表明这两个算法都好根据GD收敛;然而,E-MOEA值比除了DTLZ7 MOSADE所有测试问题。这意味着从E-MOEA产生帕累托方面更接近真正的最优帕累托方面。获得的解集E-MOEA可以更快地收敛到最优,这可能是由于增强精英主义应用于E-MOEA。随着DTLZ7更大范围的最优解决方案,在E-MOEA收敛的效果并不比MOSADE应用微分进化。的指标2-objective问题,MOSADE有更多的均匀分布和3-objective E-MOEA有更好的结果。可能的原因是,拥挤熵多样性度量策略MOSADE更有效的测试问题最佳的前面是一个近似的曲线。然而,由于考虑空间因素,保持多样性entropy-based策略更适合解决这个问题的最佳的前面是一个表面。因此,E-MOEA DTLZ1-4和DTLZ7具有更好的多样性。

5。结论

摘要小说entropy-based多目标进化算法的增强精英机制(E-MOEA)提出。该算法提高了精英主义和提出了一种新的策略基于熵构建精英人群。起初我们只选择人口中的nondominated解决方案作为精英的解决方案,当nondominated解决方案的大小超过了人口的规模,我们删除差的解决方案一个接一个通过entropy-based保持人口的多样性策略。实验结果在七广泛使用流行的测试函数表明E-MOEA可以获得更好的解决方案集或比较收敛性和多样性表演与NSGA-II相比,SPEA2, MOSADE。

消除一个解决方案需要重新计算的熵拥挤的地区,E-MOEA是最糟糕的时间复杂度,这是SPEA2也一样。未来的研究将如何减少计算开销,同时保持良好的性能。

确认

这项工作是支持的国家自然科学基金委重大研究计划(60496322,60496327),北京市自然科学基金(4102010)。作者非常感谢吴教授Lianghong MOSADE指导实验。