导弹技术保障资源均衡优化的遗传算法求解

瞿 军，吴文军，黄 全

（1.海军航空工程学院 a.飞行器工程系；b.研究生管理大队，山东 烟台 264001；2.91515 部队，海南 三亚 572016）

导弹技术保障是一项复杂的系统工程，需要进行周密计划、合理组织。资源均衡是制定保障计划时需要考虑的一个重要问题，资源经过均衡优化后，可以削减资源使用的峰值，便于组织和管理。

资源均衡优化是一类复杂的组合优化问题，虽然采用分枝定界法等传统方法能得到可靠的解，但是存在求解效率低、计算量大的不足。现代智能优化方法如模拟退火算法、遗传算法等，克服了上述的缺陷，得到了广泛的应用。比较而言，遗传算法作为一种全局最优搜索算法，其性能是最好的[1]。

本文利用遗传算法对导弹技术保障中的人力资源均衡优化进行研究，旨在为保障资源的优化配置提供一种合理的方法和依据。

1 资源均衡优化模型的建立

1.1 问题分析

资源均衡优化是在不影响项目按期完工的前提下，利用仿真计算得到的工作时差，不断改进初始进度计划，使得某一评价资源均衡程度的指标达到最优的过程。评价指标有不均衡系数、方差、最大绝对离差和极差值4种[2]。本文采用资源方差指标来评价。

资源均衡优化的实质是在每项工作的总时差范围内确定一个最佳的时间作为工作的开始时间，最后使总体的资源分布趋于均衡。各项工作的实际开始时间 TS (i,j)就是工作最早开始时间 TE(i,j)加上该工作总时差 R (i,j)范围内的一个随机值，即

实际上就是在n 项非关键工作的最早和最迟开始时间所构成的解空间中找到满足约束条件的开工时间序列，即 TS=(T S1,TS2,…,TSn)，使资源均衡的评价指标最优。在给定初始网络计划的条件下，假设每项工作所需资源量事先确定，网络计划的时间参数通过仿真计算事先得到。

1.2 资源均衡优化模型的建立

根据初始资源计划及仿真计算得到的初始时间参数，以工期内的资源强度方差值最小作为评价目标函数，以工期一定、各项工作的紧前紧后关系等作为约束条件，建立优化模型如下：

式中：T为项目仿真总工期；R、R (t)分别为项目平均资源强度值和t时刻的资源强度值；Ri′j、Rij(t)分别为工作(i,j)的资源强度值和t时刻的资源强度值；D (i,j)、TE(i,j)、TL(i,j)和 TS (i,j)分别为工作(i,j)的持续时间、最早开工时间、最迟开工时间和实际开工时间；(h,i)为工作(i,j)的紧前工作；m为工作的总项数。

2 资源均衡优化的遗传算法设计

2.1 染色体结构和编码设计及适应度设计

1）染色体结构和编码设计。编码是设计算法时的关键步骤，将影响到进化运算的精度和效率。本文以每项工作的实际开始时间TSi作为基因值，然后按照工作编号顺序将所有工作排列成一行，形成一个染色体串。由于系统涉及的工作数量较多，采用实数编码，以提高算法运行效率。

2）适应度设计。遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来确定的。由于目标函数是求最小优化问题，所以进行如下变换[3]

式中：νk为当前种群的第k个染色体；g (νk)为适应度函数；f (νk)为目标函数值；fmax和 fmin分别为当前种群的最大和最小目标函数值；γ ∈[0,1]，可以防止式(4)被零除，还可使选择行为从适应度比例选择调整到纯随机选择。

2.2 遗传算子设计及控制参数的确定

遗传算法的操作算子一般包括选择、交叉和变异三种基本操作[4-5]，它们构造了遗传算法具备强大搜索能力的核心。

1）选择操作。选择之前要计算种群中个体的适应度，然后根据种群中个体的适应度大小，确定每个个体的选择概率。选择的方法有多种，最常用的操作方法[4]有比例选择、排序选择和随机联赛选择等。本文采用比例选择，即产生随机数 ξ∈[0]1,，若

则选择状态i 进行复制，其中 fi为个体i的适应度。

