文化算法(cultural algorithm, CA)^[1-3]是Reynolds在1994年提出的, 一经提出便受到广泛关注, 国内外学者将其改进后的算法成功应用在图像处理、优化控制、工程设计、生产调度等方面.

遗传算法(genetic algorithm, GA) 是最早提出、应用最广的一种群智能优化算法. 模拟退火算法(simulated annealing, SA)于1953年提出, 并于1983年成功地将退火思想融入组合优化^{[4, 5]}领域. 精英保留(maintain the best solution found over time before selection)策略^[6]是由De Jong针对遗传算法收敛速度慢提出的. 此方法可以避免适应度最好的前1或n个个体的基因产生交叉、变异而遭到破坏. 协同进化^[7]这一观点是由Rave与Ehrlich在研究植食性动物与植物时提出的, 后来越来越多的学者用到了这一观点, 并将其应用到各个领域, 又将其细分为合作协同进化与竞争协同进化, 本文中使用了合作协同进化.

生产调度是组织进行生产计划进程的工作, 它可以通过安排生产资源, 来合理地利用生产时间, 缩小生产成本, 在整个生产过程中扮演着十分重要的角色. 流水车间调度^[8]是生产调度中的一种典型调度问题. 伴随着社会的前进, 流水车间调度引起了业内广泛的关注, 为解决现代工业企业中生产连续性强、环节多、情况变化快、调度关系复杂等问题, 使得资源能得到最大化利用, 如何在流水车间中合理安排调度方案成为了一个很重要的问题.

本文在文化算法框架的基础上, 提出了一种混合文化优化算法(hybrid culture optimization algorithm, HCOA). 与传统的算法相比, 本文提出的算法在结合了精英策略的高效性、模拟退火算法的突变特性^[9]等优点之后, 提高了算法的收敛速度以及解决了遗传算法易陷入局部最优解、种群多样性低的问题. 通过函数优化实验分析了HCOA算法在优化问题中的高效性, 接着描述了流水车间调度模型, 给出了使用该算法求解流水车间调度问题的具体操作. 最后进行仿真实验, 与其他几种经典算法进行对比后发现, 本文的算法在求解小型流水车间调度问题中性能优良.

1 混合文化优化算法 1.1 基本文化算法

文化算法的本质是利用双层空间进行合作协同进化, 包括3大元素: 种群空间、信念空间和通信协议. 下层种群空间通常采用基本的遗传算法来实现种群的优化, fitness函数进行适应度的计算; 上层信念空间由各种知识所组成, 当新的知识传递到信念空间时, 则通过更新函数update来更新; 上下层空间的连接则是由接受函数accept和影响函数influence来执行, 种群空间将选取的优势个体通过接受函数传递到信念空间, 信念空间将更新的知识通过影响函数返回给种群空间, 来指导其进化. 图1为文化算法的框架模型.

文化算法下层种群空间采用的是遗传算法, 其下层空间在进化操作中仅采用变异算子^[10], 且遗传算法不能够及时利用反馈信息, 导致了其后期收敛速度变慢, 又因其处理维数小, 且得到较精确的解也需要更多的训练时间, 故算法的搜索速度比较慢. 容易早熟, 这也是遗传算法最大的缺点, 传统遗传算法全局寻优性能较好, 依赖于其交叉操作, 而本文中遗传算法只采用变异算子, 因此其全局寻优性能降低, 也更易收敛到局部最优解. 文化算法依赖于其种群空间中的遗传算法, 因此遗传算法的缺点也过渡到了文化算法中, 导致了其收敛速度慢且易陷入局部最优解.

1.2 混合文化优化算法

由于文化算法种群空间中通常采用的是遗传算法, 所以也携带了诸多遗传算法的缺点, 例如收敛速度慢、易陷入局部最优解以及种群多样性低等问题. 学者们也提出过一些改进的文化算法来提高其在优化问题中的寻优性能, 但依旧存在很多不足. 湖北工业大学的陈详提出了一种新型文化基因算法^[11]用以解决车间调度问题, 该算法在原有遗传算法的基础上加入了局部搜索策略, 每一代种群进行完交叉、变异操作后, 都会再次通过爬山法进行局部搜索, 此举提高收敛速度并确保了解的质量有所上升; 广西民族大学的刘凌子提出一种基于模拟退火和文化粒子群的新型混合优化算法^[12], 该算法针对基本文化粒子群优化算法易陷入局部最优的缺点, 将模拟退火引入文化算法框架中, 作为知识空间的一个演化过程, 通过模拟退火的概率突跳特性促使寻优过程跳出局部极值, 保证了群体的多样性.

