《（现场管理）求解车间调度问题的自适应混合粒子群算法计算机学报》由会员分享，可在线阅读，更多相关《（现场管理）求解车间调度问题的自适应混合粒子群算法计算机学报（12页珍藏版）》请在金锄头文库上搜索。
1、 计算机学报2009年11期，2009，32（11） 求解车间调度问题的自适应混合粒子群算法*基金项目：国家自然科学基金重大项目基金(60496320, 60496321)，国家自然科学基金资助项目（60773097，60873148），新世纪优秀人才支持计划项目基金、吉林省科技发展计划项目基金(20060532, 20080107)，吉林省青年科研基金项目（20080107，20080617），东北师范大学自然科学青年基金（20081003）张长胜 孙吉贵 欧阳丹彤 张永刚（吉林大学计算机学院，符号计算与知识工程教育部重点实验室，长春，130012，中国）摘要：针对最小完工时间的流水车间作业
2、调度问题，提出了一种自适应混合粒子群进化算法-AHPSO，将遗传操作有效的结合到粒子群算法中。定义了粒子相似度及粒子能量，粒子相似度阈值随迭代次数动态自适应变化，而粒子能量阈值与群体进化程度及其自身进化速度相关。此外，针对算法运行后期进化速度慢的缺点，提出了一种基于邻域的随机贪心策略进一步提高算法的性能。最后将此算法在不同规模的实例上进行了测试，并与其他几种最近提出的具有代表性的算法进行了比较，实验结果表明，无论是在求解质量还是稳定性方面都优于其他几种算法，并且能够有效求解大规模车间作业问题关键词：粒子群算法；车间调度；粒子相似度；粒子能量；贪心策略1引言调度问题是很多实际流水线生产调度问题的
3、简化模型，因此其研究具有极高的理论价值和实践价值。本文研究的置换流水车间作业调度问题是在满足工件约束和机器约束条件下，使得最小完工时间尽可能小。工件约束指每个工件在每台机器上恰好加工一次,每个工件在每个机器上的加工顺序相同；机器约束指每台机器在任何时刻至多加工一个工件,每台机器加工的各工件的顺序相同.该问题一般可以描述为: 个待加工的作业,需要在台机器上加工M,每个作业包含道工序,其中代表作业在机器上的加工时间为,的工序。作业的完工时间为其最后一个工序完成时间即。求解目标是求得一个可行调度,使得加工完所有作业所花的时间尽可能少.该问题可用如下的数学模型表示:其中表示工序的完工时间。此问题已被证
4、明是NP难度问题1，因此，精确方法2在合理的时间内只能求解小规模问题，其求解时间随着问题规模成指数倍增长。而启发式算法能够在可接受的时间内，使用较少的存储空间求得问题近似最优解或最优解，主要分为构造启发式3和元启发式两种4：构造启发式方法虽可以在较短时间内获得调度问题的解，但其在构造调度的过程中依赖根据问题局部信息设计的调度规则,所获得的调度一般为局部最优解；元启发式方法，是基于仿生学机理的调度算法能够在可行时间内以较大概率获得该类问题的最优解或近似最优解，成为求解各种车间调度问题的有效算法，正受到研究者的广泛关注。粒子群算法（PSO）是受鸟群觅食启发提出的一种进化计算方法，其收敛速度快、易于
5、实现，被成功应用在多个领域中5。目前，应用PSO算法求解调度问题的研究还很少，实验表明，在求解调度问题时，它们较GA算法更为有效。但已提出的算法都存在早熟收敛，易陷入局部最优、进化后期算法收敛速度明显下降等缺点6,7。主要由于进化过程中粒子能量不断下降，导致粒子进化停滞不前，群体多样性过低造成的。为了克服这些不足，本文提出了一种混合元启发式算法-AHPSO，将PSO算法与GA算法8结合在一起，利用遗传操作不断引入新的信息指导群体的进化。定义了粒子相似度及粒子能量，粒子相似度阈值随迭代次数动态自适应变化，而粒子能量阈值与群体进化程度及其自身进化速度相关。使用排序策略保持群体的多样性，当相邻的两个
6、粒子的相似度大于其当前的相似度阈值时，对其中的一个粒子执行变异操作。设计了一种基于遍历矩阵的快速计算最小完工时间方法。此外，针对进化后期进化速度慢得缺点，提出了一种基于邻域的随机贪心策略进一步提高算法的性能。最后，分析了算法的复杂度及收敛性，并通过实验对比证明了算法的有效性。2AHPSO算法为了使用PSO算法求解调度问题，Rameshkumar提出了一种置换离散粒子群算法7，粒子在更新过程中只交换相应位置的元素，而不引入新元素。受其启发，我们将置换的思想引入到所提出的算法中。对于一个含有个作业的流水调度问题，粒子的位置及速度均被表示为一个满足“alldifferent”约束9的维向量，即所有作
7、业的一个全排列，然后结合GA算法中的交叉及变异操作不断更新粒子的位置及速度。2.1算法进化模型在PSO算法中，每个粒子的行为主要受其当前动量项、个体认知部分及群体认知部分的影响。因此，传统的粒子速度公式可通过将粒子的当前速度与其个体最优解及当前的群体最优解分别进行交叉来取代，粒子的位置更新也相应的变为将粒子当前位置与当前速度交叉求得。粒子速度及位置更新公式可表示如下：（2.1）（2.2）其中符号表示交叉操作。由上面的公式可以看出，每个粒子追随其当前个体最优解及全局最优解运动。与传统的PSO算法一样，它具有快速收敛，计算简单等优点。但是，进化过程中粒子的速度会迅速逼近零，即粒子的当前速度和其当前
8、位置相同，使算法易于陷入局部最优解，如实验部分的AHPSO-S-A算法所示。为此，本文引入了粒子能量及粒子能量阈值的概念。粒子能量阈值随着迭代次数粒子的进化速度动态自适应调整，使算法在进化初期具有较强的全局搜索能力，在后期则侧重局部精化能力。定义1：给定粒子Pi，其当前位置和速度分别为Xi、Vi，当前的个体最优位置和群体最优位置分别为Pibest、Pgbest。此粒子的当前所具有能量可计算如下：，其中 。粒子能量用于刻画粒子的搜索能力，与粒子当前状态及群体当前最优位置相关。易见。定义2：设当前迭代次数为currGen，最大迭代次数MAXGEN。eIni与eFin分别代表粒子能量的上界及下界，则
9、对于给定的粒子Pi，其能量阈值定义如下：其中，e为预先指定的常量，用于控制粒子能量阈值的变化趋势。粒子能量阈值与群体进化程度及粒子进化速度相关。可以看出，算法运行过程中粒子能量不断变化，当粒子能量小于它当前的能量阈值时，对其当前速度及位置执行变异操作如公式（2.3-2.4）所示，以此引入新的信息增加粒子能量，扩大其能够到达的搜索范围。（2.3）（2.4）以上模型在迭代过程中群体多样性会不断减少，全局搜索能力不断下降，影响群体的进化质量，如实验中AHPSO-S算法所示。由此，我们定义了粒子相似度及粒子相似度阈值，采用排序策略保持群体的多样性。粒子相似度用于度量两个粒子的相近程度，根据相邻两个粒子
10、的个体最优位置的距离定义。定义3：给定粒子Pi、Pj，它们的相似度计算如下：其中，dim表示待加工的作业数量。定义4：设最大迭代次数MAXGEN，粒子相似度阈值的取值范围为sIni，sFin，则当迭代次数为currGen时粒子相似度阈值定义如下：其中s为一常量，用于控制粒子相似度阈值每次变化的幅度。粒子相似度阈值设定当前群体中粒子之间距离的下界，它随迭代次数动态自适应变化。在算法运行的初始阶段，粒子相似度阈值取值较大，使得粒子在搜索空间中分布均匀，扩大搜索范围；随着群体的不断进化，相似度阈值不断减小，使得粒子之间能够逐渐聚合到当前的全局最优位置，加强搜索最优位置的邻域，进一步提高最优解的精度。
11、为了保持群体的多样性，在进化过程中，根据适应度值对群体中的所有粒子进行排序，当两个相邻的粒子的相似度小于当前的粒子相似度阈值时，对较差粒子的历史最优解执行变异操作，如公式（2.5）所示。（2.5）通过变异操作能够在群体中重新引入新的有用信息，指导粒子搜索那些未曾搜索过的区域，进一步抑制算法的早熟收敛。2.2适应度计算为了提高算法的速度，我们设计了一种基于遍历矩阵的快速计算粒子适应度的方法。对于给定的个待加工作业,每个作业包含道工序，我们将调度的加工时间矩阵定义为其中，表示作业在第台处理机上的加工时间，,。算法中粒子的适应度值由最小完工时间表示，根据以上定义，通过对问题数学模型的分析，给定的调度
12、对应的最小完工时间，可通过按照如下公式遍历矩阵求得。遍历完成后，新计算出的的值就是调度的最小完工时间。2.3算法描述及分析在我们的AHPSO算法中，群体的初始化采用随机的方式，即在搜索空间中随机的产生粒子的初始位置和初始速度，将每个粒子的历史最优位置设置为其当前位置，并计算每个粒子当前位置所代表调度的最小完工时间，将其作为粒子的适应度值。根据算法的进化模型，AHPSO算法可描述如下：收敛通常是指一个系统或过程达到一个稳定状态，对基于群体的优化算法来说，算法的收敛可以根据群体的行为来定义10。给定待求解的调度问题，其搜索空间，为算法在时间或在群体的第次进化中求得的最优位置。为中的一个固定位置，收
13、敛的定义可记为也就是说，如果由算法求得的不在变化，那么就说处于收敛状态。如果为搜索空间的全局最佳位置，则算法获得了全局最优收敛，否则算法陷入局部最优位置。定理1：AHPSO算法是收敛的。证明：将群体中的每个粒子的当前位置视为一个状态，则所有的粒子当前位置的集合可视为一种状态分布。这种状态分布会随算法的运行而改变。由于AHPSO算法的运行具有随机性，其基本操作只与当前状态有关，是无后效性的，因此可以把群体内的个体视为一个具有不同状态的随机变量的概率分布。首先证明由公式（2.1-2.2）构成的迭代过程是收敛的。设群体规模为m，问题规模为群体的状态记为(p1,p2,pm)，最佳调度为p*。所有的群体
14、状态构成一个的行向量，其中，这个行向量的每个元素由排在一起的m个粒子的当前位置构成。可表示为假设经过若干代进化后，达到种群最优状态p*，不妨设其排在状态行向量的第一个分两处，即根据粒子的速度及位置更新公式可知，此时，处在最优位置粒子的速度及历史最优位置均为p*，在下一次迭代中求得的粒子当前位置不变。状态状态转移矩阵可写为：其中为随机矩阵，其每一行至少有一个正的元素，为N-1维行向量。显然为可约随机矩阵，且、不是零矩阵，根据可约随机矩阵的性质有：其中。因为可看作是一个状态分布，所以应有，于是，即算法收敛到了p*。当算法中粒子能量小于其当前的能量阈值或粒子的相似度大于当前相似度阈值时，虽然引入了变
15、异操作，但并没有改变当前已经得到的历史全局最优位置，而且在以后的进化中，只有当得到的位置由于此最优位置时才会被取代，即全局最优位置总是朝着更好的位置进化。所以，根据定义6，AHPSO算法是收敛的。定理2：AHPSO算法求得的解是一个合法调度。证明：算法中使用的交叉及变异操作可参看文献8，每种操作都满足“alldifferent”约束，都是一个合法调度，即AHPSO算法的搜索空间是由所有合法调度构成的。所以由AHPSO算法求得的解必然合法。定理3：AHPSO算法的空间复杂度为O(4n+2m+2)d)，群体每次进化的最坏渐进时间复杂度为O(mnd2)。其中n为群体规模，d表示作业数量，m为处理机个数。证明：在AHPSO算法运行过程中需要存储每个粒子的当前位置、个体最佳位置、上一次迭代的个体最佳位置及速度，令群体规模为n，则它所消耗存储空间为O(4nd)；在求解粒子适应度时还需要存储处理时间矩阵，所消耗的空间为O(2md)；每次执行交叉及变异等操作时还需要一个存储新位置或速度的空间，此外还需要存储一个全局最优调度；所以HPGA算法的空间复杂度为O(4n+2m+2)d)。算法运行时，执行一次交叉操作消耗的时间最多为O(2d-1),变异
