遗传算法GA

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

生物在自然界中的生存繁衍，显示了其对自然环境的优异的自适应能力。遗传算法所借鉴的生物学基础就是生物的进化和遗传。

生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化(Evolution)。生物的进化是以集团的形式共同进行的，这样的一个团体称为群体(Population)，组成群体的单个生物称为个体(Individual)，每个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness)。按照达尔文的讲化论，那些具有较强适应环境变化能力的生物个体具有更高的生存能力容易存活下来，并有较多的机会产生后代;相反，具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少，直至消亡。---->自然选择，适者生存

生物的遗传和变异：

生物从其亲代继承特性或性状，这种生命现象就称为遗传(Heredity)。控制生物遗传的物质单元称为基因(Gene),它是有遗传效应的DNA片段。

• 细胞在分裂时，遗传物质DNA通过复制(Reproduction)而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。

• 有性生物在繁殖下一代时，两个同源染色体之间遗过**交叉(Crossover)**而重组。

• 在进行复制时，可能以很小的概率产生某些差错，从而使DNA发生某种变异(Mutation)，产生出新的染色体。

生物进化的本质：染色体的改变和改进===>生物进化过程本质是一种优化过程

遗传算法的基本思想：

遗传算法是根据问题的目标函数构造一个适值函数(Fitness Function)，对一个由多个解(每个解对应一个染色体)构成的种群进行评估、遗传运算、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解。具体如下：

1. 产生一个初始种群
2. 根据问题的目标函数构造Fitness Function 适值函数
3. 根据适应值的好坏不断选择和繁殖
4. 若干代后得到适应值最好的个体即为最优解

遗传算法的构成要素：

• 种群和种群大小

  -种群由染色体构成，每个个体就是一个染色体，每个染色体对应着问题的一个解。一般设为100-1000

• 编码方法

  正确的对染色体进行编码来表示问题的解释遗传算法的基础工作，也是最重要的工作 一般是二进制编码、有意义的实数、符号等等

• 遗传算子

  • 包括交叉和变异，是遗传算法的精髓

  • 双亲染色体是否进行交叉由交叉率进行控制。交叉率为各代中交叉产生的后代数与种群中个体数的比

  • 染色体是否进行变异由变异率来进行控制。变异率为种群中变异基因数在总基因数中的百分比

    变异率的选择很重要，太大会将上一代的最优解杀死

• 选择策略

  • 选择策略是从当前种群中选择适应值高的个体以生成交配池的过程。使用最多的是正比选择策略

    适应值大=>生存至下一代的概率更大

• 停止准则

  一般为最大迭代次数为停止准则

基本遗传算法的运算过程：

1. 初始种群的产生

2. 编码

   将实际问题转化为计算机能够“看懂”的代码。（比如二进制码） ==>编码方法

3. 选择(复制)：

   根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t) 中选择出一些优良的个体遗传到下一代群体**P(t+1)**中； ==> 筛选方法

4. 交叉：

   将群体P(t)内的各个个体随机搭配成对，对每一对个体，以交叉概率交换它们之间的部分染色体；

5. 变异：

   对群体P(t)中的每一个个体，以变异概率改变某一个或某一些基因座上的基因值为其他基因值。

6. 检验：

   是否已达到要求或达到遗传代数。

7. 结束：

   达到目标要求或达到遗传代数。

编码

编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步骤。编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。

初始种群：基本遗传算法（SGA）采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。

• 二进制编码方法 [最常见]

  • 最大最小值
  • 背包问题
  • 指派问题

• 浮点数编码方法

• 符号编码方法

  • 旅行商问题TP

    约束问题：每个城市在一次路线只能经过一次

二进制编码

优点：

• 编码、解码操作简单易行；
• 交叉、变异等遗传操作便于实现；
• 符合最小字符集编码原则；
• 便于利用模式定理对算法进行理论分析。

缺点：

• 对于一些连续函数的优化问题，由于其随机性使得其局部搜索能力较差。如对于一些高精度的问题，当解迫近于最优解后，由于其变异后表现型变化很大，不连续，所以会远离最优解，达不到稳定。

适应度函数

