(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210981192.3 (22)申请日 2022.08.16 (71)申请人 北京百度网讯科技有限公司 地址 100085 北京市海淀区上地十街10号 百度大厦2层 (72)发明人 丁建辉　曹宜超　陈珍　 (74)专利代理 机构 北京品源专利代理有限公司 11332 专利代理师 倪焱 (51)Int.Cl. G06N 20/00(2019.01) (54)发明名称 可行解的启发式策略调度方法、 装置、 设备 和介质 (57)摘要 本公开提供了一种可行解的启发式策略调 度方法、 装置、 设备、 介质、 程序产品和求解器， 涉 及运筹优化技术领域， 尤其涉及大数据和人工智 能技术。 具体实现方案为： 根据待求解问题的特 征和各启发式策略的特征确定所述各启发式策 略与待求解问题的相关度， 并根据所述相关度对 所述各启发式策略进行排序， 其中， 所述相关度 用于衡量所述待求解问题在分支定界的不同求 解状态下， 所述各启发式策略的可行解求解结果 的质量； 将所述排序的结果作为调度所述各启发 式策略的优 先级。 本公开可以为不同类型的待求 解问题确定更加匹配的优先级调度策略， 具有良 好的泛化能力， 从而在不同的类型和场景中提升 可行解的求 解效率。 权利要求书2页 说明书10页 附图3页 CN 115329982 A 2022.11.11 CN 115329982 A 1.一种可 行解的启发式策略调度方法， 包括： 根据待求解问题的特征和各启发式策略的特征确定所述各启发式策略与待求解问题 的相关度， 并根据所述相关度对所述各启发式策略进 行排序， 其中， 所述相关度用于衡量所 述待求解问题在分支定界的不同求解状态下， 所述各启发式策略的可行解求解结果的质 量； 将所述排序的结果作为调度所述各启发式策略的优先级。 2.根据权利要求1所述的方法， 其中， 所述待求 解问题的特 征包括： 所述待求解问题的原始问题中各个变量类型和约束类型的占比， 以及根据所述待求解 问题的类型 预定义的分类特 征。 3.根据权利要求1所述的方法， 其中， 所述待求 解问题的特 征包括： 在所述分支定界的任意节点的子问题中， 各个变量类型和约束类型的占比， 以及所述 任意节点所处的决策深度。 4.根据权利要求1所述的方法， 其中， 所述待求 解问题的特 征包括： 在所述分支定界的不同求解状态下， 使用所述各启发式策略得到可行解， 并且得到的 可行解的质量得到提升的累计次数和累计提升幅度； 以及 在所述分支定界的不同求解状态下， 使用所述各启发式策略没有得到可行解的累计次 数。 5.根据权利要求1所述的方法， 其中， 所述启发式策略的特 征包括： 根据所述各启发式策略的类型预定义的类型特征， 以及根据所述各启发式策略的默认 优先级确定的优先级特 征。 6.根据权利要求1所述的方法， 其中， 所述启发式策略的特 征包括： 基于所述各启发式策略的唯一性配置的共享特征， 其中， 所述共享特征通过低维稠密 向量表示。 7.根据权利要求1所述的方法， 其中， 所述根据待求解问题的特征和各启发式策略的特 征确定所述各启发式策略与待求解问题的相关度， 并根据所述相关度对所述各启发式策略 进行排序， 包括： 利用预先训练 的排序模型， 根据待求解问题的特征和各启发式策略的特征确定所述各 启发式策略与待求 解问题的相关度， 并根据所述相关度对所述各启发式策略进行排序。 8.根据权利要求7 所述的方法， 其中， 所述 排序模型的训练过程包括： 采集多个历史已求解问题在分支定界的不同求解状态下， 所述各启发式策略的可行解 求解结果； 根据所述可 行解求解结果构建所述各启发式策略的排序结果标签； 分别提取所述多个历史已求解问题的特征和各启发式策略的特征， 根据 所述提取的特 征和所述 排序结果标签构建训练样本； 利用所述训练样本训练所述 排序模型。 9.根据权利要求8所述的方法， 其中， 所述排序模型的训练过程是采用文档对方法进行 优化的； 相应的， 所述各启发式策略的排序 结果标签用于表示任意两个启发式策略组成的策略 对是否满足顺序关系。权　利　要　求　书 1/2 页 2 CN 115329982 A 210.根据权利要求1所述的方法， 其中， 所述待求 解问题为混合整数规划问题。 11.一种可 行解的启发式策略调度装置， 包括： 排序模块， 用于根据待求解问题的特征和各启发式策略的特征确定所述各启发式策略 与待求解问题的相关度， 并根据所述相关度对所述各启发式策略进 行排序， 其中， 所述相关 度用于衡量所述待求解问题在分支定界的不同求解状态下， 所述各启发式策略的可行解求 解结果的质量； 优先级确定模块， 用于将所述 排序的结果作为调度所述各启发式策略的优先级。 12.一种电子设备， 包括： 至少一个处 理器； 以及 与所述至少一个处 理器通信连接的存 储器； 其中， 所述存储器存储有可被所述至少一个处理器执行的指令， 所述指令被所述至少一个处 理器执行， 以使 所述至少一个处理器能够执行权利要求 1‑10中任一项 所述的可行解的启发 式策略调度方法。 13.一种存储有计算机指令的非瞬时计算机可读存储介质， 其中， 所述计算机指令用于 使所述计算机执 行根据权利要求1 ‑10中任一项所述的可 行解的启发式策略调度方法。 14.一种计算机程序产品， 包括计算机程序/指令， 所述计算机程序/指令在被处理器执 行时实现根据权利要求1 ‑10中任一项所述的可 行解的启发式策略调度方法。 15.一种求 解器， 包括： 可行解优化模块， 用于根据待求解问题的特征和各启发式策略的特征确定所述各启发 式策略与待求解问题的相关度， 并根据所述相关度对所述各启发 式策略进 行排序， 其中， 所 述相关度用于衡量所述待求解问题在分支定界的不同求解状态下， 所述各启发式策略的可 行解求解结果的质量； 将所述 排序的结果作为调度所述各启发式策略的优先级； 求解模块， 用于利用分支定界法求解所述待求解问题， 并在分支定界的每个节点调用 所述可行解优化模块， 获取与所述节点对应的各启发式策略的优先级， 在所述节点按照所 述优先级 进行各启发式策略的调度。权　利　要　求　书 2/2 页 3 CN 115329982 A 3