【遗传算法】【机器学习】【Python】常见交叉方法（二）、多点交叉和均匀交叉

往期遗传算法文章见：
【遗传算法】【机器学习】【Python】常见交叉方法（一）、单点交叉和两点交叉

一、遗传算法流程图

交叉过程即存在于上图的”交叉“（crossover）步骤中。

二、多点交叉

多点交叉的原理就是，随机地从父代两个基因型中，选择n个位点进行交换，其中n小于等于父代基因型长度（假设双亲基因长度相同，使用一维数组进行表示），如下图所示：

用Python实现如下：

import random


# 简单的多点交叉算法
def multi_cross(list1, list2, n):
    # 假设list1和list2长度相同， n为交叉位点个数
    for i in range(n):
        pos = random.randint(i, len(list1) - 1)  # 保证下一个位点在上一个位点之后
        list1[pos], list2[pos] = list2[pos], list1[pos]  # 交换数组元素

    return list1, list2


for i in range(5):
    list1 = [1, 2, 3, 4, 5, 6, 7, 8]
    list2 = [10, 20, 30, 40, 50, 60, 70, 80]
    print(multi_cross(list1, list2, 3))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

程序输出（5次不同的交叉结果）：

三、均匀交叉

均匀交叉是指，从头到尾遍历双亲的每一个基因位点，每一个位点以概率p交换。在Python中，我们用random.random()方法可以产生一个0，1之间的随机小数，可以方便地模拟“概率”，见如下代码：

import random


def uniform_cross(list1, list2, prob):
    # 以概率prob对list1和list2进行均匀交叉
    # 假设list1和list2长度相同
    for i in range(len(list1)):
        val = random.random()
        if val <= prob:
            list1[i], list2[i] = list2[i], list1[i]

    return list1, list2


for i in range(5):
    list1 = [1, 2, 3, 4, 5, 6, 7, 8]
    list2 = [10, 20, 30, 40, 50, 60, 70, 80]
    print(uniform_cross(list1, list2, 0.666))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

程序输出（5次不同的交叉结果）：