适应度函数用于评价个体的适应度。===>适应度越高，越接近最优解。

最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函数的全局最小值。由目标函数值 f(x) 到搜索空间中对应个体的适应度函数值F(x)的转换，对于求最大值的问题，作下述转换：

初始群体选取

初始群体中的个体是随机产生的。

方法：

​ a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。

​ b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。

选择

从群体中选择优胜的个体，淘汰劣质个体的操作。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

常用选择算子：

• 轮盘赌选择法[最常用]

• 适应度比例方法

• 随机遍历抽样法

• 局部选择法

轮盘赌选择法

想象有一个轮盘，现在我们将它分割成 m 个部分，这里的 m 代表我们总体中染色体的个数。每条染色体在轮盘上占有的区域面积将根据适应度分数成比例表达出来。

比如有如下四个染色体及其适应度信息：

基于上图中的值，我们建立如下「轮盘」。

轮盘赌选择又称比例选择算子，其基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。

设群体大小为N，个体xi 的适应度为 f(xi)，则个体xi的选择概率为：

轮盘赌选择法模拟：

1. 在［0, 1］内产生一个均匀分布的随机数r。
2. 若r≤q1,则染色体x1被选中。
3. 若qk-1<r≤qk(2≤k≤N), 则染色体xk被选中。
4. 其中的qi称为染色体xi (i=1, 2, …, n)的积累概率

简单的例子：

四个染色体二进制编码：$s_1=13(01101)，s_2=24(11000)，s_3=8(01000)，s_4=19(10011)$

假定适应度为$f(s)=s^2$ ，则$f(s_1)=13^2=169，f(s_2)=24^2=576，f(s_3)=8^2=64，f(s_4)=19^2=361$

▸例如设从区间［0, 1］中产生4个随机数:

r1 = 0.450126, r2 = 0.110347, r3 = 0.572496, r4 = 0.98503

交叉

交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。

• 单点交叉算法

  它是指在个体编码串中只随机设置一个交叉点， 然后在该点相互交换两个配对个体的部分染色体。

• 双点交叉

  指在个体编码串中随机设置了二个交叉点，然后再进行部分基因交换。

• 多点交叉

  指在个体编码串中随机设置多个交叉点，然后进行基因交换。多点交叉又称为广义交叉。

变异

遗传算法中使用变异算子主要有以下两个目的：

• 改善遗传算法的局部搜索能力。
• 维持群体的多样性，防止出现早熟(可以理解为局部最优解)现象。

变异算子：

• 基本位变异：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。

• 均匀变异：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）

均匀变异

•依次指定个体编码串中的每个基因座为变异点。

•对每一个变异点，以变异概率pm从对应基因的取值范围内取一随机数来替代原有基因值。

比如说：假设有一个体为X=x1x2…xk…xn, 若xk为变异点，其取值范围为[Ukmin,Ukmax], 在该点对个体X进行均匀变异操作后，可得到一个新的个体X=x1x2…xk’…xn, 其中变异点的新基因值是： xk’ = Ukmin + r · (Ukmax – Ukmin)式中，r 为[0, 1] 范围内符合均匀概率分布的一个随机数。

终止

遗传算法是一个反复迭代的过程，每次选代期间，要执行适应度计算、复制、交叉、变异等操作，直至满足终止条件。

终止方法：

1. 规定最大迭代次数
2. 规定最小偏差
3. 观察适应度函数变化趋势

实例

例：求下述二元函数的最大值：
$$f(x_1,x_2)=x_1^2+x_2^2$$
其中：
x 1 ∈ { 1 , 2 , 3 , 4 , 5 , 6 , 7 } x_1 \in \{1,2,3,4,5,6,7\} x1​∈{1,2,3,4,5,6,7}

x 2 ∈ { 1 , 2 , 3 , 4 , 5 , 6 , 7 } x_2 \in \{1,2,3,4,5,6,7\} x2​∈{1,2,3,4,5,6,7}

编码：

​ 因x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。

例如，基因型X＝101110所对应的表现型是：x＝[56]。

初始种群产生：

​ 假设随机生成种群：011101，101011，011100，111001

