基于记忆精英种群的灾变自适应大邻域搜索方法及装置

摘要

本发明提供一种基于记忆精英种群的灾变自适应大邻域搜索方法及装置，属于人工智能技术领域。所述方法包括：构建任务分配优化模型；该模型包括目标函数和多个约束条件，目标函数用于表征最小化机器人的最大完工时间，多个约束条件包括任务分配约束条件和任务优先级约束条件；初始化搜索种群和精英种群；通过迭代执行以下步骤来求解该模型，直至迭代次数大于终止迭代次数：针对搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测当前解是否被更新；若是，则对精英种群进行相应更新；若否，则在满足灾变条件时从当前的精英种群中随机选择一个解对当前解进行更新，可以弥补自适应大邻域搜索过程的无记忆性和提高搜索深度。

权利要求

1.一种基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，包括：构建任务分配优化模型；其中，所述任务分配优化模型包括目标函数和多个约束条件，所述目标函数用于表征最小化机器人的最大完工时间，所述多个约束条件包括任务分配约束条件和任务优先级约束条件；

初始化搜索种群和精英种群；

通过迭代执行以下步骤来求解所述任务分配优化模型，直至迭代次数大于终止迭代次数：针对所述搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测所述当前解是否被更新；

若所述当前解被更新，则对所述精英种群进行相应更新；

若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新；

所述对所述精英种群进行相应更新，包括：

计算预设数值与第一比值之间的乘积的正弦值，所述第一比值为当前迭代次数和所述终止迭代次数之间的比值；

根据所述正弦值将所述精英种群划分为最优精英种群和记忆精英种群；

更新所述最优精英种群中的所有解为种群最优解；

针对所述记忆精英种群中的每个解，若所述解的适应度大于所述当前解的适应度，则按照第一预设概率更新所述解为所述当前解；

若所述解的适应度不大于所述当前解的适应度，则按照第二预设概率更新所述解为所述当前解；

其中，所述第一预设概率为说服概率，所述第二预设概率为1减去所述说服概率所得到的差值；

所述若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新，包括：针对每次邻域搜索，若该次邻域搜索后所述当前解未被更新，则将所述当前解对应的灾变计数器加一；

在满足所述当前解对应的灾变计数器大于预设阈值的灾变条件时，从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

2.根据权利要求1所述的基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，所述采用自适应大邻域搜索算法对当前解进行邻域搜索，包括：从当前解关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子，并利用所述目标移除算子和目标插入算子依次对所述当前解进行处理，得到邻域解；

计算所述邻域解的适应度；

基于接受准则，更新所述当前解、历史邻域最优解和种群最优解；

根据权重更新规则，更新所述当前解关联的多个移除算子和插入算子的权重。

3.根据权利要求2所述的基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，所述从当前解关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子，包括：基于当前解关联的每个候选算子的权重，计算所述候选算子的选择概率；其中，所述候选算子为移除算子或插入算子；

基于所述候选算子的选择概率计算所述候选算子的累积概率；

生成一个随机数，所述随机数大于0且小于等于1；

若所述候选算子的累积概率大于等于所述随机数、且所述候选算子的前序算子的累积概率小于所述随机数，则选中所述候选算子为目标移除算子或目标插入算子。

4.根据权利要求2或3所述的基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，所述移除算子包括：随机路径移除算子、最坏路径移除算子、随机移除算子和随机移除不重复任务算子中的至少一个移除算子；

其中，所述随机路径移除算子用于随机移除一个机器人的所有任务，所述最坏路径移除算子用于移除最大完工时间对应的机器人的所有任务，所述随机移除算子用于随机移除若干任务并保证命中相同货架的所有任务被同步移除，所述随机移除不重复任务算子用于随机移除命中货架不重复的任务。

5.根据权利要求2或3所述的基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，所述插入算子包括：优先级随机插入算子、优先级随机概率插入算子、优先级基本任务时间插入算子和优先级基本任务时间概率插入算子中的至少一个插入算子；

其中，所述优先级随机插入算子用于按照优先级数值升序、同优先级内随机乱序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务；

所述优先级随机概率插入算子用于按照优先级数值升序、同优先级内随机乱序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则以预设命中概率选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务；

所述优先级基本任务时间插入算子用于按照优先级数值升序、同优先级按基础任务时间降序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务；

所述优先级基本任务时间概率插入算子用于按照优先级数值升序、同优先级按基础任务时间降序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则以预设命中概率选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务。

6.根据权利要求2所述的基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，所述基于接受准则，更新所述当前解、历史邻域最优解和种群最优解，包括：若所述邻域解的适应度小于所述当前解的适应度，则以第三预设概率接受所述邻域解，并根据所述邻域解更新所述当前解、历史邻域最优解和种群最优解；

若所述邻域解的适应度大于等于所述当前解的适应度，则以第四预设概率接受所述邻域解；

其中，所述第三预设概率为犯错概率，所述第四预设概率为1减去所述犯错概率所得到的差值。

7.根据权利要求2所述的基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，所述根据权重更新规则，更新所述当前解关联的多个移除算子和插入算子的权重，包括：在当前迭代次数达到 次时，通过以下表达式更新所述当前解关联的算子 的权重，所述算子 为所述移除算子或所述插入算子：其中， 表示权重更新周期， 表示算子 的权重， 表示 次迭代中算子 的累积得分， 表示 次迭代中算子 的使用次数， 表示权重更新系数，所述当前解关联的所有算子的初始权重均为1。

8.根据权利要求1所述的基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，所述任务分配约束条件包括：

所有任务均已分配给所述机器人；

分配给所述机器人的任务不重复中；

所述任务优先级约束条件包括：

针对任务堆内部的各个任务，后序任务的优先级不能高于前序任务的优先级；

针对各个任务堆，后序任务堆的优先级不能高于前序任务堆的优先级；

其中，所述任务堆是将所述机器人的任务列表按顺序进行分堆得到的，一个所述任务堆包括命中相同货架的相邻任务，所述任务堆的优先级为所述任务堆内部的各个任务的优先级中的最高优先级。

9.根据权利要求1所述的基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，所述初始化搜索种群，包括：将全体任务按优先级从高到低排列生成第一有序集合；

