一种自适应差分进化算法及应用

周艳平，蔡 素

(青岛科技大学 信息科学技术学院，山东 青岛 266061)

0 引 言

差分进化算法[1]是一种新兴的进化计算方法，可以通过种群内的合作与竞争智能产生优化搜索。差分进化算法是R. Storn和K. Price为了求解Chebyshev多项式而提出的[2]，该文献通过多个领域验证了算法的有效性和稳定性[3]。随着社会的发展，流水车间调度问题引起了广泛的关注[4]。流水车间调度问题的特点是资源共享固定，需要合理安排调度方案，以使问题的性能指标得到最大化利用[5]。流水车间调度问题有很多求解方法，其中主要有精确求解算法、启发式求解算法和人工智能求解算法等。其中对于小规模、小数据量的车间调度优化问题比较适合用精确求解算法。启发式算法的思想是利用优化问题的另一种方案间接地求解车间调度优化问题，启发式算法通过求解该间接方案的次优解，从而加快问题的求解速度，但是对于大规模的流水车间调度问题该方法仍然效率较低。人工智能算法是一种具有自组织、自学习的寻优搜索方法，是解决流水车间调度问题的主要研究方向，如基于遗传算法、蚁群算法和差分进化算法等的流水车间调度优化算法[6]。

文中首先介绍了基本差分进化算法和一些改进算法，在现有算法的基础上，提出了一种新型的自适应差分进化算法(FMDE)，通过函数优化测试分析了FMDE算法的优良性能。接着描述了流水车间调度问题的模型，给出了使用FMDE算法求解流水车间调度问题的步骤。最后通过仿真实验对比分析了FMDE算法在求解流水车间调度问题的优良性能。

1 一种自适应差分进化算法及函数优化测试

1.1 一种自适应差分进化算法

差分进化算法的基本思想是利用随机产生的初始种群，把初始种群中任意两个个体的向量做差，然后加权再按照规定的规则与第三个个体进行求和得到新个体，当变异操作完成后，会将新个体与当代种群中预先决定的个体进行比较，通过比较两个适应函数值，进行选择，如果新产生个体的函数值优于旧个体函数值，则淘汰旧个体，利用新个体进行替换，否则仍然保留原个体。接着通过不断的迭代计算，优胜劣汰，引导搜索过程向最终的最优解靠近。

差分进化算法有变异、交叉、选择三个操作。变异是将初始种群中任意两个个体的向量做差，然后加权再按照规定的规则与第三个个体进行求和得到新个体。交叉指将上一步新得到的个体与另外预先确定的个体按照一定的规则进行混合，得到更新的个体，从而进行下一步实验。选择是按照贪婪准则将试验向量与当前种群中的目标向量进行比较，选择目标函数值较小的作为下一代种群。差分进化算法的性能和变异因子、交叉概率因子和种群规模等三个控制参数有很大的相关性。为解决差分进化算法对参数敏感的问题，研究者们有针对性地提出了一些改进差分进化算法[7-8]，这些改进差分进化算法与标准差分进化算法相比，在一些优化问题中具有较好的收敛性能和优化性能。

基本差分进化算法在搜索过程中变异算子取实常数，实施中变异算子比较难确定，当变异率太大时，算法搜索效率低下，求得全局最优解精度低；变异率太小时，种群多样性就会降低，容易出现“早熟”现象。颜学峰等提出了一种具有自适应变异算子的差分进化算法(MDE)[9]，根据算法搜索进展情况，自适应的变异算子如下：

(1)

其中，F0为变异算子；Gm为最大进化代数；G为当前进化代数。

算法开始时，变异率为F=2*F0，具有较大的变异率，从而在初期保持个体的多样性；随着算法的进展，变异率逐步降低，到了算法后期变异率接近于F0，从而避免最优解遭到破坏，保留了优良信息，增加了搜索到全局最优解的概率。上式中的变异算子F跟其他一些通过创建自适应变异算子的差分进化算法文献类似，都具有随着进化代数的增长而变小的特性，并且未考虑当代个体的适应值是否向着最优个体的适应值逼近，即个体适应值是否朝着最优解的方向发展。假设当代个体经过变异、交叉后，其适应值并未向着最优个体的适应值逼近,偏离了正确的迭代方向，并且变异算子F变小了，迫使子代个体变化很小，因此不易迅速收敛于全局最优值[10]。

根据MDE算法的不足，文中提出一种改进的自适应差分进化算法(FMDE)，其中变异算子F定义为：

(2)

其中，fi(pre)表示上一代个体的函数值；f(min)表示当代的目标函数最优值；fi(suf)表示当代个体的函数值。

如果当代个体函数值与当代最优值差的绝对值比上一代个体函数值与最优值差的绝对值要小，说明当代的个体偏离了最优值的变化方向，这时适当增加变异算子F，但又考虑到变异算子的取值范围，所以采取添加一个单调递减的指数函数的策略[11]。

1.2 函数优化测试

为了检验和说明FMDE算法在求解全局最优问题的性能，分别采用算法MDE、FMDE对以下函数优化问题进行寻优[12-13]。

-5.12≤xi≤5.12,i=1,2,…,10

(3)

优化问题的目标函数在10维可行域内有210-1个局部最优解，差分进化算法可以求解这一问题。对三种算法设置相同的操作参数，包括相同的初始群体，群体规模为Np=100，最大进化代数是800，交叉参数CR=0.1。

