﻿ 改进遗传算法在MSPSP问题中的验证
 计算机系统应用  2020, Vol. 29 Issue (10): 235-241 PDF

1. 东南大学 自动化学院, 南京 210096;
2. 复杂工程系统测量与控制教育部重点实验室, 南京 210096

Verification of Improved Genetic Algorithm in MSPSP Problem
SONG Yao1,2, YANG Yan-Lan1,2, YE Hua1,2
1. School of Automation, Southeast University, Nanjing 210096, China;
2. Key Laboratory of Measurement and Control of Complex Systems of Engineering, Ministry of Education, Nanjing 210096, China
Foundation item: The Fundamental Research Funds for the Central Universities of China (2242020K40244)
Abstract: In order to solve the Multi-Skilled resource-constrained Project Scheduling Problem (MSPSP), this study proposes an improved genetic algorithm. First, based on the mathematical model of the problem, a priority-based real number encoding method is established, and the objective function is converted into a fitness function for subsequent fitness calculations. Next, the niche technology based on group sharing is incorporated into the selection process of the genetic algorithm. In addition, with the help of deterministic sampling selection and subpopulation adjustment, the search ability of the algorithm is further improved. Then, gene repair and multiple verification mechanisms are introduced in the crossover and mutation operations to enhance the algorithm’s optimization ability. Finally, the overall process of the algorithm is given. The effect of the algorithm on the iMOPSE data set shows that the improved genetic algorithm is an effective method for solving MSPSP problem, and it has a sound reference significance for the study of related practical problems.
Key words: resource-constrained project scheduling     MSPSP     genetic algorithm     niche technology

1 MSPSP介绍 1.1 问题描述

MSPSP的基本概念是: 一个项目中涉及多个任务, 任务之间存在时间约束关系, 项目中的各种资源都具备一种或多种技能, 问题的目标是在满足各种约束的条件下合理调度和分配已有的资源和任务, 使得完成整个项目的总时间或总成本最小化.

 图 1 MSPSP示意图

1.2 数学模型

J: 任务集合, J={1, 2, ···, m};

H: 资源集合, H={1, 2, ···, n};

S: 技能集合;

dj: 完成任务j的工期;

bj: 任务j的开始时间;

fj: 任务j的结束时间;

kjh: 任务j所需要的资源 h的数量;

Pj: 任务j的前置任务集合;

Kh: 资源h的数量;

wh: 资源h的单位成本;

Sh: 资源h所拥有的技能集合;

Jh: 资源h可完成的任务集合;

ls: 技能s的等级;

qs: 技能s的类别;

α: 优化目标的权重系数;

T: 工作持续时间;

Qjht: 0-1变量, 资源ht时刻作用于任务j时为1, 否则为0.