针对所述第一有序集合中优先级相同的多个任务，将所述多个任务进行随机排序，得到第二有序集合；

初始化所有机器人的任务列表为空；

按照所述第二有序集合中的任务顺序，将每个任务插入当前基础完工时间最小的机器人的任务列表的末端，得到第一预备解；

计算所述第一预备解的适应度；

若所述第一预备解的适应度不等于正无穷，则将所述第一预备解加入所述搜索种群。

10.根据权利要求1所述的基于记忆精英种群的灾变自适应大邻域搜索方法，其特征在于，所述初始化精英种群，包括：将全体任务按优先级从高到低排列生成第三有序集合；

针对所述第三有序集合中优先级相同的多个任务，将所述多个任务进行随机排序，得到第四有序集合；

初始化所有机器人的任务列表为空；

按照所述第四有序集合中的任务顺序，在满足所述任务优先级约束条件时遍历所述所有机器人的任务列表中的可插入位置，计算每个所述可插入位置的插入成本增量，将每个任务插入最小的所述插入成本增量对应的所述可插入位置，得到第二预备解；

计算所述第二预备解的适应度；

若所述第二预备解的适应度不等于正无穷，则将所述第二预备解加入所述精英种群。

11.一种基于记忆精英种群的灾变自适应大邻域搜索装置，其特征在于，包括：构建模块，用于基于目标函数和任务约束条件构建任务分配优化模型；其中，所述目标函数用于表征最小化最大完工时间，所述任务约束条件用于对任务分配和任务优先级进行约束；

初始化模块，用于基于所述任务分配优化模型，初始化搜索种群和精英种群；

求解模块，用于通过迭代执行以下操作来求解所述任务分配优化模型，直至迭代次数大于终止迭代次数：针对所述搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测所述当前解是否被更新；

若所述当前解被更新，则对所述精英种群进行相应更新；

若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新；

所述求解模块具体用于：

计算预设数值与第一比值之间的乘积的正弦值，所述第一比值为当前迭代次数和所述终止迭代次数之间的比值；

根据所述正弦值将所述精英种群划分为最优精英种群和记忆精英种群；

更新所述最优精英种群中的所有解为种群最优解；

针对所述记忆精英种群中的每个解，若所述解的适应度大于所述当前解的适应度，则按照第一预设概率更新所述解为所述当前解；

若所述解的适应度不大于所述当前解的适应度，则按照第二预设概率更新所述解为所述当前解；

其中，所述第一预设概率为说服概率，所述第二预设概率为1减去所述说服概率所得到的差值；

所述求解模块具体用于：

针对每次邻域搜索，若该次邻域搜索后所述当前解未被更新，则将所述当前解对应的灾变计数器加一；

在满足所述当前解对应的灾变计数器大于预设阈值的灾变条件时，从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

12.一种电子设备，包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1至10任一项所述的基于记忆精英种群的灾变自适应大邻域搜索方法。

13.一种非暂态计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现如权利要求1至10任一项所述的基于记忆精英种群的灾变自适应大邻域搜索方法。

说明书

基于记忆精英种群的灾变自适应大邻域搜索方法及装置

技术领域

[0001] 本发明涉及人工智能技术领域，尤其涉及一种基于记忆精英种群的灾变自适应大邻域搜索方法及装置。

背景技术

[0002] 随着网络购物、网上支付、移动电子商户的数量急剧增加，仓储业发展迅猛，在如今的仓储环境中，商品种类多、订单批量大、任务实时更新，传统的仓储物流系统已经难以满足这些要求，智能仓库的应用日趋流行。

[0003] 目前，智能仓库一般采用多机器人系统进行货架搬运及拣选，机器人需要根据订单信息将指定货架运输到对应拣选站，这其中就牵涉到任务分配问题。此环境下任务是指运输货架前往拣选站的搬运任务，机器人获取需要运输的货架序列即为任务分配的过程。通常采用自适应大邻域搜索算法（Adaptive Large Neighborhood Search，ALNS）进行任务分配。

[0004] 现有技术的不足在于：ALNS搜索过程无记忆性，且搜索深度不高。

发明内容

[0005] 本发明提供一种基于记忆精英种群的灾变自适应大邻域搜索方法及装置，用以解决现有技术中ALNS搜索过程无记忆性，且搜索深度不高的缺陷，实现弥补ALNS搜索过程的无记忆性和提高搜索深度的目的。

[0006] 本发明提供一种基于记忆精英种群的灾变自适应大邻域搜索方法，包括：

[0007] 构建任务分配优化模型；其中，所述任务分配优化模型包括目标函数和多个约束条件，所述目标函数用于表征最小化机器人的最大完工时间，所述多个约束条件包括任务分配约束条件和任务优先级约束条件；

[0008] 初始化搜索种群和精英种群；

[0009] 通过迭代执行以下步骤来求解所述任务分配优化模型，直至迭代次数大于终止迭代次数：

[0010] 针对所述搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测所述当前解是否被更新；

[0011] 若所述当前解被更新，则对所述精英种群进行相应更新；

[0012] 若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

[0013] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述对所述精英种群进行相应更新，包括：

[0014] 计算预设数值与第一比值之间的乘积的正弦值，所述第一比值为当前迭代次数和所述终止迭代次数之间的比值；

[0015] 根据所述正弦值将所述精英种群划分为最优精英种群和记忆精英种群；

[0016] 更新所述最优精英种群中的所有解为种群最优解；

[0017] 针对所述记忆精英种群中的每个解，若所述解的适应度大于所述当前解的适应度，则按照第一预设概率更新所述解为所述当前解；

[0018] 若所述解的适应度不大于所述当前解的适应度，则按照第二预设概率更新所述解为所述当前解；

[0019] 其中，所述第一预设概率为说服概率，所述第二预设概率为1减去所述说服概率所得到的差值。

[0020] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新，包括：

[0021] 针对每次邻域搜索，若该次邻域搜索后所述当前解未被更新，则将所述当前解对应的灾变计数器加一；

[0022] 在满足所述当前解对应的灾变计数器大于预设阈值的灾变条件时，从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

[0023] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述采用自适应大邻域搜索算法对当前解进行邻域搜索，包括：

