基于动态分解和选择的超多目标优化方法、系统、终端

技术领域

本发明属于计算机技术领域，尤其涉及一种基于动态分解和选择的超多目标优化方法、系统、终端。

背景技术

目前，单目标、多目标以及超多目标优化问题是日常生活中常见的问题。针对单目标优化问题，演化算法(Evolutionary Algorithm，EA)利用自然进化选择和自然进化的随机搜索机制，很好的解决了此类问题。但是在多目标与超多目标优化问题中，目标之间存在着相互冲突或者相互促进的关系。所以多目标和超多目标优化不同于单目标优化，单目标优化存在唯一的最优解。但多目标和超多目标优化问题需要通过权衡各个小目标，来获取一系列的最优解集。

针对多目标优化问题和超多目标优化问题，常用的方法类型有：基于支配的，基于指标和基于分解的。其中，基于分解的算法由于其使用的广泛性，备受一些研究者地关注。基于分解的多目标优化算法，最具有代表性的就是MOEA/D，将多目标优化问题转化为一系列单目标优化问题，并对这些单目标优化问题同时进行优化。

随着研究的不断深入，一些专家学者发现。传统的基于分解的算法，每个子区域在每一代演化过程中都是固定不变的，将会导致基于分解的多目标优化算法的性能受到真实Pareto fronts(PF)形状的影响。

DDEA算法使用了动态分解的方法去解决超多目标优化的问题。在此算法中，固定的参考点被解集自身取代。因为在演化过程中，可以根据解集的分布情况可以更好的反映出PF的形状。但是此算法选择最优解集，容易使得算法在解决具有凸类型的PF问题，解集都集中于PF的中间部分。导致所获得解集多样性差，解集陷入局部最优。

通过上述分析，现有技术存在的问题及缺陷为：现有的多目标有优化方法不适用所有情景，同时其优化结果具备一定限制。

解决以上问题及缺陷的难度为：

不知道真实的Pareto front，根据最优解自身可以大致反映出真实PF。DDEA算法虽然可以动态的调整参考点的位置，但是在选择最优个体时，容易使得具有凸类型的PF问题最优个体聚集到PF的中部，导致解集的多样性差，解集陷入局部最优。

解决以上问题及缺陷的意义为：

解决该问题之后，算法的鲁棒性更强。可以使得得到的解均匀分布到整个PF面上，得到一组最优解集。提高后的算法可以更好的解决不同类型的PF问题，比如复杂的、多峰的、凸类型和凹类型等问题。

发明内容

针对现有技术存在的问题，本发明提供了一种基于动态分解和选择的超多目标优化方法、系统、终端。

本发明是这样实现的，一种基于动态分解和选择的超多目标优化方法，所述基于动态分解和选择的超多目标优化方法包括：

步骤一，随机初始化具有N个个体的种群P，初始化当代演化代数为0；计算出被选个体距离超平面的距离和个体对应的参考点之间的距离，并利用DDS策略选择N个优秀个体作为下一代演化子代P；

步骤二，初始化子代种群O为空集；

步骤三，针对父代中的N个个体，开始循环处理；初始化用于存储子代个体的R，对当前父代利用Mating-Selection选择出一个交配个体；对两个父代利用SBX和PM生成一个子代R，将子代R加入到子代种群O中；

步骤四，重复步骤三，直至产生的子代种群集O的大小为N个为止；合并子代O和原来的父代P，组成一个新的种群大小为2N的种群P；在种群P中利用DDS选择得到最优的N个种群P；

步骤五，演化代数加1，重复步骤二至步骤四，直至达到最大演化代数为止。

进一步，所述种群P的初始化处理包括：

(1)在种群P中寻找每一位坐标轴上所对应的极值点，第i个坐标轴上的极值点如下：

式中，

(2)根据矩阵E＝(e

其中，a

(3)将种群P中的每一个个体都归一化为：

(4)将种群中每个个体x都转化为平面上的参考点RP：

进一步，所述对当前父代利用Mating-Selection选择出一个交配个体包括：

设置一个随机数，当该随机数大于ζ时，随机从父代中选择一个个体进行交配；否则，在选择距离该个体最近(d

进一步，所述在种群P中进行DDS选择得到最优的N个种群P包括：

1)将每个轴上的极值点加入到已经选择的个体集Q中,余下的个体W＝P-Q。得到每个个体对应在超平面上参考点的距离distance，x,y∈P，则个体x和个体y之间的距离为distance(x,y)；

distance(x,y)＝||RP(x)-RP(y)||

2)选择一个个体x距离已经选择解集Q最远的那个个体作为中心轴ρ，计算公式如下：

