遗传算法的遗传算子

    在遗传算法中，遗传算子模拟生物的遗传过程产生新的后代，在遗传算法中起着重要的作用。在我们的算法中，交叉算子、变异操作以及选择过程设计如下。

    6．5．3．1 染色体的交叉

    设P1＝（v1，v2，…，vk），P2＝（v1′，v′2，…，v′k／）为两条染色体。我们针对这两条染色体设计如下的交叉过程：如果在两条染色体中有共同的节点，则随机选择一个，譬如vi＝vi′。则我们可以得到两条新的染色体：（v1，v2，…，vi，v′i′，…，v′k′），（v′1，v′2，…，v′i′，vi＋1，…，vk）。显然这两条新的染色体也是从节点1到节点n的一条可行路径。如果两条染色体没有共同的节点，则不进行交叉。

    6．5．3．2 染色体变异

    设P＝（v1，v2，…，vk）为一条染色体，我们设计如下的变异操作过程。从｛1，2，…，k｝中随机地产生一个整数，记为i。我们利用染色体初始化的方法从节点vi到n产生一条路径（v′i＋1，…，v′k′），则可产生一条新的染色体（v1，v2，…，vi，v′i＋1，…，v′k′）。

    6．5．3．3 选择过程

    我们利用轮盘赌选择方法来选择染色体。每次选择一条染色体，直到获得pop＿ size条染色体为止。