[0024] 从当前解关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子，并利用所述目标移除算子和目标插入算子依次对所述当前解进行处理，得到邻域解；

[0025] 计算所述邻域解的适应度；

[0026] 基于接受准则，更新所述当前解、历史邻域最优解和种群最优解；

[0027] 根据权重更新规则，更新所述当前解关联的多个移除算子和插入算子的权重。

[0028] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述从当前解关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子，包括：

[0029] 基于当前解关联的每个候选算子的权重，计算所述候选算子的选择概率；其中，所述候选算子为移除算子或插入算子；

[0030] 基于所述候选算子的选择概率计算所述候选算子的累积概率；

[0031] 生成一个随机数，所述随机数大于0且小于等于1；

[0032] 若所述候选算子的累积概率大于等于所述随机数、且所述候选算子的前序算子的累积概率小于所述随机数，则选中所述候选算子为目标移除算子或目标插入算子。

[0033] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述移除算子包括：随机路径移除算子、最坏路径移除算子、随机移除算子和随机移除不重复任务算子中的至少一个移除算子；

[0034] 其中，所述随机路径移除算子用于随机移除一个机器人的所有任务，所述最坏路径移除算子用于移除最大完工时间对应的机器人的所有任务，所述随机移除算子用于随机移除若干任务并保证命中相同货架的所有任务被同步移除，所述随机移除不重复任务算子用于随机移除命中货架不重复的任务。

[0035] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述插入算子包括：优先级随机插入算子、优先级随机概率插入算子、优先级基本任务时间插入算子和优先级基本任务时间概率插入算子中的至少一个插入算子；

[0036] 其中，所述优先级随机插入算子用于按照优先级数值升序、同优先级内随机乱序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务；

[0037] 所述优先级随机概率插入算子用于按照优先级数值升序、同优先级内随机乱序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则以预设命中概率选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务；

[0038] 所述优先级基本任务时间插入算子用于按照优先级数值升序、同优先级按基础任务时间降序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务；

[0039] 所述优先级基本任务时间概率插入算子用于按照优先级数值升序、同优先级按基础任务时间降序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则以预设命中概率选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务。

[0040] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述基于接受准则，更新所述当前解、历史邻域最优解和种群最优解，包括：

[0041] 若所述邻域解的适应度小于所述当前解的适应度，则以第三预设概率接受所述邻域解，并根据所述邻域解更新所述当前解、历史邻域最优解和种群最优解；

[0042] 若所述邻域解的适应度大于等于所述当前解的适应度，则以第四预设概率接受所述邻域解；

[0043] 其中，所述第三预设概率为犯错概率，所述第四预设概率为1减去所述犯错概率所得到的差值。

[0044] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述根据权重更新规则，更新所述当前解关联的多个移除算子和插入算子的权重，包括：

[0045] 在当前迭代次数达到 次时，通过以下表达式更新所述当前解关联的算子 的权重，所述算子 为所述移除算子或所述插入算子：

[0046]

[0047] 其中， 表示权重更新周期， 表示算子 的权重， 表示 次迭代中算子的累积得分， 表示 次迭代中算子 的使用次数， 表示权重更新系数，所述当前解关联的所有算子的初始权重均为1。

[0048] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述任务分配约束条件包括：

[0049] 所有任务均已分配给所述机器人；

[0050] 分配给所述机器人的任务不重复中；

[0051] 所述任务优先级约束条件包括：

[0052] 针对任务堆内部的各个任务，后序任务的优先级不能高于前序任务的优先级；

[0053] 针对各个任务堆，后序任务堆的优先级不能高于前序任务堆的优先级；

[0054] 其中，所述任务堆是将所述机器人的任务列表按顺序进行分堆得到的，一个所述任务堆包括命中相同货架的相邻任务，所述任务堆的优先级为所述任务堆内部的各个任务的优先级中的最高优先级。

[0055] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述初始化搜索种群，包括：

[0056] 将全体任务按优先级从高到低排列生成第一有序集合；

[0057] 针对所述第一有序集合中优先级相同的多个任务，将所述多个任务进行随机排序，得到第二有序集合；

[0058] 初始化所有机器人的任务列表为空；

[0059] 按照所述第二有序集合中的任务顺序，将每个任务插入当前基础完工时间最小的机器人的任务列表的末端，得到第一预备解；

[0060] 计算所述第一预备解的适应度；

[0061] 若所述第一预备解的适应度不等于正无穷，则将所述第一预备解加入所述搜索种群。

[0062] 根据本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法，所述初始化精英种群，包括：

[0063] 将全体任务按优先级从高到低排列生成第三有序集合；

[0064] 针对所述第三有序集合中优先级相同的多个任务，将所述多个任务进行随机排序，得到第四有序集合；

[0065] 初始化所有机器人的任务列表为空；

[0066] 按照所述第四有序集合中的任务顺序，在满足所述任务优先级约束条件时遍历所述所有机器人的任务列表中的可插入位置，计算每个所述可插入位置的插入成本增量，将每个任务插入最小的所述插入成本增量对应的所述可插入位置，得到第二预备解；

[0067] 计算所述第二预备解的适应度；

[0068] 若所述第二预备解的适应度不等于正无穷，则将所述第二预备解加入所述精英种群。

[0069] 本发明还提供一种基于记忆精英种群的灾变自适应大邻域搜索装置，包括：

[0070] 构建模块，用于基于目标函数和任务约束条件构建任务分配优化模型；其中，所述目标函数用于表征最小化最大完工时间，所述任务约束条件用于对任务分配和任务优先级进行约束；

[0071] 初始化模块，用于基于所述任务分配优化模型，初始化搜索种群和精英种群；

[0072] 求解模块，用于通过迭代执行以下操作来求解所述任务分配优化模型，直至迭代次数大于终止迭代次数：

[0073] 针对所述搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测所述当前解是否被更新；

[0074] 若所述当前解被更新，则对所述精英种群进行相应更新；

[0075] 若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

[0076] 本发明还提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如上述任一种所述的基于记忆精英种群的灾变自适应大邻域搜索方法。

[0077] 本发明还提供一种非暂态计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现如上述任一种所述的基于记忆精英种群的灾变自适应大邻域搜索方法。

