一种基于遗传文化基因算法的项目调度方法

摘要

本发明公开了一种基于遗传文化基因算法的项目调度方法，（1）读取项目信息，包括任务和软件工程师的属性；（2）初始化算法参数；（3）产生初始父代种群，并进行局部搜索；（4）对父代种群执行选择、交叉和变异操作，构成子代种群；（5）对子代种群进行局部搜索；（6）合并父代和经局部搜索后的子代种群，从中选取适应度最优的一半个体构成下一代父代种群并进行迭代；（7）判断迭代代数是否达到最大值，若达到，则终止迭代，输出适应度最优的个体，该个体即为项目中每位软件工程师在每项任务中投入的工作量分配结果。本发明具有搜索能力强，生成的调度方案效率高的优点。

主权项

一种基于遗传文化基因算法的项目调度方法，其特征在于，包括以下步骤：(1)读取项目的输入信息，定义优化目标，设定约束条件：项目的输入信息包括每个任务的工作量、技能要求和任务优先级图，每位软件工程师所掌握的技能、可在本项目中投入的最大工作量、正常月薪和加班月薪；优化目标包括项目工期和项目成本；约束条件包括任务技能约束和软件工程师未超负荷工作的约束；(2)初始化遗传文化基因算法参数：设置遗传文化基因算法的迭代次数T_max、种群规模size_pop、联赛选择规模S_tour、交叉概率P_c以及局部搜索的迭代次数_gmax，设项目中有M名软件工程师，N项任务，则变异概率P_m为1/(MN)，设迭代次数计数器t＝0；(3)产生初始父代种群，并进行局部搜索，得到新的父代种群：随机生成size_pop个个体构成初始父代种群P'(t)，每个个体表示一个工作量分配矩阵：X＝(x_ij)_M×N其中,为第i个工程师e_i在第j项任务T_j中投入的工作量占全日制工作量的百分比，i＝1,2,…,M，j＝1,2,…,N；为第i个工程师e_i能够对本项目投入的最大工作量占全日制工作量的百分比；k为解的划分粒度；计算初始种群中每个个体的目标值duration和cost，duration和cost分别表示项目工期和成本，并进行约束处理；按下式计算每个个体的适应度：f(X)＝ω₁·duration+ω₂·cost其中，ω₁和ω₂表示目标duration和cost的相对重要性权重；对每个个体分别进行局部搜索，得到新的父代种群P(t)；从P(t)中确定出当前最优个体X_best，即适应度值最小的个体；(4)生成子代种群：对父代种群P(t)执行选择、交叉和变异操作，产生新的个体构成子代种群Q'(t)；计算Q'(t)中每个子代个体的目标值和适应度；(5)对子代种群进行局部搜索：在子代种群Q'(t)中每个个体V_p的邻域内，分别执行局部搜索操作得到新个体Z_p，其中，p＝1,2,…,size_pop；将Z_p与当前最优个体X_best进行比较，如果Z_p的适应度优于X_best，即f(Z_p)＜f(X_best)，则令X_best＝Z_p；经局部搜索后产生的所有个体Z_p构成新的子代种群Q(t)；(6)生成新一代父代种群：合并父代种群P(t)和子代种群Q(t)，从中选取适应度最优的一半个体构成下一代父代种群P(t+1)；令t＝t+1；(7)终止准则判断：若t＞T_max，则终止迭代，输出适应度最优个体X_best，该个体即为项目中每位软件工程师在每项任务中投入的工作量分配结果；否则，转至步骤(4)。