(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 20221078146 5.X (22)申请日 2022.07.05 (65)同一申请的已公布的文献号 申请公布号 CN 114862067 A (43)申请公布日 2022.08.05 (73)专利权人 北京邮电大 学 地址 100876 北京市海淀区西土城路10号 北京邮电大 学 (72)发明人 翁迅　张经天　胡晓　范宏强　 张静　曹忠辉　 (74)专利代理 机构 北京路浩知识产权代理有限 公司 11002 专利代理师 梁军丽 (51)Int.Cl. G06Q 10/04(2012.01)G06Q 10/06(2012.01) G06Q 10/08(2012.01) G06N 3/12(2006.01) (56)对比文件 CN 103384354 A,2013.1 1.06 CN 110097218 A,2019.08.0 6 CN 108320 062 A,2018.07.24 US 20183 56802 A1,2018.12.13 US 201908024 4 A1,2019.0 3.14 田旻 等.分层混合遗传算法求 解柔性作业 车间调度问题. 《工业工程与管理》 .2017,(第0 5 期), 审查员 张千 (54)发明名称 基于记忆精英种群的灾变自适应大邻域搜 索方法及装置 (57)摘要 本发明提供一种基于记忆精英种群的灾变 自适应大邻域搜索方法及装置， 属于人工智能技 术领域。 所述方法包括： 构建任务分配优化模型； 该模型包括目标函数和多个约束条件， 目标函数 用于表征最小化机器人的最大完工时间， 多个约 束条件包括任务分配约束条件和任务优先级约 束条件； 初始化搜索种群和精英种群； 通过迭代 执行以下步骤来求解该模型， 直至迭代次数大于 终止迭代次数： 针对搜索种群中的每个解， 采用 自适应大邻域搜索算法对当前解进行邻域搜索， 并检测当前解是否被更新； 若是， 则对精英种群 进行相应更新； 若否， 则在满足灾变条件时从当 前的精英种群中随机选择一个解对当前解进行 更新， 可以弥补自适应大邻域搜索过程的无记忆 性和提高搜索深度。 权利要求书5页 说明书19页 附图8页 CN 114862067 B 2022.11.18 CN 114862067 B 1.一种基于记 忆精英种群的灾变自适应大邻域搜索方法， 其特 征在于， 包括： 构建任务分配优化模型； 其中， 所述任务分配优化模型包括目标函数和多个约束条件， 所述目标函数用于表征最小化机器人的最大完工时间， 所述多个约束 条件包括任务分配约 束条件和任务优先级约束条件； 初始化搜索种群和精英种群； 通过迭代执行以下步骤来求解所述任务分配优化模型， 直至迭代次数大于终止迭代次 数： 针对所述搜索种群中的每个解， 采用自适应大邻域搜索算法对当前解进行邻域搜索， 并检测所述当前解是否被更新； 若所述当前解被更新， 则对所述精英种群进行相应更新； 若所述当前解未被更新， 则在满足灾变条件时从当前的所述精英种群中随机选择一个 解对所述当前解进行 更新； 所述对所述精英种群进行相应更新， 包括： 计算预设数值与第 一比值之间的乘积的正弦值， 所述第 一比值为当前迭代次数和所述 终止迭代次数之间的比值； 根据所述 正弦值将所述精英种群划分为 最优精英种群和记 忆精英种群； 更新所述 最优精英种群中的所有解 为种群最优解； 针对所述记忆精英种群中的每个解， 若所述解的适应度大于所述当前解的适应度， 则 按照第一预设概 率更新所述 解为所述当前解； 若所述解的适应度不大于所述当前解的适应度， 则按照第 二预设概率更新所述解为所 述当前解； 其中， 所述第 一预设概率为说服概率， 所述第 二预设概率为1减去所述说服概率所得到 的差值； 所述若所述当前解未被更新， 则在满足灾变条件时从当前的所述精英种群中随机选择 一个解对所述当前解进行 更新， 包括： 针对每次邻域搜索， 若该次邻域搜索后所述当前解未被更新， 则将所述当前解对应的 灾变计数器加一； 在满足所述当前解对应的灾变计数器大于预设阈值的灾变条件时， 从当前的所述精英 种群中随机 选择一个解对所述当前解进行 更新。 2.根据权利要求1所述的基于记忆精英种群的灾变自适应大邻域搜索方法， 其特征在 于， 所述采用自适应大邻域搜索算法对当前解进行邻域搜索， 包括： 从当前解关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子， 并利 用所述目标移除算子和目标插 入算子依次对所述当前解进行处 理， 得到邻域 解； 计算所述邻域 解的适应度； 基于接受准则， 更新所述当前解、 历史邻域 最优解和种群最优解； 根据权重更新规则， 更新所述当前解关联的多个移除算子和插 入算子的权 重。 3.根据权利要求2所述的基于记忆精英种群的灾变自适应大邻域搜索方法， 其特征在 于， 所述从当前解关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子， 包括：权　利　要　求　书 1/5 页 2 CN 114862067 B 2基于当前解关联的每个候选算子的权重， 计算所述候选算子的选择概率； 其中， 所述候 选算子为移除算子或插 入算子； 基于所述 候选算子的选择概 率计算所述 候选算子的累积概 率； 生成一个随机数， 所述随机数 大于0且小于等于1； 若所述候选算子的累积概率大于等于所述随机数、 且所述候选算子的前序算子的累积 概率小于所述随机数， 则选中所述 候选算子为目标移除算子或目标插 入算子。 4.根据权利要求2或3所述的基于记忆精英种群的灾变自适应大邻域搜索方法， 其特征 在于， 所述移除算子包括： 随机路径移除算子、 最坏路径移除算子、 随机移除算子和随机移 除不重复任务 算子中的至少一个移除算子； 其中， 所述随机路径移除算子用于随机移除一个机器人的所有任务， 所述最坏路径移 除算子用于移除最大完工时间对应的机器人的所有任务， 所述随机移除算子用于随机移除 若干任务并保证命中相同货架的所有任务被同步移除， 所述随机移除不重复任务算子用于 随机移除命中货架不重复的任务。 5.根据权利要求2或3所述的基于记忆精英种群的灾变自适应大邻域搜索方法， 其特征 在于， 所述插入算子包括： 优先级随机插入算子、 优先级随机概率插入算子、 优先级基本任 务时间插 入算子和优先级基本任务时间概 率插入算子中的至少一个插 入算子； 其中， 所述优先级随机插入算子用于按照优先级数值升序、 同优先级内随机乱序的规 则确定多个待插入任务的顺序， 针对每个待插入任务， 若在已分配任务列表中存在与所述 待插入任务命中货架相同的目标任务， 则将所述待插入任务插入与所述目标任务相邻的位 置； 若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务， 则选择基 础完工时间最小的机器人为接收方， 以插入成本增量最小的方式确定出所述待插入任务的 插入位置， 并在所述待插 入任务的插 入位置插 入所述待插 入任务； 所述优先级随机概率插入算子用于按照优先级数值升序、 同优先级内随机乱序的规则 确定多个待插入任务的顺序， 针对每个待插入任务， 若在已分配任务列表中存在与所述待 插入任务命中货架相同的目标任务， 则将所述待插入任务插入与所述目标任务相邻的位 置； 若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务， 则以预设 命中概率选择基础完工时间最小的机器人为接收方， 以插入成本增量最小的方式确定出所 述待插入任务的插 入位置， 并在所述待插 入任务的插 入位置插 入所述待插 入任务； 所述优先级基本任务 时间插入算子用于按照优先级数值升序、 同优先级按基础任务 时 间降序的规则确定多个待插入任务的顺序， 针对每个待插入任务， 若在已分配任务列表中 存在与所述待插入任务命中货架相同的目标任务， 则将所述待插入任务插入与所述目标任 务相邻的位置； 若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任 务， 则选择基础完工时间最小的机器人为接 收方， 以插入成本增 量最小的方式确定出所述 待插入任务的插 入位置， 并在所述待插 入任务的插 入位置插 入所述待插 入任务； 所述优先级基本任务 时间概率插入算子用于按照优先级数值升序、 同优先级按基础任 务时间降序的规则确定多个待插入任务的顺序， 针对每个待插入任务， 若在已分配任务列 表中存在与所述待插入任务命中货架相同的目标任务， 则将所述待插入任务插入与所述目 标任务相 邻的位置； 若在已分配任务列 表中不存在与所述待插入任务命中货架相同的目标 任务， 则以预设命中概率选择基础完工时间最小的机器人为接 收方， 以插入成本增 量最小权　利　要　求　书 2/5 页 3 CN 114862067 B 3