[0078] 本发明还提供一种计算机程序产品，包括计算机程序，所述计算机程序被处理器执行时实现如上述任一种所述的基于记忆精英种群的灾变自适应大邻域搜索方法。

[0079] 本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法及装置，在求解任务分配优化模型的过程中，在自适应大邻域搜索的基础上动态维护搜索种群和精英种群，在当前解被更新的情况下，对精英种群进行相应更新，即保留搜索种群产生的优质解到精英种群，可以弥补自适应大邻域搜索过程的无记忆性；并且，在当前解未被更新的情况下，在满足灾变条件时从当前的精英种群中随机选择一个解对当前解进行更新，即在满足灾变条件时搜索种群产生的优质解可以重新进入搜索种群，并在新的方向上得到搜索，可以提高自适应大邻域搜索的搜索深度。

附图说明

[0080] 为了更清楚地说明本发明或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0081] 图1是本发明提供的基于记忆精英种群的灾变自适应大邻域搜索方法的流程示意图；

[0082] 图2是本发明提供的初始化搜索种群的流程示意图；

[0083] 图3是本发明提供的初始化精英种群的流程示意图；

[0084] 图4是本发明提供的自适应大邻域搜索的流程示意图；

[0085] 图5是本发明提供的自适应大邻域搜索的接受准则的流程示意图；

[0086] 图6是本发明提供的搜索种群灾变机制的流程示意图；

[0087] 图7是本发明提供的精英种群更新机制的流程示意图；

[0088] 图8是本发明提供的基于记忆精英种群的灾变自适应大邻域搜索装置的结构示意图；

[0089] 图9是本发明提供的电子设备的结构示意图。

具体实施方式

[0090] 为使本发明的目的、技术方案和优点更加清楚，下面将结合本发明中的附图，对本发明中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0091] 下面结合图1‑图7描述本发明的基于记忆精英种群的灾变自适应大邻域搜索方法。

[0092] 图1是本发明提供的基于记忆精英种群的灾变自适应大邻域搜索方法的流程示意图。如图1所示，本发明提供的基于记忆精英种群的灾变自适应大邻域搜索方法包括以下步骤：

[0093] 步骤101、构建任务分配优化模型；其中，任务分配优化模型包括目标函数和多个约束条件，目标函数用于表征最小化机器人的最大完工时间，多个约束条件包括任务分配约束条件和任务优先级约束条件；

[0094] 步骤102、初始化搜索种群和精英种群；

[0095] 步骤103、初始化迭代次数为0；

[0096] 步骤104、遍历搜索种群中的每个解；

[0097] 步骤105、采用自适应大邻域搜索算法对当前解进行邻域搜索；

[0098] 步骤106、检测当前解是否被更新，若否，则转入步骤107，若是，则转入步骤108；

[0099] 步骤107、在满足灾变条件时从当前的精英种群中随机选择一个解对当前解进行更新，转入步骤109；

[0100] 步骤108、对精英种群进行相应更新；

[0101] 步骤109、判断遍历是否结束，若是，则转入步骤110，若否，则转入步骤104；

[0102] 步骤110、迭代次数加一；

[0103] 步骤111、判断当前迭代次数是否大于终止迭代次数，若是，则转入步骤112，若否，则转入步骤104；

[0104] 步骤112、输出种群最优解。

[0105] 下面通过智能仓库中的任务分配场景对上述各个步骤进行详细说明：

[0106] 针对下发给多个拣选站的某批次订单，按订单行拆分为M个搬运任务(简称任务)。本实施例中有N个机器人共同执行这些任务，规定每个机器人同时只能执行一个任务，每个任务只能由一个机器人执行。需要在订单优先级约束(即优先级高的订单必须在优先级低的订单拣选完毕之前完成，同一优先级的订单没有完成顺序要求)下，给每个机器人分配一个任务列表，机器人在优化的作业流程下依次执行任务列表中的任务，使得所有机器人完成其任务列表的完工时间的最大值最小。

[0107] 需要说明的是，本实施例对全体任务进行自然数编码，任务的排列顺序即为机器人执行任务的顺序。取最大完工时间为解的适应度，考虑到本实施例是求解最小化问题，因此遵从“适应度越小，解的质量越好"的原则。

[0108] 首先，构建如下任务分配优化模型：

[0109] 目标函数：

[0110]

[0111] 任务分配约束条件：

[0112]

[0113]

[0114] 任务优先级约束条件：

[0115]

[0116]

[0117] 其中，表达式（1）用于表征最小化机器人的最大完工时间；表达式（2）用于表征所有任务均已分配给机器人；表达式（3）用于表征分配给机器人的任务不重复中；表达式（4）用于表征针对任务堆内部的各个任务，后序任务的优先级不能高于前序任务的优先级；表达式（5）用于表征针对各个任务堆，后序任务堆的优先级不能高于前序任务堆的优先级；其中，任务的优先级为任务关联订单行所属订单的优先级；任务堆是将机器人的任务列表按顺序进行分堆得到的，一个任务堆包括命中相同货架的相邻任务，任务堆的优先级为任务堆内部的各个任务的优先级中的最高优先级，任务堆内部的任务排序和任务堆之间的排序均由原始任务列表的任务顺序决定。

[0118] 上述任务分配优化模型中的符号说明如表1所示：

[0119] 表1 符号说明

[0120]

[0121] 可选地，如图2所示，在步骤102中，初始化搜索种群可以包括以下子步骤：

[0122] 步骤201、将全体任务按优先级从高到低排列生成第一有序集合；

[0123] 步骤202、针对第一有序集合中优先级相同的多个任务，将多个任务进行随机排序，得到第二有序集合；

[0124] 步骤203、初始化所有机器人的任务列表为空；

[0125] 步骤204、按照第二有序集合中的任务顺序，将每个任务插入当前基础完工时间最小的机器人的任务列表的末端，得到第一预备解；

[0126] 步骤205、计算第一预备解的适应度；

[0127] 步骤206、判断第一预备解的适应度是否等于正无穷，若否，则转入步骤207，若是，则转入步骤202；

[0128] 步骤207、将第一预备解加入搜索种群。

