求解车间调度问题自适应混合粒子群算法-计算机学报

　求解车间调治问题的自适应殽杂粒子群算法  

　张长胜 孙吉贵 欧阳丹彤 张永刚 （吉林大学盘算机学院，标记盘算与知识工程教诲部重点实验室，长春，130012，中国）

　摘要：针对最小完工时间的流水车间作业调治问题，提出了一种自适应殽杂粒子群进化算法-AHPSO，将遗传操纵有效的结合到粒子群算法中。界说了粒子相似度及粒子能量，粒子相似度阈值随迭代次数动态自适应变革，而粒子能量阈值与群体进化水平及其自身进化速度相关。别的，针对算法运行后期进化速度慢的缺点，提出了一种基于邻域的随机贪心战略进一步提高算法的性能。最后将此算法在差别范围的实例上进行了测试，并与其他几种最近提出的具有代表性的算法进行了比力，实验结果表明，无论是在求解质量照旧稳定性方面都优于其他几种算法，并且能够有效求解大范围车间作业问题 要害词：粒子群算法；车间调治；粒子相似度；粒子能量；贪心战略 1 1 ．引言

　调治问题是许多实际流水线生产调治问题的简化模型，因此其研究具有极高的理论代价和实践代价。本文研究的置换流水车间作业调治问题是在满足工件约束和呆板约束条件下，使得最小完工时间尽可能小。工件约束指每个工件在每台呆板上恰好加工一次,每个工件在每个呆板上的加工顺序相同；呆板约束指每台呆板在任何时刻至多加工一个工件,每台呆板加工的各工件的顺序相同.该问题一般可以描述为: n 个待加工的作 业  J  1 ,,nJ J , 需 要 在 m 台 呆 板 上 加 工 M  1 ,,mM M  , 每 个 作 业 包 罗 m 道 工 序 m i i i iO O O J, 2 , 1 ,, ,   ,其中k iO,代表作业 i 在呆板 k 上的加工时间为ikt , 1 i n   , 1 j m   的工序。作业jJ 的完工时间jC 为其最后一个工序完成时间即j jmC C  。求解目标是求得一个可行调治,使得加工完所有作业所花的时间maxC 尽可能少.该问题可用如下的数学模型体现: 1 11 1C t 

　 11 1 12, ,j j jC C t j n     

　  1 1 112, ,k k kC C t k m      

　    1 ,1max , 2, , , 2, ,j j j jk k k kC C C t j n k m       

　maxmaxjC C 

　其中jkC 体现工序jkO 的完工时间。

　此问题已被证明是 NP 难度问题[1] ，因此，精确要领 [2] 在公道的时间内只能求解小范围问题，其求解时间随着问题范围成指数倍增长。而启发式算法能够在可担当的时间内，使用较少的存储空间求得问题近似最优解或最优解，主要分为结构启发式[3] 和元启发式两种 [4] ：结构启发式要领虽可以在较短时间内得到调治问题的解，但其在结构调治的历程中依赖凭据问题局部信息设计的调治规矩,所得到的调治一般为局部最优解；元启发式要领，是基于仿生学机理的调治算法能够在可行时间内以较大概率得到该类问题的最优解或近似最优解，成为求解种种车间调治问题的有效算法，正受到研究者的遍及存眷。

