一种决策变量分类的动态多目标优化问题解决方法

1.本发明涉及多目标进化领域，特别涉及一种基于k-means聚类的决策变量分类的动态多目标优化问题解决方法。


背景技术：

2.在工业应用和科学研究中，例如作业车间调度、组合优化、工程设计、电力调度、投资管理、图像分割、网络通信、数据挖掘等优化领域，经常会遇到诸多动态多目标优化问题。这些问题要求算法在及时跟踪变化的pareto最优前沿的同时，还要尽可能提供多样性的解集来得到最新的随时间变化的近似pareto最优前沿。但是当环境变化的速度比较快时，问题的求解会更加困难。决策变量分类方法的优势在于可以依据决策变量不同的性质，针对性的采取不同的优化策略，提高算法的收敛性与多样性。另外，环境变化后新环境信息对指导种群进化也具有良好作用。
3.因此，如何有效提高算法的收敛性与多样性，是目前动态多目标优化领域所需解决的一重要问题。


技术实现要素：

4.本发明的目的在于提供一种决策变量分类的动态多目标优化问题解决方法，以解决上述背景技术中提出的问题。
5.为实现上述目的，本发明提供如下技术方案：
6.基于k-means聚类的决策变量分类的动态多目标优化问题解决方法，包括以下步骤：
7.步骤1：在种群中随机选择个体，对个体的各个维度进行n次扰动。
8.步骤2：归一化扰动每个变量所生成的样本解，并且生成拟合线l来拟合每组归一化样本解。
9.步骤3：使用标准化样本解和拟合线l，并且计算每个拟合线l与超平面的法线之间的角度。
10.步骤4：采用k-means聚类方法，根据每个变量的特征将决策变量分为两类。
11.步骤5：根据分类结果，针对与收敛性相关变量，结合历史信息与环境变化后新环境信息，使用中心点预测方法，获得良好收敛性。
12.步骤6：针对与多样性相关变量，采用多样性引进措施，获得优异多样性。
13.进一步的，步骤2中，最小归一化为：
[0014][0015]
进一步的，步骤3中，拟合线和超平面的夹角sinθ为：
[0016][0017]
式中，a向量为拟合线的方向向量，n向量为超平面的法向量。
[0018]
进一步的，步骤5中，环境变化程度k为：
[0019]
k＝k2/k1[0020]
式中，t-1时刻种群非支配解中心与环境变化后种群独自进化一段时间后种群中心之间的欧氏距离为k1；
[0021]
t-2时刻种群非支配解中心与环境变化后种群独自进化一段时间后种群中心之间的欧氏距离为k2。
[0022]
进一步的，步骤5中，中心点预测方法具体步骤如下：
[0023]
种群t时刻第i维度的平均值
[0024][0025]
式中，n是种群解的数量，是t时刻的解。
[0026]
第i维度在t时刻的移动方向
[0027][0028]
下一时刻收敛性变量维度值
[0029][0030]
进一步的，步骤6中，多样性引进方法为：
[0031]
t+1时刻多样性变量维度值
[0032][0033]
式中，和分别表示第i个变量在t时刻的下界和上界，rand是[0，1]中随机产生的值。
[0034]
与现有技术相比，本发明的有益效果是：
[0035]
本发明针对动态多目标优化问题，首先分析每个决策变量在新环境中对收敛性与多样性的影响，利用k-means聚类将决策变量分为两类，与多样性相关变量和与收敛性相关变量，其中为提高分类的准确性，提出了由样本解与收敛方向的夹角来度量决策变量的性质的分类方法；此外，为了使收敛性优化策略获得更高的准确性，考虑到环境变化后信息对指导种群进化的作用，结合历史信息提出一种环境变化程度计算方法；最后，针对不同的决策变量分别采取混合预测策略，以获得良好的收敛性与多样性。
附图说明
[0036]
图1为扰动产生的样本解的目标值图；
[0037]
图2为拟合线和超平面法线之间的角度图；
[0038]
图3为聚类结果图。
具体实施方式
[0039]
下面将对本发明实施例中的技术方案进行清楚、完整的描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0040]
实施例1，如图1所示，一种决策变量分类的动态多目标优化问题解决方法，其特征在于，包含以下步骤：
[0041]
步骤1：在种群中随机选择个体，对个体的各个维度进行n次扰动；为获得准确的决策变量分类结果，采取均匀随机抽样获得代表性样本个体。
[0042]
步骤2：归一化扰动每个变量所生成的样本解，并且生成拟合线l来拟合每组归一化样本解；考虑到极端数值对模型的影响，采取最大最小归一化对数据进行标准化处理。
[0043]
步骤3：使用标准化样本解和拟合线l，并且计算每个拟合线l与超平面的法线之间的角度；超平面为f1+...+fm＝1，m为目标个数。
[0044]
步骤4：采用k-means聚类方法，根据每个变量的特征将决策变量分为两类；采用k-means聚类方法，由样本解与收敛方向的夹角来度量决策变量的性质，在具有较小角度平均值的群中的变量被确定为收敛相关变量，而在具有较大角度平均值的群中的变量被确定为多样性相关变量。
[0045]
步骤5：根据分类结果，针对与收敛性相关变量，结合历史信息与环境变化后新环境信息，使用中心点预测方法，获得良好收敛性；环境变化程度k为：k＝k2/k1，t-1时刻种群非支配解中心与环境变化后种群独自进化一段时间后种群中心之间的欧氏距离为k1。
[0046]
步骤6：针对与多样性相关变量，采用多样性引进措施，获得优异多样性。
[0047]
实施例2，在实施例1的基础上，步骤5中，中心点预测方法具体步骤如下：
[0048]
种群t时刻第i维度的平均值
[0049][0050]
式中，n是种群解的数量，是t时刻的解。
[0051]
第i维度在t时刻的移动方向
[0052][0053]
下一时刻收敛性变量维度值
[0054][0055]
实施例3，在实施例2的基础上，步骤6中，多样性引进方法为：
[0056]
t+1时刻多样性变量维度值
[0057]
[0058]
式中，和分别表示第i个变量在t时刻的下界和上界，rand是[0，1]中随机产生的值。
[0059]
本发明的工作原理如下：
[0060]
以具有三个决策变量x1，x2和x3的双目标最小化问题为例，来说明所提出的决策变量聚类方法的主要思想。为了确定决策变量是收敛相关还是多样性相关，首先从总体中随机选择若干候选解(本例中为一个)。然后，对所选候选解的三个变量中的每一个进行若干扰动(本例中为六个)。图1绘制了由扰动产生的样本解的目标值。然后，归一化扰动每个变量的值生成的样本解，并生成一条线l来拟合每组归一化样本解。使用标准化样本解和拟合线l，计算每个拟合线l与超平面f1+...+fm＝1的法线之间的角度，其中法线表示收敛方向，m表示目标数。通过这种方式，每个变量与多个角度相关联，其中数量取决于用于决策变量聚类的候选解的数量。图2描绘了拟合线和超平面法线之间的角度。由于在例子中，决策变量聚类选择了三个候选解，每个变量与一个角度相关，1≤i≤3，表示为θi，如图2所示。在所提出的决策变量聚类方法中，与每个变量相关联的角度是指其对收敛性和多样性的贡献的度量。更具体地说，角度越大意味着相关变量对多样性的贡献越大，而角度越小意味着对收敛的贡献越大。最后，采用k-means聚类方法，根据每个变量的特征将决策变量分为两类。因此，具有较小角度平均值的群中变量被确定为收敛相关变量，而另一个群中的变量被确定为多样性相关变量。图3显示了三个决策变量x1，x2和x3的聚类结果。因此，x1被确定为多样性相关变量x2和x3被确定为收敛相关变量。
[0061]
对于本领域技术人员而言，显然本发明不限于上述示范性实施例的细节，而且在不背离本发明的精神或基本特征的情况下，能够以其他的具体形式实现本发明。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化囊括在本发明内。
[0062]
此外，应当理解，虽然本说明书按照实施方式加以描述，但并非每个实施方式仅包含一个独立的技术方案，说明书的这种叙述方式仅仅是为清楚起见，本领域技术人员应当将说明书作为一个整体，各实施例中的技术方案也可以经适当组合，形成本领域技术人员可以理解的其他实施方式。