[0129] 在步骤201中，将全体任务按优先级从高到低排列生成第一有序集合 (例如 ={1，2，3，...，20}，例如：编号1 10的任务优先级数值为1，编号11 20的任务优先级数值为2)。

[0130] 在步骤202中，在每个优先级相同的多个任务内部随机打乱任务顺序，保证不同优先级之间的相对顺序不变，得到第二有序集合 ，例如。

[0131] 在步骤204中，按顺序考虑第二有序集合 里每一个任务 ，每次将任务j插入当前基础完工时间最小的机器人的任务列表的末端，直至第二有序集合 里的任务全部分配完毕，得到第一预备解 。

[0132] 在步骤205中，计算第一预备解 的适应度 。

[0133] 在步骤206和207中，若 ，则第一预备解 可行，将加入搜索种群S；否则转入步骤202。

[0134] 在本实施例中，可以基于随机均衡任务分配的思想生成初始搜索种群S的每一个解，即初始化搜索种群S。

[0135] 可选地，如图3所示，在步骤102中，初始化精英种群可以包括以下子步骤：

[0136] 步骤301、将全体任务按优先级从高到低排列生成第三有序集合；

[0137] 步骤302、针对第三有序集合中优先级相同的多个任务，将多个任务进行随机排序，得到第四有序集合；

[0138] 步骤303、初始化所有机器人的任务列表为空；

[0139] 步骤304、按照第四有序集合中的任务顺序，在满足任务优先级约束条件时遍历所有机器人的任务列表中的可插入位置，计算每个可插入位置的插入成本增量，将每个任务插入最小的插入成本增量对应的可插入位置，得到第二预备解；

[0140] 步骤305、计算第二预备解的适应度；

[0141] 步骤306、判断第二预备解的适应度是否等于正无穷，若否，则转入步骤307，若是，则转入步骤302；

[0142] 步骤307、将第二预备解加入精英种群。

[0143] 图3中的步骤301‑303、305‑307与图2中的步骤201‑203、205‑207类似，此处不再赘述。

[0144] 在步骤304中，按顺序考虑第四有序集合里每一个任务 ，在满足任务优先级约束条件时遍历所有机器人的任务列表中的可插入位置，计算每个可插入位置的插入成本增量，将每个任务插入最小的插入成本增量 对应的可插入位置，得到第二预备解 。

[0145] 其中，

[0146] 在本实施例中，相较于任务列表末端的插入方式，插入成本增量 最小的插入方式能够得到更优质的初始解，即初始化精英种群E。

[0147] 可选地，如图4所示，步骤105可以包括以下子步骤：

[0148] 步骤401、从当前解关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子，并利用目标移除算子和目标插入算子依次对当前解进行处理，得到邻域解；

[0149] 步骤402、计算邻域解的适应度；

[0150] 步骤403、基于接受准则，更新当前解、历史邻域最优解和种群最优解；

[0151] 步骤404、根据权重更新规则，更新当前解关联的多个移除算子和插入算子的权重。

[0152] 在步骤401中，从当前解 关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子，并利用目标移除算子和目标插入算子依次作用于当前解 ，得到邻域解。

[0153] 在步骤402中，计算邻域解 的适应度 。

[0154] 在步骤403中，基于接受准则，更新当前解 、历史邻域最优解 和种群最优解。

[0155] 在步骤404中，根据权重更新规则，更新当前解 关联的多个移除算子和插入算子的权重。

[0156] 在本实施例中，通过自适应大邻域搜索算法选择目标移除算子和目标插入算子对当前解进行改进，并根据各移除算子和插入算子的表现进行权重调整，提高算法寻优能力，从而找到局部最优解。

[0157] 可选地，步骤401中，从当前解关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子，可以包括以下步骤：

[0158] 步骤4011、基于当前解关联的每个候选算子的权重，计算候选算子 的选择概率；其中，候选算子 为移除算子或插入算子；

[0159]

[0160] 步骤4012、基于候选算子 的选择概率 计算候选算子 的累积概率 ；

[0161]

[0162] 步骤4013、生成一个随机数 ，随机数 位于区间 内；

[0163] 步骤4014、若候选算子 的累积概率 大于等于随机数 、且候选算子 的前序算子 的累积概率 小于随机数 ，即 ，则选中该候选算子为目标移除算子或目标插入算子。

[0164] 在本实施例中，可以通过赌盘算法选择合适的移除算子和插入算子。

[0165] 可选地，移除算子包括：随机路径移除（Random Path Remove，RPR）算子、最坏路径移除（Worst Path Remove，WPR）算子、随机移除 算子和随机移除不重复 任务算子
中的至少一个移除算子。

[0166] 其中，RPR算子用于随机移除一个机器人的所有任务；WPR算子用于移除最大完工时间对应的机器人的所有任务； 算子用于随机移除若干任务并保证命中相同货架的所有任务被同步移除，移除的任务数量不小于 ； 算子用于随机移除命中货架不重复的任务，移除的任务数量等于 。

[0167] 可选地，插入算子包括：优先级随机插入 算子、优先级随机概率插入 算子、优先级基
本任务时间插入 算子和优先级基本任务时
间概率插入 算子中的
至少一个插入算子。

[0168] 其中， 算子用于按照优先级数值升序、同优先级内随机乱序的规则确定多个待插入任务 的顺序，针对每个待插入任务 ，若在已分配任务列表中存在与待插入任务命中货架相同的目标任务 ，则将待插入任务 插入与目标任务 相邻的位置；若在已分配任务列表中不存在与待插入任务 命中货架相同的目标任务 ，则选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出待插入任务 的插入位置，并在待插入任务 的插入位置插入待插入任务 ；

[0169] 算子用于按照优先级数值升序、同优先级内随机乱序的规则确定多个待插入任务 的顺序，针对每个待插入任务 ，若在已分配任务列表中存在与待插入任务 命中货架相同的目标任务 ，则将待插入任务 插入与目标任务 相邻的位置；若在已分配任务列表中不存在与待插入任务 命中货架相同的目标任务 ，则以预设命中概率选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出待插入任务 的插入位置，并在待插入任务 的插入位置插入待插入任务 ；

