软件学报  2018, Vol. 29 Issue (9): 2580-2594   PDF    
基于编码转换的离散演化算法设计与应用
贺毅朝1, 王熙照2, 赵书良3, 张新禄3     
1. 河北地质大学 信息工程学院, 河北 石家庄 050031;
2. 深圳大学 计算机与软件学院, 广东 深圳 518060;
3. 河北师范大学 数学与信息科学学院, 河北 石家庄 050024
摘要: 为了求解离散域上的组合优化问题,借鉴遗传算法(GA)、二进制粒子群优化(BPSO)和二进制差分演化(HBDE)中的映射方法,给出了一种基于映射变换思想设计离散演化算法(DisEA)的实用方法——编码转换法(ETM).为了说明ETM的实用性与有效性,首先,基于ETM给出了一个离散粒子群优化算法(DisPSO);然后,分别利用BPSO,HBDE和DisPSO等基于ETM构造的演化算法求解集合联盟背包问题和折扣{0-1}背包问题.通过与GA的计算结果比较指出,BPSO,HBDE和DisPSO的求解性能均优于GA,说明基于ETM提出的DisEA在求解背包问题方面具有良好的性能.由此表明,利用ETM方法设计DisEA是一种实用的有效方法.
关键词: 离散演化算法     编码转换     SUKP问题     D{0-1}KP问题    
Design and Applications of Discrete Evolutionary Algorithm Based on Encoding Transformation
HE Yi-Chao1, WANG Xi-Zhao2, ZHAO Shu-Liang3, ZHANG Xin-Lu3     
1. College of Information and Engineering, Hebei GEO University, Shijiazhuang 050031, China;
2. College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China;
3. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024, China
Foundation item: National Natural Science Foundation of China (61503252, 71371063, 11471097); Shenzhen Science and Technology Project (JCYJ20150324140036825); Scientific Research Plan of the Higher Education Institutions of Hebei Province, China (ZD2016005); Natural Science Foundation of Hebei Province of China (F2016403055)
Abstract: In order to solve a combinatorial optimization problem in discrete domains by using evolutionary algorithms, this study draws lessons from the design concept of genetic algorithm (GA), binary particle swarm optimization (BPSO) and binary differential evolution with hybrid encoding (HBDE), to propose a simple and practical method for designing discrete evolution algorithm (DisEA) based on the idea of mapping transformation. This method is named encoding transformation method (ETM). For illustrating the practicability of ETM, a discrete particle swarm optimization (DisPSO) algorithm based on ETM is presented. For showing the feasibility and effectiveness of ETM, GA, BPSO, HBDE and DisPSO are used to solve the set union knapsack problem (SUKP) and the discounted {0-1} knapsack problem (D{0-1}KP), respectively. The results show that for SUKP and D{0-1}KP, the discrete evolutionary algorithms based on ETM, i.e. BPSO, HBDE and DisPSO have better performance than GA. This indicates that the design of DisEA based on ETM is not only a feasible method, but also a very practical and efficient method.
Key words: discrete evolutionary algorithm     encoding transformation     set union knapsack problem     discounted{0-1}knapsack problem    

演化算法(evolutionary algorithm, 简称EA)[1]是一类群体智能算法, 主要优点是不需要计算导数和梯度, 不要求目标函数具有连续性, 并且算法具有内在的隐含并行性和极强的全局寻优能力.

经典EA有遗传算法(genetic algorithm, 简称GA)[2]、粒子群优化(particle swarm optimization, 简称PSO)[3]、差分演化(differential evolution, 简称DE)[4]、蚁群优化(ant colony optimization, 简称ACO)[5]和人工鱼群(artificial fish swarm, 简称AFS)[6]等, 已被广泛应用于数值优化、自动控制、图像处理、决策与规划、组合优化、信号处理、模式识别、人工生命、机器人学、机器学习和图像处理等领域[2-10].

近年来, 由于EA在求解优化问题中的成功应用, 引起了人们的极大关注, 纷纷通过模仿自然界中生物群体的行为或借鉴社会活动中的某些现象, 相继提出了诸如人工蜂群(artificial bee colony, 简称ABC)[11]、萤火虫算法(firefly algorithm, 简称FFA)[12]、烟花算法(fireworks algorithm, 简称FWA)[13]、果蝇优化(fruit fly optimization, 简称FFO)[14]、灰狼优化(grey wolf optimizer, 简称GWO)[15]、人工藻算法(artificial algae algorithm, 简称AAA)[16]和鸽群优化(pigeon-inspired optimization, 简称PIO)[17]等许多新颖演化算法.虽然大量新算法的提出壮大了EA家族, 为应用EA求解不同领域中的优化问题提供了更多新的可行方法, 但是并未改变经典EA所存在的缺点, 即:除了GA和ACO以外, 大部分算法只适于求解连续域上的数值优化问题, 不能被直接用于求解离散域上的组合优化问题.为了改变这种不利现状, 人们从对已有算法的改进进行尝试, 提出了两种可行方法:一种方法[18, 19]是改变原有算法的进化算子, 重新定义使之满足离散域上的计算要求, 以实现对组合优化问题的求解; 另一种方法[20, 21]是保持原有算法的进化算子不变, 利用映射将个体对应的实向量映射为一个0-1向量, 由此实现对某些组合优化问题(例如背包问题[21]和集合覆盖问题[22])的求解.本文是对后一种方法的总结与提高:首先, 指出GA、二进制粒子群优化(BPSO)[23]和具有混合编码的二进制差分演化(HBDE)[21]中编码转换思想的一致性, 给出一种将实向量映射为整型向量(包括0-1向量)的简单方法, 提出基于编码转换(ETM)设计离散演化算法(discrete evolutionary algorithm, 简称DisEA)的一般框架.然后, 基于ETM给出了一个离散粒子群优化算法(DisPSO), 通过对集合联盟背包问题(set union knapsack problem, 简称SUKP)[24, 25]和折扣{0-1}背包问题(discounted {0-1} knapsack problem, 简称D{0-1}KP)[26, 27]等的求解, 验证利用ETM设计DisEA的实用性与有效性.