适应度计算：

​ 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接 利用目标函数值作为个体的适应度。

选择运算：

把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。

具体操作过程：

​ -先计算出群体中所有个体的适应度的总和
$$\sum _{i=1}^M{f}_i(i=1.2,\dots ,M)$$

​ -其次计算出每个个体的相对适应度的大小 $f_i/\sum f_i$ ，它即为每个个体被遗传到下一代群体中的概率；

​ -每个概率值组成一个区域，全部概率值之和为1；

​ -最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。

交叉运算：

•先对群体进行随机配对；

•其次随机设置交叉点位置；

•最后再相互交换配对染色体之间的部分基因

变异运算：

​ 变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。

​ •首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置,其中的数字表示变异点设置在该基因座处；

​ •然后依照某一概率将变异点的原有基因值取反。

经过选择，交叉，变异后，便可以得到新一代群体p(t+1)如下：

下面附上一个python版代码，具体注释已经加上：

import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D

#染色体长度
DNA_SIZE = 24
#种群规模
POP_SIZE = 200
#交叉率 一般在0.6~0.9之间
CROSSOVER_RATE = 0.8
#变异率 一般小于0.1
MUTATION_RATE = 0.005
#种群迭代次数
N_GENERATIONS = 200
#自变量x和y的范围
X_BOUND = [-3, 3]
Y_BOUND = [-3, 3]

GET_MAX = 0

#定义函数
def F(x, y):
    return x ** 2 + y ** 2

#获取最大适应度
def get_Maxfitness(pop):
    x, y = translateDNA(pop)
    pred = F(x, y)
    # 减去最小的适应度是为了防止适应度出现负数，通过这一步fitness的范围为[0, np.max(pred)-np.min(pred)],最后在加上一个很小的数防止出现为0的适应度
    return (pred - np.min(pred)) + 1e-3    #np.min(pred) 获得pred中的最小值 相减是为了获得非负数 加上一个很小的数防止出现为0的适应度

#获取最小适应度
def get_Minfitness(pop):
    x, y = translateDNA(pop)
    pred = F(x, y)
    #减去最大值后fitness范围:[np.min(pred) - np.max(pred),0] 加上-号后范围为[0, np.max(pred) - np.min(pred)]   加上一个很小的数防止出现为0的适应度
    return -(pred - np.max(pred)) + 1e-3

def translateDNA(pop):  # pop表示种群矩阵，一行表示一个二进制编码表示的DNA，矩阵的行数为种群数目
    #友情提示：pop是二维的哦~
    x_pop = pop[:, 1::2]  # 奇数列表示X
    y_pop = pop[:, ::2]  # 偶数列表示y

    # pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1)     dot() 矩阵乘法计算
    x = x_pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2 ** DNA_SIZE - 1) * (X_BOUND[1] - X_BOUND[0]) + X_BOUND[0]
    y = y_pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2 ** DNA_SIZE - 1) * (Y_BOUND[1] - Y_BOUND[0]) + Y_BOUND[0]
    #返回的是x与y染色体的实数值(解码值)
    return x, y


def crossover_and_mutation(pop, CROSSOVER_RATE=0.8):
    new_pop = []
    for father in pop:  # 遍历种群中的每一个个体，将该个体作为父亲
        child = father  # 孩子先得到父亲的全部基因
        if np.random.rand() < CROSSOVER_RATE:  # 产生一个0~1随机值，如果小于0.8则交叉
            mother = pop[np.random.randint(POP_SIZE)]  # 再种群中选择另一个个体，并将该个体作为母亲
            cross_points = np.random.randint(low=0, high=DNA_SIZE * 2)  # 随机产生交叉的点 [low, high)
            child[cross_points:] = mother[cross_points:]  # 孩子得到位于交叉点后的母亲的基因
        mutation(child)  # 后代变异
        new_pop.append(child) #加入下一代种群

    return new_pop #返回新一代种群

#变异
def mutation(child, MUTATION_RATE=0.003):
    if np.random.rand() < MUTATION_RATE:  # 以MUTATION_RATE的概率进行变异
        mutate_point = np.random.randint(low=0, high=DNA_SIZE * 2)  # 随机产生一个实数，代表要变异基因的位置
        child[mutate_point] = child[mutate_point] ^ 1  # 将变异点的二进制为反转