MSPSP的数学模型为:

 $\min {F_s} = \min \alpha {F_\tau } + (1 - \alpha ){F_c}\quad \alpha \in [0,1]$ (1)

 ${F_\tau } = \mathop {\max }\limits_{j \in J} {f_j}$ (2)
 ${F_c} = \sum\limits_{j = 1}^m {\sum\limits_{h = 1}^n {{d_j}{w_h}\theta (jh)} }$ (3)

 ${f_j} = {b_j} + {d_j}\quad \forall j \in J$ (4)
 ${f_p} \le {f_j}\quad \forall j \in J,\forall p \in {P_j}$ (5)
 ${S_h}\not = \emptyset \quad \forall h \in H,{S_h} \in S$ (6)
 ${w_h} \ge 0\quad \forall h \in H$ (7)
 $\sum\limits_{j = 1}^m {{Q_{jht}} \le 1\quad \forall h \in H,\forall t \in T} ,\forall j \in J$ (8)
 ${l_s} \ge {l_{{s_i}}} \wedge {q_s} = {q_{{s_i}}}\quad \forall i \in {J_h},\exists s \in {S_h}$ (9)
 $\theta (jh) = {Q_{jht}} = \left\{ {\begin{array}{*{20}{c}} {1\quad {b_j} \le t \le {f_j}}\\ {0\quad t \notin [{b_j},{f_j}]} \end{array}} \right.\quad \forall j \in J,\forall h \in H,\forall t \in T$ (10)

2 改进遗传算法 2.1 编解码方案

(1) 在不考虑技能约束的情况下, 根据任务的权重生成任务序列, 当权重相等时, 任务编号小的优先;

(2) 根据技能约束和资源约束对资源进行分配, 在此过程中如果发现资源分配冲突则需要对任务序列进行调整, 如果无法通过调整满足需求则放弃该方案.

2.2 适应度函数

 ${f_g}({c_k}) = \frac{{{F_{s\_\max }} - {F_s}}}{{{F_{s\_\max }} - {F_{s\_\min }}}}$ (11)

2.3 基于群体共享的小生境选择

(1) 算法搜索初期, 适应度很好的一批个体不但拥有更长的生存时间, 而且易被视为优良父代将本身的基因传承下去, 进而影响整个种群的进化方向, 从而削弱了算法的全局搜索能力;

(2) 算法搜索后期, 经过多代的进化, 个体间的差异变小, 种群多样性降低, 演变成了近亲繁殖, 在此基础上生成的后代也很难有新的变化, 最终算法可能会陷入局部最优.

2.3.1 定义说明

 $\begin{array}{l} d({c_i},{c_j}) = ||{c_i} - {c_j}|| = \sqrt {\displaystyle \sum\limits_{k = 1}^{binLen} {{{({c_{ik}} - {c_{jk}})}^2}} } \\ \forall {c_i},{c_j} \in G,{c_i} \ne {c_j} \end{array}$ (12)

 $s({c_i},{c_j}) = 1 - \frac{{d({c_i},{c_j})}}{{binLen}}$ (13)

 ${s_g} = \sum {s({c_i},{c_j})} \quad \forall {c_i},{c_j} \in G,{c_i} \ne {c_j}$ (14)
2.3.2 确定式采样选择

Step 1. 计算各个子种群中的个体在下一代中的期望数目:

 ${N_{exp}}({c_i}) = subS\!i{\textit{z}} e \cdot \frac{{f({c_i})}}{{\displaystyle \sum\limits_{i = 1}^{subSi{\textit{z}} e} {f({c_i})} }}\;\;\;{\kern 1pt} i = 1,2, \cdots ,subS\!i{\textit{z}} e$ (15)

Step 2. 取 $\left[ {{N_{\rm {exp}}}({c_i})} \right]$ 作为 ${c_i}$ 在下一代中的生存数目, 其中 $\left[ {{N_{\rm {exp}}}({c_i})} \right]$ 表示不大于 ${N_{\rm {exp}}}({c_i})$ 的最大整数;

Step 3. 根据 ${N_{\rm {exp}}}({c_i})$ 的小数部分对所有个体进行排序, 选择最大的 $subS\!i{\textit{z}}e - \displaystyle \sum\limits_{i = 1}^{subS\!i{\textit{z}}e} {\left[ {{N_{\rm {exp}}}({c_i})} \right]}$ 个个体进入到下一代种群中.

2.3.3 子种群适应度和规模调整

(1) 根据共享种群的群体共享度占总群体共享度的比值, 略微调高共享种群的适应度;

(2) 当普通种群的群体共享度大于共享种群的群体共享度时, 调低普通种群的适应度, 反之调高;

(3) 在总的种群规模不变的情况下, 根据种群的适应度比例重新分配子种群的规模.

 ${f_{\rm {share}}} = {f_{\rm {share}}} \cdot \exp ({N_e}\frac{{{s_{\rm {share}}}}}{{\displaystyle \sum\limits_{j = 1}^{{N_{\rm {sub}}}} {{s_g}(j)} }})$ (16)

 ${f_{\rm {others}}} = {f_{\rm{others}}}\exp \left( - \frac{{{s_g} - {s_{\rm {share}}}}}{{{s_{\rm {share}}}}}\right)$ (17)

 $subS\!i{\textit{z}} e(i) = \frac{{{f_g}(i)}}{{\displaystyle \sum\limits_{j = 1}^{{N_{\rm {sub}}}} {{f_g}(j)} }} \cdot popS\!i{\textit{z}} e\quad i = 1,2, \cdots ,{N_{\rm {sub}}}$ (18)

2.4 基于修复机制的单点交叉

 图 2 基于修复机制的单点交叉示意图

2.5 基于多重验证的变异

Step 1. 随机为子种群中的所有个体分配概率 $p({c_i})$ ;

Step 2. 选择一个个体, 判断是否满足 $p({c_i}) \le {P_m}$ , 如果是则执行变异操作, 否则另选个体进行判断;

Step 3. 在所选个体上随机选择两个任务 $c_i^{{k_1}}$ $c_i^{{k_2}}$ 进行交换;

Step 4. 判断新个体是否满足时序约束, 且适应度比旧个体高, 如果都满足则用新个体代替旧个体; 否则抛弃新个体, 保留旧个体;

Step 5. 判断当前种群中的所有个体是否都检测完毕, 如果是, 则结束变异操作; 否则转到Step 2.

2.6 算法总流程

Step 1. 设置遗传算法的相关参数(种群规模 $popSi{\textit{z}}e$ , 变异概率 ${P_m}$ , 最大迭代次数 ${N_{\rm {iter}}}$ ), 并用贪心算法初始化种群;

Step 2. 划分子种群;

Step 3. 计算个体的适应度, 并在各个子种群内独立执行进化操作: 首先按照确定式采样规则进行个体选择, 然后执行基于修复机制的单点交叉操作, 最后完成基于多重验证的变异操作;

Step 4. 判断子群体进化次数 ${k_{\rm {sub}}}$ 是否达到上限值 ${N_e}$ , 如果是则先将 ${k_{\rm {sub}}}$ 清零, 再转到Step 5; 否则转到Step 3;

Step 5. 计算子种群的平均适应度, 选择适应度值最高的作为共享种群;

Step 6. 根据群体共享度和适应度调整所有子种群的适应度和规模;

Step 7. 淘汰连续几代表现最差的子群体, 并产生相同规模的新群体进行替换;

Step 8. 判断当前迭代次数是否达到上限, 或者连续几代的求解结果偏差是否满足收敛条件, 如果满足任意一条则结束算法, 输出结果; 否则转到Step 3.

3 实验分析

 图 3 改进遗传算法流程图

 图 4 改进GA和传统GA在10_20_46_15上的求解对比图( $\alpha {\rm{ = }}1$ )

4 结束语

 [1] Blazewicz J, Lenstra JK, Rinnooy Kan AHG. Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 1983, 5(1): 11-24. DOI:10.1016/0166-218X(83)90012-4 [2] 任逸飞, 陆志强, 刘欣仪, 等. 考虑技能水平的多技能资源约束项目调度. 工学版, 2017, 51(5): 1000-1006. [3] Myszkowski PB, Skowroński ME, Podlodowski L. Novel heuristic solutions for multi-skill resource-constrained project scheduling problem. Proceedings of 2013 Federated Conference on Computer Science and Information Systems. Krakow, Poland. 2013. 159–166. [4] Skowroński ME, Myszkowski PB, Adamski M, et al. Tabu search approach for multi-skill resource-constrained project scheduling problem. Proceedings of 2013 Federated Conference on Computer Science and Information Systems. Krakow, Poland. 2013. 153–158. [5] Myszkowski PB, Skowroński ME. Specialized genetic operators for multi-skill resource-constrained project scheduling problem. Proceedings of the 19th International Conference on Soft Computing Mendel 2013. At Brno, Czech Republic. 2013. 57–62. [6] Myszkowski PB, Skowroński ME, Sikora K. A new benchmark dataset for multi-skill resource-constrained project scheduling problem. Proceedings of 2015 Federated Conference on Computer Science and Information Systems. Lodz, Poland. 2015. 129–138. [7] 张立毅, 高杨, 费腾. 求解旅行商问题的萤火虫遗传算法. 计算机工程与设计, 2019, 40(7): 1939-1944. [8] Laszczyk M, Myszkowski PB. Improved selection in evolutionary multi-objective optimization of multi-skill resource-constrained project scheduling problem. Information Sciences, 2019, 481: 412-431. DOI:10.1016/j.ins.2019.01.002 [9] Lin J, Zhu L, Gao KZ. A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. Expert Systems With Applications, 2020, 140: 112915. DOI:10.1016/j.eswa.2019.112915 [10] Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 1996, 90(2): 320-333. DOI:10.1016/0377-2217(95)00357-6 [11] 包振明, 王琪, 徐一新, 等. 基于小生境遗传算法的两栖车辆车轮收放装置的优化. 汽车实用技术, 2015(9): 41-45. [12] 梁存利. 遗传算法在分配问题中的应用[硕士学位论文]. 西安: 西安电子科技大学, 2006. [13] Myszkowski PB, Skowroński ME, Olech ŁP, et al. Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem. Soft Computing, 2015, 19(12): 3599-3619. DOI:10.1007/s00500-014-1455-x