[0170] 算子用于按照优先级数值升序、同优先级按基础任务时间降序的规则确定多个待插入任务 的顺序，针对每个待插入任务 ，若在已分配任务列表中存在与待插入任务 命中货架相同的目标任务 ，则将待插入任务 插入与目标任务 相邻的位置；若在已分配任务列表中不存在与待插入任务 命中货架相同的目标任务 ，则选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出待插入任务 的插入位置，并在待插入任务 的插入位置插入待插入任务 ；

[0171] 算子用于按照优先级数值升序、同优先级按基础任务时间降序的规则确定多个待插入任务 的顺序，针对每个待插入任务 ，若在已分配任务列表中存在与待插入任务 命中货架相同的目标任务 ，则将待插入任务 插入与目标任务 相邻的位置；若在已分配任务列表中不存在与待插入任务 命中货架相同的目标任务 ，则以预设命中概率选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出待插入任务 的插入位置，并在待插入任务 的插入位置插入待插入任务 。

[0172] 可选地，如图5所示，步骤403可以包括以下子步骤：

[0173] 步骤501、判断邻域解的适应度是否小于当前解的适应度，若是，则转入步骤502，若否，则转入步骤507；

[0174] 步骤502、以第三预设概率接受邻域解，并根据邻域解更新当前解；其中，第三预设概率为犯错概率；

[0175] 步骤503、判断邻域解的适应度是否小于历史邻域最优解的适应度，若是，则转入步骤504，若否，则结束；

[0176] 步骤504、根据邻域解更新历史邻域最优解；

[0177] 步骤505、判断邻域解的适应度是否小于种群最优解的适应度，若是，则转入步骤506，若否，则结束；

[0178] 步骤506、根据邻域解更新种群最优解，转入束；

[0179] 步骤507、以第四预设概率接受邻域解，并根据邻域解更新当前解；其中，第四预设概率为1减去犯错概率所得到的差值。

[0180] 在本实施例中，为了跳出局部最优解，在接受准则中加入一定的扰动。定义一个极小的犯错概率 ，若邻域解 优于当前解 ，则以较大概率 接受邻域解，并根据邻域解与历史邻域最优解 、种群最优解 的适应度对 和 进行相应的更新；否则以较小的概率( )接受邻域解。

[0181] 可选地，步骤404可以包括：在当前迭代次数达到 次时，通过表达式（9）更新当前解关联的算子 的权重，算子 为移除算子或插入算子，并重置迭代次数为0；否则，采用表达式（10）更新本次迭代选中算子 的累积得分：

[0182]          （9）

[0183] 其中， 表示权重更新周期， 表示算子 的权重， 表示 次迭代中算子的累积得分， 表示 次迭代中算子 的使用次数， 表示权重更新系数，当前解关联的所有算子的初始权重均为1；

[0184]     （10）

[0185] 其中， 表示在新解优于种群最优解时算子的分数， 表示在新解优于当前解邻域历史最优解时算子的分数， 表示在新解优于当前解时算子的分数， 表示在新解次于当前解但被接受时算子的分数。

[0186] 在本实施例中，可以根据上述权重更新规则，更新当前解关联的多个算子的权重。

[0187] 可选地，如图6所示，步骤107可以包括以下子步骤：

[0188] 步骤601、针对每次邻域搜索，若该次邻域搜索后当前解未被更新，则将当前解对应的灾变计数器加一；

[0189] 步骤602、判断当前解对应的灾变计数器是否大于预设阈值，若是，则转入步骤603，若否，则转入步骤604；

[0190] 步骤603、从当前的精英种群中随机选择一个解对当前解进行更新；

[0191] 步骤604、重置当前解对应的灾变计数器。

[0192] 为了防止陷入局部最优解，在搜索种群S中引入常用于遗传算法的灾变算子。具体地，对于搜索种群S中的每一个解 ，维护一个灾变计数器 ，并初始化为0。若在某次ANLS执行后未被更新，则相应的灾变计数器 加1，当满足灾变条件(即 预设阈值)时，执行灾变策略（即从当前精英种群E中随机选择一个解更新 ），并重置 为0。若 在某次ANLS执行后被更新，则需重置 为0。

[0193] 在本实施例中，一方面，通过灾变算子主动放弃持续未得到改进的解，达到防止陷入局部最优解的目的。另一方面，在满足灾变条件时搜索种群产生的优质解可以重新进入搜索种群，并在新的方向上得到搜索，可以提高自适应大邻域搜索的搜索深度。

[0194] 可选地，如图7所示，步骤108可以包括以下子步骤：

[0195] 步骤701、计算预设数值与第一比值之间的乘积的正弦值，第一比值为当前迭代次数和终止迭代次数之间的比值；

[0196] 步骤702、根据正弦值将精英种群划分为最优精英种群和记忆精英种群；

[0197] 步骤703、更新最优精英种群中的所有解为种群最优解；

[0198] 步骤704、针对记忆精英种群中的每个解，判断该解的适应度是否大于当前解的适应度，若是，则转入步骤705，若否，则转入步骤706；

[0199] 步骤705、按照第一预设概率更新该解为当前解，第一预设概率为说服概率；

[0200] 步骤706、按照第二预设概率更新该解为当前解，第二预设概率为1减去说服概率所得到的差值。

[0201] 在步骤701中，计算预设数值（例如1.5）与第一比值 之间的乘积的正弦值 ，第一比值 为当前迭代次数 和终止迭代次数
之间的比值。

[0202]

[0203] 在步骤702中，根据正弦值 将精英种群E划分为最优精英种群E1和记忆精英种群E2。例如：假设精英种群E共有e个解，将精英种群E的前 个解组成最优精英种群E1，后 个解组成记忆精英种群E2。

[0204] 在步骤703中，更新最优精英种群E1中的所有解为种群最优解 。

[0205] 在步骤704‑706中，对于记忆精英种群E2中的每个解 ，生成一个随机数 ，若当前解 比 更优，则依说服概率 更新 为当前解 ，否则依概率更新 为当前解 ，直至记忆精英种群E2遍历完毕。