文化算法最重要的特点之一就是允许不同算法的混合问题求解, 即只要满足要求的进化算法都可以融合到文化算法架构中作为一个进化过程. 本文以文化算法框架为主体, 在种群、信念空间中均加入带有精英保留策略的遗传算法和模拟退火算法的混合方法^[13], 此方法支持两个空间的协同进化, 实现双重进化继承, 两者相互促进, 实现求解过程. 流程图如图2所示.

将只进行变异操作的遗传算法融入文化算法上下两层空间, 作为运行的基础算法, 其存在收敛速度慢的问题, 因此本文将精英保留策略贯穿到遗传算法中, 并融合到文化算法^[14]的框架中, 来加快收敛速度, 以此解决收敛速度慢的问题. 精英策略能够保证种群空间、信念空间在每一次迭代过程中都能够使群体中前3个适应度值最好的个体不进行单点交换变异而直接进入下一代, 此举既减少了运行时间, 又保留了每一代的优秀个体并提高了种群的收敛速度.

遗传算法的精英保留策略定义如下: 设到第k代时, 种群中j(k)为最优个体, J(k+1)为下一代种群, 将j(k)直接保留到J(k+1)代中, 并替代其最差个体, 使种群个体数量保持不变, 或者将J(k)中的前n个适应度值最优的个体替代下一代最差的n个个体.

假设j₁(k)、j₂(k)、j₃(k)为本文算法中第k次迭代过程中适应度值最好的前3个个体, 则直接进入下一代, 其他个体j_m(k)进行单点交换变异生成过渡个体.

设D维空间内j_m(k)的基因型为:

j_m(k)=(x₁, x₂, x₃, …, x_D–1, x_D)

随机生成D范围内的两个整数, 例如2和3, 交换后j_m(k)=(x₁, x₃, x₂, …, x_D–1, x_D), 若过渡个体适应度值比原个体小则替代原个体, 并进入下一代.

易陷入局部最优解、种群多样性低也是遗传算法存在的缺陷, 本文在以上基础中又加入了模拟退火的思想来保证算法能够及时跳出局部最优解并增加种群多样性. 种群在迭代初期需要较大的突变概率^{[15, 16]}来跳出局部最优, 保持种群多样性; 当迭代到后期, 种群中的个体基因型已经较好, 因此突变概率不需要太大, 如果过大则会破坏进化的成果, 而模拟退火算法中的Metropolis准则正好满足这一思想, 假设j(k)为要进行单点交换变异的个体, 变异前其适应度值为f(j(k)), 变异后j(k+1)的适应度值为f(j(k+1)), 将两者做差得dE=f(j(k+1))–f(j(k)), 如果dE≤0, 则接受产生的新解或原解, 否则依概率P=exp(–dE/T)接受j(k+1)作为新的当前解, 接受概率P为:

$ P = \left\{ {\begin{array}{*{20}{l}} {1, }&{f(j(k + 1)) \leqslant f(j(k))} \\ {{{\rm{e}}^{ - [f(j(k + 1)) - f(j(k))]/T}}, }&{f(j(k + 1)) > f(j(k))} \end{array}} \right. $

(1)

显而易见, 当突变个体f(k+1)适应度值变大, 既dE=f(j(k+1))–f(j(k))>0时, 概率P的范围是(0, 1), 若P>Random(0, 1)则接受突变个体, 这也正是模拟退火算法的独特之处, 依概率接受少数的变差个体, 来增大种群多样性, 跳出局部最优解. 假设指数的分子部分–[f(j(k+1))–f(j(k))]大小是不变的, 当T值较大时, 接受劣质解的概率P也是较高的, 伴随着温度T的下降, P是逐渐减小的, 因此将突变概率的前中后期相比较而言, 其大小呈指数形式逐渐减小, 而当T趋近于0时, 接受劣质解的概率也接近0, 这样就保证了种群在进化前期有较大的可能性跳出局部最优, 保持种群多样性; 中后期在个体较优的情况下, 发生突变的概率逐渐变小, 跳出局部最优的能力也逐渐减弱, 并趋近于0, 以此来保护优化的成果.

1.3 算法复杂度

假设种群规模为N, 个体维度为D, 所有温度下迭代总次数为G, HCOA分为种群和信念空间, 所以一次迭代的时间复杂度为两层空间之和. 进化过程中种群空间因前3个精英个体不做变化, 所以在经过单点交换变异、计算适应度、Metropolis准则接受新解后时间复杂度为O(3×N–9), 因两层空间进化机制相同, 所以一次迭代的时间复杂度为O(2×(3N–9)), 总的时间复杂度为G×O(2×(3×N–9)), 可以化简为O(G×N), 而模拟退火算法的时间复杂度也为O(G×N), 由此可见本文提出的算法复杂度与基础算法处于一个数量级, 但性能却更强.

1.4 函数优化测试

为了效验HCOA在智能优化问题中的性能, 将其与GA、GASA、CA在函数求解测试中进行对比, 测试函数^[7]如下:

$\left\{ { \begin{split} & y = \sum\limits_{i = 1}^N {\left( {{x_i}^2 - 10\cos \left( {2\pi {x_i}} \right) + 10} \right)} \\ &{x_i} \in \left[ { - 5.12, 5.12} \right], \; i = 1, 2, \cdots, 30 \end{split} } \right.$

(2)

该函数是用于调度问题的标准测试函数, 名称为Rastrigr函数, 属于多峰函数, 当其维数上升时, 局部最优点的数量呈指数递增, 假设自变量的维数是N, 则局部最优解的数量为2N–1, 全局最优解为x=0, f(x)=0. 4种算法都有的参数必须保持一致才能确保实验结果的有效性及准确性, 例如随机初始化、种群规模为50、迭代次数为100、维度为10等, 4种算法的函数优化对比如图3所示.

从图3可以看出, 迭代次数相同时, HCOA得到的解明显优于GA、GASA和CA, 且HCOA的值能够达到最优解; 目标函数值相同时, HCOA迭代次数少于另外3种算法, 说明HCOA的收敛速度较快. 综上所述: 无论是收敛精度或收敛速度, HCOA都优于GA、GASA和CA, 展现出了HCOA的准确性和有效性.

2 HCOA求解流水车间调度问题 2.1 流水车间调度问题模型

自1954年学者Johnson在优化领域发表了第1篇流水车间调度^[17]问题的文章以来, 流水车间调度问题就获得了大量学者的关注. 该问题可以表述为n个工件需要于m台机器上进行流水加工, 每个工件都要在m台机器上仅加工一遍, 并且加工顺序一样, 共有m道工序; 各个工件于每机器上的加工时间和准备时间已知. 调度的指标是评价一个调度问题优劣的标准, 本文以最小化最大完工时间为指标, 目标函数如下:

$ {{F = }}\mathop {{\text{min\{max\{max}}T_{ij}{\text{\}\} }}}\limits_{1 \leqslant {{j}} \leqslant m , \; 1 \leqslant i \leqslant n} $

(3)

使得T_ij为工件i于机器j上的完工时间, 且T_ij>0,i=1, 2, …, n, j=1, 2, …, m. $\{ \max T_{ij}\}$ 指在所有工件中于机器j上加工的最长完工时间, $\{ \max \{ \max T_{ij}\} \}$ 是指所有机器加工完所有工件后所用的最长完工时间, 因此使用 $\min \{ \max \{ \max T_{ij}\} \}$ 来代表流水车间调度问题的最小化最大完工时间^[18].

2.2 求解步骤

HCOA求解流水车间调度问题的步骤如下.

1) 初始化参数, 包括种群大小N, 初始温度T, 衰减参数a, 接受率acc、某温度下迭代次数g等;

2) 以流水车间调度问题为根据, 采用适宜的编码、解码方式随机生成一个可以进行优化的初始种群, 根据适应度函数计算群体内所有个体的适应度值f(X)并降序排序;

3) 根据种群大小和接受率, 将前N×acc个优秀个体通过接受函数accept传入信念空间;

