(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111477211.0 (22)申请日 2021.12.0 6 (71)申请人 南京信息 工程大学 地址 224002 江苏省盐城市 盐南高新区新 河街道文港南路10 5号 (72)发明人 申晓宁　陈庆洲　潘红丽　许笛　 姚铖滨　徐继勇　葛忠佩　 (74)专利代理 机构 北京众合诚成知识产权代理 有限公司 1 1246 代理人 刘珊珊 (51)Int.Cl. G06N 3/12(2006.01) G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 10/10(2012.01) (54)发明名称 一种移动群智感知变速多任务分配问题的 混合蛙跳求解方法 (57)摘要 本发明公开了一种移动群智感知变速多任 务分配问题的混合蛙跳求解方法包括以下步骤： (1)问题信息读取， 包括每个任务和每位用户的 坐标， 以及用户信誉度等问题中的数据； (2)初始 化算法参数， 使用基于启发信息的目标锚定混合 初始化算子生成初始种群； (3)对种群进行约束 处理， 计算种群中所有个体的目标值， 确定非支 配解集放入外部存储器； (4)进入快速收敛阶段， 对种群根据快速非支 配排序结果使用 “S”型分组 方式划分子组， 对各个子组进行基于离散跳跃规 则的局部搜索， 将各子组混洗， 基于非支配概念 更新外部存储器， 对外部存储器中的个体采用外 部档案个体区域挖掘策略， 等。 本发明具有搜索 速度快， 搜索能力强， 规划的分配方案更合理的 优点。 权利要求书4页 说明书11页 附图3页 CN 114298307 A 2022.04.08 CN 114298307 A 1.一种移动群智感知变速多任务分配问题的混合蛙跳求解方法， 其特征在于， 包括以 下步骤： S1， 读取问题输入的信息， 定义优化目标， 设定约束条件； S2， 初始化 三阶段多目标混合蛙 跳算法参数； S3， 使用基于启发信息的目标锚定混合初始化 算子生成初始种群； S4， 使用约束处 理算子处 理后， 计算优化目标值fj； S5， 根据目标值选出当前种群Pop中所有非支配解 放入外部存储器A； S6， 进入快速收敛阶段： 对种群Pop根据快速非支配排序结果使用 “S”型分组方式划分 子组MPopi； S7， 对各子组基于 离散跳跃规则进行局部 搜索； S8， 混洗所有子组， 使用支配关系更新外部存储器A， 对外部存储器A中的个体采用外部 档案个体区域挖掘策略， 判断是否满足快速收敛阶段终止条件， 若满足， 则终止快速收敛阶 段迭代， 进入下一阶段， 否则转S5； S9， 进入探索扩展阶段： 依次根据目标fj使用前沿划分策略从外部存储器A提取引导各 子群探索的引导集Aj， 依次根据目标fj将种群Pop分为m个子群CPopj， 对每个子群根据快速 非支配排序结果使用 “S”型分组方式划分子组MPopi； S10， 对各子群CPopj的各子组MPopi基于 离散跳跃规则进行局部 搜索； S11， 混洗所有子组， 使用支配关系更新外部存储器A， 对外部存储器A中的个体采用外 部档案个体区域挖掘策略， 判断是否满足探索扩展阶段终止条件， 若满足， 则终止探索扩展 阶段迭代， 进入下一阶段， 否则转 步骤S9； S12， 进入极值挖掘阶段： 依次根据目标fj将种群Pop分为m个子群CPopj， 对每个子群根 据降序排序结果使用 “S”型分组方式划分子组MPopi； S13， 对各子群CPopj的各子组MPopi基于 离散跳跃规则进行局部 搜索； S14， 混洗所有子组， 使用支配关系更新外部存储器A， 对外部存储器A中的个体采用外 部档案个体区域挖掘策略， 判断是否满足极值挖掘阶段终止条件， 若满足， 则终止 极值挖掘 阶段迭代， 输出外 部存储器A； 否则转S12。 2.根据权利要求1所述的一种移动群智感知变速多任务分配问题的混合蛙跳求解方 法， 其特征在于， 所述S1中， 所述问题的输入信息包括任务平台在线的m位用户集合U＝ {u1,…,ui,…,um},i∈{1,2, …,m}， 任务平台当前发布的n个任务集合TA＝{ta1, …, taj,…,tan},j∈{1,2, …,n}， 任一用户或任务点k与任务j之间的距离dkj,k∈U∪TA， 每个 任务需求的用户数 ψ， 每位用户可接受的任务数上限η， 用户i的信誉度gri， 单个任务的固定 报酬p， 成年人的步行速度v1， 成年人骑共享单车速度v2， 平台发布的所有任务截止时间DL， 共享单车单位时间的费用bp； 所述优化 目标为最大化参与任务的用户平均净收入， 以及最 大化用户完成任务时间与截止时间差的平均值； 所述约束条件为每个任务需要ψ位用户执 行， 每位用户执 行任务数量的上限为 η个， 每位用户对分配给他的每 个任务只能执 行一次。 3.根据权利要求2所述的一种移动群智感知变速多任务分配问题的混合蛙跳求解方 法， 其特征在于， 所述S1中， 所述读取问题输入的信息， 定义优化目标， 设定约束 条件的过程 包括以下步骤： 设定问题的规模表示每个任务需求用户数ψ的和加上用户前往每个任务的出行方式数权　利　要　求　书 1/4 页 2 CN 114298307 A 22×n×ψ； 定义优化目标主体为参与任务的用户平均净收入以及用户完成任务时间与截止时间 差的平均值， 其定义 为： 其中， PT表示参与任务的用户平均净收入； ST表示用户完成任务时间与截止时间差的 平均值； bp表示共享单车单位时间的费用； dkj表示任一用户或任务点k与任务j之间的距 离； v1表示成年人的步行速度； v2表示成年人骑共享单车速度； yikj表示用户i是否使用共 享单车从k点前往j点； zijk表示用户i是否从k点前往j点； xi表示用户i是否至少参与一项 任务； m表示用户数量； DL表示平 台发布的所有任务截止时间； p表示单个任务的固定报酬； ctij表示用户i执行任务j时已做的任务数； ATi表示用户i的报酬衰减阈值； gri表示用户i 的信誉度； n表示任务数量； 定义约束条件 包括以下三个： (1)每个任务需要 ψ位用户执 行， 即： 其中， n表示任务数量； zijk表示用户i是否从k点前往j点； ψ表示每个任务需求的用户数 量；权　利　要　求　书 2/4 页 3 CN 114298307 A 3