3)以选择的轴ρ为出发点，选择一组多样性最好的解作为候选解集S

d

S

S

4)从候选解集S

HPF(x,p)＝d

其中，d

进一步，所述选择候选解的标准为：一个个体x如果距离轴ρ比距离已经选择的解集Q更近，则该个体x可以作为候选解被选入到候选解集S

本发明的另一目的在于提供一种基于动态分解和选择的超多目标优化系统，所述基于动态分解和选择的超多目标优化系统包括：

被选个体超平面和个体对应的参考点距离获取模块，用于随机初始化具有N个个体的种群P，初始化当代演化代数为0；利用DDS选择N个优秀个体作为下一代演化子代P，并计算出被选个体距离超平面的距离和个体对应的参考点之间的距离；

空集获取模块，用于初始化子代种群O为空集；

子代添加模块，用于对父代中的N个个体，开始循环处理；初始化用于存储子代个体的R，对当前父代利用Mating-Selection选择出一个交配个体；对两个父代利用SBX和PM生成一个子代R，将子代R加入到子代种群O中；

最优种群获取模块，用于重复子代添加模块的功能，直至产生的子代种群集O的大小为N个为止；合并子代O和原来的父代P，组成一个新的种群P；在种群P中进行DDS选择得到最优的N个种群P；

最大演化代数获取模块，用于演化代数加1，重复空集获取模块、子代添加模块、最优种群获取模块的功能，直至达到最大演化代数为止。

本发明的另一目的在于提供一种计算机设备，所述计算机设备包括存储器和处理器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器执行所述基于动态分解和选择的超多目标优化方法。

本发明的另一目的在于提供一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，使得所述处理器执行所述基于动态分解和选择的超多目标优化方法。

本发明的另一目的在于提供一种信息数据处理终端，所述信息数据处理终端用于实现所述基于动态分解和选择的超多目标优化方法。

本发明的另一目的在于提供一种存储在计算机可读介质上的计算机程序产品，包括计算机可读程序，供于电子装置上执行时，提供用户输入接口以实施所述基于动态分解和选择的超多目标优化方法。

结合上述的所有技术方案，本发明所具备的优点及积极效果为：本发明利用个体到单元超平面的垂直距离作为解集收敛性的评价标准，距离约小表明收敛性越好，反之则越差。本发明的评价标准可以针对任何形状的PF都适用，在未知真实PF的情况下，本发明更加公平且适用。

本发明在选择最优个体时，根据演化阶段自适应的调整收敛性和多样性之间的关系，使得选择的解集在演化前期在保证多样性的前提条件下更快的收敛，在后期只需要考虑多样性即可。

本发明利用每一代个体的收敛性和个体之间的多样性，作为个体在交配变异的信息，可以促使后代朝着更好的方向进化。

具体实例来演示本算法的效果：

