篮球投篮技巧基于变量分组的大规模多目标优化算法
林涛;霍丽娜
【摘 要】含有大规模决策变量的多目标优化问题,是当前多目标进化算法领域中的研究难点之一.针对此问题,提出一种基于变量分组的大规模多目标优化算法.该算法的贡献在于两个方面:1)提出一种新的决策变量分组方法,该方法通过随机采样与非支配排序,将决策变量分为收敛性变量和多样性变量;2)在种群进化过程中,采用levy分布函数产生新个体,同时设计出适应于此分布函数的优化过程.以反向世代距离(inverted generational distance,IGD)作为评价指标,在标准测试集函数上进行实验,实验结果证明该算法在解决大规模多目标优化问题时是有效的.
【期刊名称】《郑州大学学报（理学版）》
【年(卷),期】2018(050)004
【总页数】6页(P8-13)
【关键词】大规模;多目标;进化算法;变量分组;levy分布
【作 者】林涛;霍丽娜
【作者单位】河北工业大学计算机科学与软件学院 天津300400;河北工业大学计算机科学与软件学院 天津300400
【正文语种】中 文
【中图分类】TP18
0 引言
MOEA/D[1]、NSGA-III[2]、GHEA2、IBEA等这些多目标进化算法在解决多目标优化问题时，大多关注目标数量增多时的性能，没有考虑含有大规模变量的情况，将决策变量当作整体优化，因此比较适合低维决策变量的多目标优化问题.文献[3-4]提出了一些大规模变量的单目标优化方法，但与多目标问题之间相互冲突，解决大规模变量的多目标优化问题更为复杂.文献[5]与文献[6]类似，采用决策变量随机分解策略，将大规模变量随机分组，然后融合合作协同框架[7]与粒子群算法[8]，进行优化，此算法易陷入局部最优，也没有提供一种降低分组变量之间依赖性的明确方法.在国外的文献中，2016年提出的MOEA/DVA[9]算
法，根据变量的控制属性将变量分为3类：多样性相关变量；收敛性相关变量；混合变量(两者都相关的变量).从而将大规模变量的多目标优化问题分解为多个简单的子多目标优化问题.但该算法不能处理混合变量过多的问题，并且算法只研究了目标数为2或3时的算法性能，对高维目标优化问题并不适用.受MOEA/DVA算法启发，文献[10]提出了LMEA算法，经过奇异值分解.计算角度、误差平方和等，基于聚类分析，首先将变量分为收敛性变量和多样性变量，然后再应用不同的优化策略分别优化.经实验验证，LMEA算法处理大规模变量多目标优化问题时，性能优于NSGA-III等主流优化算法.但LMEA算法变量分组效果并不稳定且分解过程过于复杂.本文基于LMEA算法框架，首先提出了一种变量分解方法，不仅简化变量分解过程，并且提高变量分组准确率，然后在优化阶段采用levy变异策略产生子代，提高算法的全局寻优能力.
1 相关理论
1.1 变量相关性分析
相互独立的变量可以分开优化，各自的优化结果不会相互影响，相关变量因为它们之间的相关性，整体优化的结果可能与它们分开优化的结果不同，所以不能分开优化.设多目标优
六年级下册语文教案化问题min f(x)=(f1(x)，f2(x)，…，fn(x))，如果存在决策向量x，实数a1，a2，b1，b2和至少一个目标函数fk，1≤k≤n，使得fk(x)|xi=a2，xj=b1<fk(x)|xi=a1，xj=b1，fk(x)|xi=a2，xj=b2>fk(x)|xi=a1，xj=b2，那么决策变量xi与xj相关.
1.2 levy变异策略
levy变异[11]能够产生更强烈的扰动作用，有助于提高算法的全局寻优能力.设种群规模为N，变量维度为D，其中个体x=(x1，…，xD)，经过levy变异产生的新个体设为x′=(x1，…，xD)，那么x与x′存在的关系为其中：N(0,1)是满足均值为0，方差为1的正态分布；是满足levy分布的随机数，β=0.8.
2 基于变量分组的多目标优化算法(GLEA)
2.1 基于随机采样与非支配排序的大规模变量分组策略
根据变量的控制属性，MOEA/DVA算法将大规模变量分为了3类：多样性变量；收敛性变量；混合变量.基于此，LMEA更细致地将变量分为收敛性变量和多样性变量.本文优化了LMEA算法的变量分解过程，通过对变量随机采样，根据对应目标空间的非支配排序结果，
冬瓜海带汤更简单精确地将变量分为收敛性变量和多样性变量.主要先进事迹怎么写
设多目标优化问题为：其中x1、x2、x3、x4为决策变量.4个变量分组过程为，对变量x1，从种群中随机选择一个个体，对个体中的x1随机采样5次，采样过程为在决策变量所在范围内，随机生成一个值，个体中的其他变量值保持不变，这样就得到一个拥有5个新个体的种群，在目标空间中对应的位置如图1(a)中x1所示，然后对5个个体进行非支配排序.x2、x3、x4与x1的处理过程相同，4个变量的非支配排序结果如图1(b)所示.从图中可以看出，变量x1、x2非支配等级覆盖范围从1到5，个体朝最优解的方向收敛，变量表现为收敛性相关，而变量x3、x4对应的非支配等级只有1，没有收敛性，表现为多样性相关.于是根据非支配等级覆盖范围将变量分为了两组.
图1 变量分组过程Fig.1 The process of variable grouping
设个体为x=(x1，…，xD)，决策变量分组算法流程如下.
Step1： 输入当前种群Pop，随机采样的次数nSample，初始化收敛性变量集合CV=∅，多样性变量集合DV=∅，i=1；
Step2： 当i≤D时，执行以下步骤，否则算法结束，输出变量分组后的结果CV和DV集合；
Step3： 从Pop中随机选择一个个体p1；
Step4： 对p1中的变量xi随机采样nSample次，形成一个种群SP；
Step5： 对种群SP进行非支配排序，排序后的非支配序集合为{1，2，…，maxRankNo}；
Step6： 如果 maxRankNo>nSample/2，那么判定决策变量xi是收敛性变量CV∪{xi}，否则为多样性变量DV∪{xi}；
Step7： i++，转到Step2.
其中，本文都采用T-ENS[10]进行非支配排序.
文明之花2.2 基于levy变异的优化算法
将大规模变量分组后，对于收敛性变量和多样性变量两类变量，分别采用不同的优化策略.多样性变量集合中的变量同时优化，收敛性变量集合中的变量经过相关性分析后划分为多个子组，每个子组中的变量同时优化.
在多样性变量的优化策略中，对当前种群P通过levy变异操作得到第1代子种群，从第2代开始，将父代种群与子代种群合并，进行非支配排序分级，若前k个非支配层中的个体数量和大于P种群大小，那么前k-1非支配排序分级层中的个体直接作为下1代种群的一部分，另一部分从第k非支配层中选取，选取过程基于角度，首先计算第k非支配层中和已选中的个体在目标空间中的两两角度，记录每个第k非支配层中的个体与其他个体所成角度的最小角度，相继选择其中值最大的个体进入下1代种群.直到新的父代种群大小与原种群P大小相同.多样性变量的优化过程如下.
Step1： 输入当前种群P，多样性变量集合DV，初始化下1代种群Q为空；
Step2： 从种群P中随机选择|P|个个体{P1，…，Pm，…，P|p|}，对每个个体Pm(m=1，2，…，|P|)中的与多样性相关的变量值(即DV集合中指示的决策变量)，都通过levy分布产生一个新值，如此便得到|P|个新的个体，组成种群O；
心想事成的唯美句子Step3： 将种群O与种群P合并，并进行非支配排序，得到f个非支配层，Fi表示第i个非支配层；
Step4： 从非支配层的第1层开始累加，若第1层中的个体数量超过了P种群的个体数量，即|Fi|>|P|，那么首先选出F1中的极值放入Q，Fk=F1\Q; 若加到第k(k>1)层时，个体数量便超过了P种群数量，即 |F1|+…+|Fk|>|P|，|F1|+…+|Fk-1|≤|P|,那么将前k-1层的个体都放入种群Q；
Step5： 在目标空间中计算Q∪Fk中的任何两个解的角度；
杂志征稿>总胆固醇降低Step6: 如果|Q| < |P|，执行Step7，否则输出新种群Q,优化结束；
Step7： 记录Fk中每个个体与Q中个体所成角度的最小角，并将Fk中的个体按照角度从大到小排序，从中选择最大角度的个体放入Q中，转到Step6.
优化收敛性变量，以相关性分析后生成的收敛性变量子组为单位，应用二元联赛法从当前种群中循环选择较优个体，以非支配序和目标空间个体到原点的距离分别作为第1和第2选择依据.通过levy变异策略产生子代，后代种群与父代种群合并，以距离和非支配序作为选择依据，从中选取较优个体生成下1代种群.收敛性变量的优化过程如下.
Step1： 输入当前种群P、收敛性变量集合CV，经过相关性分析过程后生成的子组集合sub
CVs={group1，group2，…，groupn}，n表示子组的个数；
Step2： 对种群P进行非支配排序；
Step3： 在目标空间中计算种群P中每个个体到原点的距离；
Step4： i=1；
Step5： 判断i是否小于n，如果i<n，执行后面步骤，否则输出优化后的种群P；
