基于多色集合的遗传算法优化求解

2013-04-09邓建胜姜莉莉李德治卿前茂

机械制造与自动化 2013年2期

邓建胜，姜莉莉，李德治，卿前茂

(广东工业大学机电工程学院，广东广州 510006)

0 引言

遗传算法具有很强的全局搜索能力，从理论上讲，算法从任意初始种群出发，都可以找到全局最优解。但是当种群数量很大时，算法由于存在早熟收敛的问题，即容易收敛到局部最优解而不再进化或者种群中不能再产生性能超过父代的个体。多色集合的优点是将传统的集合涂上不同的颜色，即给传统的集合及集合中的各个元素赋予一定的意义。如果集合为遗传算法中的编码，那么编码就可以具有一定的意义或者与其他编码建立一定的关系。

将约束模型引入遗传算法的作用主要体现在两方面:1)去掉无意义的解或无效解从而保证所有解都是有效解。设计特定的染色体编码或遗传算子来保证解的可行性，这样遗传编码和遗传算子的设计成为遗传算法的应用瓶颈。2)通过缩小解的空间而减少早熟收敛的可能性和改善收敛速度［1］。当种群数目一定时，解的空间越大，种群中的采样点覆盖全局解的概率就越小，产生早熟收敛的几率就越大。并且当解的空间很大，但有效解的数量相对较少时，不但容易产生早熟收敛，而且收敛速度较慢，得到的解也有可能是无效解。反之，如果缩小解的空间或去掉无意义的解，不但可以减少早熟收敛的可能，而且可以加快收敛速度。

1 算法总流程

针对柔性车间作业调度问题受到工艺约束和设备约束，结合实例讲述如何采用多色集合理论描述这两个约束条件，其他的FJSS 问题都可以采用同意的方法描述调度任务中待加工工序的工艺约束和设备约束。

表1 工序加工设备和加工时间［2］

例有4 个待加工工件，共12 道工序，6 台设备，各工序具体可加工设备和相应的加工时间如表1 所示。

为了便于理解，在针对表1 中的4×6 FJSS 问题建立的约束模型基础上详细设计算法。基于约束模型的遗传算法求解0 问题的流程图［3］如图1 所示，其中2N +1 为种群大小。此图比一般的遗传算法流程图有着明显的特点:1)采用保优策略，将每一代中最有个体直接复制进入下一代，从而每一代中都能得到目前为止最好的解。2)编码、解码、适应度计算以及变异过程在模型约束下进行。

图1 基于约束模型的遗传算法求解FJSS 问题流程图

2 基于约束模型进行编码

编码是遗传算法实施优化的首要和关键问题，鉴于车间调度问题的约束性，编码技术必须考虑其合法性和可行性。针对经典的调度问题，大多数研究采用的是基于工序的编码。这种编码方法把调度编码为工序，每个基因代表一道工序，给所有同一工件的工序指定相同的符号，然后根据它们在给定染色体中出现的顺序加以解释。对于本文的FJSS 问题，问题的解包含两方面的内容:工序的顺序和［4］设备的选择，因此编码也要反映这两方面的内容。为此采用基于工序和设备的两层编码方法。

第一层编码采用基于优先权规则的自然编码方法，其优点是:具有Lamarckian 特性，且能保证调度的可行性，具有2 类解码复杂性［5］。各基因对应的工序按照式(1)矩阵Mwp的行对应的工序的排序依次放置，基因值为优先权随机数。若有12 道工序，则在{1，…，12}中产生不同的随机数作为基因。

第二层编码采用实数编码方法，为第一层编码对应各工序所使用的设备，通过搜索式(2)矩阵Mpm获得各基因，其优先是:具有Lamarckian 特性，且能保证调度的可行性，具有0 类解码复杂性，即不需要解码。各工序的基因从矩阵Mpm中对应的统一颜色中为1 的个人颜色所对应的设备编号中随机获取，以保证每个基因是有效的。

表2 就是采用以上编码方法解决表1 中FJSS 问题的一种编码方案，即一条染色体。

表2 一种编码方案

3 基于约束模型进行解码

由于第一层编码具有2 类解码复杂性，第二层具有0类编码复杂性，所以解码是针对第一层的。解码的目的是确定工序的加工顺序。基于约束模型的解码步骤如下:

步骤1 搜索式(1)矩阵Mwp，挑出各列第一个不为0的元素所在的行对应的工序，由于同一工件的工序在式(1)矩阵Mwp的行中是按先后顺序排列，这样就能满足同一工件每个工序之间的先后关系约束。