　粒子群算法（PSO）是受鸟群觅食启发提出的一种进化盘算要领，其收敛速度快、易于实现，被乐成应用在多个领域中[5] 。目前，应用 PSO 算法求解调治问题的研究还很少，实验表明，在求解调治问题时，它们较 GA 算法更为有效。但已提出的算法都存在早熟收敛，易陷入局部最优、进化后期算法收敛速度明显下降等缺点[6,7] 。主要由于进化历程中粒子能量不绝下降，导致粒子进化停滞不前，群体多样性过低造成的。为了克服这些不敷，本文提出了一种殽杂元启发式算法-AHPSO，将 PSO 算法与 GA 算法[8] 结合在一起，利用遗传操纵不绝引入新的信息指导群体的进化。界说了粒子相似度及粒子能量，粒子相似度阈值随迭代次数动态自适应变革，而粒子能量阈值与群体进化水平及其自身进化速度相关。使用排序战略保持群体的多样性，当相邻的两个粒子的相似度大于其当前的相似度阈值时，对其中的一个粒子执行变异操纵。设计了一种基于遍历矩阵的快速盘算最小完工时间要领。别的，针对进化后期进化速度慢得缺点，提出了一种基于邻域的随机

　 基金项目：国家自然科学基金重大项目基金(60496320, 60496321)，国家自然科学基金资助项目（60773097，60873148），新世纪优秀人才支持计划项目基金、吉林省科技发展计划项目基金(20060532, 20080107)，吉林省青年科研基金项目（20080107，20080617），东北师范大学自然科学青年基金（20081003）

　贪心战略进一步提高算法的性能。最后，阐发了算法的庞大度及收敛性，并通过实验比拟证明了算法的有效性。

　2 2

　AHPSO 算法

　为了使用 PSO 算法求解调治问题，Rameshkumar 提出了一种置换离散粒子群算法[7] ，粒子在更新历程中只互换相应位置的元素，而不引入新元素。受其启发，我们将置换的思想引入到所提出的算法中。对付一个含有 n 个作业的流水调治问题，粒子 i 的位置及速度均被体现为一个满足“alldifferent”约束[9] 的 n维向量，即所有作业的一个全排列，然后结合 GA 算法中的交错及变异操纵不绝更新粒子的位置及速度。

　2.1 算法进化模型 在 PSO 算法中，每个粒子的行为主要受其当前动量项、个别认知部分及群体认知部分的影响。因此，传统的粒子速度公式可通过将粒子的当前速度与其个别最优解及当前的群体最优解分别进行交错来取代，粒子的位置更新也相应的变为将粒子当前位置与当前速度交错求得。粒子速度及位置更新公式可体现如下：

　( 1) ( )i i gbest ibestV k V k P P    

　 （2.1）

　( 1) ( ) ( 1)i i iX k X k V k    

　 （2.2）

　其中标记  体现交错操纵。由上面的公式可以看出，每个粒子追随其当前个别最优解及全局最优解运动。与传统的 PSO 算法一样，它具有快速收敛，盘算简单等优点。但是，进化历程中粒子的速度会迅速迫近零，即粒子的当前速度和其当前位置相同，使算法易于陷入局部最优解，如实验部分的 AHPSO-S-A 算法所示。为此，本文引入了粒子能量及粒子能量阈值的看法。粒子能量阈值随着迭代次数粒子的进化速度动态自适应调解，使算法在进化初期具有较强的全局搜索能力，在后期则偏重局部精化能力。

　说 界说 1：给定粒子 P i ，其当前位置和速度分别为 X i 、V i ，当前的个别最优位置和群体最优位置分别为 P ibest 、P gbest 。此粒子的当前所具有能量可盘算如下：

　    1 10.6* ( ), ( ) 1.4* ( ), ( )2*dim dimibest gbest i ij kisame P j P j same X k V kenergy Pdim  ， 其中  0,1if x ysame x yif x y  。

　粒 子 能 量 用 于 刻 画 粒 子 的 搜 索 能 力 ， 与 粒 子 当 前 状 态 及 群 体 当 前 最 优 位 置 相 关 。

　易 见  [0,1]ienergy P  。

　说 界说 2：设当前迭代次数为 currGen，最大迭代次数 MAXGEN。eIni 与 eFin 分别代表粒子能量的上界及下界，则对付给定的粒子 P i ，其能量阈值界说如下：

