Python遗传算法部分匹配交叉(PMX)

文章目录

问题描述部分匹配交叉步骤(单点交叉为例）代码运行结果同理我们可以写出两点交叉变异的修订

问题描述

在进化算法的交叉环节中，无论是一点交叉还是两点交叉，基因重组后产生的后代可能出现编码重复的情况，那么就需要我们对产生的子代进行修订，常见修订算法有部分匹配交叉（PMX），顺序交叉（OX），循环交叉（CX）等

部分匹配交叉步骤(单点交叉为例）

step1： 确定初始种群 list1: [9, 3, 5, 4, 6, 0, 2, 1, 7, 8] list2: [1, 4, 0, 2, 7, 8, 6, 9, 5, 3]

step2: 随机产生小于父代向量长度的数，如y=2 [9, 3] [5, 4, 6, 0, 2, 1, 7, 8] [1, 4] [0, 2, 7, 8, 6, 9, 5, 3]

step3： 互换交换片段 [9, 3] [0, 2, 7, 8, 6, 9, 5, 3] [1, 4] [5, 4, 6, 0, 2, 1, 7, 8]

step4: 修订 保持被交换的片段不动，在没有交换的片段中寻找重复值，然后在父代被换走的部分中找到对应位置的元素进行替换。 说起来比较模糊，举例说明 本例中[9，3]均与换过来的[0, 2, 7, 8, 6, 9, 5, 3]有重复元素。 我们找到[5, 4, 6, 0, 2, 1, 7, 8]中与9,3对应位置的元素，然后[9,3]中的元素对应替换 第一次交换后的片段由[9, 3]变为了[1, 8]。但是8也与交叉片段重复，依次执行本操作，将8->0，继续查重，发现还重复，然后0->5->7->6->2->4 最终的片段为[1, 4] 相同原理对第二个子染色体进行修订 最终的染色体为 [1, 4, 0, 2, 7, 8, 6, 9, 5, 3] [9, 3, 5, 4, 6, 0, 2, 1, 7, 8]

代码

###########整数修正############ import random import copy a1 = random.sample(range(10), 10) a2 = random.sample(range(10), 10) # a1 = [4, 0, 8, 5, 9, 1, 7, 2, 6, 3] # a2 = [4, 7, 3, 1, 6, 8, 5, 0, 2, 9] a1_1 = copy.deepcopy(a1) a2_1 = copy.deepcopy(a2) print('初始种群为：\n', a1_1, '\n', a2_1) # 交叉位置 y = random.randint(0,len(a1_1)) # 记录交叉项 fragment1 = a1[y:] fragment2 = a2[y:] print('--' * 20, '\n单点交叉交换元素为:\n{}{}\n{}{}'.format(a1_1[:y], fragment1, a2_1[:y], fragment2)) a1_1[y:], a2_1[y:] = a2_1[y:], a1_1[y:] print('--' * 20, '\n{}位置以后元素实现单点交叉:\n{}{}\n{}{}'.format(y - 1, a1_1[:y], fragment2, a2_1[:y], fragment1)) a1_2 = [] a2_2 = [] for i in a1_1[:y]: while i in fragment2: i = fragment1[fragment2.index(i)] a1_2.append(i) for i in a2_1[:y]: while i in fragment1: i = fragment2[fragment1.index(i)] a2_2.append(i) child1 = a1_2 + fragment2 child2 = a2_2 + fragment1 print('--' * 20) print('修正后的子代为:\n{}\n{}'.format(child1, child2))

运行结果

同理我们可以写出两点交叉变异的修订

import random import copy # random.seed(10) # a1 = random.sample(range(1, 11), 10) # a2 = random.sample(range(1, 11), 10) def two_points_cross(a1,a2): # 不改变原始数据进行操作 a1_1 = copy.deepcopy(a1) a2_1 = copy.deepcopy(a2) # 交叉位置,point1<point2 point1 = random.randint(0, len(a1_1)) point2 = random.randint(0., len(a1_1)) while point1 > point2 or point1 == point2: point1 = random.randint(0, len(a1_1)) point2 = random.randint(0., len(a1_1)) # 记录交叉项 fragment1 = a1[point1:point2] fragment2 = a2[point1:point2] # 交叉 a1_1[point1:point2], a2_1[point1:point2] = a2_1[point1:point2], a1_1[point1:point2] # 定义容器 a1_2 = [] # 储存修正后的head a2_2 = [] a1_3 = [] # 修正后的tail a2_3 = [] # 子代1头部修正 for i in a1_1[:point1]: while i in fragment2: i = fragment1[fragment2.index(i)] a1_2.append(i) # 子代2尾部修正 for i in a1_1[point2:]: while i in fragment2: i = fragment1[fragment2.index(i)] a1_3.append(i) # 子代2头部修订 for i in a2_1[:point1]: while i in fragment1: i = fragment2[fragment1.index(i)] a2_2.append(i) # 子代2尾部修订 for i in a2_1[point2:]: while i in fragment1: i = fragment2[fragment1.index(i)] a2_3.append(i) child1 = a1_2 + fragment2 + a1_3 child2 = a2_2 + fragment1 + a2_3 # print('修正后的子代为:\n{}\n{}'.format(child1, child2)) return child1,child2