[人工智能]遗传算法自问自答

1. 遗传算法的选择算子为什么用在交叉算子，变异算子的前面？

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

def selection_tournament_faster(self, tourn_size=3):
    '''
    Select the best individual among *tournsize* randomly chosen
    Same with `selection_tournament` but much faster using numpy
    individuals,
    :param self:
    :param tourn_size:
    :return:
    '''
    aspirants_idx = np.random.randint(self.size_pop, size=(self.size_pop, tourn_size))
    aspirants_values = self.FitV[aspirants_idx]
    winner = aspirants_values.argmax(axis=1)  # winner index in every team
    sel_index = [aspirants_idx[i, j] for i, j in enumerate(winner)]
    self.Chrom = self.Chrom[sel_index, :]
    return self.Chrom

从算法中可以看出，$selectio{n}_{t}ournament\_faster$改选择算子可能导致重复，其实本质上就是竞标赛选择，使用了numpy加速。

2. 遗传算法中，有哪些选择算子？

答： 轮盘赌（roulette），锦标赛（tournament）

3. 遗传算法中，有哪些交叉算子？

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

4. 异或 ^运算的思考。

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

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

异或相关的应用:

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

5. 4中对于异或的疑问，都是来自于这段代码：

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

6. 遗传算法中，有哪些变异算子？

思考： 在代码中可以尝试用到异或运算，会让代码变得简洁不少。

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

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

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

pmx: also call 2-opt，removes two random edges, reconnecting them so they cross