本文在第1节分别简述了GA, BPSO和HBDE中实现编码转换所使用的映射及其简单性质.在第2节中分析了GA, BPSO和HBDE中编码转换函数的一致性, 给出了一种将实向量映射为整型向量的简单方法, 提出了基于编码转换方法ETM设计DisEA的一般思路, 并基于ETM给出了一个离散粒子群优化算法DisPSO.在第3节, 分别利用BPSO, HBDE和DisPSO求解SUKP和D{0-1}KP, 通过与GA及其改进算法的计算结果, 比较验证了基于ETM设计的离散演化算法在求解组合优化问题方面的优越性能, 以此说明利用ETM设计DisEA的实用性与有效性.最后总结全文并展望今后进一步的研究方向.

1 编码转换思想 1.1 GA中的编码转换思想

遗传算法[2, 28]是Holland教授于1975年借鉴生物进化规律提出的一种演化算法, 是最早被提出的演化算法之一, 已被广泛应用于数值优化、组合优化、机器学习、图像识别、神经网络和模糊控制等领域[28-30].GA的进化过程主要由3种遗传算子——交叉算子、变异算子和选择算子实现, 而且每一种遗传算子均存在多种不同的实现方式.限于篇幅, 有关它们的详细介绍不再赘述, 请见文献[28]中所述.

利用GA求解数值优化问题时, 一般个体编码采用0-1向量的形式, 这就必须将其转换为一个表示问题解向量的实数向量, 由此对个体进行性能的评价和实现对问题的求解.设个体X的编码为X=[x11, x12, …, x1k, x21, …, x2k, x31, …, xdk]∈{0, 1}dk, 它所对应的解向量为Y=[y1, y2, …, yd], 其中, yi∈[Li, Ui], Li < Ui且为实数, i=1, 2, …, d, d为问题的维数.记GA将dk维0-1向量X转换为d维实数向量Y的编码转化函数映射为ψGA, 则Y=ψGA(X), 且对于i=1, 2, …, d有:

$ {y_i} = {L_i} + \left( {\sum\nolimits_{j = 1}^k {{x_{ij}}{2^{j-1}}} } \right)\frac{{{U_i}-{L_i}}}{{{2^k}-1}} $ (1)

其中, δi=(Ui-Li)/(2k-1)表示第i维分量yi的编码精度.显然, ψGA是从离散空间{0, 1}dk到连续空间$\prod\nolimits_{i = 1}^d {\left[{{L_i}, {U_i}} \right]} $上的一个单射, 当限定解向量Y中分量yi的编码精度为δi之后, ψGA也可以看做是一个双射.

GA利用遗传算子产生新个体X∈{0, 1}dk, 利用映射ψGA求得它对应的解向量Y, 利用Y的目标函数值对个体X进行评价, 并根据评价结果确定当前全局最优个体.由此可以看出, 编码转换函数ψGA在GA的个体与解向量之间起着非常重要的桥梁作用.

1.2 BPSO中的编码转换思想

微粒群优化[3, 31]是由Kennedy和Eberhart在1995提出的一种演化算法, 其基本思想源于对自然界中鸟类等生物群体觅食过程的仿真研究.在PSO中, 每个粒子(个体)具有一个飞行速度和一个位置, 并用粒子位置表示待求解问题的一个潜在解.PSO利用速度更新方程不断改变粒子的飞行速度, 并根据其速度确定粒子的新位置, 不断搜寻更佳的结果, 以实现算法的进化过程.

设粒子的速度为V=[v1, v2, …, vd], 位置为X=[x1, x2, …, xd], P=[p1, p2, …, pd]表示粒子的历史最好位置, G=[g1, g2, …, gd]表示PSO的全局最好位置, 其中, vj∈[LVj, UVj], LVj < UVj且为实数, xj, pj, gj∈[LXj, UXj], LXj < UXj且为实数, j=1, 2, …, d, d为问题的维数, 则PSO依次利用公式(2)与公式(3)实现粒子速度与位置的更新:

$ {v_j} = {v_j} + {c_1} \times {r_1} \times \left( {{p_j}-{x_j}} \right) + {c_2} \times {r_2} \times \left( {{g_j}-{x_j}} \right) $ (2)
$ {x_j} = {v_j} + {x_j} $ (3)

其中, j=1, 2, …, d; r1~U(0, 1)与r2~U(0, 1)为两个相互独立的随机数; c1c2为加速常数, 在0~2之间取值.

为了能够利用PSO求解二元优化问题, Kennedy和Eberhart[23]于1997年提出了二进制微粒群算法(binary particle swarm optimization, 简称BPSO).在BPSO中, 粒子的速度V=[v1, v2, …, vd]中的分量均限定为vj∈[-A, A], A是一个正实数; 粒子的位置被一个0-1向量X=[x1, x2, …, xd]∈{0, 1}d取代, 粒子速度更新方程仍使用公式(2), 粒子的位置更新方程改为由公式(4)实现:

