求解置换流水车间调度问题的一种混合算法

《求解置换流水车间调度问题的一种混合算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、求解置换流水车间调度问题的一种混合算法【摘要】置换流水车间调度问题是一类经典的组合优化问题，智能优化算法是求解该问题的首要方法。遗传算法和分布估计算法在PFSP问题上均存在着一定的缺陷，即无法平衡局部搜索和全局搜索。为了克服它们的缺陷，本文将分布估计算法与遗传算法结合，并引入模糊逻辑控制来调节两种算法的参与率，最后用基准算例的测试结果证实了本文所设计的混合【关键词】置换流水车间调度；分布估计算法；遗传算法；模糊逻辑控制0.刖目置换流水车间调度问题(PFSP)是对经典的流水车间调度问题进行简化后得到的一类子问题，最早在石化工业中得到应用，随后扩展到制造系统、生产线组

2、装和信息设备服务上［1］。该问题一般可以描述为，n个待加工工件需要在m台机器上进行加工。问题的目标是求出这n个工件在每台机器上的加工顺序，从而使得某个调度指标达到最优，最常用的指标为工件的总完工时间(makespan)最短。PFSP最早由」ohnson于1954年进行研宄［2］，具有NP难性质［3］。求解方法主要有数学规划，启发式方法和基于人工智能的元启发式算法［4］。数学规划等适用于小规模问题，启发式方法计算便捷，却又无法保证解的质量。随着计算智能的发展，基于人工智能的元启发式优化算法成为研究的重点。遗传算法(GA)是研究与应用得最为广泛的智能优化算法，利用遗传

3、算法求解PFSP问题的研究也有很多。遗传算法具有操作简单、容易实现的优点，且求解时不受约束条件限制。然而，遗传算法通常存在着过早收敛，容易陷入局部最优的现象。导致这一现象的原因在于遗传算法的交叉、变异操作具有一定的随机性，在求解PFSP问题的过程中往往会破坏构造块，产生所谓的连锁问题。为了克服遗传算法的缺陷，研究人员提出了一种不进行遗传操作的分布估计算法［5］(EDA)。EDA是一种运用统计学习的新型优化算法。相比GA，EDA在全局搜索上有较大的优势，而局部搜索能力不足，同样会导致局部最优［6］［7］。以混合优化为思路，本文将设计一种EDA与GA结合的混合算法来求

4、解PFSP问题，混合算法通过EDA的概率模型和GA的交叉变异操作两种方式来生成个体，并引入模糊控制理论［8］来自适应调节两种算法生成个体的比例。1.置换流水车间调度问题PFSP问题通常假设：(1)n台工件在m台机器上加工。(2)每个工件以相同的顺序在m台机器上加工。(3)每个工件在每台机器上的加工时间是预先确定的。(4)每台机器只能同时加工一个工件。2.混合算法设计2.1种群初始化初始种群含有PS个个体，利用经典的启发式方法NEH［9］算法产生1个个体，其余PS-1个个体采用随机初始化的方法生成。2.2选择根据PFSP问题所给的加工时间表计算出种群中所有个体的总完

5、工时间Cmax，显然Cmax越小，个体的质量就越好，据此可将评价个体好坏的适应度函数设为1/Cmaxo本文选择的是轮盘赌法，加工时间越小，适应度值越高，个体被选择的概率也就越大2.3概率模型2.4局部搜索对概率模型采样即可得到新一代的个体，对个体进行局部搜索可以提高EDA的性能［11］，本文将对较好的个体进行局部搜索，分别有如下三种搜索方法：插入：选择一个工件并随机插入到某一位置。交换：随机选择两个工件并交换其所在位置。倒置：随机选择两个工件，将这两个工件之间的序列反转。2.5交叉算子本文采用的交叉算子为次序保留交叉。例如，亲代个体为｛2，3，5，1，4，9，8，

6、6，7，10｝和｛1，2,4，5，6，7，8，3，9，10｝，在交叉过程中保留的片段为｛4,9,8,6｝，则生成的子代个体为｛1，2,5,7,4，9，8，6，3，10｝和｛2，3,4，5，6，1，8，7，910｝，图示如下：2.6变异算子本文选取的变异算子为移码变异，例如，变异前的个体为｛6，8,9，10,7,4,3，1，2，5｝，选择7，8这两个位点进行变异，变异后个体为｛6，9,10,7，8，4，3，1，2，5｝，如下图所示：2.7模糊逻辑控制混合优化策略中，不同算法的比例是影响算法性能的关键，传统的算法比例混合方法主要包括固定比例和动态比例两种。使用固定比例

7、时，比例值将在整个算法搜索过程中保持不变。这种方法需要进行试验来确定合适的比例值，其缺点在于为寻找到最佳比例值所需进行的试验多，耗时久。而动态比例调节则只需预先确定一个比例的初始值，而在运行过程中会根据搜索情况调节比例。调节方式又可以分为两种：一种是应用传统的启发式规则控制算法生成个体的比例这些规则可以用确定的数学公式表示；而另一种是用人工智能技术自适应调整生成个体的比例，最常见的是将模糊逻辑应用于比例调节，能根据算法性能的变化来实现比例控制［12］。为了使混合算法具有优良的适应性，本文采用模糊逻辑控制来进行比例调节：在EDA表现良好时提高EDA生成个体的比例发挥

8、其全局搜索