[0206] 在本实施例中，采用基于概率的更新机制保留搜索种群产生的优质解到精英种群，可以弥补自适应大邻域搜索过程的无记忆性。并且，引入随迭代次数呈正弦函数变化的，来动态调节全局最优解在精英种群中的比例，既保证了算法在运行初期的种群多样性，又使得算法在迭代次数不断增加的过程中迅速收敛，提高了算法的搜索效率。

[0207] 综上，本发明提供的一种基于记忆精英种群的灾变自适应大邻域搜索方法及装置，在求解任务分配优化模型的过程中，在自适应大邻域搜索的基础上动态维护一个基于灾变算子的搜索种群和一个基于概率、具有记忆性的精英种群，在当前解被更新的情况下，对精英种群进行相应更新，即保留搜索种群产生的优质解到精英种群，可以弥补自适应大邻域搜索过程的无记忆性。并且，在当前解未被更新的情况下，在满足灾变条件时从当前的精英种群中随机选择一个解对当前解进行更新，即在满足灾变条件时搜索种群产生的优质解可以重新进入搜索种群，并在新的方向上得到搜索，可以提高自适应大邻域搜索的搜索深度。

[0208] 下面对本发明提供的基于记忆精英种群的灾变自适应大邻域搜索装置进行描述，下文描述的基于记忆精英种群的灾变自适应大邻域搜索装置与上文描述的基于记忆精英种群的灾变自适应大邻域搜索方法可相互对应参照。

[0209] 图8是本发明提供的基于记忆精英种群的灾变自适应大邻域搜索装置的结构示意图。如图8所示，本发明提供的基于记忆精英种群的灾变自适应大邻域搜索装置可以包括：

[0210] 构建模块10，用于构建任务分配优化模型；其中，所述任务分配优化模型包括目标函数和多个约束条件，所述目标函数用于表征最小化机器人的最大完工时间，所述多个约束条件包括任务分配约束条件和任务优先级约束条件；

[0211] 初始化模块20，用于初始化搜索种群和精英种群；

[0212] 求解模块30，用于通过迭代执行以下操作来求解所述任务分配优化模型，直至迭代次数大于终止迭代次数：

[0213] 针对所述搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测所述当前解是否被更新；

[0214] 若所述当前解被更新，则对所述精英种群进行相应更新；

[0215] 若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

[0216] 可选地，求解模块30具体用于：

[0217] 计算预设数值与第一比值之间的乘积的正弦值，所述第一比值为当前迭代次数和所述终止迭代次数之间的比值；

[0218] 根据所述正弦值将所述精英种群划分为最优精英种群和记忆精英种群；

[0219] 更新所述最优精英种群中的所有解为种群最优解；

[0220] 针对所述记忆精英种群中的每个解，若所述解的适应度大于所述当前解的适应度，则按照第一预设概率更新所述解为所述当前解；

[0221] 若所述解的适应度不大于所述当前解的适应度，则按照第二预设概率更新所述解为所述当前解；

[0222] 其中，所述第一预设概率为说服概率，所述第二预设概率为1减去所述说服概率所得到的差值。

[0223] 可选地，求解模块30具体用于：

[0224] 针对每次邻域搜索，若该次邻域搜索后所述当前解未被更新，则将所述当前解对应的灾变计数器加一；

[0225] 在满足所述当前解对应的灾变计数器大于预设阈值的灾变条件时，从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

[0226] 可选地，求解模块30具体用于：

[0227] 从当前解关联的多个移除算子和插入算子中选择目标移除算子和目标插入算子，并利用所述目标移除算子和目标插入算子依次对所述当前解进行处理，得到邻域解；

[0228] 计算所述邻域解的适应度；

[0229] 基于接受准则，更新所述当前解、历史邻域最优解和种群最优解；

[0230] 根据权重更新规则，更新所述当前解关联的多个移除算子和插入算子的权重。

[0231] 可选地，求解模块30具体用于：

[0232] 基于当前解关联的每个候选算子的权重，计算所述候选算子的选择概率；其中，所述候选算子为移除算子或插入算子；

[0233] 基于所述候选算子的选择概率计算所述候选算子的累积概率；

[0234] 生成一个随机数，所述随机数大于0且小于等于1；

[0235] 若所述候选算子的累积概率大于等于所述随机数、且所述候选算子的前序算子的累积概率小于所述随机数，则选中所述候选算子为目标移除算子或目标插入算子。

[0236] 可选地，所述移除算子包括：随机路径移除算子、最坏路径移除算子、随机移除算子和随机移除不重复任务算子中的至少一个移除算子；

[0237] 其中，所述随机路径移除算子用于随机移除一个机器人的所有任务，所述最坏路径移除算子用于移除最大完工时间对应的机器人的所有任务，所述随机移除算子用于随机移除若干任务并保证命中相同货架的所有任务被同步移除，所述随机移除不重复任务算子用于随机移除命中货架不重复的任务。

[0238] 可选地，所述插入算子包括：优先级随机插入算子、优先级随机概率插入算子、优先级基本任务时间插入算子和优先级基本任务时间概率插入算子中的至少一个插入算子；

[0239] 其中，所述优先级随机插入算子用于按照优先级数值升序、同优先级内随机乱序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务；

[0240] 所述优先级随机概率插入算子用于按照优先级数值升序、同优先级内随机乱序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则以预设命中概率选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务；

[0241] 所述优先级基本任务时间插入算子用于按照优先级数值升序、同优先级按基础任务时间降序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务；

[0242] 所述优先级基本任务时间概率插入算子用于按照优先级数值升序、同优先级按基础任务时间降序的规则确定多个待插入任务的顺序，针对每个待插入任务，若在已分配任务列表中存在与所述待插入任务命中货架相同的目标任务，则将所述待插入任务插入与所述目标任务相邻的位置；若在已分配任务列表中不存在与所述待插入任务命中货架相同的目标任务，则以预设命中概率选择基础完工时间最小的机器人为接收方，以插入成本增量最小的方式确定出所述待插入任务的插入位置，并在所述待插入任务的插入位置插入所述待插入任务。

[0243] 可选地，求解模块30具体用于：

[0244] 若所述邻域解的适应度小于所述当前解的适应度，则以第三预设概率接受所述邻域解，并根据所述邻域解更新所述当前解、历史邻域最优解和种群最优解；

