遗传算法在项目管理多目标决策模型中的应用

周红

摘要

项目管理工作中成本、工期、质量和资源构成互为约束条件的基本要素，各个要素之间有多种组合模式可以实现项目目标。但如何在多种组合模式、多种约束条件和多种资源之间取得平衡，以达成项目目标是本文论述的重点。本文提供一种模型用于综合考虑成本、工期和资源，并使用基本遗传算法建立解决问题的数学模型，最后通过实际应用说明该模型在项目管理多目标决策中的有效性。

【关键词】遗传算法 项目管理 多目标决策

1 引言

项目管理通过建立在时间轴上一系列项目活动使用资源，凝聚价值，达成项目目标。随着项目的复杂度和成本的不断提高，对项目管理有效性的要求也越来越高。项目管理者拟定项目计划时需要综合考虑多个项目管理目标，如工期、成本、资源等。过去我们经常使用PERT/CPM方法安排项目计划，但是它在复杂项目应用中有着较大的局限性。本文主要阐述实际项目中存在多种组合模式、多个资源约束条件下，对项目管理多目标决策问题进行研究，从而指导项目管理者制定有效的项目计划。

每个项目活动均存在多种实现途径，即多种成本、工期和资源的组合模式，每种组合模式中完成项目活动所需的资源种类、数量和工期也就不同，并且，项目资源在项目活动的时间轴上是互斥的，一种资源安排到项目活动A，则就不能再同时安排到项目活动B，即项目的资源之间存在约束关系，尤其在信息技术领域这种情况尤为突出。下面我们将建立一种数学模型，在多种组合模式、多个项目资源的情况下对项目的成本、工期和资源分配进行综合决策，安排比较合理的项目计划，实现项目管理目标。

2 数学模型

2.1 问题描述

已知：某项目有i个项目活动，分别记为T_i;有j种资源，分别记为R_j，每种资源的总量分别为N_j，第i种资源的单位成本为C_j;M_im表示项目活动i的第m种组合模式;在组合模式M_im下，对各资源的需求量为（a_im^（1），_im^（2），a_im^（3），……，a_im^（j）），所需的工期为D_im;

问题：计算各个项目活动的组合模式集（M₁₁]，m_2k2，……M_iki，使得：

（1）成本较低;

（2）工期较短;

（3）资源分配较平衡。

约束条件：

（1）Nk，其中k=1，2 ....... j;即每种资源的需求量不能超过其总量;

（2）总成本在Co_max以内;

（3）总工期在D_max以内。

2.2 几点假设

（1）资源是指消耗性资源，或时间点上互斥的人力资源;

（2）项目活动逻辑关系一定，不随组合模式而变化;

（3）成本仅考虑直接成本和间接成本，且间接成本和工期存在线性函数关系。

（4）构造度量函数评价项目管理目标，且度量函数权重之和为1。

2.3 問题模型

（1）在组合模式集（M_1k1，M_2k2，M_3k3，，……M_{iki）下对i种资源的需求量为则资}

源的直接成本为。根据假设，间接成本是工期的一个线性函数，记为Co_i=a*D+b（其中a、b为系数），则总成本CO=Co_d+CO_i;

（2）在组合模式集（M_1k1，M_2k2，M_3k3，，……M_iki）下对应的工期为（D_1k1，D_2k2，D_3k3，……，D_iki），根据项目活动之间的逻辑关系可以计算出在该组合模式集下项目活动的关键路径，并计算出总工期D;

（3）资源平衡的效果采用标准差度量，第k种资源的标准差记为;D为总工期;P_d^（k）为第d天对资源k的需求量;p^（k）为在D天内平均每天对资源k的需求量。

2.4 度量函数

综上，我们构造一个项目管理目标的度量函数F，用于度量项目计划是否合理。上面三个项目管理目标的度量函数分别为F_工期、F_成本、F_资源平衡，每个度量函数的权重分别为ω_工期、ω_成本、ω_资源平衡，根据假设ω_工期+ω_成本+ω_资源平衡=1。

度量函数的构造基于以下原则：

（1）是无量纲函数，可比性较强;

（2）满足工期D，成本Co和资源分配的标准差S_k越小，度量函数的值越高;

（3）度量函数的取值范围比较相近，从而避免某一项目管理目标的函数值过大而掩盖其余目标的度量效果。

根据以上度量函数的构造原则，构造如下三个目标函数：

其中D₁，Co₁，S_k1参照基准，分别为当所有项目活动都选择第一种组合模式时对应的工期、成本和第k种资源分配的标准差;若S_k1为0，则另外选取其他组合模式，使之不为零作为对比值;ω_k为第k种资源分配标准差的权重。

根据度量函数并考虑约束条件，可得如下具有惩罚性的综合度量函数，记为（如图1所示）。

因此，问题就转化为求项目活动所在组合模式的最大值，具体实践中可以利用遗传算法进行搜索，找出多目标情况下的最优解。

3 遗传算法模型

遗传算法的基本理论是借鉴自然界生物从简单到复杂、低级到高级的优胜劣汰、适者生存的进化机制，其本质是一种求解优化问题的高效并行全局搜索方法。

遗传算法的主要计算过程是：从随机产生的一个初始种群开始，通过一些算子（选择、交叉、变异）的作用，产生下一代种群，再以新产生的种群为出发点，重复上述过程，直到满足结束准则为止。算法主要流程可描述为：

