(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111449296.1 (22)申请日 2021.11.30 (71)申请人 南京信息 工程大学 地址 224002 江苏省盐城市 盐南高新区新 河街道文港南路10 5号 (72)发明人 申晓宁　徐继勇　林屹　许笛　 葛忠佩　姚铖滨　 (74)专利代理 机构 北京同辉知识产权代理事务 所(普通合伙) 11357 代理人 赵丹 (51)Int.Cl. G06F 30/27(2020.01) G06F 111/06(2020.01) G06F 119/02(2020.01) (54)发明名称 基于分组学习粒子群优化的众包软件项目 调度方法及 介质 (57)摘要 本发明公开基于分组学习粒子群优化的众 包软件项目调度方法， 包括以下步骤： 读取问题 信息， 定义优化目标， 设定约束条件， 初始化改进 粒子群算法的参数， 生成初始候选种群， 评价个 体适应度， 产生个体极值和全局极值， 采用分组 学习策略根据个体适应度进行排序和分组， 子组 中粒子数量的自适应变化； 更新个体价值； 考虑 任务人数上限的启发信息对全局极值进行局部 搜索； 终止准则判断。 本发明建立了众包软件项 目约束双目标三耦合调度模型， 该模 型融入开发 者的信誉、 最大工作负荷度属性， 任务最大人头 数属性， 开发者对任务所需技能熟练度等实际因 素， 通过寻找最佳开发者选择和任务分配方案， 最小化项目的工期和最大化项目质量。 权利要求书4页 说明书10页 附图3页 CN 114139453 A 2022.03.04 CN 114139453 A 1.基于分组学习粒子群优化的众包软件项目调度方法， 其特 征在于， 包括以下步骤： S1： 读取问题信息： 所述问题的输入信 息包括开发者的已有技 能、 已有技能熟练度、 可投入的最大工作量， 每项任务的工作量、 技能需求、 任务优先级和最大 人头数限制； S2： 定义优化目标： 优化目标为 最佳开发者 ‑任务分配方案中， 项目工期最短和项目质量 最大化； S3： 设定约束条件： 约束条件 包括任务 技能约束、 任务 最大人头数约束和开发者 不能超负荷工作； S4： 初始化改进粒子群算法的参数： 设置改进粒子群算法的进化种群规模为N， 最大迭代次数G， 局部搜索次数K， 全局极值 刷新间隙λ、 子组1初始种群数量在 全部种群数量的占比、 迭代计数器t ＝0， 设项目中候选开 发者人数为m， 任务数为 n， 项目所需技能数为S； S5:生成初始候选种群， 评价个 体适应度， 产生个 体极值和全局极值： 采用整数编码和实数编码相结合的混合编码方式， 随机生成N个个体， 每个个体表示开 发者选择 方案和任务的分配方案： X＝(xij)m×n， i＝1,2,...,m， j＝1,2,. ..,n 其中， xij∈[0,1]表示开发者ei对任务Tj的投入度， 若X的第i行为非零向量， 则表示开发 者ei被选中参与该项目； 若xij＞0， 则表示开发者ei非分配到项目的开发中， 且其对任务 的 投入度为xij； 计算每个个体的目标函数值： F＝ωt×dur+ωQ×Q 其中， dur为项目工期， Q为项目质量； 利用权重系数ωt和ωQ将项目工期dur和项目完 成 质量Q加权求和； 本模型令ωt＝1， ωQ＝‑100， 旨在将两个目标统一为最小化目标且数量级 统一； 最小化问题， 目标函数值越小， 适应度越好； S6:采用分组学习策略根据个 体适应度进行排序和分组： 初始化以及每一次进化迭代结束之后， 评价粒子的适应度， 根据适应度对种群排序分 组； 子组1中的个体需同时向个体极值pbi和全局极值gb学习， 并充分利用它们的有效信息 进行更新； 子组2中的个体具有更大 的进化空间， 需进一步向全局极值学习并快速收敛， 为 了防止种群快速同化， 选择一个新的对象xli来引导粒子学习， xli为适应度排序在粒子i之 前的个体， 其选取不受分组限制； 子组3中的个体在全局最优解gb附近， 在其周围做局邻域 搜索,其学习对象为个 体极值pbi和任意一个适应度排序在粒子i之前的个 体xli； S7:子组中粒子数量的自适应 变化： 在迭代的前期， 令三个子组中个体数量相同， 以加强对种群中其它个体有效信息的利 用， 实现对 决策空间的大范围和多元化的搜索； 随着迭代的深入， 子组1的个体数量逐渐变 多， 子组2和子组3的个体逐渐减少， 即向个体xli学习的粒子逐渐减少， 而 向全局最优gb学 习的个体逐渐增多， 逐步加强全局最优解gb对粒子的引导， 使种群最终全局收敛； S8:更新个体价值： 根据分组学习策略后， 粒子更新为新的个体， 根据优胜劣汰的规则在每次迭代中更新 个体极值和全局极值； S9:考虑任务人 数上限的启发信息对 全局极值进行局部 搜索：权　利　要　求　书 1/4 页 2 CN 114139453 A 2在算法的每一代进化判断全局极值gb是否发生变化， 若连续λ代没有更新则认为算法 陷入局部最优， 启动对gb的局部搜索； 随机选取一项任务， 若其已到达任务最大人头数上 限， 则对其进行位替换变异， 用一名现有开发者组合外的一名匹配度更高的开发者替换当 前开发组合中的一名随机开发者， 新开发者的投入随机产生； 若选取 的任务参与人数未达 到其最大人头数限制， 则增加 一名现有开发者组合外的开发者参与到任务中， 其投入度随 机产生； 经 过K次局部搜索后， 更新全局极值； S10:终止准则判断： 若t＞G， 则终止迭代， 输出适应度的最优个体， 即为项目中所选开发者在每项任务中投 入的工作量分配结果， 否则， 转入S4。 2.根据权利要求1所述的基于分组学习粒子群优化的众包软件项目调度方法， 其特征 在于， 所述 步骤S1中， 所述的技能熟练度， 定义 为： 开发者ei的技能熟练度集 合， 其中 表示ei对第k项技能的熟练度， 表示ei不具备第k项技 能， 表示ei完全掌握第k项技能。 3.根据权利要求1所述的基于分组学习粒子群优化的众包软件项目调度方法， 其特征 在于， 所述 步骤S2中， 所述的项目工期， 定义 为： 其中， 和 分别表示任务Tj的开始时间和完成时间， 且 所述的项目完成质量的定义如下： 其中， 表示开发者ei对任务Tj的熟练程度， 表示开发者信誉度， xij表示开发 者ei对任务Tj的投入度。 4.根据权利要求1所述的基于分组学习粒子群优化的众包软件项目调度方法， 其特征 在于， 所述 步骤S3中， 所述的约束条件 包括以下三个： 1)任务技能约束指参与某项任务的所有开发者总的技能集合必须满足该任务的所有 技能需求， 即： 其中， reqj表示任务Tj所需技能集， 表示开发者ei已掌握的技能集合， xij表示开发者 ei对任务Tj的投入度； 2)开发者不能超负荷工作约束指的是， 在任意时刻t， 每个开发者对可执行任务集的总 投入度不得超过 该开发者的最大投入， 即： 权　利　要　求　书 2/4 页 3 CN 114139453 A 3