改进的布谷鸟算法求解置换流水车间调度问题

徐杨丽，叶春明 XU Yang-li,YE Chun-ming

（上海理工大学 管理学院，上海 200093）

(College of Management,University of Shanghai for Science and Technology,Shanghai 200093,China)

0 引言

置换流水车间调度问题（Permutation Flow-shop Scheduling Problem，PFSP）是组合优化问题的简单模型，是流水车间调度问题当工件在机器上加工顺序一定时的特殊模式，具有很强的工程代表性。对该问题求解质量、求解速度的研究关系到企业生产资源集约化、生产效率高速化和生产过程机械化的实现。PFSP问题可描述为n工件要在m台机器上加工，每个工件在每台机器上的加工时间已知，且每个工件在每台机器上的加工顺序一定，工件加工顺序相同。同时规定每个工件同一时间只能被一台机器加工，每台机器同一时间也只能加工一个工件，工件在机器上加工不间断。PFSP问题的目的是求出最优的工件加工顺序，使总流程完工时间最短。

国内外许多学者对该问题进行了研究，并对其求解算法不断进行优化。已知的优化算法如精确算法（分枝定界法、动态规划法、整数规划法等）对求解小规模调度问题能寻得问题精确解；启发式算法（Johnson法、Palmer法、Gupta法、NEH法等）能快速建立问题的解，但算法的优化质量差，算法设计复杂，收敛速度慢，难以满足工程需要。智能优化算法（如遗传算法、果蝇算法、蝙蝠算法等[1-3]）是新的启发式算法，是模仿自然界“优胜劣汰，适者生存”规则发展而成的，在问题优化求解方面表现出高度有效性。

布谷鸟算法（Cuckoo Search，CS）是2009年由剑桥大学Xin-SheYang和S.Deb提出的一种新兴启发式智能算法[4]，该算法选用参数少，全局搜索能力强，编程易实现，目前已被广泛应用于项目调度、函数优化、工程结构优化、整数规划等[5-8]许多领域。已有文献中布谷鸟算法主要用来求解连续问题，对离散组合优化生产调度问题应用较少。针对布谷鸟算法求解精度较低，后期收敛速度慢，容易陷入局部最优解等问题，目前许多学者对其进行了改进，如郑洪清等[9]通过调整布谷鸟现有鸟窝位置和最佳鸟窝位置之间的距离以调整布谷鸟搜索步长，屈迟文等[10]在原始布谷鸟算法上引入非均匀变异算子对鸟窝位置进行变异，并对陷入局部最优的鸟窝位置用高斯变异算子进行调整，仿真实验均取得了较好的效果。

本文引入差分进化算子改进原始布谷鸟算法被发现鸟窝位置，并将其应用到PFSP问题求解，以求在不断更新、保持种群多样性的同时，提高算法的求解精度，避免陷入局部最优。通过与原始布谷鸟算法和猫群算法（Cat Swarm Optimization，CSO）[11]求解结果的比较，证明改进后的布谷鸟算法优化效果显著。

1 相关问题数学描述

1.1 布谷鸟算法数学描述。布谷鸟算法是模拟布谷鸟为寻找合适产卵的鸟窝而随机游走的寻窝过程。布谷鸟是自然界少有的通过寄生而不是自己孵化产卵繁殖后代的鸟类，为了提高繁殖率，布谷鸟在选择宿主鸟窝时需要选择跟自己的卵形相似，卵的颜色、孵化周期一样的鸟窝。即使如此也存在被宿主发现寄生卵的可能性。若寄生卵被发现，则在下一次选择宿主鸟窝时就要放弃该鸟窝，重新选择。为了更好地实现算法的优化性能，假设布谷鸟种群可利用的宿主鸟窝数量固定，且宿主发现外来蛋的概率固定。布谷鸟每一次随机选择一个宿主鸟窝孵化所产的一个卵，布谷鸟种群在随机选择的一组寄生卵鸟窝中，具有最优位置的寄生卵鸟窝将会保留到下一代。

在布谷鸟算法中，每个宿主鸟窝原有的卵表示一个候选解，每个新入住的布谷鸟的卵表示一个新的解。依据上述假设可将布谷鸟寻窝的路径和位置更新公式如下：

1.2 差分进化算法数学描述。差分进化算法与遗传算法、粒子群算法一样是一种基于群体智能理论的随机并行搜索优化算法，由Storn R和Price K于1995年提出，并且在1996年举行的第一届国际IEEE进化优化竞赛中，被证明是速度最快的进化计算。算法主要通过变异操作、交叉操作、选择操作实现对群体和个体更新。算法为保持在搜索方向和搜索步长上的自适应性[4]，将种群中任意两个个体的差分向量加权后，根据一定的规则加到第三个个体上，作为第三个个体的扰动向量。在进化早期，因为种群中个体的差异性较大使得扰动量较大，从而使得算法能够在较大范围内搜索，具有较强的勘探能力；而到了进化后期，当算法趋向于收敛时，种群中个体的差异性小，算法在个体附近搜索，这使得算法具有较强的局部开采能力。这里主要介绍算法的变异算子、交叉算子和选择算子。

