面向制造过程调度问题遗传算法的设计方法ppt课件

1、. 在求解制造过程调度问题的遗传算法中，染在求解制造过程调度问题的遗传算法中，染色体编码方式、交叉方法和变异方法是求解制造色体编码方式、交叉方法和变异方法是求解制造过程调度问题的遗传算法的关键环节，其设计好过程调度问题的遗传算法的关键环节，其设计好坏直接影响所构造的遗传算法的调度功能。坏直接影响所构造的遗传算法的调度功能。 在求解制造过程调度问题的遗传算法中，根在求解制造过程调度问题的遗传算法中，根据所求解问题的不同特点，染色体可采用不同的据所求解问题的不同特点，染色体可采用不同的编码方式。其中，置换编码是运用最广泛的一种编码方式。其中，置换编码是运用最广泛的一种染色体编码方式。即染色体可表示

2、为自然数染色体编码方式。即染色体可表示为自然数1，2，.，n组成的陈列，用以表示工件的加工顺序。组成的陈列，用以表示工件的加工顺序。对以置换编码表示的染色体假设采用前面提到的对以置换编码表示的染色体假设采用前面提到的交叉方法和变异方法，将产生不可行解的子染色交叉方法和变异方法，将产生不可行解的子染色体。体。.对具有9个工件的单机调度问题，采用2点交叉法：父染色体子染色体采用2点交叉法，得到的子染色体是不可行的。.求解制造过程调度问题等组合优化问题的交叉方法求解制造过程调度问题等组合优化问题的交叉方法.基于顺序交叉法和基于位置交叉法根本类似，只是在父亲V中随机选取的假设干基因位的值在子染色体V1

3、中的位置不同而已，子染色体其他位置的基因值是一样的。后者在假设干基因位的原来的位置，而前者在父亲V2相对应的基因位上。.对顺序交叉法进展了改良。在就是顺序交叉的根底上，将相应改动的基因串集合在一同放到选取的位置中间。.省略V2的建立方法.省略V2的建立方法.求解制造过程调度问题等组合优化问题的变异方法求解制造过程调度问题等组合优化问题的变异方法将某一个随机子串倒置.将随机选取的一个基因插入到另一个随机选取的基因的前边.交换两个位置的基因值.将串挪动位置.基于上述遗传操作的遗传算法具有较好的全局搜索才基于上述遗传操作的遗传算法具有较好的全局搜索才干，且算法实现简单，已在各类制造过程调度问题中得到

4、干，且算法实现简单，已在各类制造过程调度问题中得到广泛运用，但将其运用于较为复杂的制造过程调度问题时，广泛运用，但将其运用于较为复杂的制造过程调度问题时，由于其存在部分搜索才干缺乏的缺陷，所获得的调度性能由于其存在部分搜索才干缺乏的缺陷，所获得的调度性能仍难以令人称心。因此，在运用遗传算法求解较为复杂的仍难以令人称心。因此，在运用遗传算法求解较为复杂的制造过程调度问题时，还可经过构造即有较强的全局搜索制造过程调度问题时，还可经过构造即有较强的全局搜索才干，又有较好的部分搜索才干的混合遗传算法来提高算才干，又有较好的部分搜索才干的混合遗传算法来提高算法的调度性能。法的调度性能。 如将遗传算法与具有较强部分搜索才干的模拟退火如将遗传算法与具有较强部分搜索才干的模拟退火等邻域搜索方法相结合构造的基于部分搜索机制的混合遗等邻域搜索方法相结合构造的基于部分搜索机制的混合遗传算法、将遗传算法与传统启发式方法相结合构造的混合传算法、将遗传算法与传统启发式方法相结合构造的混合遗传算法是求解复杂单机、并行机、遗传算法是求解复杂单机、并行机、Flow Shop和和Job Shop等制造过程调度问题常用的两种混合遗传算法。等制造过程调度问题