2）交叉操作。交叉操作在配对的两个个体之间进行。对于实数编码，其交叉操作的运算方式大体上可以分为传统交叉、算术交叉和基于方向的交叉三种[3]。本文采用算术交叉，双亲产生的两个后代定义为

其中，0＜α＜1。

3）变异操作设计。对实数编码，变异操作的运算方法分为传统变异、算术变异和基于方向的变异三种类型，本文采用算术变异中的非均匀变异[4]。

对于父代x，若元素 xk被选出进行变异，则后代为则

式中：t为遗传代数；∆ (t,y)为微调函数。

∆(t,y)返回[0,y]中符合非均匀分布的一个随机数，使得 ∆(t,y)随t 增加而趋于0的概率逐渐增加。函数的这种性质使得算法在初始阶段进行均匀随机搜索，而到后期则进行局部搜索。∆(t,y)计算公式：

式中：r为[0]1,内的随机数；T为最大进化代数；b为不均匀度参数[4]，取3。

种群规模M 取40、交叉概率 pc取0.8、变异概率 pm取0.04、最大代数T 取100。[3-4]

2.3 非法个体的处理

对交叉和变异过程中产生的非法个体，目前有拒绝策略、改进遗传算子策略、修复策略和惩罚策略四种处理方式[6]，本文采用修复策略。依据基本约束：设计编码范围，产生初始种群及后代个体；利用修复程序对所有工作逐一判断是否满足：若不满足，强行改变 Ts(j)使其成立，解决了变量间的冲突。

2.4 流程设计

根据前文分析，资源均衡优化流程如图1所示。

图1 资源均衡优化流程图

3 实例求解

某导弹分系统现有的技术准备流程为一条作业线，所有工作都是关键工作。经分析发现，在资源和场地许可的条件下，有些工作可以并行进行，以缩短准备时间。优化后的流程网络计划图见图2。

利用PERT仿真，可得到最早、最迟开工时间等时间参数，如表1所示（表中，ES、LS、PR、GA 开工分别指最早、最迟开始时间、Project2003和遗传算法优化后的开始时间开工，以项目开工为0时刻开始计，单位min）。

图2 优化后的技术准备流程网络计划图

表1 不同方案开工时间表

若项目所有工作以最早开始时间开工，资源强度方差为17.9122，资源最大负荷为20人，如图3a）所示；若以最迟开始时间开工，资源强度方差为9.410 4，资源最大负荷为16人，如图3b）所示。

图3 初始资源负荷图

利用遗传算法进行资源均衡优化，优化结果如图4所示，进化到第96代得到的34 项非关键工作的开工时间，见表1，目标函数值5.6507，资源最大负荷12人，见图5a），资源强度均衡性显然优于最早或最迟开始时间开工。而利用Project 2003 进行优化，目标函数值8.5553，资源最大负荷13人，见图5b），遗传算法的优化结果和效率显然更优。

图4 资源均衡遗传算法优化结果

图5 优化后的资源负荷图

4 结论

利用遗传算法对某导弹技术保障资源进行均衡优化，使资源配置更加合理。优化结果表明本文采用的遗传算法求解资源均衡优化完全可行，优化模型是合理有效的，优化效果明显优于Project 2003，而且可搜索到多个次优方案供管理者选用，这是Project 2003 无法实现的，为导弹技术保障资源的均衡优化提供了合理的方法和依据。

[1]HARTMANN S,KOLISCH R.Experimental evaluation of state-of-the-art heuristics for the resourceconstrained project scheduling problem[J].European Journal of Operational Research,2000(127):394-407.

[2]李良宝.建设项目施工进度计划仿真研究[D].哈尔滨:哈尔滨工业大学,2007:69-70.

[3]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2003:205-208:21-30.

[4]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2000:25-58.

[5]HEGAZY T.Optimization of resource allocation and leveling using genetic algorithms[J].Journal Construction Engineering Management,1999,117(3):380-392.

[6]SONKE HARTMANN.A self-adapting genetic algorithm for project scheduling under resource constraints[J].Naval Research Logistics,2002(49):433-448.