4) 按精英保留策略的思路, 本文将群体的前3个个体直接保留, 其余个体进行单点交换变异, 利用模拟退火算法的Metropolis准则, 计算新解、原解之差dE, 依概率判断是否接受新解;

5) 判断在当前温度下是否已经迭代g次, 若否则计算适应度并返回步骤4);

6) 判断是否满足终止条件, 若不满足则进行降温, 跳转到步骤7), 否则终止迭代, 算法结束;

7) 通过影响函数influence将前2个最优个体返回种群空间, 替代种群空间中最差的2个个体, 保持种群数量不变, 计算种群空间适应度并返回步骤3).

2.3 仿真实验 2.3.1 实验准备

本文采用Taillard等人给出的标准TA类^[19]流水车间调度问题进行测试, 数据集分别采用20×5、20×10、20×20、50×5、50×10、50×20、100×5、100×10、100×20共9种规模, 每种规模下选取1个典型种子. 运行平台为Windows 10下的Matlab软件. 设置算法的种群规模为50, 迭代次数为800, 接受率为0.35, 初始温度为200, 衰减参数为0.994, 某温度下迭代次数为10, 个体基因型采用十进制编码.

2.3.2 实验结果与分析

采用GA、GASA (遗传退火算法)^[20]、CA以及HCOA验证以上9种不同规模的数据集在流水车间调度问题中的解, 以最小化最大完工时间为优化目标. 实验时为使结果更精确, 避免偶然性, 每种算法在不同数据集下运行10次. 分析实验结果, 以10次结果的最优值、最差值、平均值为指标, 结果均越小越好, 最优值、平均值越小, 说明优化的精确度越高.

仿真实验结果如表1所示, 从均值及最小值都能够看出, 在9种规模的数据集下, HCOA的优化结果相比其他算法都是最好的, GA都是最差的.

GASA与GA相比, 在任何规模的数据集下GASA的结果(最小值、均值)都优于GA, 又一次印证了遗传算法在融合了模拟退火算法的突变特性后, 能够保持种群的多样性, 增强算法的全局搜索能力, 的确使得种群优化结果更好.

CA与GASA相比, 结果不分伯仲, CA在结合了精英策略及模拟退火算法的突变特性后, 得到的混合算法HCOA各方面参数性能与其相比都有大幅增强.

HCOA在机器数为5或工件数为20的小规模数据集中, 都能得到该目标下的最优解, 但伴随着工件数或机器数的增加, 得到最优解的次数逐渐减少. 以20×10、50×10、100×10为例, 获得HCOA的均值与已知最优解的差值为: 7、49.8、75.3, 则在机器数量相同时, 随着工件数量的增加, 优化效果逐渐减弱; 又以20×5、20×10、20×20为例, 获得HCOA的均值与已知最优解的差值为: 1.9、7、16.1, 则在工件数量相同时, 随着机器数的增加, 优化效果也逐渐减弱. 3种机器数为5的小规模问题(20×5、50×5、100×5) HCOA的方差分别是32.49、4、1, 很明显可以看出, 随着工件数量增多优化稳定性增强; 3种工件数为20的小规模问题(20×5、20×10、20×20) HCOA的方差分别是32.49、72.4、413, 显而易见, 随着机器数量增多优化稳定性降低.

从以上分析可以看出, HCOA在小规模(机器数为5或工件数为20)问题中是十分有效的, 在20×5的规模时, 运行10次能够得到9次最优解; 随着工件数量的增多, 虽然得到最优解次数减少, 但稳定性是增强的; 当工件数量不变, 机器数增大时, 稳定性、有效性、准确性逐渐降低.

3 结论与展望

本文提出了一种混合文化优化算法, 该算法通过将带有精英策略的遗传算法、模拟退火算法纳入文化算法上下层空间, 提高了收敛速度、跳出局部最优的能力及扩大了种群多样性, 最终使得优化效果增强. 通过函数优化实验, 验证了HCOA算法的准确性和有效性. 用HCOA求解以最小化最大完工时间为指标的流水车间调度问题, 通过与GA、GASA和CA对照, 验证了该算法在求解车间调度问题的良好性能. 之后的研究工作将着重于提高HCOA初始种群的效果, 在种群多样性、跳出局部最优的问题上做得更好, 并且将HCOA应用到其他的调度问题中.