在演化前期，要加快种群的收敛速度，所以在演化前期更加偏向于收敛性较好的个体。如下图4所示，在有11个体{x

在演化中后期，要注意种群的多样性，所以在演化前期更加偏向于收敛性较好的个体。在后期阶段会更加注重种群的多样性，所以会选择{x

对比的技术效果或者实验效果。包括：

该算法在DTLZ4上的实验效果如图6。(a)DDEA(b)MOEA/DDS,由图6分析可知，新提出的MOEA/DDS算发的多样性和收敛性要优于DDEA，所以MOEA/DDS算法的综合性能优于DDEA。

附图说明

为了更清楚地说明本申请实施例的技术方案，下面将对本申请实施例中所需要使用的附图做简单的介绍，显而易见地，下面所描述的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下还可以根据这些附图获得其他的附图。

图1是本发明实施例提供的基于动态分解和选择的超多目标优化方法流程图。

图2是本发明实施例提供的个体对应的参考点示意图。

图3是本发明实施例提供的HPF表示示意图。

图2-图3中：ο表示个体；·表示个体对应的参考点。

图4是本发明实施例提供的在演化前期，要加快种群的收敛速度，所以在演化前期更加偏向于收敛性较好的个体图.

图5是本发明实施例提供的在演化中后期，要注意种群的多样性，所以在演化前期更加偏向于收敛性较好的个体。在后期阶段会更加注重种群的多样性，所以会选择{x

图6是本发明实施例提供的算法在DTLZ4上的实验效果图。其中图6(a)DDEA；图6(b)MOEA/DDS。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

针对现有技术存在的问题，本发明提供了一种基于动态分解和选择的超多目标优化方法，下面结合附图对本发明作详细的描述。

如图1所示，本发明实施例提供的基于动态分解和选择的超多目标优化方法包括以下步骤：

S101，随机初始化具有N个个体的种群P，初始化当代演化代数为0；利用DDS选择N个优秀个体作为下一代演化子代P，并计算出被选个体距离超平面的距离和个体对应的参考点之间的距离；

S102，初始化子代种群O为空集；

S103，针对父代中的N个个体，开始循环处理；初始化用于存储子代个体的R，对当前父代利用Mating-Selection选择出一个交配个体；对两个父代利用SBX和PM生成一个子代R，将子代R加入到子代种群O中；

S104，重复步骤S103，直至产生的子代种群集O的大小为N个为止；合并子代O和原来的父代P，组成一个新的种群P；在种群P中进行DDS选择得到最优的N个种群P；

S105，演化代数加1，重复步骤S102至步骤S104，直至达到最大演化代数为止。

本发明实施例提供的种群P的初始化处理包括：

(1)在种群P中寻找每一位坐标轴上所对应的极值点，第i个坐标轴上的极值点如下：

式中，

(2)根据矩阵E＝(e

其中，a

(3)将种群P中的每一个个体都归一化为：

(4)将种群中每个个体x都转化为平面上的参考点RP：

本发明实施例提供的对当前父代利用Mating-Selection选择出一个交配个体包括：

设置一个随机数，当该随机数大于ζ时，随机从父代中选择一个个体进行交配；否则，在选择距离该个体最近(d

本发明实施例提供的在种群P中进行DDS选择得到最优的N个种群P包括：

1)将每个轴上的极值点加入到已经选择的个体集Q中,余下的个体W＝P-Q。得到每个个体对应在超平面上参考点的距离distance，x,y∈P，则个体x和个体y之间的距离为distance(x,y)；

distance(x,y)＝||RP(x)-RP(y)||

2)选择一个个体x距离已经选择解集Q最远的那个个体作为中心轴ρ，计算公式如下：

3)以选择的轴ρ为出发点，选择一组多样性最好的解作为候选解集S

d

S

S

4)从候选解集S

HPF(x,p)＝d

其中，d

本发明实施例提供的选择候选解的标准为：一个个体x如果距离轴ρ比距离已经选择的解集Q更近，则该个体x可以作为候选解被选入到候选解集S

下面结合具体实施例对本发明的技术效果作进一步描述。

实施例1：

(一)发明内容(算法思想)：

MOEA/DDS针对DDEA中DDR策略也做出了修改，提出了一种新的动态分解和选择策略dynamical decomposition and selection strategy(DDS)，可以更好的选择出一组多样性和收敛性平衡的最优解集。MOEA/DDS算法的主要亮点在于：

(1)利用个体到单元超平面的垂直距离作为解集收敛性的评价标准，距离约小表明收敛性越好，反之则越差。这种评价标准可以针对任何形状的PF都适用。优点在于未知真实PF的情况下，这种评价标准更加公平且适用。

(2)在选择最优个体时，根据演化阶段自适应的调整收敛性和多样性之间的关系，使得选择的解集在演化前期在保证多样性的前提条件下更快的收敛，在后期只需要考虑多样性即可。

(3)利用每一代个体的收敛性和个体之间的多样性，作为个体在交配变异的信息，可以促使后代朝着更好的方向进化。

MOEA/DDS算法的主要流程如下：

第一步：MOEA/DDS算法中，首先随机初始化具有N个个体的种群P，初始化当代演化代数为0。

第二步：利用DDS选择N个优秀个体作为下一代演化子代P，并计算出被选个体距离超平面的距离和个体对应的参考点之间的距离distance。

第三步：初始化子代种群O为空集。

第四步：针对父代中的N个个体，开始循环操作。

第五步：初始化用于存储子代个体的R，对当前父代利用Mating-Selection选择出一个交配个体。对这两个父代利用SBX和PM操作生成一个子代R。将子代R加入到子代种群O中。

第六步：重复步骤第四步和第五步，直到产生的子代种群集O的大小为N个为止。

第七步：合并子代O和原来的父代P，组成一个新的种群P。

第八步：在种群P中进行DDS选择得到最优的N个种群P。

第九步：演化代数加1。

第十步：重复第三步到第九步，直到达到最大演化代数为止。

接下来仔细介绍MOEA/DDS的主要操作过程，构造参考点、DDS(DynamicalDecomposition and Selection Strategy)策略和Mating selection策略。

1.1构造参考点

本发明采用了极值点标准化方法对种群P进行归一化处理。具体步骤如下：

1)在种群P中寻找每一位坐标轴上所对应的极值点。第i个坐标轴上的极值点

