(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111674697.7 (22)申请日 2021.12.31 (71)申请人 杭州电子科技大 学 地址 310018 浙江省杭州市钱塘新区白杨 街道2号大街1 158号 申请人 新华三技术有限公司 (72)发明人 周青　陈文冲　谌平　吴正熠　 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/12(2006.01) G06Q 10/08(2012.01) G06Q 30/02(2012.01) G06Q 50/04(2012.01) G06F 111/04(2020.01) G06F 111/06(2020.01) G06F 111/10(2020.01) (54)发明名称 基于嵌套NSGA-II的多目标双层交互 式优化 方法 (57)摘要 本发明公开了一种基于嵌套 NSGA‑II的多目 标双层交互 式优化方法， 步骤包括： S1、 多目标双 层交互式优化模型构建； S2、 上层主 导者NSGA ‑II 的实现； S3、 下层 跟随者NSGA ‑II的实现； S4、 上下 层NSGA‑II交互式迭代。 本发明考虑一个多目标 主导者和多个多目标跟随者的双层交互式优化 问题， 可以同时实现分层多目标和上下层多目标 的协同和Pareto改善， 具有重要的实际应用背景 与价值； 设计了嵌套NSGA ‑II对多目标双层交互 式优化问题进行求解， 主要技术特点包括隔板 法、 单点放缩法等处理复杂的等式或不等式约 束， 多染色体并行下传， 下层Pareto前沿解最优 组合搜索与上传， 上下层NSGA ‑II交互迭代式优 化， 算法流程设计合理， 可极大的提高算法搜索 效率。 权利要求书2页 说明书12页 附图2页 CN 114519297 A 2022.05.20 CN 114519297 A 1.一种基于嵌套NSGA ‑II的多目标双 层交互式优化方法， 其特 征在于， 步骤 包括： S1、 多目标双 层交互式优化模型构建； S2、 上层主导 者NSGA‑II的实现 S2‑1、 染色体编码和种群初始化， 采用二进制编码， 根据变量取值空间确定二进制编码 长度； 对于约束简单的决策变量， 采用传统随机生成法产生符合约束 条件的变量值； 对于累 加型的等式或不 等式约束， 采用隔板法来随机生成决策变量 值； S2‑2、 解码与适应度函数值计算， 对二进制编码进行实数解码， 以确定变量取值， 并将 对应的变量 值传递至下层规划问题； S2‑3、 非支配排序和拥挤度计算， 对每个染色体进行非支配性排序形成非支配前沿， 然 后， 对非支配前沿进行拥挤距离计算； S2‑4、 交叉、 变异操作， 采取多点交叉和多点逆序变异的方式进行交叉、 变异操作； S2‑5、 变量取值 修复， 通过回归边界值和多点缩放两种方法进行变量取值 修复； S2‑6、 终止条件判断与Pareto前沿输出， 判断迭代次数是否超过预设的最大迭代次数， 若不超过， 继续迭代； 否则， 终止算法， 并输出对应的最优Pareto前沿； S3、 下层跟随者 NSGA‑II的实现； S4、 上下层NSGA ‑II交互式迭代。 2.根据权利要求1所述的基于嵌套NSGA ‑II的多目标双层交互式优化方法， 其特征在 于， 所述步骤S1中， 多目标双 层交互式优化模型的构建方法： 设x为上层决策变量集， y为下层决策变量集， M为跟随着数量， 则通用的数学模型可表 示为： s.t.G(x,y)≤ 0   (2) 变量y取决于下层问题： s.t.gj(y)≤0   (4) 其中， i,i'∈I为上层主导者的决策目标， j∈M为下层跟随者索引， G(x,y)为上层主导 者的约束条件， gj(y)≤0为第j个跟随者的约束条件。 3.根据权利要求1所述的基于嵌套NSGA ‑II的多目标双层交互式优化方法， 其特征在 于， 所述步骤S2‑3中所述拥挤距离的计算方法如下： 设θ 为染色体种群集， k∈ θ 为染色体索引， 则拥挤度计算公式如下： 其中， k'是根据目标函数值Fik排序后染色体k的下标， Fik表示染色体k的第i个目标函数 值， λk是NSGA‑II染色体k的拥挤度， Fik'‑1和Fik'+1表示以第i个目标函数值排序后， 染色体k 前后个体的目标函数值。 4.根据权利要求1所述的基于嵌套NSGA ‑II的多目标双层交互式优化方法， 其特征在 于， 所述步骤S3中， 下层跟随者 NSGA‑II的实现方法：权　利　要　求　书 1/2 页 2 CN 114519297 A 2S3‑1、 下层规划模型初始化， 根据接收到的上层 决策变量集x的取值， 确定下层跟随者 的决策模型； S3‑2、 染色体编码和种群初始化， 采用二进制编码， 根据下层决策变量确定二进制编码 的长度， 同上层NSGA ‑II， 随机生成满足约束的初始种群； S3‑3、 解码和适应度函数值计算， 对二进制染色体进行实数解码， 以确定变量取值； 根 据目标函数fi'j(y)， 确定下层染色体对应的适应度函数值； S3‑4、 染色体选择、 交叉、 变异、 变量取值修复， 根据下层染色体适应度函数值， 对染色 体进行非支配排序和拥挤度计算， 选择遗传的个体， 其中拥挤度计算参加公式(5)， 并按照 上层NSGA ‑II的方式进行交叉、 变异、 变量取值 修复操作； S3‑5、 终止条件判断与Pareto前沿输出， 判断迭代次数是否超过预设的最大迭代次数， 若不超过， 继续迭代； 否则， 终止算法， 并输出每 个子跟随者对应的最优Pareto前沿。 5.根据权利要求1所述的基于嵌套NSGA ‑II的多目标双层交互式优化方法， 其特征在 于， 所述步骤S4包括： S4‑1、 上层可 行解的下传； S4‑2、 下层可 行解组合的上传。 6.根据权利要求5所述的基于嵌套NSGA ‑II的多目标双层交互式优化方法， 其特征在 于， 所述步骤S4 ‑1中， 上层可行解的下传方法为， 通过并行搜索算法 的原理， 同时将多个上 层染色体下传给下层NSGA ‑II， 下层NSGA ‑II同时搜索每个上层染色体对应的下层Pareto前 沿解。 7.根据权利要求5所述的基于嵌套NSGA ‑II的多目标双层交互式优化方法， 其特征在 于， 所述步骤S4 ‑2中， 下层可行解组合的上传的方法为， 在下层问题输出Paret o前沿后再嵌 入一个NSGA ‑II， 以搜索最优的Pareto前沿解组合； 该NSGA ‑II将采用实数编码的方式进行 染色体设计， 如染色体{5,4,3,3,4,1,3,4,6,4}； 其中元素5表示第一个跟随者的第5个 Pareto前沿解， 第二个元素4表 示第五个跟随者的第4个Pareto前沿解， 以此类推； 染色体对 应的适应度函数值由目标函数 Fi(x,y)确定； 交叉和变异的方式为多点交叉和单点变异。 8.根据权利要求6所述的基于嵌套NSGA ‑II的多目标双层交互式优化方法， 其特征在 于， 所述步骤S4‑1中， 下层NSGA ‑II的启动， 需要以上层NSGA ‑II的染色体信息为基础。 9.根据权利要求7所述的基于嵌套NSGA ‑II的多目标双层交互式优化方法， 其特征在 于， 所述步骤S4‑2中， 上层染色体的适应度函数值计算依赖 于下层子问题的可 行解。权　利　要　求　书 2/2 页 3 CN 114519297 A 3