为研究变异率对算法的影响，变异率F(或变异因子F0)分别取值。图1、图2分别展示了MDE、FMDE两种算法在不同的变异率情况下，最优值随着迭代次数的变化曲线。

从图1和图2可以看出，随着变异参数的增加，会需要更多的迭代次数才能达到最终的全局最优解(即进化结束)，比如F=0.1时只需要100次迭代就能进化完成，F=0.7时需要大约250次能完成进化，但是F=2.0时需要近450次才能完成进化，性能逐渐减小。同时也能看出，在固定的迭代次数下，变异率越小，最优解的值就越靠近全局最优解。为更好地比较两种差分进化算法的性能，选取最大迭代次数为1 000，变异参数的值为1.5。比较结果如图3所示。

图1 MDE算法变异参数曲线

图2 FMDE算法变异参数曲线

图3 算法性能比较

通过图3可以看出，在相同的变异参数下，FMDE算法能更快地靠近全局最优解0，而且MDE算法达到最优解要比FMDE算法有更多的迭代次数；在固定的迭代次数下，FMDE算法要比MDE算法更靠近全局最优解，效果更好，表明FMDE算法使群体的平均适应度和最优适应度都有一定的提高。

2 FMDE算法求解流水车间调度问题

2.1 流水车间调度问题模型

流水车间调度问题研究m台机器上n个工件的流水加工过程。每个工件需要经过m道工序，每个工件在每台机器上只加工一次，假设每台机器在某一时刻只能加工一个工件，而且各个工件在机器上所需要的加工时间和准备时间已知，且各个工序都有相应的约束条件，以使工件完工时间最小[14]。

令cik表示工件i在设备k上的完成时间，tik表示工件i在设备k上的加工时间，且cik>0，i,j=1,2,…,n，k=1,2,…,m。该流水车间调度问题的目标函数为：

(4)

约束条件为：

(1)设备h先于设备k加工工件i：

cik-tik≥cih。

(2)工件i先于工件j在设备k上加工：

cjk-tjk≥cjh。

2.2 FMDE求解流水车间调度问题的步骤

利用FMDE来求解流水车间调度问题，主要步骤如下：

(1)规定算法的种群规模、最大迭代次数、初始变异算子等参数；

(2)根据流水车间调度问题，随机初始化一个种群；

(3)对种群进行评价；

(4)判断是否达到终止条件或进化代数达到最大。若是，根据最优个体得到流水车间调度问题的最优方案，进化终止；若否，继续进行；

(5)利用式2计算新的变异算子，进行变异和交叉操作，对边界条件进行处理，得到新的临时种群；

(6)通过适应函数对临时种群进行评价，计算临时种群中每个个体的目标函数值；

(7)进行选择操作，得到新种群。转步骤4。

2.3 仿真实验

2.3.1 实验准备

采用标准TA类车间调度问题进行实验测试，分别选择20工件5机器、50工件5机器以及100工件5机器，在上述三个数据集上进行流水车间调度问题的实验，实验采用Pascal语言编程。设置改进自适应差分进化算法的种群规模为40，最大进化代数为800。

2.3.2 实验结果与分析

分别使用三种算法DE、MDE、FMDE对三种不同规模的调度集进行仿真实验，进行makespan目标最小化。在测试实验过程中，为了使结果科学及更具说服力，三种算法分别运行10次，分析10次结果的最优值(makespan)和平均值，结果如表1所示。

从运行10次结果的平均值可以看出，对于每一种数据规模，MDE算法的值比DE算法要优，FMDE算法比MDE算法的值更理想，说明算法DE、MDE、FMDE的性能依次更加有效(makespan值越小)。

为了更有效地研究FMDE算法在不同数据规模下的优化强度(靠近最优值的力度)，考虑将几种算法平均值(Avg)的差作为评价指标。在三种不同规模的数据集(20*5、50*5、100*5)下，FMDE算法的平均值与DE算法的平均值差值分别是74.4、100.3、128.8。从差值可以看出，当机器数量相同时，随着工件数的增加，FMDE算法较DE算法的优化强度也随之增加，说明FMDE算法随着数据规模越大就会越有效。

通过表1的结果发现，在三种数据规模(20*5、50*5、100*5)下，FMDE算法的方差依次为52.32、50.67、26.84。说明当机器数量相同时，随着工件数目的增加，FMDE算法更趋于稳定。

通过上述分析可以发现，FMDE算法比MDE算法和DE算法表现出了更好的有效性和稳定性，通过在进化过程中对变异因子适时进化合理的优化，能够保证种群个体的多样性，增强算法的全局搜索能力。

图4给出了使用FMDE算法对规模为20*5的调度集进行优化时得到的一次计算结果的甘特图。

3 结束语

考虑到群体中的个体函数值可能会朝着最优解相反的方向变化，会降低全局最优解的搜索进度，提出了一种改进的自适应差分进化算法，适度加快搜索速度。通过实验验证FMDE算法的可行性和优越性，FMDE算法的性能要比MDE算法有适当的提升。用FMDE算法求解流水车间调度问题，将最小化最大完成时间作为调度方案的最优评价指标，实验结果表明该算法加快了全局搜索速度和跳出局部最优解的能力，具有较好的应用价值。