遗传算法的自我问答与解析

1. 遗传算法的选择算子为什么用在交叉算子&＃xff0c;变异算子的前面&＃xff1f;

答&＃xff1a; 选择算子的目的是选择哪些个体参与交叉与变异&＃xff0c;其余的个体不参与交叉与变异&＃xff0c;但是会作为parent参与offspring的比较&＃xff0c;如果获胜&＃xff0c;任然有机会存在于种群&＃xff1b;如果失败&＃xff0c;则会被淘汰。所以&＃xff0c;选择算子其实不完全等同于淘汰操作。

def selection_tournament_faster(self, tourn_size&＃61;3):&＃39;&＃39;&＃39;Select the best individual among *tournsize* randomly chosenSame with &＃96;selection_tournament&＃96; but much faster using numpyindividuals,:param self::param tourn_size::return:&＃39;&＃39;&＃39;aspirants_idx &＃61; np.random.randint(self.size_pop, size&＃61;(self.size_pop, tourn_size))aspirants_values &＃61; self.FitV[aspirants_idx]winner &＃61; aspirants_values.argmax(axis&＃61;1) # winner index in every teamsel_index &＃61; [aspirants_idx[i, j] for i, j in enumerate(winner)]self.Chrom &＃61; self.Chrom[sel_index, :]return self.Chrom


从算法中可以看出&＃xff0c;$\text{selection\_tournament\_faster}$改选择算子可能导致重复&＃xff0c;其实本质上就是竞标赛选择&＃xff0c;使用了numpy加速。

2. 遗传算法中&＃xff0c;有哪些选择算子&＃xff1f;

答&＃xff1a; 轮盘赌&＃xff08;roulette&＃xff09;&＃xff0c;锦标赛&＃xff08;tournament&＃xff09;

3. 遗传算法中&＃xff0c;有哪些交叉算子&＃xff1f;

答&＃xff1a;值得注意的是&＃xff0c;在遗传算法实现中&＃xff0c;通过选择算子选择的个体&＃xff0c;相邻的两个进行交叉运算&＃xff08;之前以为是随机挑选两个个体进行交叉&＃xff09;。单点交叉&＃xff0c;两点交叉&＃xff0c;pmx&＃xff08;适用于tsp问题&＃xff09;。

4. 异或 ^运算的思考。

异或运算的性质&＃xff1a;
a) 与True异或&＃xff0c;相当于取反
b) 与False异或&＃xff0c;相当于本身
c) 从真值表中&＃xff0c;不难得出&＃xff0c;相同为False, 不同为True。
d) 异或满足交换律与结合律

# 交换两个数&＃xff0c;不新增空间
a &＃61; a ^ b
b &＃61; a ^ b
a &＃61; a ^ b
# 神奇的异或&＃xff0c;很多地方都会变相的利用异或来交换两个值


异或相关的应用:

1. 快速比较两个值(a ^ b &＃61;&＃61; 0);
   2&＃xff09;性质a&＃xff0c;可以实现某些位的快速翻转;
   3&＃xff09;使用异或来判断一个二进制数中1的数量是奇数还是偶数;
   4&＃xff09;面试题&＃xff1a;一个整型数组里除了N个数字之外&＃xff0c;其他的数字都出现了两次&＃xff0c;找出这N个数字&＃xff1b;

5. 4中对于异或的疑问&＃xff0c;都是来自于这段代码&＃xff1a;

mask &＃61; np.zeros(shape&＃61;(half_size_pop, len_chrom), dtype&＃61;int)
for i in range(half_size_pop):n1, n2 &＃61; np.random.randint(0, self.len_chrom, 2)if n1 > n2:n1, n2 &＃61; n2, n1mask[i, n1:n2] &＃61; 1
mask2 &＃61; (Chrom1 ^ Chrom2) & mask
Chrom1 ^&＃61; mask2
Chrom2 ^&＃61; mask2
# 整体代码目的就是两点交叉&＃xff0c;变相使用异或来交换两个数


6. 遗传算法中&＃xff0c;有哪些变异算子&＃xff1f;

思考&＃xff1a; 在代码中可以尝试用到异或运算&＃xff0c;会让代码变得简洁不少。

mask &＃61; (np.random.rand(self.size_pop, self.len_chrom) < self.prob_mut)self.Chrom ^&＃61; mask# 这段代码多帅哦&＃xff0c;用异或算法&＃xff0c;两行代码就实现了种群染色体随机变异(取反)&＃xff0c;变异概率&＃xff08;self.prob_mut&＃xff09;


上面的代码只是在染色体随机点位上取反&＃xff0c;对于TSP问题&＃xff0c;实际上这种变异算子是不适用的。

随机交换:每个染色体的每个基因按照变异概率&＃xff0c;与当前染色体的随机基因交换。
2-swap: 染色体中随机选择两个位点&＃xff0c;将两个位点所在基因交换。
2-opt:&＃xff0c;染色体中随机选择两个位点&＃xff0c;将以两个位点为起点终点的基因段逆序交换。