(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202110869302.2 (22)申请日 2021.07.3 0 (71)申请人 南京信息 工程大学 地址 210044 江苏省南京市江北新区宁六 路219号 (72)发明人 申晓宁　陈庆洲　潘红丽　徐继勇　 姚铖滨　许笛　葛忠佩　 (74)专利代理 机构 南京钟山专利代理有限公司 32252 代理人 戴朝荣 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/08(2006.01) G06F 111/04(2020.01) G06F 111/06(2020.01) (54)发明名称 一种多目标背 包问题的混合蛙 跳求解方法 (57)摘要 本发明公开了一种多目标背包问题的混合 蛙跳求解方法， （1） 问题信息读取， 包括每个背包 的每个货物的价值与重量信息和每个背包重量 限制信息； （2） 初始化算法参数； （3） 计算种群中 所有个体的目标值， 确定非支 配解集放入外部存 储器； （4） 进入快速收敛阶段， 对种群根据快速非 支配排序结果使用 “S”型分组方式划分子组， 对 各个子组进行基于离散跳跃规则和贪婪生成的 局部搜索， 将各子组混洗， 更新外部存储器， 判断 目标评价次数是否满足快速收敛阶段终止条件， 若不满足， 则继续迭代， 若满足， 则进入下一阶 段； （5） 进入探索扩展阶段； （6） 进入极值挖掘阶 段。 本发明具有搜索速度快， 搜索能力强， 规划的 背包利润高的优点。 权利要求书3页 说明书10页 附图2页 CN 113887122 A 2022.01.04 CN 113887122 A 1.一种多目标背包问题的混合蛙 跳求解方法， 其特 征在于， 包括以下步骤： S1， 读取问题输入的信息， 定义优化目标， 设定约束条件； S2， 初始化 新型多目标混合蛙 跳算法参数； S3， 生成初始种群， 使用放松约束修复策略处 理后， 计算优化目标值fj； S4， 根据目标值选出当前种群Pop中所有非支配解 放入外部存储器A； S5， 进入快速收敛阶段： 对种群Pop根据快速非支配排序结果使用 “S”型分组方式划分 子组MPopi； S6， 对各子组局部 搜索； S7， 混洗所有子组， 使用支配关系更新外部存储器A， 判断是否满足快速收敛阶段终止 条件， 若满足， 则终止快速收敛阶段迭代， 进入下一阶段， 否则转S4； S8， 进入探索扩展阶段： 依次根据目标fj使用前沿划分策略从外部存储器A提取引导各 子群探索的引导集Aj， 依次根据目标fj将种群Pop分为m个子群CPopj， 对每个子群根据快速 非支配排序结果使用 “S”型分组方式划分子组MPopi； S9， 对各子群CPopj的各子组MPopi局部搜索； S10， 混洗所有子组， 对目标向量重复的解进行降重操作， 使用支配关系更新外部存储 器A， 判断是否满足探索 扩展阶段终止条件， 若满足， 则终止探索扩展阶段迭代， 进入下一阶 段， 否则转 步骤S8； S11， 进入极值挖掘阶段： 依次根据目标fj将种群Pop分为m个子群CPopj， 对每个子群根 据降序排序结果使用 “S”型分组方式划分子组MPopi； S12， 对各子群CPopj的各子组MPopi局部搜索； S13， 混洗所有子组， 对重复解进行降重操作， 使用支配关系更新外部存储器A， 判断是 否满足极值挖掘阶段终止条件， 若满足， 则终止 极值挖掘阶段迭代， 输出外部存储器A； 否则 转S11。 2.根据权利要求1所述的多目标背包问题的混合蛙跳求解方法， 其特征在于， S1中， 所 述问题的输入信息包括每个背包的每个货物的价值与重量信息和问题规模n； 所述优化 目 标为最大化每个背包中物品的总利润； 所述约束条件为每个背包都有一个重量上限， 放入 每个背包中的物品的总重量 不能超过 该背包的重量上限。 3.根据权利要求2所述的多目标背包问题的混合蛙跳求解方法， 其特征在于， S1中， 所 述读取问题输入的信息， 定义优化目标， 设定约束条件的过程包括以下步骤： 设定问题的规模表示每 个背包可放入物品的数量 n； 定义优化目标主体为每 个背包的总利 润的大小， 其定义 为： 其中， fj表示第j个背包的总利润； X表示决策变量xi的集合； xi表示背包里的第i个物品 是否放入各个背包中； pij表示第j个背包中第i个物品的利 润； 定义约束条件 包括以下两个：权　利　要　求　书 1/3 页 2 CN 113887122 A 2(1)第j个背包的重量限制cj， 即： 其中， n是 可放入第j个背包中物品的数量； wij是可放入第j个背包中第i个物品的重量； (2)第j个背包中放入物品的总重量 不能超过 该背包的重量限制， 即： 4.根据权利要求1所述的多目标背包问题的混合蛙跳求解方法， 其特征在于， S2中， 在 每次生成新个体后， 若新个体超出约束 条件限制， 则使用放松约束修复策略进 行处理， 将不 可行解修复为可 行解， 具体步骤如下： S21、 计算每 个背包中每 个物品的利 润pij/重量wij； S22、 依次计算第i个物品在所有背包中利润pij/重量wij的均值AKi， 重复S22， 直至每个 物品在所有 背包中利 润重量比的均值计算完毕； S23、 对背包内的物品， 将AKi最小的一个物品移出背包； S24、 对背包外的物品， 在 AKi取值最大的k个物品中随机选 取一个放入背包中； 若背包外 的物品数 大于5， 则令k＝5， 否则， 令k ＝背包外的物品数； S25、 计算此时每个背包中物品的总重量， 若满足每个背包的重量限制， 则输出可行解， 若不满足， 转至S23 。 5.根据权利要求1所述的多目标背包问题的混合蛙跳求解方法， 其特征在于， S5中， 所 述“S”型分组方式具体为： 假设将规模为m*N且排序后的种群Pop分成e个子组， 每组m*b个个体， 满足m*N＝e*m*b； 将第1至e个个体依次放入第1至e组， 第w+1至2*e个个体倒序放入第w组至第1组， 第2*e+1至 3*e个个体依次放入第1至e组， 以此类 推。 6.根据权利要求1所述的多目标背包问题的混合蛙跳求解方法， 其特征在于， S6包括， 从外部存储器A 中随机选取w个个体分配为每个子组MPopi的专属全局最优解Xig， 采用离散 跳跃规则和贪婪生成策略作为个体生成方式， 并根据优胜劣汰的规则更新局部最劣Xiw， 每 个子组进行局部 搜索L次， t＝t+m*N； 所述离散跳跃规则具体实现步骤如下： S61， 确定需要跳跃的劣解Xw和被学习的优解Xb； S62， 计算优解Xb和劣解Xw之间的汉明距离dis， 将优解和劣解取值不同的基因位索引存 放在集合dif中， 取值相同的基因位索引存放在集 合same中； S63， 从集合 dif中随机选取 向上取整的β ％*dis个基因位， 将对应基因位上优解Xb赋予 劣解Xw对应的基因位上； β ％为信息 接收百分比； S64， 选取集合same中的一个基因位， 通过生成一个[0， 1]之间的随机数rand， 若rand< pm， 则劣解Xw对应的基因位上的取值翻转， 重复步骤S64， 直至集 合same中的基因位选取完； S65， 输出劣解Xw经过离散跳跃规则改进的新 解Xwn。 7.根据权利要求6所述的多目标背包问题的混合蛙跳求解方法， 其特征在于， S6中， 所 述贪婪生成策略具体实现步骤如下：权　利　要　求　书 2/3 页 3 CN 113887122 A 3