　( * ( ( )))( ) *( )eiiMAXGEN curGen speed P curGenenergyThreshold P eIni eFin eFinMAXGEN       其中 ( ( ) ) ( ) ( 1)i ibest ibestspeed P k P k P k   ， e 为预先指定的常量，用于控制粒子能量阈值的变革趋势。

　粒子能量阈值与群体进化水平及粒子进化速度相关。可以看出，算法运行历程中粒子能量不绝变革，当粒子能量小于它当前的能量阈值时，对其当前速度及位置执行变异操纵如公式（2.3-2.4）所示，以此引入新的信息增加粒子能量，扩大其能够到达的搜索范畴。

　( ) ( ( ))i iV k mutation V k 

　（2.3）

　( ) ( ( ))i iX k mutation X k 

　（2.4）

　以上模型在迭代历程中群体多样性会不绝淘汰，全局搜索能力不绝下降，影响群体的进化质量，如实验中 AHPSO-S 算法所示。由此，我们界说了粒子相似度及粒子相似度阈值，采取排序战略保持群体的多样性。

　粒子相似度用于度量两个粒子的相近水平，凭据相邻两个粒子的个别最优位置的距离界说。

　说 界说 3：给定粒子 P i 、P j ，它们的相似度盘算如下：

　 1( ), ( )( , )dimibest jbestki jsame P k P ksimilarity P Pdim 其中，dim 体现待加工的作业数量。

　说 界说 4：设最大迭代次数 MAXGEN，粒子相似度阈值的取值范畴为[sIni，sFin]，则当迭代次数为 currGen时粒子相似度阈值界说如下：