（1）差分变异算子。常见的差分方法有四种：随机向量差分法（DE/rand/1）、最优解加随机向量差分法（DE/best/1）、最优解加多个随机向量差分法（DE/best/2）、最优解与随机向量差分法（DE/rand-best/1）。本文为保持种群的多样性，采用随机向量差分法，其变异公式描述如下：为需要变异的个体，在当前种群随机选择两个个体则产生变异个体表达式如式（3） 所示：

其中，F为放大因子，是差分向量的加权值，一般F∈［0,2］，i、j、k为互不相同的三个个体。经过变异后的个体X（ t+1）即保留了父代Xi（t）的部分信息，又借鉴了个体Xj（t）、Xk（t）的信息又实现了个体间信息的传递。

（2）交叉算子。差分进化算法的交叉算子是依据交叉概率Pc使得父代个体和由他经过差分变异操作产生的新个体之中的部分基因位进行交换，从而生成新个体，具体规则如下所示：i

（3）贪婪选择算子。贪婪选择操作是通过比较经过变异、交叉操作后得到的子代个体与原向量适应度值，只有当子代个体适应度优于原向量时，才会被选取成为下一代的父代，否则原向量将直接进入下一代。贪婪选择算子如式（5）所示规则生成：

其中，Ui（t）表示经过变异、交叉后生成的新个体，Xi（t）表示原始个体，DECS_fitness（）表示计算适应度值函数。

2 求解置换流水车间调度问题的改进布谷鸟算法

2.1 改进后算法思想。布谷鸟采用莱维飞行更新步长和路径后，考率后期寻优过程中由于种群多样性缺乏而造成的寻优速度慢，收敛精度不高问题，改进后在每一代的寻优过程中引入差分进化算子，对被发现的鸟窝进行随机扰动，选择三个未被发现的鸟窝进行变异、交叉、选择操作，生成新的子代个体，若新的子代个体适应度优于父代个体则保留，否则抛弃新的子代个体，使用父代个体之间进入下一代循环。

2.2 编解码方法。本文采用基于最大位置法的编码方法，即一个布谷鸟表示一个加工序列，但具有最大值的位置将被首先加工的编码方法。如一个布谷鸟的各维度值为 （-2.1680,1.7131,17.8920,13.8472,-6.7494,15.1746 ）则其对应的加工顺序为（3,6,4,2,1,5），即首先应该加工第三个工件，其次加工第六个工件，然后加工第四个工件，再依次加工第二个工件，第一个工件和第五个工件，一个维数为一道工序。

2.3 改进后算法流程

Step1初始化算法基本参数，布谷鸟选择宿主鸟窝数目N，发现概率Pa，差分进化操作的缩放因子F，交叉概率CR，最大迭代次数maximum generation或搜索精度e；

Step2布谷鸟随机选择鸟窝位置xi（ i=1,2,…,N ），基于最大位置法的编码规则将鸟窝位置转换为工序排列，根据各鸟窝位置评估各鸟窝的适应度，在初始鸟窝中找出最优鸟窝Xbest；

Step3当不满足最大迭代次数或停止条件，则继续；

Step4根据式（1）选择更新鸟窝，并保留当前最优鸟窝；

Step5评估鸟窝适应度，若更新后鸟窝适应度更优，则在更新后鸟窝中产卵，并找出更新后最优鸟窝位置；

Step6产生随机数r，若r>Pa，则通过差分进化算法的变异、交叉、选择操作来重建被宿主抛弃的鸟窝，否则，接受更新位置后的鸟窝；

Step7当满足搜索精度e或者达到最大迭代次数maximum generation转Step8，否则转Step3，进行下一轮搜索；

Step8输出最优值和最终的调度方案。

3 仿真实例

为测试改进后算法（即DECS算法）的优化性能，选择Carlier提出的Car类共8个不同规模的测试问题对算法进行测试，并将测试结果与选择同样算法参数的标准布谷鸟算法（CS算法）和文献[11]中的算法（CSO）比较。