在该表达式中，

2)假设a

可以根据矩阵E＝(e

当矩阵的秩小于m，或者存在

3)标准化，种群P中的每一个个体都归一化为

4)接下来将种群中每个个体x都转化为平面上的参考点RP。如图1所示，通过将个体用白色的点表示转换到相应的超平面上，得到对应的参考点用黄色的点表示。

1.2)Dynamical Decomposition and selection(DSS)策略

首先将每个轴上的极值点加入到已经选择的个体集Q中,余下的个体W＝P-Q。求出每个个体对应在超平面上参考点的distance，x,y∈P，则个体x和个体y之间的距离为distance(x,y)。

distance(x,y)＝||RP(x)-RP(y)||

1)寻找轴ρ

选择一个个体x距离已经选择解集Q最远的那个个体作为中心轴ρ。计算方式如下：

2)动态分解策略

以第一步选择的轴ρ为出发点，选择一组多样性最好的解作为候选解集S

d

S

S

3)动态选择策略

从S

HPF(x,p)＝d

其中d

且θ是根据演化代数进行调整的，因为在演化早期要更加注重个体的收敛性，在演化后期要更加注重个体的多样性。

1.3Mating selection策略

对于多目标优化问题，当目标维数很大时，目标在空间中的分布比较分散。为了加快种群的收敛并且保持种群中个体的多样性，本发明采用了一种新的交配方式。设置一个随机数，当该随机数大于ζ时，随机从父代中选择一个个体进行交配；否则，在选择距离该个体最近(d

2、试验情况

MOEA/DDS算法在PaltEMO上进行验证，并且与DDEA算法进行对比。实验的设置的参数见表1，表2。DTLZ

表1目标数以及其对应的种群大小

表2不同问题不用目标数对应的演化代数

其中MOEA/DDS算法中ζ设置为0.9，K值设为20。本文采用HV和IGD指标，得到的实验结果分别见表3和表4。HV和IGD都是用于衡量算法多样性和收敛性的综合指标。

表3 DDEA和MOEA/DDS算法对应的HV值

注：“+”代表结果比MOEA/DDS好，“-”代表结果比MOEA/DDS差，“＝”代表结果与MOEA/DDS相近的数据(下同)

表4 DDEA和MOEA/DDS算法对应的IGD值

具体实例来演示本算法的效果：

在演化前期，要加快种群的收敛速度，所以在演化前期更加偏向于收敛性较好的个体。如下图4所示，在有11个体{x

在演化中后期，要注意种群的多样性，所以在演化前期更加偏向于收敛性较好的个体。在后期阶段会更加注重种群的多样性，所以会选择{x

对比的技术效果或者实验效果。包括：

该算法在DTLZ4上的实验效果如图6。(a)DDEA(b)MOEA/DDS,由图6分析可知，新提出的MOEA/DDS算发的多样性和收敛性要优于DDEA，所以MOEA/DDS算法的综合性能优于DDEA。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，都应涵盖在本发明的保护范围之内。