变长度染色体遗传算法

3.2变长度染色体遗传算法•在生物的进化过程中，其染色体的长度并不是固定不变的，而是随着进化过程也在慢慢地变化着。•在遗传算法的实际应用中．有时为简要地描述问题的解，也需要使用不同长度的编码串。•结点1和结点6之间的连通路线，可用以下二种方法来描述：•(1)用二进制编码来表示各个结点是否在连通路线上，其中l表示在连通路线上，0表示不在连通路线上。此时可使用等长度的编码串来表示连通路线，如：•PATH1：110011•PATH2：111111•(2)用连通路线所经过结点的顺序排列来表示该条连通路线，如：•PATH1：1—2—5—6•PATH2：1—2—3—4—5—6•该方法使用的就是变长度的染色体编码方法。•Goldberg等提出的MessyGA(简称MGA)是一种典型的变长度染色体遗传算法。变长度染色体遗传算法的编码与解码（MessyGA）•编码•将常规遗传算法的染色体编码串中各基因座位置及相应基因值组成一个二元组，把这个二元组按一定顺序排列起来，就组成了变长度染色体的一种通用染色体编码方式。一般它可表示为:•ik是所描述约基因在原常规染色体中的基因座编号，vk为对应的基因值。•对于所需求解的问题，若使用常规遗传算法时的染色体长度固定为l，各基因值取自集合V，则有•例如，若常规遗传算法中一个个体的基因型是：•X：10010l•其染色体长度为l＝6。使用变长度染色体编码，该个体就可表示为：•Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)•在这种变长度染色体遗传算法中，允许染色体的长度可长可短。如：•Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0)•Xm：(1，1)(3，0)(5，0)(6，1)•前者称为过剩指定，后者称为缺省指定。而当个体的所有基因都能在编码串中得到唯一的描述时，这种描述称为正常指定。解码•对变长度染色体进行解码处理时，在正常指定情况下，将变长度染色体遗传算法中的个体基因型转换为常规遗传算法中的个体基因型时不会有什么问题，而在过剩指定或缺省指定时，就会产生描述过剩或描述不足的问题，此时可按下述规则来进行解码处理：•(1)描述过剩时的解码方法。此时，常规遗传算法中的一个基因座可能在变长度染色体中同时有几个对应的二元组，规定取最左边的二元组来进行解码。•例如，对于变长度染色体遗传算法中的个体•Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0)•它在常规遗传算法中所对应的个体为：•X：100101•2)描述不足时的解码方法。此时，常规遗传算法中有些基因座上的基因值未被在变长度染色体中明确地指定，这时可规定它们取某一项先设定的标准值(或缺省值)。•例如，对于变长度染色体遗传算法中的个体•Xm：(1，1)(3，0)(5，0)(6，1)•若取缺省值为0的话，则它在常规遗传算法中所对应的个体为：•X：100001切断算子与拼接算子•变长度染色体遗传算法除了使用常规遗传算法中的选择算子和变异算子之外，不再使用通用的交叉算子。而代之以使用下述的切断算子和拼接算子，以它们作为产生新个体的主要遗传算子。•1．切断算子(Cutoperator)•切断算子以某一预先指定的概率，在变长度染色体中随机选择一个基因座，在该处将个体的基因型切断，使之成为二个个体的基因型。•2．拼接算子(Spliceoperator)•拼按算子以某一预先指定的概率，将二个个体的基因型连接在一起，使它们合并为一个个体的基因型。变长度染色体遗传算法的算法结构•变长度染色体遗传算法的算法结构可描述如下：•算法MessyGA•①初始化。随机产生M个染色体，长度全部为k的个体，以它们作为变长度遗传算法的初始个体集合P(0)，其中k为根据问题的不同而设定的一个参数，并且k≤l。•②适应废评价。对变长度的染色体进行解码处理后，评价或计算各个个体的适应度。•③基本处理阶段。对群体P(t)施加选择算子，以保留适应度较高的个体。•④并列处理阶段。对群体P(t)施加变异算子、切断算子和拼接算子，以生成新的个体。•③重复第②~④步，直到满足终止条件为止。