实验仿真环境为Windows 7操作系统，处理器主频1.87GHZ，CPU为Intel（R） Core（TM） i3-350M和内存2G，采用MATLAB R2012a实现算法编程。算法参数设置为：初始种群规模Popsize=25，最大迭代次数N_iterTotal=100，步长控制因子a=0.5，发现概率Pa=0.25，变异概率F=0.8，交叉概率PC=0.5，算法独立运行30次。表1为改进后的布谷鸟算法（即DECS算法）与标准布谷鸟算法（即CS算法）独立运行20次的寻优效果对比。其中Max表示20寻优过程中出现的最大值，Min表示20次寻优过程中出现的最小值，Avg表示20次寻优的平均值，BNO表示20次寻优最优解最早出现代数，C*表示求解问题已知最优解。为测试算法的优化性能，将本文算法独立运行20次并与文献[11]算法的寻优效果比较，表2为两个算法寻优结果对比，其中WRE为算法寻得最差结果相对已知最优解C*的百分比，ARE为平均值相对C*的百分比，BRE为最优结果相对C*的百分比。图1为两算法BRE比较结果图。

表1 DECS算法与CS算法寻优效果比较

从表1可以看出，在求解8个规模的不同问题时，改进的布谷鸟算法和原始布谷鸟算法的Min值均与已知最优解C*相同，说明两个算法均能求得问题最优解。比较两个算法的Max值和Avg值可知，在求解Car1、Car2、Car4、Car7和Car8问题时，两个算法也都表现出极好的优化性能。对于Car3、Car5问题两个算法表现良好，虽能求得算法最优解，但不是每次运行都取得良好的效果，尤其是原始布谷鸟算法，所求得近似解远远大于改进后的布谷鸟算法所求得近似解。对于Car6问题，改进后的布谷鸟算法Max值、Min值和Avg值相等且均等于C*值，说明该算法每次都能寻得问题最优解，但原始布谷鸟算法只能求得问题近似解。改进后的布谷鸟算法的BNO值均小于原始布谷鸟算法的BNO值，显示出改进后的布谷鸟算法能更快地向全局最优解收敛，说明其具有更优异的种群多样性。

表2 本文算法与文献[11]算法寻优效果比较

表2本文算法与文献[11]算法BRE值均为0显示两算法均能求得问题最优解，均具有很好的优化性能，图1显示出本文算法最差误差百分比在寻求每一个问题时都比文献[11]算法小，尤其是求解Car2和Car4问题时，本文算法与文献[11]算法差距很大，对Car5问题求解差距最小。说明本文算法求解能力更强，寻优性能更好，鲁棒性更高。

4 结束语

本文以最小化最大完工时间为目标，改进原始布谷鸟算法，在保持布谷鸟算法强全局寻优能力的基础上引入差分进化算子，促进被发现鸟窝中候选解与未被发现候选解之间的信息交互，以增加种群多样性。通过与原始布谷鸟算法和文献[11]算法处理Car类问题寻优结果比较，显示改进后的布谷鸟算法求解优化效果明显，证明该算法求解置换流水车间调度问题是可行和有效的。但是改进后的布谷鸟算法依然有局限性，如变异概率和交叉概率的选择，步长因子控制及其与进化代数的关系等，及其影响算法的收敛速度和收敛精度，这些问题是进一步需要研究的内容。

[1] 李小缤，白焰，耿林霄.求解置换流水车间调度问题的改进遗传算法[J].计算机应用，2013,33(12):3576-3579.

[2] 郑晓龙，王凌，王圣尧,等.求解置换流水线调度问题的混合离散果蝇算法[J].控制理论与应用，2014,31(2):159-164.

[3] 盛晓华，叶春明.基于蝙蝠算法的PFSP调度干扰管理研究[J].计算机工程与应用，2014,50(8):241-246.

[4] Xin-She YANG,Suash Deb.Cuckoo search via Lévy flights[C]//Proc of World Congress on Nature and Biologically Inspired Computing[S.I]:IEEE Press,2009:210-214.

[5]聂慧，刘波，韦向远,等.一种求解资源受限项目调度问题的差分进化——布谷鸟搜索算法[J].桂林理工大学学报，2014,34(2):315-321.

[6] 胡欣欣.求解函数优化问题的改进布谷鸟搜索算法[J].计算机工程与设计，2013,34(10):3639-3642.

[7] 陈乐，龙文.求解工程结构优化问题的改进布谷鸟搜索算法[J].计算机应用研究，2014,31(3):679-683.

[8] 吴炅，周健勇.整数规划的布谷鸟算法[J].数学理论与应用，2013,33(3):99-106.

[9] 郑洪清，周永权.一种自适应步长布谷鸟搜索算法[J].计算机工程与应用，2013,49(10):68-71.

[10]屈迟文，傅彦铭.基于混合变异算子的布谷鸟优化算法[J].科学技术与工程，2013,13(27):8008-8013.

[11]马邦雄，叶春明.利用猫群算法求解流水车间调度问题[J].现代制造工程，2014(6):12-15,71.