【AI】Genetic Algorithm 遗传算法

遗传算法是一种基于自然选择的搜索算法，可用于解决人工智能优化问题。
遗传算法是解决最优化问题的一种方法，也是进化算法的一种。

遗传算法概述

遗传算法借鉴了生物演变进化的理念，会不断淘汰掉无法适应环境的个体，从而让优良的基因在后代中留存下来。经过基因突变以及基因互换的方法进行进化，通过与适应度的比较不断的进行筛选，保留优秀的基因。

---

基因互换

注意：需要注意的是，以下只是一种基因互换（杂交）方式方法。根据题目情形，会有很多不同的方案方法进行杂交。

我们有两组基因序列：$a$ 与 $b$

我们在基因 $a$ 中随意截取一段基因序列，在 $b$ 中提出相同的基因，同时将剩余的基
因连接：

再将 $a$ 中截取的部分接入到 $b$ 中，这样就形成了一个新的染色体：

我们称新的染色体为基因互换形成的染色体。

---

基因突变

注意：需要注意的是，以下只是一种基因突变方式方法。根据题目情形，会有很多不同的方案方法进行突变。

我们有一组基因序列 $a$：

我们在基因 $a$ 中随意截取一段基因序列，然后将其提取出，打乱顺序重新排列：

然后将打乱顺序重新排列后的截取部分重新插入到基因序列 $a$ 中，形成基因突变后的新的基因序列。

注意：需要注意的是，以上只是基因突变以及基因互换（杂交）的其中一种方式，根据题目情形，会有很多不同的方案方法进行突变以及杂交。

---

基因突变机率

基因突变有助于维持生物的群体多样性，避免让族群中的染色体过于接近，造成生物进化的延缓或者停滞。

基因的突变是有利的，但是突变不总是有利的，我们不会设置过高的基因突变机率，一般设置基因突变的机率为：1%-10%

---

遗传算法宏观步骤

① 初始阶段

首先随机生成N个序列，作为染色体的祖先群落；$e.g.$ 比如我们要探究TSP旅行商问题有10座城市，那么我们就要生成N组序列，每组序列中有10个随机排列的城市编号，代表着路径解。

② 基因互换与基因变异

接下来，经过基因互换与基因变异两种方式，分别生成 $x$ 和 $y$ 个染色体。其中满足 $x+y=N$。

③+④ 排序以及进化

现在我们将新生成的N个新染色体与之前初始阶段生成的祖先群落的N个染色体放在一起，按照适合度从小到大将2N个染色体进行排序，将适合度最高的N组染色体作为本次进化的优胜者，替换祖先群落，完成一次进化。

⑤ 循环

可以预见的是，每次循环，我们都将获得适合度更低，更为优化的染色体；重复上述步骤，直到适合度值几乎不再优化，即完成进化，达到局部最优解以及全局最优解。

---

适应度 fitness

求解不同的问题对于适应度的定义自然不同；但是总归来看，适应度是被用来衡量生物对周围环境的“适应程度”。适应度越高，代表着生物在环境下的表现越好。

$e.g.$ 比如我们想用GA来求TSP问题，我们想要求得的是最短路径。所以适应度越高代表着其路径越短，越符合我们的期望。

---

遗传算法简单案例

$e.g.$ 用遗传算法去模拟一个简单图片。

规定在7*7的矩阵中，0代表无色，1代表红色，通过遗传算法尝试画出“心形”。

① 初始阶段：

构建10个长度为49(7*7)的数组，每个数组构成一个基因序列。由10个基因序列构成祖先群落。

② 基因互换与基因变异

基因互换：序列a中任意一个位置的值与序列b相同位置的值兑换；
基因变异：将序列a中任意一个位置的值0突变1，1突变0。

基因互换和基因变异的方法可以自行设定，只要合理且可行即可。

③+④ 排序以及进化

重复步骤② 10次，从而产生10个基因序列，计算这10个基因序列的损失函数，以及祖先群落10个基因序列的损失函数，保留前十个相对最小损失函数的基因序列构成新的祖先群落。

⑤ 重复①、②③以及④

---

复杂遗传算法python求解

尝试通过遗传算法解决TSP问题，见博客：【AI】遗传算法解决TSP商旅问题（更新中）