　( *( ) *( )sMAXGEN curGensimiThreshold curGen sIni sFin sFinMAXGEN       其中 s 为一常量，用于控制粒子相似度阈值每次变革的幅度。

　粒子相似度阈值设定当前群体中粒子之间距离的下界，它随迭代次数动态自适应变革。在算法运行的初始阶段，粒子相似度阈值取值较大，使得粒子在搜索空间中漫衍均匀，扩大搜索范畴；随着群体的不绝进化，相似度阈值不绝减小，使得粒子之间能够逐渐聚合到当前的全局最优位置，增强搜索最优位置的邻域，进一步提高最优解的精度。为了保持群体的多样性，在进化历程中，凭据适应度值对群体中的所有粒子进行排序，当两个相邻的粒子的相似度小于当前的粒子相似度阈值时，对较差粒子的历史最优解执行变异操纵，如公式（2.5）所示。

　( 1) ( ( 1))ibest ibestP k mutation P k   

　（2.5）

　通过变异操纵能够在群体中重新引入新的有用信息，指导粒子搜索那些未曾搜索过的区域，进一步抑制算法的早熟收敛。

　2.2 适应度盘算 为了提高算法的速度，我们设计了一种基于遍历矩阵的快速盘算粒子适应度的要领。对付给定的 n 个待加事情业,每个作业包罗 m 道工序，我们将调治1 2, , ,nS s s s   的加工时间矩阵 T 界说为

　1 21 21 21, 1, 1,2, 2, 2,, , ,nnns s ss s sm s m s m st t tt t tTt t t        其中is J  ，jkt 体现作业 j 在第 k 台处理惩罚机上的加工时间， 1 i n   , 1 j m   。

　算法中粒子的适应度值由最小完工时间体现，凭据以上界说，通过对问题数学模型的阐发，给定的调治S 对应的最小完工时间，可通过凭据如下公式遍历矩阵 T 求得。

　1,11, 1 11,1 ,1,1, , 1, , 1, 1 , 1, , 11, 11, 11, 1j ji ii ji j i j i j i ji j i j i j i jt if i jt t if i jt t if i j tt t if t tt t if t t               遍历完成后，新盘算出的, m nt 的值就是调治 S 的最小完工时间。

　2.3 算法描述及阐发 在我们的 AHPSO 算法中，群体的初始化采取随机的方法，即在搜索空间中随机的产生粒子的初始位置和初始速度，将每个粒子的历史最优位置设置为其当前位置，并盘算每个粒子当前位置所代表调治的最小完工时间，将其作为粒子的适应度值。凭据算法的进化模型，AHPSO 算法可描述如下：

　Algorithm AHPSO begin

　initialize(pop)；

　currGen := 0;

　while currGen<MAXGEN do

　 for j:=1 to popNum do

　 pop[j].v[currGen+1] := pop[j].v[currGen]  gBest  pop[j].pBest;

　pop[j].x[currGen+1] := pop[j].x[currGen]  pop[j].v[currGen+1]; pop[j].fitness := C max (pop[j].current);

　if pop[j].fitness< C max (pop[j].pBest) then

　pop[j].pBest:=pop[j].current; endif if pop[j].fitness< C max (gBest) then gBest:= pop[j].current; endif. c := j; while pop[c].fitness<pop[c-1]&&c!=1 do

　swap(pop[c],pop[c-1]);

　c:=c-1; endwhile

　 endfor for k:=1 to popNum do

　particleEnergy := particleEnergyComputing(pop[k]);

　if particleEnergy<particleEnergyThreshold(pop[k],currGen) then

　 increaseParticleEnergy(pop[k]);

　endif if k!=1 then

　similarity := particleSimilarityComputing(pop[k]);

　if similarity<similarityThreshold(currGen) then

　 pop[k].pBest := mutation(pop[k].pBest);

　endif endif endfor currGen++；

　endwhile

　return gBest; end. MAXFGEN 表示算法的最大迭代次数； currGen 及 popNum 分别为当前迭代次数和群体规模； random 表示[0,1]之间的随机数

　 收敛通常是指一个系统或历程到达一个稳定状态，对基于群体的优化算法来说，算法的收敛可以凭据群体的行为来界说[10] 。给定待求解的调治问题P ，其搜索空间  ， ( ) gbest t  为算法在时间 t 或在群体的第t 次进化中求得的最优位置。

　gbest  为  中的一个牢固位置，收敛的界说可记为

　 lim ( )tgbest t gbest 

　也就是说，如果由算法求得的 gbest 不在变革，那么就说处于收敛状态。如果 gbest 为搜索空间的全局最佳位置，则算法得到了全局最优收敛，不然算法陷入局部最优位置。

　理 定理 1 1：AHPSO 算法是收敛的。

　证明：将群体中的每个粒子的当前位置视为一个状态，则所有的粒子当前位置的聚集可视为一种状态漫衍。这种状态漫衍会随算法的运行而改变。由于 AHPSO 算法的运行具有随机性，其根本操纵只与当前状态有关，是无后效性的，因此可以把群体内的个别视为一个具有差别状态的随机变量的概率漫衍。

　首先证明由公式（2.1-2.2）组成的迭代历程是收敛的。设群体范围为 m，问题范围为 l 群体的状态记为(p 1 ,p 2 ,…,p m )，最佳调治为 p*。所有的群体状态组成一个 1 N  的行向量，其中 ( . )! N ml  ，这个行向量的每个元素由排在一起的 m 个粒子的当前位置组成。可体现为        (1) (1) (1) (2) (2) (2) ( ) ( ) ( )1 2 1 2 1 2, , , , , , , , , , , ,N N Nm m mp p p p p p p p p

　假设经过若干代进化后，到达种群最优状态 p*，不妨设其排在状态行向量的第一个分两处，即        (*) (*) (*) (2) (2) (2) ( ) ( ) ( )1 2 1 2 1 2, , , , , , , , , , , ,N N Nm m mp p p p p p p p p

　凭据粒子的速度及位置更新公式可知，此时，处在最优位置粒子的速度及历史最优位置均为 p*，在下一次迭代中求得的粒子当前位置稳定。状态状态转移矩阵可写为：

　21 221CC C     其中 C 为...