$ {x_j} = \left\{ \begin{gathered} 0, sig\left( {{v_j}} \right) \leqslant {r_3} \hfill \\ 1, {\text{otherwise}} \hfill \\ \end{gathered} \right. $ (4)

其中, sig(x)=1/(1+e-x)是模糊函数, r3~U(0, 1)是一个随机数.

在BPSO中, 确定粒子的位置实质上是利用一个从连续空间[-A, A]d上到离散空间{0, 1}d的映射ψBPSO实现的, 即X=ψBPSO(V), 其中, X的每一维分量xjV的相应分量vj利用公式(4)来确定.显然, 映射ψBPSO是BPSO中的编码转换函数, 它是一个满射, 并且在粒子的速度与位置(问题解向量)之间也起着重要的桥梁作用.

1.3 HBDE中的编码转换思想

差分演化[4, 32]是Storn和Price于1997年为求解切比雪夫多项式而提出的一种演化算法, 它也是基于实数编码的演化算法, 非常适合于求解连续域上的最优化问题, 在第1届IEEE演化大赛中表现超群, 引起了国内外学者的普遍关注.DE进化原理为:首先, 利用差异个体重组得到一个父子混合的中间个体, 若其优于父代个体则替换之, 否则保持父代个体不变.在DE的10种变异策略中, “DE/r/1/bin”使用最多, 为此, 下面基于此模式描述DE通过差异个体重组产生中间个体的方法.

X1=[x11, x12, …, x1d], X2=[x21, x22, …, x2d], X3=[x31, x32, …, x3d]是DE种群中不同于X=[x1, x2, …, xd]的3个互不相同的个体, V=[v1, v2, …, vd]是相应于个体X的中间个体, 其中, x1j, x2j, x3j, xj, vj∈[Lj, Uj], j=1, 2, …, d, d为问题维数, 则中间个体V利用下面的公式(5)产生:

$ {v_j} = \left\{ \begin{gathered} {x_{1, j}} + {F^*}\left( {{x_{2j}}-{x_{3j}}} \right), {\text{if}}\;r \leqslant CR \vee j = R\left( i \right) \hfill \\ {x_j}, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\text{otherwise}} \hfill \\ \end{gathered} \right. $ (5)

其中, 0 < F < 1称为缩放因子; r~U(0, 1)是一个随机数; CR称为变异因子, 且CR∈(0, 1);R(i)是[1, n]上的随机正整数.

为了利用DE求解二元优化问题, 贺毅朝等人[21, 33]基于编码转换设计理念提出了具有混合编码的二进制差分演化算法HBDE.在HBDE中, 限定个体X与中间个体V在[-A, A]d上取值, A是一个正实数, 并仍然使用公式(5)产生中间个体V.此外, 引入一个0-1向量Y=[y1, y2, …, yd]∈{0, 1}d作为个体X对应于求解问题的潜在解, Y利用映射Y=ψHBDE(X)得到, 其中, 分量yj(j=1, 2, …, d)与xj之间的对应关系见下式:

$ {y_j} = \left\{ \begin{gathered} 1, \;\;{\text{if}}\;{x_j} > 0 \hfill \\ 0, \;\;{\text{otherwise}} \hfill \\ \end{gathered} \right. $ (6)

易见, 映射Y=ψHBDE(X)是从连续空间[-A, A]d到离散空间{0, 1}d的一个满射, 它将个体X的实数向量编码转换为0-1向量Y作为问题的潜在解, 并由此利用Y的目标函数值来评价X的优劣, 实现了DE在二元优化问题求解中的应用.

2 一种设计DisEA的简单方法及其应用 2.1 基于编码转换思想的DisEA设计方法

无论是GA中从离散空间映射到连续空间上的编码转换函数ψGA, 还是BPSO和HBDE中从连续空间映射到离散空间上的编码转换函数ψBPSOψHBDE, 它们在算法中起到的作用是完全一致的, 都是为了把个体编码转换为问题的可行解或潜在解.事实上, 这种编码转换思想存在于每一个演化算法中, 因为即使是仅适于求解连续域上优化问题的演化算法(如PSO, DE, ABC和FFA等), 也可视其编码转换函数为连续空间上的一个自同构恒等映射.

E1是演化算法A中个体编码构成的度量空间, E2是待求解问题的潜在解构成的度量空间, 我们将利用从E1E2上的一个编码转换函数ψA对算法A离散化的方法称为编码转换法(encoding transformation method, 简称ETM).一般情况下, 函数ψA必须是一个满射.尽管理论上这样的满射有无数多个, 但从实用的角度而言, 简单高效且易于实现的ψA是算法A离散化的关键所在.

为了能够利用PSO, DE, AFS, ABC和FFA等演化算法求解可行解为{0, 1, …, n-1}d (其中n≥2)中的d维整型向量的组合优化问题, 例如可行解为{0, 1}d中的d维0-1向量的SUKP问题, 可行解为{0, 1, 2, 3}dd维整型向量的D{0-1}KP问题, 下面根据已有的工作经验, 借鉴BPSO和HBDE的设计思路给出一个简单通用且易于实现的编码转换函数ψDisEA.

设组合优化问题的可行解为Y=[y1, y2, …, yd]∈{0, 1, …, n-1}d, 其中, n≥2, d为问题的维数.设EA中个体X的编码为d维实数向量X=[x1, x2, …, xd], xj∈[-A, A], j=1, 2, …, d, A是一个正实数, 于是定义映射ψDisEA:[-A, A]d→{0, 1, …, n-1}d, n≥2, 对任意X∈[-A, A]d, Y=ψDisEA(X)且满足:

$ {y_j} =\\ \left\{ {\begin{array}{*{20}{l}} {0, \;\;\;\;\;\;\;{\text{if }}{x_j} \in [- A, - A + 2 \times A \times {\alpha _0})} \\ {k, \;\;\;\;\;\;\;{\text{if }}{x_j} \in [- A + 2 \times A \times \sum\nolimits_{i = 0}^{k- 1} {{\alpha _i}, - A + 2 \times A \times \sum\nolimits_{i = 0}^k {{\alpha _i}} } ), 1 \leqslant k \leqslant n - 2} \\ {n - 1, {\text{ if }}{x_j} \in [-A + 2 \times A \times \sum\nolimits_{i = 0}^{n-2} {{\alpha _i}, A}]} \end{array}} \right. $ (7)

其中, αj(j=0, 1, …, n-1)是满足条件α0+α1+…+αn-1=1且0 < aj < 1的实数.

容易看出, 映射ψDisEA对每一维分量yj是一个分段函数, 它将区间[-A, A]分成n个小区间:I0=[-A, -A+2A×α0), I1=[-A+2A×α0, -A+2A×(α0+α1)), …, In-2=[-A+2A×(α0+…+αn-3), -A+2A×(α0+…+αn-2)), In-1=[-A+2A×(α0+…+αn-2), A], 当分量xjIkyj=k.

在理论上, 公式(7)中满足条件α0+α1+…+αn-1=1且0 < aj < 1的实数α0, α1, …, αn-1有无数个, 如何选取它们的值, 是ψDisEA实现的关键.事实上, 注意到分量xj在[-A, A]上随机均匀变化, 而且它对应的yj值也是一个不确定的量, 因此我们可以取aj=1/n(j=0, 1, …, n-1), 于是, 公式(7)简化为

$ {y_j} = \\ \left\{ {\begin{array}{*{20}{l}} {0, \;\;\;\;\;\;\;{\text{if }}{x_j} \in [- A, - A + 2 \times A/n)} \\ {k, \;\;\;\;\;\;\;{\text{if }}{x_j} \in [- A + 2k \times A/n, - A + 2(k + 1) \times A/n), 1 \leqslant k \leqslant n- 2} \\ {n - 1, {\text{ if }}{x_j} \in [-A + 2(n-1) \times A/n, A]} \end{array}} \right. $ (8)

映射ψDisEA:[-A, A]d→{0, 1, …, n-1}d是一个满射, 它实现了将d维实数向量转化为d维整型向量的功能, 为设计DisEA提供了一个简单可行的编码转换方法.

显然, BPSO中的映射ψBPSO、HBDE中的映射ψHBDE以及BABC[25]中使用的编码转换函数均为ψDisEA的特例.为了说明如何利用ψDisEA基于ETM构造DisEA, 下面对已有演化算法A, 给出它的基于ETM构造的离散演化算法A-DisEA的一般算法框架.

算法1. A-DisEA.

Input:组合优化问题实例f(Y), 其中, Y∈{0, 1, …, n-1}d; 算法A的参数;

Output:最优解或近似最优解${Y^*} = [y_1^*, y_2^*, ..., y_d^*]$f(Y*).

1   随机产生初始种群P(0)={Xi(0)=[xi1(0), xi2(0), …, xid(0)]∈[-A, A]d|1≤iN};

2   Yi(0)←ψDisEA(Xi(0)), 1≤iN; //计算个体Xi(0)对应的解

3   根据f(Yi(0))确定P(0)中的最优个体B(0)=[b1(0), b2(0), …, bd(0)]和当前最好解Y*(0);t←1;

4   while (tMaxIt) do

5     利用算法A的进化算子产生种群P(t)={Xi(t)=[xi1(t), xi2(t), …, xid(t)]∈[-A, A]d|1≤iN};

6     Yi(t)←ψDisEA(Xi(t)), 1≤iN; //计算个体Xi(t)对应的潜在解

7     根据f(Yi(t))确定P(0)∪P(1)∪…∪P(t)中最优个体B(t)=[b1(t), b2(t), …, bd(t)]和当前最好解Y*(t);

8     tt+1;

9   end while

10   return (Y*(MaxIt), f(Y*(MaxIt))).

在算法1中, MaxIt是算法迭代次数, 它一般是维数d的常数倍.令算法A产生新一代种群的时间复杂度为T(A), 计算函数值f(Y)的时间复杂度为T(f), 则算法A-DisEA的时间复杂度为MaxIt×(T(A)+O(d×N)+N×T(f)).

2.2 基于ETM的离散粒子群优化算法

BPSO, HBDE和BABC等DisEA主要用于求解二元组合优化问题, 例如SUKP问题、集合覆盖问题[22]和可满足性问题[34]等, 并不完全适用于求解可行解为{0, 1, …, n-1}d(n≥3)上的一个整数向量的组合优化问题(例如有界背包问题[35]).为此, 下面基于A-DisEA框架, 利用PSO给出一个基于ETM的离散粒子群优化算法DisPSO, 以阐明如何利用已有演化算法基于ETM构造求解此类组合优化问题的离散演化算法.

Vi(t)=[vi1(t), vi2(t), …, vid(t)]∈[-A, A]d表示DisPSO的第t代种群P(t)中的第i个粒子的飞行速度, 它的位置记为Xi(t)=[xi1(t), xi2(t), …, xid(t)]∈{0, 1, …, n-1}d(n≥3), 表示所求解问题的一个可行解(或潜在解).又记Pi(t)=[pi1(t), pi2(t), …, pid(t)]∈{0, 1, …, n-1}d为第i个粒子的历史最好位置, G(t)=[g1(t), g2(t), …, gd(t)]∈{0, 1, …, n-1}dP(0)∪ P(1)∪…∪P(t)中的全局最好位置, MaxIt为算法的迭代次数, 则对于最大组合优化问题Maxf(X), X∈{0, 1, …, n-1}d (n≥3), DisPSO的算法伪代码描述如下:

算法2. DisPSO.

Input:Maxf(X)的一个实例, 参数A的值以及PSO的参数值;

Output:最优解或近似最优解G(MaxIt)∈{0, 1, …, n-1}df(G(MaxIt)).

1   随机产生初始种群P(0)={Vi(0)=[vi1(0), vi2(0), …, vid(0)]∈[-A, A]d|1≤iN};

2   Xi(0)←ψDisEA(Vi(0)), 并根据f(Xi(0))确定Pi(0), 1≤iN;

3   确定P(0)中的全局最好位置G(0);t←0;

4   while (t≤MaxIt) do

5     for i←1 to N do

6       for j←1 to d do //生成第t+1代种群P(t+1)

7         vij(t+1)←vij(t)+c1×r1×(pij(t)-xij(t))+c2×r2×(gj(t)-xij(t));

8       end for

9       Xi(t+1) ψDisEA(Vi(t+1)), 并根据f(Xi(t+1))确定Pi(t+1);

10     end for

11     确定P(0)∪P(1)∪…∪P(t+1)中的全局最好位置G(t+1);

12     tt+1;

13   end while

14   return (G(MaxIt), f(G(MaxIt))).

在算法2中, 编码转换函数yDisEA利用公式(7)实现; 参数r1, r2, c1c2与PSO中的含义完全相同; 参数A的值由yDisEA的值域中n的大小决定, n越大, A的值越大.一般地, 当n=4时, 可取A=3.0.易知, DisPSO的算法时间复杂度为O(MaxIt×(d+T(f))×N)), T(f)表示计算函数值f(X)的时间复杂度.

3 实例计算与比较

目前, 经典演化算法GA已成为衡量新算法性能优劣的标准.因此, 为了说明基于ETM构造的DisEA在求解组合优化问题时的性能优劣, 我们利用BPSO和HBDE求解SUKP问题, 利用DisPSO求解D{0-1}KP问题, 通过与GA的计算结果, 比较验证它们的求解性能.所有计算使用Acer Aspire E1-570G笔记本, 硬件配置为Intel(R) Core(TM)i5-3337u CPU-1.8GHz, 4GB DDR3内存(3.82GB可用), 操作系统为Microsoft Windows 8, 用C++语言编程实现各算法, 编译环境为Visual C++6.0.

3.1 BPSO, HBDE与GA求解SUKP的比较

SUKP[24]是0-1 KP的一个扩展形式.在SUKP中, 给定一个元素集合U={1, 2, …, n}和一个项的集合S={1, 2, …, m}, 其中:每一个项iS(i=1, 2, …, m)对应一个元素的非空子集UiU, 并具有一个价值pi>0;每一个元素jU (j=1, 2, …, n)具有一个重量wj>0.对于任意的非空子集AS, 定义A的价值为$P(A) = \sum\limits_{i \in A} {{p_i}} $, A的重量为W(A)= $\sum\nolimits_{j \in \bigcup\limits_{i \in A} {{U_i}} } {{w_j}} $.SUKP的目标是:对于给定预算(或背包载重)C, 求子集S*S, 使得在满足W(S*)≤C的前提下, P(S*)达到最大.

不失一般性, 设SUKP中pi, wjC均为正整数; 子集族{U1, U2, …, Um}是U的一个覆盖, 其中:UiU(i=1, 2, …, m)且UiΦ; W(S)>C且对∀iS, 有$\sum\nolimits_{j \in {U_i}} {{w_j}} \leqslant C$.设Y=[y1, y2, …, ym]∈{0, 1}m是一个m维0-1向量, AY={i|yiYyi=1, 1≤im}⊆S, 则SUKP的整数规划模型[25]

$ {\text{MAX}}f(Y) = \sum\nolimits_{i = 1}^m {{y_i}{p_i}} $ (9)
$ {\text{s}}{\text{.t}}{\text{. }}W({A_Y}) = \sum\nolimits_{j \in \bigcup\limits_{i \in {A_Y}} {{U_i}} } {{w_j}} \leqslant C $ (10)

显然, 任意0-1向量Y=[y0, y1, …, ym]∈{0, 1}m都是SUKP的一个潜在解, 当它满足约束条件(10)时是一个可行解, 否则为一个不可行解.

文献[25]中提出的BABC即是一个基于ETM的DisEA, 通过对3类大规模SUKP实例的计算表明, BABC的求解性能明显比GA的更优.因此, 我们只需比较BPSO, HBDE与GA在求解SUKP问题时的性能优劣, 即可判定基于ETM构造的离散演化算法在求解SUKP问题时的性能.

在BPSO, HBDE和GA中, 个体编码都采用n维0-1向量形式, 算法的最大迭代次数为MaxIt=Max{m, n}, 其中, m为SUKP中项的个数, n为元素个数; 并且均使用文献[25]中提出的算法S-GROA处理求解过程中所产生的不可行解.在HBDE中, 种群规模为N=20, [-A, A]=[-3.0, 3.0], 缩放因子F=0.5, 变异因子CR=0.3.在BPSO中, 种群规模为N=20, [-A, A]=[-5.0, 5.0], 加速常数为c1=c2=2.0.GA的种群规模为N=50, 其他参数设置与文献[25]中的完全相同, 略.

表 1~表 3中, CBEST是各SUKP实例目前已知的最好结果, Best和Worst是HBDE, BPSO和GA独立求解各实例100次所得结果中的最好值和最差值, Mean和StD是100次求解结果的平均值和标准差, Time是各算法独立求解每个实例一次的平均耗费时间.

Table 1 Comparing with HBDE, BPSO and GA for the first kinds of SUKP instances 表 1 利用HBDE, BPSO和GA求解第1类SUKP实例的计算结果比较

Table 2 Comparing with HBDE, BPSO and GA for the second kinds of SUKP instances 表 2 利用HBDE, BPSO和GA求解第2类SUKP实例的计算结果比较

Table 3 Comparing with HBDE, BPSO and GA for the third kinds of SUKP Instances 表 3 利用HBDE, BPSO and GA求解第3类SUKP实例的计算结果比较

表 1可以看出:

● 从求解效果看, BPSO求解所有实例的结果(Best, WorstMean)均优于GA; 除实例sukp400_385_0.10_ 0.75和sukp500_485_0.10_0.75以外, HBDE求解其他实例的结果(Best, WorstMean)均优于GA;

● 从稳定性看, HBDE的稳定性远远优于GA和BPSO, GA略优于BPSO;

● 虽然GA的求解速度比HBDE和BPSO快, 但当实例规模不大时, 它们之间的差距很小.

以上比较结果表明:HBDE和BPSO比GA更适于求解n>m的一类SUKP实例.

表 2可以看出:

● 从求解效果看, BPSO求解所有实例的结果(Best, WorstMean)均优于GA; 除实例sukp100_100_0.10_ 0.75和sukp300_300_0.15_0.85之外, HBDE求解其他实例的结果(Best, WorstMean)均优于GA;

● 从稳定性看, BPSO和HBDE的算法稳定性远远优于GA;

● 从求解速度看, GA的速度最快, HBDE和BPSO的速度虽然略慢, 但是与GA的差距不大.

以上比较结果表明:HBDE和BPSO比GA更适于求解n=m的一类SUKP实例.

表 3可以看出:

● 从求解效果看, 除了实例sukp185_200_0.15_0.85之外, BPSO求解其他实例的结果(Best, WorstMean)均优于GA; 除了实例sukp285_300_0.15_0.85以外, HBDE求解其他实例的结果(Best, WorstMean)均优于GA;

● 从稳定性看, HBDE的稳定性远远优于GA和BPSO, GA与BPSO的稳定性基本相同;

● 虽然GA的求解速度比HBDE和BPSO的略快, 但相比后者极佳的求解结果, 这点差距是微不足道的.

以上比较表明:HBDE和BPSO均比GA更适于求解n < m的一类SUKP实例.

可以看出:HBDE和BPSO求解SUKP问题的效果明显比GA的更佳, 稳定性也更好, 而且求解速度与GA差别不大.说明基于ETM方法构造的离散演化算法HBDE和BPSO是求解SUKP问题的有效算法, 由此也表明基于ETM构造离散演化算法是一种简单且有效的方法.

3.2 DisPSO, FirEGA与SecEGA求解D{0-1}KP的比较

D{0-1}KP[26]是Guldan于2007年提出的一个新颖背包问题, 它的定义为:给定n个均含有3个项(或物品)的项集, 项集i(0≤in-1)中含有的3个项分别记为3i, 3i+1, 3i+2, 其中:前两个项3i和3i+1具有的价值系数分别为p3ip3i+1, 具有的重量系数分别为w3iw3i+1; 前两个项合并在一起构成第3个项3i+2, 它具有的价值系数为p3i+2=p3i+p3i+1, 具有的折扣重量系数为w3i+2, 满足w3i+2 < w3i+w3i+1并且w3i < w3i+2, w3i+1 < w3i+2.在项集i(0≤in-1)中, 项3i, 3i+1, 3i+2中至多有一个可以被选择装入载重为C的背包中.D{0-1}KP为如何选择各项装入背包, 使得装入背包的所有项的重量系数之和在不超过背包载重的前提下价值系数之和达到最大?

不失一般性, 设pj, wj(0≤j≤3n-1)和C均为正整数, 且w3i+2C(0≤in-1), $\sum\nolimits_{i = 0}^{n-1} {{w_{3i + 2}}} > C$.则D{0-1}KP的第一数学模型[26]

$ {\text{MAX}}f(X) = \sum\nolimits_{i = 0}^{n-1} {({x_{3i}}{p_{3i}} + {x_{3i + 1}}{p_{3i + 1}} + {x_{3i + 2}}{p_{3i + 2}})} $ (11)
$ {\text{s}}{\text{.t}}{\text{.}}\;\;\;\;{x_{3i}} + {x_{3i + 1}} + {x_{3i + 2}} \leqslant 1, i = 1, 2, ..., n-1 $ (12)
$ \sum\nolimits_{i = 0}^{n-1} {({x_{3i}}{w_{3i}} + {x_{3i + 1}}{w_{3i + 1}} + {x_{3i + 2}}{w_{3i + 2}})} \leqslant C $ (13)
$ {x_{3i}}, {x_{3i + 1}}, {x_{3i + 2}} \in \left\{ {0, 1} \right\}, i = 0, 1, \ldots, n-1 $ (14)

其中, 变量xj(0≤j≤3n-1)表示项j是否被装入背包中:xj=1, 表示项j被装入了背包中; xj=0, 表示项j没有被装入背包.显然, 任意3n维0-1向量均表示D{0-1}KP的一个潜在解, 当它同时满足约束条件(12)和约束条件(13)时为一个可行解.

X=[x0, x1, …, xn-1]∈{0, 1, 2, 3}n为一个n维整型向量, 则D{0-1}KP的第二数学模型[27]

$ {\text{MAX}}f(X) = \sum\nolimits_{i = 0}^{n-1} {\left\lceil {{x_i}/3} \right\rceil {p_{3i + |{x_i}-1|}}} $ (15)
$ {\text{s}}{\text{.t}}{\text{. }}\sum\nolimits_{i = 0}^{n-1} {\left\lceil {{x_i}/3} \right\rceil {w_{3i + |{x_i}-1|}}} \leqslant C $ (16)
$ {x_i} \in \left\{ {0, 1, 2, 3} \right\}, i = 0, 1, \ldots, n-1 $ (17)

其中,

●  $\left\lceil x \right\rceil $为顶函数;

● 变量xi(0≤in-1)表示项集i中是否存在项被装入了背包中:xi=0, 表示项集i中没有项被装入背包; xi=1, 表示项3i被装入了背包中; xi=2, 表示项3i+1被装入了背包中; xi=3, 表示项3i+2被装入了背包中.

任意n维整型向量均表示D{0-1}KP的一个潜在解, 当其满足约束条件(16)时即为一个可行解.

文献[27]利用GA求解D{0-1}KP问题, 分别基于不同的模型给出了求解它的两种有效算法FirEGA和SecEGA.为此, 下面利用DisPSO求解文献[27]中的4类大规模D{0-1}KP实例, 通过与FirEGA和SecEGA的计算结果进行比较, 验证DisPSO的求解性能.在利用DisPSO求解时使用第二数学模型, 即个体的编码为{0, 1, 2, 3}n上一个n维整型向量; 种群规模和迭代次数与算法FirEGA和SecEGA的相同, 即N=50与MaxIt=3n, n为项集的个数; 取[-A, A]=[-3.0, 3.0], 加速常数为c1=c2=0.5.FirEGA和SecEGA的其他参数设置请参考文献[27], 不再赘述.

表 4~表 7中给出了所有实例的最优值OPT, DisPSO, FirEGA和SecEGA独立求解各实例100次的计算结果中的最好值Best和最差值Worst, 各实例100次独立计算结果的数学期望Mean与标准差StD以及各算法独立求解每个实例一次的平均耗费时间Time.

Table 4 Comparison of calculation results of DisPSO, FirEGA and SecEGA for solving UDKP1~UDKP10 表 4 DisPSO, FirEGA和SecEGA求解实例UDKP1~UDKP10的计算结果比较

Table 5 Comparison of calculation results of DisPSO, FirEGA and SecEGA for solving WDKP1~WDKP10 表 5 DisPSO, FirEGA和SecEGA求解实例WDKP1~WDKP10的计算结果比较

Table 6 Comparison of calculation results of DisPSO, FirEGA and SecEGA for solving SDKP1~SDKP10 表 6 DisPSO, FirEGA和SecEGA求解实例SDKP1~SDKP10的计算结果比较

Table 7 Comparison of calculation results of DisPSO, FirEGA and SecEGA for solving IDKP1~IDKP10 表 7 DisPSO, FirEGA和SecEGA求解实例IDKP1~IDKP10的计算结果比较

表 4可以看出:

● 从求解效果看, DisPSO求解所有实例的结果(Best, WorstMean)远远优于FirEGA和SecEGA的求解结果;

● 从稳定性看, DisPSO的StD值远比FirEGA和SecEGA的更小, 因此它的算法稳定性更佳;

● 虽然FirEGA和SecEGA的求解速度比DisPSO的略快, 但是这点差距不足以影响DisPSO在求解结果方面所具有的巨大优势.

因此, DisPSO比FirEGA和SecEGA更适用于求解UKDP类实例.

表 5可以看出:

● 从求解效果看, 除了SDKP10的Best以外, DisPSO求解所有实例的结果(Best, WorstMean)均远远优于FirEGA和SecEGA的结果;

● 从稳定性看, DisPSO的算法稳定性最好, FirEGA只是对部分实例而言稳定性较好, SecEGA的稳定性极差;

● 从求解速度看, 虽然FirEGA和SecEGA比DisPSO的速度快, 但是差距不大.

因此, DisPSO比FirEGA和SecEGA更适用于求解SKDP类实例.

表 6可以看出:

● 从求解效果看, DisPSO求解所有实例的结果(Best, WorstMean)远远优于FirEGA和SecEGA的求解结果;

● 从稳定性看, DisPSO的稳定性明显比FirEGA和SecEGA的更优, 并且随着实例规模的增大, 这种优势变得愈加明显;

● 虽然DisPSO的求解速度比FirEGA和SecEGA的略慢, 但是这点差距不足以撼动DisPSO在求解结果方面的明显优势.

因此, DisPSO比FirEGA和SecEGA更适用于求解WKDP类实例.

表 7可以看出:

● 从求解效果看, DisPSO求解所有实例的结果(Best, WorstMean)远远优于FirEGA和SecEGA的求解结果, 而且DisPSO能够求得IDKP1, IDKP2, IDKP4和IDKP5的最优值;

● 从稳定性看, DisPSO的算法稳定性远远比FirEGA和SecEGA的更优, 而且随着实例规模的增大, 这种优势变得愈加突出;

● 虽然DisPSO的求解速度比FirEGA和SecEGA的略慢, 但是对其在求解结果方面的优势影响不大.

因此, DisPSO比FirEGA和SecEGA更适用于求解IKDP类实例.

以上比较结果表明:DisPSO比FirEGA和SecEGA更适于求解D{0-1}KP问题, 这说明基于ETM方法构造的离散演化算法DisPSO不仅简单、易于实现, 而且求解D{0-1}KP问题的效果极佳.由此进一步表明:基于ETM方法构造DisEA不仅是可行的, 而且是高效的.

4 结束语

本文在分析GA, BPSO和HBDE中所使用的编码转换函数的共性基础上, 提出了一种基于编码转换思想设计离散演化算法(DisEA)的方法——编码转换法(ETM), 在给出一个简单且具有普遍适用性的编码转换函数ψDisEA的基础上, 提出了基于ETM设计DisEA的一般算法框架.随后, 利用函数ψDisEA, 基于ETM给出了一个离散粒子群优化算法DisPSO, 并分别利用BPSO, HBDE和DisPSO求解SUKP问题和D{0-1}KP问题.通过与GA及其改进算法的计算结果相比较, 验证了这些算法在求解组合优化问题方面的优越性能.这说明对已有EA(例如PSO, DE和ABC等), 基于ETM方法(使用函数ψDisEA)构造相应DisEA是一种可行且有效的方法.

当前, 存在许多组合优化问题的可行解表示为{0, 1, …, n-1}d(n≥4)上的一个d维整数向量更适宜, 例如有界背包问题[35]和广义二次多背包问题[36]等.DisPSO(或DisDE, DisABC)求解这些问题的效果如何?还是一个有待于今后探讨的问题.此外, 萤火虫算法(FFA)[12]、烟花算法(FWA)[13]、果蝇优化(FFO)[14]、灰狼优化(GWO)[15]、人工藻算法(AAA)[16]和鸽群优化(PIO)[17]等新被提出的这些算法主要用于求解数值优化问题, 如何利用它们高效求解组合优化问题, 是一个有意义的研究问题.为此, 今后将研究它们基于ETM构造的离散演化算法在求解组合优化问题方面的优劣.由于ψDisEA在ETM方法中的重要地位, 深入探讨简单易行、效果极佳且具有普遍适用性的新编码转换函数, 是值得进一步研究的问题.

参考文献
[1]
De Jong KA. Evolutionary Computation-A Unified Approach. Cambridge: MIT Press, 2016.
[2]
Mitchell M. An Introduction to Genetic Algorithms. Cambridge: MIT Press, 1996.
[3]
Kennedy J, Eberhart RC. Particle swarm optimization. In: Proc. of the IEEE Int'l Conf. on Neural Networks. Perth: IEEE Service Center, Piscataway, 1995. 1942-1948.
[4]
Storn R, Price K. Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11: 341–359. [doi:10.1023/A:1008202821328]
[5]
Dorigo M, Stützle T. Ant Colony Optimization. Cambridge: MIT Press, 2004.
[6]
Li XL. A new intelligent optimization method-Artificial fish swarm algorithm[Ph. D. Thesis]. Hangzhou: Zhejiang University, 2003.
[7]
Yao X, Chen GL, Xu XH, Liu Y. A survey of evolutionary algorithms. Chinese Journal of Computers, 1995, 18(9): 694–706(in Chinese with English abstract). [doi:10.3321/j.issn:0254-4164.1995.09.008]
[8]
Wang L. Intelligent Optimization Algorithms with Applications. Beijing: Tsinghua University Press, 2001.
[9]
Gong MG, Jiao LC, Yang DD, Ma WP. Research on evolutionary multi-objective optimization algorithms. Ruan Jian Xue Bao/Journal of Software, 2009, 20(2): 271–289(in Chinese with English abstract). http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=3483&journal_id=jos
[10]
Coello CAC. An introduction to evolutionary algorithms and their applications. In: Proc. of the Advanced Distributed Systems. Berlin, Heidelberg: Springer-Verlag, 2005. 425-442.
[11]
Karaboga D, Basturk B. A powerful and efficient algorithm for numerical function optimization:Artificial bee colony (ABC) algorithm. Journal of Global Optimization, 2007, 39(3): 459–471. [doi:10.1007/s10898-007-9149-x]
[12]
Yang XS. Firefly algorithms for multimodal optimization. In: Proc. of the Stochastic Algorithms: Foundations and Applications (SAGA 2009). LNCS 5792, 2009. 169-178.
[13]
Tan Y, Zhu Y. Fireworks algorithm for optimization. In: Tan Y, Shi Y, Tan KC, eds. Proc. of the ICSI 2010. LNCS 6145, Heidelberg: Springer-Verlag, 2010. 355-364.
[14]
Pan WT. A new fruit fly optimization algorithm:Taking the financial distress model as an example. Knowledge-Based Systems, 2012, 26(2): 69–74. http://dl.acm.org/citation.cfm?id=2107817
[15]
Mirjalili S, Mirjalili SM, Lewis A. Grey wolf optimizer. Advances in Engineering Software, 2014, 69(1): 46–61. http://d.old.wanfangdata.com.cn/Periodical/xxgyh201609002
[16]
Uymaz SA, Tezel G, Yel E. Artificial algae algorithm (AAA) for nonlinear global optimization. Applied Soft Computing, 2015, 31(C): 153–171. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=JJ0234451418
[17]
Duan HB, Ye F. Progresses in pigeon-inspired optimization algorithms. Journal of Beijing University of Technolory (Natural Sciences Edition), 2017, 43(1): 1–7(in Chinese with English abstract). http://d.old.wanfangdata.com.cn/Periodical/bjgydxxb201701001
[18]
Tasgetiren MF, Pan QK, Suganthan PN, Chen AHL. A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops. Information Sciences, 2011, 181(16): 3459–3475. [doi:10.1016/j.ins.2011.04.018]
[19]
Jia DL, Duan XT, Khan MK. Binary artificial bee colony optimization using bitwise operation. Computers & Industrial Engineering, 2014, 76(C): 360–365. http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0233614633/
[20]
Kiran MS. The continuous artificial bee colony algorithm for binary optimization. Applied Soft Computing, 2015, 33(C): 15–23. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=JJ0234714483
[21]
He YC, Wang XZ, Kou YZ. A binary differential evolution algorithm with hybrid encoding. Journal of Computer Research and Development, 2007, 44(9): 1476–1484(in Chinese with English abstract). http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz200709005
[22]
Yu Y, Yao X, Zhou ZH. On the approximation ability of evolutionary optimization with application to minimum set cover. Artificial Intelligence, 2012(2): 20–33. http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_1011.4028
[23]
Kennedy J, Eberhart RC. A discrete binary version of the particle swarm optimization. In: Proc. of the 1997 Conf. on System, Man, and Cybernetices. 1997. 4104-4109.
[24]
Arulselvan A. A note on the set union knapsack problem. Discrete Applied Mathematics, 2014, 169(41): 214–218. http://www.sciencedirect.com/science/article/pii/S0166218X1300588X
[25]
He Y, Xie H, Wong T, Wang X. A novel binary artificial bee colony algorithm for the set-union knapsack problem. In: Proc. of the Future Generation Computer Systems. 2017. http: //dx. doi. org/10. 1016/j. future. 2017. 05. 044
[26]
Rong AY, Figueira JR, Klamroth K. Dynamic programming based algorithms for the discounted {0-1} knapsack problem. Applied Mathematics and Computation, 2012, 218(12): 6921–6933. [doi:10.1016/j.amc.2011.12.068]
[27]
He YC, Wang XZ, Li WB, Zhang XL, Chen YY. Research on genetic algorithms for the discounted {0-1} knapsack problem. Chinese Journal of Computers, 2016, 39(12): 2614–2630(in Chinese with English abstract). [doi:10.11897/SP.J.1016.2016.02614]
[28]
Chen GL, Wang XF, Zhuang ZD, Wang DS. Genetic Algorithms and Its Applications. Beijing: Science Press, 2003.
[29]
Deng L, Zhao J, Wang X. Genetic algorithm solution of network coding optimization. Ruan Jian Xue Bao/Journal of Software, 2009, 20(8): 2269–2279(in Chinese with English abstract). http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=3370&journal_id=jos
[30]
Wang Z, Fan XY, Zou YG, Chen X. Genetic algorithm based multiple faults localization technique. Ruan Jian Xue Bao/Journal of Software, 2016, 27(4): 879–900(in Chinese with English abstract). http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=4970&journal_id=jos [doi:10.13328/j.cnki.jos.004970]
[31]
Zeng JC, Jie J, Cui ZH. Particle Swarm Optimization Algorithm. Beijing: Science Press, 2004.
[32]
Price KV, Storn RM, Lampinen JA. Differential Evolution: A Practical Approach to Global Optimization. Springer-Verlag, 2005.
[33]
He YC, Wang XZ, Li WB, Zhao SL. Exact algorithms and evolutionary algorithms for randomized time-varying knapsack problem. Ruan Jian Xue Bao/Journal of Software, 2017, 28(2): 185–202(in Chinese with English abstract). http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=4937&journal_id=jos [doi:10.13328/j.cnki.jos.004937]
[34]
Kilani Y. Comparing the performance of the genetic and local search algorithms for solving the satisfiability problems. Applied Soft Computing, 2010, 10(1): 198–207. [doi:10.1016/j.asoc.2009.07.012]
[35]
Kellerer H, Pferschy U, Pisinger D. Knapsack Problems. Berlin: Springer-Verlag, 2004.
[36]
Chen Y, Hao JK. Memetic search for the generalized quadratic multiple knapsack problem. IEEE Trans. on Evolutionary Computation, 2016, 20(6): 908-923.http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7440882
[7]
姚新, 陈国良, 徐惠敏, 刘勇. 进化算法研究进展. 计算机学报, 1995, 18: 694–706. [doi:10.3321/j.issn:0254-4164.1995.09.008]
[8]
王凌. 智能优化算法及其应用. 北京: 清华大学出版社, 2001.
[9]
公茂果, 焦李成, 杨咚咚, 马文萍. 进化多目标优化算法研究. 软件学报, 2009, 20(2): 271–289. http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=3483&journal_id=jos
[17]
段海滨, 叶飞. 鸽群优化算法研究进展. 北京工业大学学报(自然科学版), 2017, 43(1): 1–7. http://d.old.wanfangdata.com.cn/Periodical/bjgydxxb201701001
[21]
贺毅朝, 王熙照, 寇应展. 一种具有混合编码的二进制差分演化算法. 计算机研究与发展, 2007, 44(9): 1476–1484. http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz200709005
[27]
贺毅朝, 王熙照, 李文斌, 张新禄, 陈嶷瑛. 基于遗传算法求解折扣{0-1}背包问题的研究. 计算机学报, 2016, 39(12): 2614–2630. [doi:10.11897/SP.J.1016.2016.02614]
[28]
陈国良, 王熙法, 庄镇泉, 王东生. 遗传算法及其应用. 北京: 人民邮电出版社, 2003.
[29]
邓亮, 赵进, 王新. 基于遗传算法的网络编码优化. 软件学报, 2009, 20(8): 2269–2279. http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=3370&journal_id=jos
[30]
王赞, 樊向宇, 邹雨果, 陈翔. 一种基于遗传算法的多缺陷定位方法. 软件学报, 2016, 27(4): 879–900. http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=4970&journal_id=jos [doi:10.13328/j.cnki.jos.004970]
[31]
曾建潮, 介婧, 崔志华. 微粒群算法. 北京: 科学出版社, 2004.
[33]
贺毅朝, 王熙照, 李文斌, 赵书良. 求解随机时变背包问题的精确算法与进化算法. 软件学报, 2017, 28(2): 185–202. http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=4937&journal_id=jos [doi:10.13328/j.cnki.jos.004937]