[0245] 若所述邻域解的适应度大于等于所述当前解的适应度，则以第四预设概率接受所述邻域解；

[0246] 其中，所述第三预设概率为犯错概率，所述第四预设概率为1减去所述犯错概率所得到的差值。

[0247] 可选地，求解模块30具体用于：

[0248] 在当前迭代次数达到 次时，通过以下表达式更新所述当前解关联的算子 的权重，所述算子 为所述移除算子或所述插入算子：

[0249]

[0250] 其中， 表示权重更新周期， 表示算子 的权重， 表示 次迭代中算子的累积得分， 表示 次迭代中算子 的使用次数， 表示权重更新系数，所述当前解关联的所有算子的初始权重均为1。

[0251] 可选地，所述任务分配约束条件包括：

[0252] 所有任务均已分配给所述机器人；

[0253] 分配给所述机器人的任务不重复中；

[0254] 所述任务优先级约束条件包括：

[0255] 针对任务堆内部的各个任务，后序任务的优先级不能高于前序任务的优先级；

[0256] 针对各个任务堆，后序任务堆的优先级不能高于前序任务堆的优先级；

[0257] 其中，所述任务堆是将所述机器人的任务列表按顺序进行分堆得到的，一个所述任务堆包括命中相同货架的相邻任务，所述任务堆的优先级为所述任务堆内部的各个任务的优先级中的最高优先级。

[0258] 可选地，初始化模块20具体用于：

[0259] 将全体任务按优先级从高到低排列生成第一有序集合；

[0260] 针对所述第一有序集合中优先级相同的多个任务，将所述多个任务进行随机排序，得到第二有序集合；

[0261] 初始化所有机器人的任务列表为空；

[0262] 按照所述第二有序集合中的任务顺序，将每个任务插入当前基础完工时间最小的机器人的任务列表的末端，得到第一预备解；

[0263] 计算所述第一预备解的适应度；

[0264] 若所述第一预备解的适应度不等于正无穷，则将所述第一预备解加入所述搜索种群。

[0265] 可选地，初始化模块20具体用于：

[0266] 将全体任务按优先级从高到低排列生成第三有序集合；

[0267] 针对所述第三有序集合中优先级相同的多个任务，将所述多个任务进行随机排序，得到第四有序集合；

[0268] 初始化所有机器人的任务列表为空；

[0269] 按照所述第四有序集合中的任务顺序，在满足所述任务优先级约束条件时遍历所述所有机器人的任务列表中的可插入位置，计算每个所述可插入位置的插入成本增量，将每个任务插入最小的所述插入成本增量对应的所述可插入位置，得到第二预备解；

[0270] 计算所述第二预备解的适应度；

[0271] 若所述第二预备解的适应度不等于正无穷，则将所述第二预备解加入所述精英种群。

[0272] 本申请实施例的装置，可以用于执行前述方法实施例中任一实施例的方法，其具体实现过程与技术效果与方法实施例中类似，具体可以参见方法实施例中的详细介绍，此处不再赘述。

[0273] 图9示例了一种电子设备的实体结构示意图，如图9所示，该电子设备可以包括：处理器(processor)810、通信接口(Communications Interface)820、存储器(memory)830和通信总线840，其中，处理器810，通信接口820，存储器830通过通信总线840完成相互间的通信。处理器810可以调用存储器830中的逻辑指令，以执行基于记忆精英种群的灾变自适应大邻域搜索方法，该方法包括：

[0274] 构建任务分配优化模型；其中，所述任务分配优化模型包括目标函数和多个约束条件，所述目标函数用于表征最小化机器人的最大完工时间，所述多个约束条件包括任务分配约束条件和任务优先级约束条件；

[0275] 初始化搜索种群和精英种群；

[0276] 通过迭代执行以下步骤来求解所述任务分配优化模型，直至迭代次数大于终止迭代次数：

[0277] 针对所述搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测所述当前解是否被更新；

[0278] 若所述当前解被更新，则对所述精英种群进行相应更新；

[0279] 若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

[0280] 此外，上述的存储器830中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备（可以是个人计算机，服务器，或者网络设备等）执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器（ROM，Read‑Only Memory）、随机存取存储器（RAM，Random Access Memory）、磁碟或者光盘等各种可以存储程序代码的介质。

[0281] 另一方面，本发明还提供一种计算机程序产品，所述计算机程序产品包括计算机程序，计算机程序可存储在非暂态计算机可读存储介质上，所述计算机程序被处理器执行时，计算机能够执行上述各方法所提供的基于记忆精英种群的灾变自适应大邻域搜索方法，该方法包括：

[0282] 构建任务分配优化模型；其中，所述任务分配优化模型包括目标函数和多个约束条件，所述目标函数用于表征最小化机器人的最大完工时间，所述多个约束条件包括任务分配约束条件和任务优先级约束条件；

[0283] 初始化搜索种群和精英种群；

[0284] 通过迭代执行以下步骤来求解所述任务分配优化模型，直至迭代次数大于终止迭代次数：

[0285] 针对所述搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测所述当前解是否被更新；

[0286] 若所述当前解被更新，则对所述精英种群进行相应更新；

[0287] 若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

[0288] 又一方面，本发明还提供一种非暂态计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现以执行上述各方法提供的基于记忆精英种群的灾变自适应大邻域搜索方法，该方法包括：

[0289] 构建任务分配优化模型；其中，所述任务分配优化模型包括目标函数和多个约束条件，所述目标函数用于表征最小化机器人的最大完工时间，所述多个约束条件包括任务分配约束条件和任务优先级约束条件；

[0290] 初始化搜索种群和精英种群；

[0291] 通过迭代执行以下步骤来求解所述任务分配优化模型，直至迭代次数大于终止迭代次数：

[0292] 针对所述搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测所述当前解是否被更新；

[0293] 若所述当前解被更新，则对所述精英种群进行相应更新；

[0294] 若所述当前解未被更新，则在满足灾变条件时从当前的所述精英种群中随机选择一个解对所述当前解进行更新。

[0295] 以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。

[0296] 通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备（可以是个人计算机，服务器，或者网络设备等）执行各个实施例或者实施例的某些部分所述的方法。

[0297] 最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。