def select(pop, fitness):  # nature selection wrt pop's fitness
    idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,p=(fitness) / (fitness.sum()))
    '''
    介绍以下choice方法的参数：
    numpy.random.choice(a, size=None, replace=True, p=None)
    #从a(只要是ndarray都可以，但必须是一维的)中随机抽取数字，并组成指定大小(size)的数组
    #replace:True表示可以取相同数字，False表示不可以取相同数字
    #数组p：与数组a相对应，表示取数组a中每个元素的概率，默认为选取每个元素的概率相同。
    也就是说，从种群中根据适应度函数的大小为挑选概率，挑选POP_SIZE个元素作为下一代
    '''
    return pop[idx]


def print_info(pop):
    if GET_MAX == 1:
        fitness = get_Maxfitness(pop)
    else:
        fitness = get_Minfitness(pop)
    #获取适应度最大的下标索引
    max_fitness_index = np.argmax(fitness)
    print("max_fitness:", fitness[max_fitness_index])
    x, y = translateDNA(pop)
    print("最优的基因型：", pop[max_fitness_index])
    print("(x, y):", (x[max_fitness_index], y[max_fitness_index]))

def plot_3d(ax):
    X = np.linspace(*X_BOUND, 100) #等价于 np.linspace(-3,3,100)
    Y = np.linspace(*Y_BOUND, 100)
    X, Y = np.meshgrid(X, Y) #扩展为二维矩阵，方便建图
    Z = F(X, Y) #计算函数值
    ax.plot_surface(X, Y, Z, rstride=1, cstride=1, cmap=cm.coolwarm)#设置绘图参数
    ax.set_zlim(-10, 10)
    ax.set_xlabel('x')
    ax.set_ylabel('y')
    ax.set_zlabel('z')
    plt.pause(3)
    plt.show()

if __name__ == "__main__":
    #创建画布
    fig = plt.figure()
    ax = Axes3D(fig)
    #更改为交互模式
    plt.ion()  #交互模式，程序遇到plt.show不会暂停，而是继续执行
    #绘制3D图
    plot_3d(ax)

    pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE * 2))  # 生成随机数的范围是[0，2) 矩阵大小为 rows: POP_SIZE cols:DNA_SIZE*2,因为两个自变量
    for _ in range(N_GENERATIONS):  # 迭代N代
        x, y = translateDNA(pop)
        if 'sca' in locals():#'sca'判断是不是一个全局变量，如果是，则将其移除
            sca.remove()
        #定义sca为scatter返回对象，scatter就是在函数图像上画出当前种群每个个体的位置
        sca = ax.scatter(x, y, F(x, y), c='black', marker='o');
        plt.show();
        plt.pause(0.1)
        #交叉变异，产生新一代种群
        pop = np.array(crossover_and_mutation(pop, CROSSOVER_RATE))
        #计算适应度
        if GET_MAX == 1:
            fitness = get_Maxfitness(pop)
        else:
            fitness = get_Minfitness(pop)
        #选择
        pop = select(pop, fitness)  # 选择生成新的种群
    #打印最后的全局最优信息
    print_info(pop)
    plt.ioff() #关闭交互模式
    plot_3d(ax)

在次代码中我们设置迭代次数为200次，并设置程序运行期间plot图不会被刷掉，让我们看一下运行过程。
在开始时，我们生成初始种群。

接下来开始不断地迭代种群，交叉、变异、选择…


如果你仔细观察地话，在种群迭代过程中总会有一些变异地染色体突然出现在四个角地地方，但随着选择地进行，其最终都将被淘汰。

随着迭代地不断进行，种群最终会逐渐趋向最优解
最终结果如图：

终端打印信息如下：

max_fitness: 0.0010000039026706524
最优的基因型： [1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 1 0 0
 0 0 1 0 1 1 0 0 0 0 1]
(x, y): (-0.00017398596846973646, 0.004052818063069452)

有兴趣的小伙伴赶紧去试试吧！