步骤2 比较这些工序在第一层编码中对应的基因的大小，选出基因最小的工序(基因值越小，即优先权值越小，则优先权越高，所以基因值小的工序先加工)。

步骤3 根据上一步选出的基于对应的工件和工序，将式(1)矩阵Mwp中对应位置的元素置0，即去掉已经选出的工序。

重复步骤1，步骤2，步骤3，直至确定出所有工序的加工顺序。每个工件的各工序是按照先后关系选取，所以一定满足约束条件——各工件必须按照工艺路线以指定的次序在设备上加工。部分解码过程如下:

1)搜索式(1)矩阵Mwp，找出各列第一个不为0 的元素所在的工序为101，201，301，401，如图2 所示。

图2 解码第二步示意图

2)找出工序101，201，301，401，在第一层编码中对应的基因分别为9、4、3、5，如表3 所示，并选取最小基因值为3 对应的工序301。

表3 解码第二部示意图

3)对上一步选出的工序301，即第三个工件的第一道工序，将式(1)矩阵Mwp中的第七行第三列元素置0，如图3 所示。

重复解码过程1)、2)和3)，可得第一层编码解码后的工序加工顺序为:301→201→202→401→402→403→203→101→102→302→303→103。第二层编码可得加工这些工序的设备依次为:1→5→2→4→2→3→5→1→4→4→6→3。各设备上先后加工的工序如表4 所示。

图3 解码第三步示意图

表4 解码后各设备上先后加工的工序

4 基于约束模型计算适应度

遗传算法中，以个体适应度的大小来确定该个体被遗传呆下一代群体中的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大。反之，个体的适应度越小，该个体被遗传呆下一代的概率就越小。计算个体适应度首先要确定目标函数，不妨设目标函数为fk，定义适应度fit(k)为的倒数，即:

式中:k——染色体标识。

适应度的具体计算如下:

步骤1 计算染色体中按解码后的顺序加工的各工序的开始加工时间和完工时间。设工序i(i=1，…，n)的开始加工时间为Si，完工时间为Fi，在设备上的加工时间为Pi，则Fi=Si+Pi，所以下面主要计算Si。

1)根据工序i 的编号，搜索式(1)矩阵Mwp，确定它是所属工件的第几道工序，若i 不是所属工件的第一道工序，则搜索矩阵Mwp，确定工序i 所属工件的上一道工序的编号i0，再根据工序编号i0确实工序的上一道工序的完工时间为FRi，则要求Si≥FRi;若i 是所属工件的第一道工序，则要求Si≥0。

2)根据工序i 的编号确定加工工序i 的的设备j 上加工的上一道工序的编号。若工序i 是设备上j 上的第一道加工工序，设备j 可以开始加工的时间为MSj，则要求Si≥MSj;若工序i 不是设备上j 上的第一道加工工序，设备j上加工的上一道工序的完工时间为FRi，则要求Si≥FRi。为得到最短完工时间，Si取1)和2)过程的极小值。依次求出解码后的工序的开始加工时间和完工时间。

步骤2 计算fk。

步骤3 计算适应度fit(k)。

对上面解码后得到的工序加工顺序301→201→202→401→402→403→203→101→102→302→303→103，不妨设设备2 可以加工时间为2 之外，其他设备可以加工时间均为0，适应度计算如下:

1)第一道工序301，对应属于工件3，搜索式(1)矩阵Mwp，可知它在Mwp中的第7 行、第3 列，由行列位置确定的元素值是第3 列中第一个不为0 的元素，所以工序301 是工件3 的第一道工序，所以要求Si≥0;由表4 可知，工序301 是设备1 的第一道工序，所以要求S1≥0。故S1=max(0，0)，F1=S1+P1=0 +3=3。类似的，第二道加工工序201 在设备5 上的开始加工时间和完工时间分别为S2=max(0，0)，F2=S2+P2=0 +4=4。第三道工序202，对应属于工件2，搜索式(1)矩阵Mwp，可知它在第5 行、第2 列，由行列位置确定的元素值是第2 列中第二个不为0 的元素，所以要求S3≥F2=4;由表4 可知，工序202 是设备2 上加工的第一道工序，所以要求S3≥2。综合以上结果得S3=max(4，2)=4，F3=S3+P3=4+2=6。依次类推，最后一道加工工序103 在设备3 上的开始加工时间和完工时间分别为S12=max(F9，F6)，F12=S12+P12=20 +12=32。

2)计算目标函数值:f=F12=32。

3)计算适应度:fit=1/f=1/32。