（1）编码。编码规则：设项目活动共有i个，则基因长度为i位，基因位置序号代表项目活动的序号，基因值代表项目活动所选的组合模式。例如，某项目有8个项目活动，则基因编码长度为8位，码串23432311代表项目活动T1选用组合模式2，项目活动T2选用组合模式3，以此类推。

（2）产生初始种群。先随机生成一定数目的个体，然后从中挑选出最好的个体加入到初始群体中，此过程不断迭代，直到初始群体规模达到预期值。

（3）计算每个个体的适应值。遗传算法在进化搜索中是以适应度函数为依据的。如果问题带有约束条件，则可采用惩罚函数将约束转化为一个带生存代价或惩罚因子的非约束问题。

对适应度函数的另一个问题是定标问题，即在遗传算法初期，因超常个体所占比例太大，导致选择过程过早收敛的早熟现象;另一方面，在进化过程中，有可能会出现群体的平均适应度已接近最佳个体适应度，此时每个个体有着计划相等的选择机会，从而使有目标的优化过程趋向无目标随机漫游现象。对前者，须设法降低某些超常个体的竞争力，而对后者则应提高个体的竞争力。针对这种现象可通干预个体适应度函数来实现，就就是适应度定标技术。

本文中项目管理目标的度量函数的构造同时考虑了以上两个问题。本算法计算适应度的步骤为：首先根据数码串译码，得到每个项目活动的模式;然后根据项目活动之间的逻辑关系和各模式下资源需求量和对应工期，计算项目的关键路径以及项目总工期、总成本和各资源平衡标准差;最后计算综合评价函数F。

（4）选出N/2对个体进入交配池，这里需要用到选择算子，目的是把优化的个体直接遗传下一代或通过配对交叉产生新的个体再遗传到下一代。选择算子有很多种，一般在实际应用中，可以根据问题的求解特点采用几种方法相结合的混合选择机制，这比单独使用某种选择方法效果要好。另外，Gunter Rundolph关于遗传算法收敛性问题有如下结论：

结论1：以变异概率p_m，交叉概率p_c，同时采用比例选择法的标准遗传算法不能收敛至全局最优解。

结论2：具有如结论1的参数设置，且在选择后保留当前最优解的遗产算法最终可收敛到全局最优解。

结论3：具有如结论1的参数设置，且在选择前保留当前最优解的遗产算法最终可收敛到全局最优解。

基于以上的结论，本算法采用蒙特卡洛法和最佳个体保留法相结合的选择算子。

（5）对每对个体依概率P_c执行交叉操作产生两个新个体，交叉算子是遗传算法的核心算子，本算法中的交叉算子采用部分匹配交叉（PMX）法。

（6）对每对个体依概率P_m执行变异操作，本算法中的变异算子采用基本变異算子。

（7）评价新产生的种群。

（8）判断是否满足终止准则，当群体中相同的个体数达到一定百分比时算法终止。

（9）输出最优解。

4 应用实例

假设某项目有8个项目活动，项目活动的逻辑关系见图2，其总工期不得超过30天，总成本不得超过130万元，项目中有3种资源，其总量分别为25个，30个，35个，三种资源的单价分别为1.2万元，1.5万元和1.万千元;间接成本按照公式：Co_i=0.2*D+1.5，ω₁、ω₂、ω₃分别为0.3，0.3，0.4;ω_工期、ω_成本、ω_资源平衡分别为0.6，0.35，0.05;每个项目活动对应的模式及其在该模式下资源的需求量和所需工期见表1。

按照上面所述模型及其算法，得到结果表2。

由表2可以看出，综合度量的结果中成本、工期均在预计范围内，资源分配基本均衡，使用本文所构造的模型在项目管理多目标决策时能够提供一个较优解，用于指导项目管理者安排项目计划。

5 结论与展望

本文首先提出项目管理多目标决策所面临的问题，经过综合分析建立数据模型和遗传算法模型，并通过具体项目的实践案例验证模型的可行性，用于指导项目管理者安排项目计划。不过，本文还存在一些问题需要深入分析研究，例如现实工作中的资源成本比较复杂，与工期的关系也不一定是线性的，项目活动之间的逻辑关系也可能对组合模式的工期、成本造成一定影响，后续将持续优化上文所述的模型，改进遗传算法模型中适应度函数的惩罚性因子，提高模型的客观性和稳定性。

参考文献

[1]叶平.基于PERT/CPM的甘特图应用研究[J].浙江建筑，2011.

[2]邱菀华，杨敏.项目价值管理理论与实务[J].机械工业出版社，2007.

[3]徐泽水.部分权重信息下多目标决策方法研究[J].系统工程理论与实践，2002（01）.

[4]周瑞芬.改进的遗传算法[J].企业技术开发，2011（11）.

[5]阚峻岭，李锋刚.基于相关性分析和遗传算法的属性选择[J].计算机工程，2010（36）：24.

[6]任江涛，黄焕宇，孙婧昊.印鉴，基于相关性分析及遗传算法的高维数据特征选择[J].计算机应用，2006（26）：6.

[7]哈罗德.科兹纳著，杨爱华，王丽珍，石一辰译.项目管理（计划、进度和控制的系统方法）[M].电子工业出版社，2011.

[8]潘光钦.项目进度管理中CPM、PERT和CCPM的比较研究[J].科学实践，2014.