技术领域
本发明涉及一种多目标元胞差分的优化方法。
背景技术
在科学和工程领域存在大量的多目标优化问题。多目标优化问题与单目标优化问 题的本质区别在于，前者的解不是唯一的，而是一个折中的解集，即Pareto解集。传统多目 标优化算法包括加权法、约束法和目标规划法等。这些方法都是将多目标问题转换为单目 标问题，其缺点是需要充分的先验知识，而且难以处理目标噪声，鲁棒性较差。由于多目标 优化问题的目标函数和约束可能是非线性、不可微或不连续的，传统的数学规划方法往往 效率较低，且它们对于权重值或目标给定的次序较敏感。
进化方法是一种模拟自然进化过程的随机全局优化方法，它采用群体搜索和群体 中个体间信息交换的方式搜索问题的解。与传统方法相比，其优点在于：首先，进化搜索过 程具有随机性，不易陷入局部最优；其次，它具有并行性，能够同时进化寻找到多个解，适合 多目标优化问题；第三，能够处理不连续，不可微和Pareto前沿非凸等问题，不需要过多先 验知识。
目前，既有的对元胞自动机应用于遗传算法的研究大体分为两类：第一类用元胞 自动机丰富的演化规则来替代传统遗传算法中的某些遗传操作；第二类则以复杂系统理论 为基础，它将种群中的个体分配到元胞空间中，借助元胞自动机模型的邻居结构来实现优 良的解在种群中扩散及引导其他解的进化。通过不断执行局部的遗传操作，最终实现整个 种群的进化。元胞遗传方法中，这种解的扩散作用可以使解在搜索过程中能很好地保持整 体搜索和局部寻优的良好平衡，从而有效地避免陷入局部最优。2007年，Alba等在优化城市 自组网广播策略中，提出了cMOGA。Nebro等对cMOGA进行了改进，增加了外部种群的反馈机 制，提出了MOCell。为了能更好地解决三目标问题，Durillo等将MOCell与DE算法混合，提出 了CellDE。张屹等采用一种新的优良个体的替换方法，提出了DECell。
现有的多目标元胞差分方法往往采用外部存档集来收集一些非支配的解，然后在 每代进化结束后，由外部存档集向种群反馈一定数量的非支配解。这种反馈机制不利于 Pareto前端的分布均匀性及覆盖范围，因为这种策略没有从整个种群角度来考虑Pareto前 端的分布。
发明内容
本发明要克服现有技术的上述缺点，提供一种多目标元胞差分的优化方法。
本发明所述的多目标元胞差分方法，包括如下步骤：
1、创建多目标函数，对于含约束的多目标问题，还需要创建约束条件。
2、对种群进行随机初始化，即对每个个体的决策变量随机初始化。计算每个个体 的目标函数值，再将种群中的个体随机分布到二维环形网格中，并将当前种群存入外部存 档集。
3、从每个当前个体的周围邻居中通过二元锦标赛选出两个较优秀的个体，将它们 与当前个体共同作为父本，然后进行差分变异、交叉操作获得子代，并计算子代的目标函数 值。
元胞自动机的邻居结构有很多，这里采用Moore型邻居结构。在Moore型中，一个元 胞的上、下、左、右、左上、左下、右上、右下相邻的八个元胞为该元胞的邻居。
设种群规模为N，d为解空间的维数。xr1、xr2、xr3为三个父本。vi为变异向量，ui为子 代向量。
(a)差分变异操作
vi.j＝xr1.j+F·(xr2.j-xr3.j)，i∈[1,N]，j∈[1,d]
F为介于[0,1]间的缩放因子。
(b)差分交叉操作
randi.j为[0,1]之间均匀分布的随机数，CR为介于[0,1]间的交叉常量，randj∈ [1,2,…,d]。
4、根据秩与拥挤距离，选出邻居中的最差者。整个进化过程根据替换策略的不同 分为两个阶段。在第一阶段，采用替换策略Ⅰ进化。在第二阶段，采用替换策略Ⅱ进化。
替换策略Ⅰ:如果新产生的个体不被当前个体与邻居中的最差个体支配，则对当前 个体及邻居中的最差者进行替换，并将新产生的个体加入外部存档集。
替换策略Ⅱ:一旦新产生的个体支配当前个体或邻居中的最差个体，则对当前个 体或邻居中的最差者进行替换，并将当前个体加入外部存档集。
5、重复3与4的步骤，直到完成最后一个个体的进化。
6、在每代进化结束后，根据秩与拥挤距离对外部存档集的个体进行排序(秩低的 排在前；秩相同的个体比较拥挤距离，拥挤距离大的排在前面)，并剔除超过种群规模的个 体。
7、将整个外部存档集中的个体作为下一次进化的种群，并将其随机分布到二维网 格中，继续进化直至满足进化的终止条件。
常规的元胞差分方法采用了部分反馈机制，具体的操作过程是这样的：使用外部 存档集来收集进化过程中的非支配解，然后在当代进化结束后，从外部存档集选取一定数 量的非支配解(一般为种群数量的20％)来替代从网格中随机选取的个体。
本专利提出了一种新的反馈机制：在每代进化之前，将父代种群加入外部存档集 中，同时外部存档集又被用来收集进化过程中的非支配解，然后在当代进化结束后，根据秩 与拥挤距离剔除超过种群规模的非支配个体，将剩余的所有个体作为下一代的父本，并将 它们随机分配到二维环形网状结构中。
本发明提出了一种新的多目标元胞差分方法，其反馈机制和替换策略作了根本性 改变。新的反馈机制是从整个Pareto前端的分布角度出发的，它强化了整个种群在搜索中 的作用，同时将整个种群的个体随机分布到二维环形网状结构中，又可以很好地避免整个 种群陷入局部最优。替换策略Ⅰ考虑到了Moore型邻居结构中互不支配的个体在整个种群中 的优劣是不确定的，因此采取了将与父代以及最差邻居互不支配的子代收集起来的策略。 为了进一步提高解的收敛性，提出了替换策略Ⅱ。测试表明：新的反馈机制和新的替换策略 改善了解的前端分布均匀性，提高了前端的覆盖范围。
本发明的优点是：改善了解的前端分布均匀性，提高了前端的覆盖范围。
附图说明
图1是NCellDE方法实施流程。
图2是Moore型邻居结构。
图3是两种方法求解Osyczka2时获得的Pareto前端。
图4是两种方法求解DTLZ2时获得的Pareto前端。
图5是减速器结构示意图。
图6是对减速器优化获得的Pareto前端。
具体实施方式
下面结合附图，进一步说明本发明。
本发明所述的新的反馈机制和替换策略的多目标元胞差分方法(NCellDE)。其流 程如图1所示。
具体步骤如下：
1、创建多目标函数，对于含约束的多目标问题，还需要创建约束条件。
2、对种群进行随机初始化，即对每个个体的决策变量随机初始化。计算每个个体 的目标函数值，再将种群中的个体随机分布到二维环形网格中，并将当前种群存入外部存 档集。
3、从每个当前个体的周围邻居中通过二元锦标赛选出两个较优秀的个体，将它们 与当前个体共同作为父本，然后进行差分变异、交叉操作获得子代，并计算子代的目标函数 值。
元胞自动机的邻居结构有很多，这里采用Moore型邻居结构(图2)。在Moore型中， 一个元胞的上、下、左、右、左上、左下、右上、右下相邻的八个元胞为该元胞的邻居。
设种群规模为N，d为解空间的维数。xr1、xr2、xr3为三个父本。vi为变异向量，ui为子 代向量。
(a)差分变异操作
vi.j＝xr1.j+F·(xr2.j-xr3.j)，i∈[1,N]，j∈[1,d]
F为介于[0,1]间的缩放因子。
(b)差分交叉操作
randi.j为[0,1]之间均匀分布的随机数，CR为介于[0,1]间的交叉常量，randj∈ [1,2,…,d]。
4、根据秩与拥挤距离，选出邻居中的最差者。整个进化过程根据替换策略的不同 分为两个阶段。在第一阶段，采用替换策略Ⅰ进化。在第二阶段，采用替换策略Ⅱ进化。
替换策略Ⅰ:如果新产生的个体不被当前个体与邻居中的最差个体支配，则对当前 个体及邻居中的最差者进行替换，并将新产生的个体加入外部存档集。
替换策略Ⅱ:一旦新产生的个体支配当前个体或邻居中的最差个体，则对当前个 体或邻居中的最差者进行替换，并将当前个体加入外部存档集。
5、重复3与4的步骤，直到完成最后一个个体的进化。
6、在每代进化结束后，根据秩与拥挤距离对外部存档集的个体进行排序(秩低的 排在前；秩相同的个体比较拥挤距离，拥挤距离大的排在前面)，并剔除超过种群规模的个 体。
7、将整个外部存档集中的个体作为下一次进化的种群，并将其随机分布到二维网 格中，继续进化直至满足进化的终止条件。
性能测试
为了评价算法的性能，这里采用世代距离(GD)、分布指标(△)和超体积指标(HV) 对算法进行评价。GD越小，表明解的收敛性越好。△越小，表明Pareto前端分布越均匀。HV越 大，说明获得的Pareto前端的多样性、收敛性越好，即前端覆盖性越好。为了验证其性能，将 NCellDE与CellDE作测试对比。选择3个无约束的多目标测试函数(ZDT2、ZDT3、DTLZ2)和1个 含有约束的多目标测试函数(Osyczka2)对这两种方法进行测试。在测试中，设种群规模为 100，最大进化代数5000代，交叉常量CR＝0.5，缩放因子F＝0.6。NCellDE的最后1000代采用 策略Ⅱ继续进化。两种方法求解Osyczka2、DTLZ2问题时获得的Pareto前端如图3、图4所示， 同时表1-表3分别给出了两种算法关于△、GD、HV三种指标的统计结果。
图3和图4直观地反映了NCellDE获得的Pareto前端要比CellDE获得的前端更加均 匀。
表1分布均匀性指标△
表2覆盖性指标HV
表3收敛性指标GD
由表1、表2可知，NCellDE所获得的Pareto前端的分布均匀性、覆盖性指标要优于 CellDE。由表3可知，在ZDT2与Osyczka2测试中，NCellDE的世代距离(GD)比CellDE略大，而 在ZDT3与DTLZ2中，NCellDE要优于CellDE。综上所述，本专利求得的解，其综合性能更好。
应用实例-减速器的优化设计
1、设计要求
减速器的优化设计是一个经典的含约束的多目标优化问题。此问题的优化目标为 减速器的体积最小(f1)，轴1的应力最小(f2)。减速器的输入功率为10kW，高速轴转速为 800r/min，转速比为3。齿轮材料的弹性模量取200GPa，齿形系数为2.54，压力角为20度，齿 轮的相对齿宽介于5～12之间。齿根的许用弯曲应力为22.5MPa，齿面的许用接触应力 346.6MPa。齿轮之间的中心距不超过80cm。第一轴1和第二轴2的挠度变形不超过0.001，第 一轴1的许用应力为1300MPa，第二轴2的许用应力为1100MPa。如图5所示，该问题的设计变 量分别为齿宽x1、齿轮模数x2、小齿轮的齿数x3、第一轴承11之间的距离x4、第二轴承22之间 的距离x5、第一轴1的直径x6、第二轴2的直径x7。
设计变量的范围为：
2.6≤x1≤3.6
0.7≤x2≤0.8
17≤x3≤28
7.3≤x4≤8.3
7.3≤x5≤8.3
2.9≤x6≤3.9
5≤x7≤5.5
2、根据设计要求，建立该问题的数学模型
s.t.
g10＝f2(x)≤1300,
g1：齿轮的弯曲应力约束条件；g2：齿轮的接触应力约束条件；g3、g4：轴的挠度约 束；g5～g7：齿轮的尺寸约束；g8、g9：轴的几何尺寸约束；g10、g11：轴的许用应力约束。
3、NCellDE优化步骤
1)创建多目标函数(式1)，创建约束条件(g1～g11)。
2)种群规模设为100，在每个变量范围内，对每个个体的设计变量随机初始化。这 里，将约束条件的违反程度转化为一个目标函数值，即再增加一个目标。计算每个个体的目 标函数值，再将种群中的个体随机分布到二维环形网格中，并将当前种群存入外部存档集。
3)从每个当前个体的周围邻居中通过二元锦标赛选出两个较优秀的个体，将它们 与当前个体共同作为父本，然后进行差分变异、交叉操作获得子代，并计算子代的目标函数 值。
(a)差分变异操作
vi.j＝xr1.j+0.6·(xr2.j-xr3.j)，i∈[1,100]，j∈[1,7]
缩放因子F设为0.6。
(b)差分交叉操作
交叉常量CR设为0.5。
4)根据秩与拥挤距离，选出邻居中的最差者。整个进化过程根据替换策略的不同 分为两个阶段。在第一阶段，采用替换策略Ⅰ进化2400代。在第二阶段，采用替换策略Ⅱ进化 800代。
NCellDE中的替换策略如下：
替换策略Ⅰ:如果新产生的个体不被当前个体与邻居中的最差个体支配，则对当前 个体及邻居中的最差者进行替换，并将新产生的个体加入外部存档集。
替换策略Ⅱ:一旦新产生的个体支配当前个体或邻居中的最差个体，则对当前个 体或邻居中的最差者进行替换，并将当前个体加入外部存档集。
5)重复3与4的步骤，直到完成最后一个个体的进化。
6)在每代进化结束后，根据秩与拥挤距离对外部存档集的个体进行排序(秩低的 排在前；秩相同的个体比较拥挤距离，拥挤距离大的排在前面)，并剔除超过种群规模的个 体，将种群规模控制在100。
7)将整个外部存档集中的个体作为下一次进化的种群，并将其随机分布到二维网 格中，继续进化直至进化到3200代。
图6给出了算法求解该问题时获得的Pareto前端。
在方法寻优时，将齿轮模数x2、小齿轮的齿数x3作为连续变量处理。考虑实际应用 场景，还要从获得的解中选取齿数为整数、模数为标准模数的解。获得的设计变量的具体值 见表4。
表4设计参数及目标函数值(共有100组)
4、根据求得优化解的结果，结合设计者的设计目标，选择相应优化解。
若设计者希望减速器的体积最小，对轴的应力并不是很关心，则可以选取序号为 75的解；若设计者希望减速器的体积尽量小，同时又希望轴的应力也尽量小，则可以选取序 号为8的解。
创新点
提出了一种新的多目标元胞差分方法，其反馈机制和替换策略作了根本性改变。 新的反馈机制是从整个Pareto前端的分布角度出发的，它强化了整个种群在搜索中的作 用，同时将整个种群的个体随机分布到二维环形网状结构中，又可以很好地避免整个种群 陷入局部最优。替换策略Ⅰ考虑到了Moore型邻居结构中互不支配的个体在整个种群中的优 劣是不确定的，因此采取了将与父代以及最差邻居互不支配的子代收集起来的策略。为了 进一步提高解的收敛性，提出了替换策略Ⅱ。测试表明：新的反馈机制和新的替换策略改善 了解的前端分布均匀性，提高了前端的覆盖范围。