技术特征：
1.一种决策变量分类的动态多目标优化问题解决方法，其特征在于，包含以下步骤：步骤1：在种群中随机选择个体，对个体的各个维度进行n次扰动；步骤2：归一化扰动每个变量所生成的样本解，并且生成拟合线l来拟合每组归一化样本解；步骤3：使用标准化样本解和拟合线l，并且计算每个拟合线l与超平面的法线之间的角度；步骤4：采用k-means聚类方法，根据每个变量的特征将决策变量分为两类；步骤5：根据分类结果，针对与收敛性相关变量，结合历史信息与环境变化后新环境信息，使用中心点预测方法，获得良好收敛性；步骤6：针对与多样性相关变量，采用多样性引进措施，获得优异多样性。2.根据权利要求1的一种决策变量分类的动态多目标优化问题解决方法，其特征在于，所述步骤1中，为获得准确的决策变量分类结果，采取均匀随机抽样获得代表性样本个体。3.根据权利要求1的一种决策变量分类的动态多目标优化问题解决方法，其特征在于，所述步骤2中，考虑到极端数值对模型的影响，采取最大最小归一化对数据进行标准化处理。4.根据权利要求1的一种决策变量分类的动态多目标优化问题解决方法，其特征在于，所述步骤3中，超平面为f1+...+f
m
＝1，m为目标个数。5.根据权利要求4的一种决策变量分类的动态多目标优化问题解决方法，其特征在于，所述步骤4中，采用k-means聚类方法，由样本解与收敛方向的夹角来度量决策变量的性质，在具有较小角度平均值的群中的变量被确定为收敛相关变量，而在具有较大角度平均值的群中的变量被确定为多样性相关变量。6.根据权利要求1的一种决策变量分类的动态多目标优化问题解决方法，其特征在于，所述步骤5中，环境变化程度k为：k＝k2/k1t-1时刻种群非支配解中心与环境变化后种群独自进化一段时间后种群中心之间的欧氏距离为k1。7.根据权利要求1的一种决策变量分类的动态多目标优化问题解决方法，其特征在于，所述步骤5中，中心点预测方法具体步骤如下：种群t时刻第i维度的平均值种群t时刻第i维度的平均值式中，n是种群解的数量，是t时刻的解。第i维度在t时刻的移动方向第i维度在t时刻的移动方向下一时刻收敛性变量维度值下一时刻收敛性变量维度值8.根据权利要求1的一种决策变量分类的动态多目标优化问题解决方法，其特征在于，
所述步骤6中，多样性引进方法为：t+1时刻多样性变量维度值t+1时刻多样性变量维度值式中，和分别表示第i个变量在t时刻的下界和上界，rand是[0，1]中随机产生的值。

技术总结
本发明公开了一种决策变量分类的动态多目标优化问题解决方法，属于多目标进化领域，首先分析每个决策变量在新环境中对收敛性与多样性的影响，利用k-means聚类将决策变量分为两类，与多样性相关变量和与收敛性相关变量，其中为提高分类的准确性，提出了由样本解与收敛方向的夹角来度量决策变量的性质的分类方法；此外，为了使收敛性优化策略获得更高的准确性，考虑到环境变化后信息对指导种群进化的作用，结合历史信息提出一种环境变化程度计算方法；最后，针对不同的决策变量分别采取混合预测策略，以获得良好的收敛性与多样性。以获得良好的收敛性与多样性。以获得良好的收敛性与多样性。


技术研发人员：杨清帅
受保护的技术使用者：燕山大学
技术研发日：2023.03.06
技术公布日：2023/7/20