算法简介

遗传算法（GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。该算法基于达尔文的“适者生存，不适者淘汰”的自然选择学说，将问题的可行解集合视为种群，依据适应度挑选出种群中的优势个体进行“复制”、“交叉”与“突变”，从而淘汰掉劣势个体，使得整个种群向最优的方向发展。

遗传算法将每个自变量视为一个基因，一个可行解为一个个体，所有可行解的集合为种群，目标函数值得优化程度为种群对环境得适应度。因此，可行解向最优解靠近的过程就可以被视为一个种群向适应环境方向进化的过程。在迭代中，优势解被保留，劣势解被舍弃，即为“优生劣汰”。同时，我们模仿生物遗传过程中基因与染色体的交叉、变异操作，对可行解进行扰动，即可到达全局搜索和局部搜索的目的。

算法原理

编码

生物学介绍，ATCGU等嘌呤或嘧啶的不同排列为基因编码。在遗传算法中，我们也需要将每个自变量进行编码。总的来说，编码方法可以分为三大类：二进制编码方法、浮点数编码方法、符号编码方法。本文主要介绍二进制编码方法与浮点数编码方法。

二进制编码

二进制编码方法使用二进制符号0和1对变量进行编码。对于取值范围为$[X_{min}, X_{max}]$的变量$x$，我们用长度为$l$的二进制串来表示该变量，则它能产生$2^l$中不同的编码。其中二进制数$0$映射变量下限$X_{min}$，二进制数$2^l-1$映射变量上限$X_{max}$。也就是说，我们用二进制串将区间平分为$2^l-1$份，第$i$段小区间内的值均用二进制数$2^i$表示。此时二进制编码精度为：

$\delta = \frac{X_{max}-X_{min}}{2^l-1}$

假设一个个体的二进制编码为$X_b$，则对应的解码公式为

$x=X_{min}+X_o\dot{\frac{X_{max}-X_{min}}{2^l-1}}$

其中$x$为该个体的实际值，$X_o$为二进制数$X_b$的十进制值。当个体的基因数大于1即问题包含多元变量时，我们通常将每个变量的二进制编码依次整体排列。

二进制编码的优点是编码解码操作简单易行，且交叉、变异等遗传操作便于实现，但其精度较低，局部搜索能力较差。当要求高精度时，不得不增加二进制串的长度，这将导致算法的搜索空间扩大。

格雷码编码

格雷码是普通二进制编码的变形，其表示精度与二进制编码相同。连续两个整数所对应的格雷码编码值之间仅仅只有一位编码值不同，其余位完全相同。假设有一个二进制编码为$B=b_mb_{m-1}…b_2b_1$，其与格雷码$G=g_mg_{m-1}…g_2g_1$之间的转换关系如下

$\begin{cases} g_m=b_m\\ g_i=b_{i+1}\oplus b_i & i=m-1,m-2,...,2,1\\ \end{cases}$

在突变操作时，我们需要改变一个或少数基因座的值。如果使用标准二进制编码，编码串对应的参数值将可能发生大幅改变，这样导致算法的局部搜索能力下降；如果使用格雷码编码，编码串对应的参数值仅向其邻域发生微小的改变，这样提高了算法对连续函数局部空间的搜索能力。

浮点数编码

浮点数编码也叫作真值编码，个体的每个基因值用某一范围内的一个浮点数表示，通常使用决策变量的真实值，此时基因长度为1（一个浮点数），个体的编码长度等于其决策变量的个数。例如一个优化问题含有三个变量$x_1$、$x_2$和$x_3$，对应的浮点编码串为

$X:\quad |1.05|4.90|0.97|$

这表示此时$x_1$、$x_2$和$x_3$的取值分别为$1.05$、$4.90$和$0.97$。

浮点数编码方法更适合在遗传算法中表示范围较大的数，更适合于精度要求较高的遗传算法，更适合于处理复杂的约束条件。

个体适应度评价

在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中个概率。个体适应度越大，该个体遗传到下一代的概率越大；个体适应度越小，该个体遗传到下一代的概率越小。对于求无约束的目标函数最大值的问题，如果函数值总取正值，通常设定个体适应度$F(X)$等于目标函数值；对于求无约束的目标函数最大值问题，我们对目标函数增加一个负号，将其转换为求最大值的优化问题。

由于概率是非负值，需要确保个体适应度总为非负值。因此对于最大值优化问题，个体适应度做如下转换

$F(X)= \begin{cases} f(X)+C_{min} & f(X)+C_{min}>0\\ 0 & f(X)+C_{min} \leq 0 \end{cases}$

其中$C_{min}$可以取一个充分小值，也可以取进化到当前代为止出现的最小目标函数值。

对于最小值优化问题，个体适应度做如下转换

$F(X)= \begin{cases} C_{max}-f(X) & f(X)<C_{max}\\ 0 & f(x) \geq C_{max} \end{cases}$

其中$C_{max}$可以取一个充分大值，也可以取进化到当前代为止出现的最大目标函数值

选择

选择是指从当前代群体中选择出一些优良个体，并将其复制到下一代群体，而未被选择的个体将被淘汰。通常我们采取比例选择方法，也叫作轮盘赌。我们将个体的适应度在种群总适应度所占比例视为个体被选择的概率，个体适应度占比越大，被选择的概率也就越大。因此，当种群规模为$N$时，个体$i$被选中的概率为

$P(X_i)=\frac{F(X_i)}{\sum_{i=1}^NF(x_i)}$

通常，我们在种群集合依概率$P(X)$有放回地抽取$N$个个体，组成新的种群集合，以确保不改变种群规模。

交叉

交叉是指将某两个或多个个体的基因片段进行交换，以产生出新个体，提高全局搜索能力。

单点交叉与多点交叉

单点交叉是最简单的交叉方法，即在个体编码串中随机设置一个交叉点，在该点相互交换两个配对个体的部分染色体。

$\begin{matrix} A: & 100110|{011}\\ B: & 010011|{101} \end{matrix} \quad => \quad \begin{matrix} A: & 100110|{101}\\ B: & 010011|{011} \end{matrix}$

单点交叉对个体编码结构的破坏最小，当个体适应度较高时，单点交叉降低个体适应度的可能性最小。另外，还有双点交叉与多点交叉等多种交叉方式。其中双点交叉表示在个体编码串中设置两个交叉点，将两个交叉点中间的编码串进行交换，如下：

$\begin{matrix} A: & 10|{0110}|011\\ B: & 01|{0011}|101 \end{matrix} \quad => \quad \begin{matrix} A: & 10|{0011}|011\\ B: & 01|{0110}|101 \end{matrix}$

顾名思义，多点交叉指设两个以上的交叉点。但是在交叉过程中一般不推荐使用多点交叉方式，因为它可能破坏一些好的模式，使适应度高的个体很难保存下来，从而影响遗传算法的性能。

需要注意，进行交叉的个体是随机配对的，交叉点的选取也是随机的，已配对的个体依概率发生交叉。

算术交叉

算数交叉是指由两个个体的线性组合而产生出两个新的个体，算数交叉操作的对象一般是浮点数编码的个体。假设在两个个体$X_A^t$、$X_B^t$之间进行交叉算数交叉，则交叉后产生的两个新个体为

$\begin{cases} X_A^{t+1}=\alpha X_B^{t} + (1-\alpha) X_A^t\\ X_B^{t+1}=\alpha X_A^{t} + (1-\alpha) X_B^t\\ \end{cases}$

当$\alpha$是一个常数时，此时交叉运算称为均匀算术交叉运算；当$\alpha$是一个由进化代数所决定的变量时，此时交叉运算称为非均匀算数交叉。

变异

变异是指，在较小概率内，将个体染色体编码串中的某些基因用其它等位基因替代。变异操作能够改善算法的局部搜索能力，并且维持种群的多样性，防止出现早熟现象，使程序陷入局部最优解的可能性降低。

基本位变异

二进制编码最常用的变异方法为基本位变异，其中基本位变异包括单点变异于多点变异，即随机选取编码串上一个或多个基因座发生突变。对于二进制编码，变异操作就是将个体在变异点上的基因座上的值取反。

$单点变异:\quad 1001{1}0011\ =>\ 1001{0}0011\\ 多点变异:\quad 10{0}1{1}00{1}1\ =>\ 10{1}1{0}00{0}1\\$

基本位变异基因座位置是随机的。

非均匀变异

基本位变异并不适合浮点数编码的串，对于浮点数编码的个体，可以用变量取值范围$[X_{min}, X_{max}]$内的某个值替换原基因值。当取值范围中每一个值被选中的概率是均匀的，称为均匀变异。均匀变异在遗传算法运行初期能使搜索点在整个搜索空间内自由移动，有利于增加种群多样性；但是它不适合对重点区域进行搜索，在算法运行后期将会影响性能。

非均匀变异的具体操作过程与均匀变异相似，但它重点搜索原个体附近的微小区域。若变异点$x_k$处基因值得取值范围为$[X^k_{min}, X^k_{max}]$，则新的基因值$x_k’$为

$x_k'= \begin{cases} x_k+\Delta(t,X_{max}^k-x_k) & rand()\mod 2=0\\ x_k+\Delta(t,x_k-X_{max}^k) & rand()\mod 2=1\\ \end{cases}$

其中，$\Delta(t,y)$表示在$[0,y]$范围内符合非均匀分布的一个随机数，并且随着进化代数$t$的增加，$\delta(t,y)$趋近于$0$的概率也逐渐增加。以下是一种$\Delta(t,y)$的定义方式

$\Delta (t,y)=y\cdot (1-r^{(\frac{1-t}{T})b})$

非均匀变异使得算法在初期进行均匀随机搜索，而在后期进行局部搜索。随着算法的进行，非均匀编译使得最优解的搜索过程更加集中在某一更有希望的重点区域中。

算法步骤

遗传算的步骤如下：

初始化种群。设置种群参数，包括种群规模、基因长度、染色体长度、迭代次数等
编码。确定合适的编码方式，建立由个体基因型$X$到个体表现型$x$的映射关系
评价个体适应度。确定由目标函数$f(x)$到个体适应度$F(x)$的转换规则
选择。依据个体适应度，以一定规则挑选出个体适应高的个体复制到下一代
交叉。对种群中的个体之间进行随机配对，并使用合适的交叉方法依概率交换个体的基因片段
突变。以较小概率改变个体的一个或多个基因。
判断是否满足迭代终止条件。通常为是否达到最大迭代次数$G_{max}$，若满足则输出种群最优个体；若不满足回到第4步

例程

Rosenbrock香蕉函数定义如下：

$f(x_1,x_2)=100(x_1^2+x_2)^2+(1-x_1)^2\\ ~\\ s.t.\ -2.048\leq x_1,x_2\leq 2.048\\$

设置种群规模为$100$，单个基因长度为$10$，交叉率为$0.6$，突变率为$0.01$，进化代数为$100$，利用二进制编码方式对变量进行编码，采用双点交叉、基本位变异方法，遗传算法程序如下

import numpy as np  
import random as rd 
import matplotlib.pyplot as plt

class GA:
    def __init__(self, nVar, xMin, xMax, geneLen, popSize = 100, crosRate = 0.6, mutRate = 0.01, generation = 100):
        self.nVar = nVar                            # 变量个数
        self.xMin = np.array(xMin, dtype = float)   # 自变量下限
        self.xMax = np.array(xMax, dtype = float)   # 自变量上限
        self.popSize = popSize                      # 种群规模
        self.geneLen = geneLen                      # 基因长度
        self.chromLen = nVar * geneLen              # 染色体长度  
        self.crosRate = crosRate                    # 交叉率
        self.mutRate = mutRate                      # 突变率
        self.generation = generation                # 迭代次数
        # 初始化第一代种群，二进制编码
        self.pop = np.random.randint(0, 2, size=(self.popSize, self.chromLen))
    # 解码
    def translate(self):
        popPerform = np.zeros((self.popSize, self.nVar), dtype=float)
        # 转换成十进制
        tmp = np.logspace(self.geneLen - 1, 0, self.geneLen, base=2)
        for i in range(self.popSize):
            for j in range(self.nVar):
                popPerform[i][j] = np.dot(self.pop[i][j*self.geneLen:(j+1)*self.geneLen], tmp)
        # 利用解码公式转换
        popPerform = self.xMin + popPerform * (self.xMax - self.xMin)/(2**self.geneLen - 1)
        return popPerform
    # 适应度，由于该目标函数值总为正值，因此直接将目标函数作为个体适应度评价标准
    def fitness(self, X):
        x1, x2 = X[0], X[1]
        fx = 100 * (x1**2 - x2)**2 + (1-x1)**2
        return fx
    # 选择
    def select(self):
        # 计算每个个体的适应度
        popFit = np.array([self.fitness(self.translate()[i]) for i in range(self.popSize)])
        # 轮盘赌选择下一代
        idx = np.random.choice(np.arange(self.popSize), size=self.popSize, replace=True, p=(popFit)/(popFit.sum()) )
        self.pop = self.pop[idx]
    # 交叉
    def crossover(self):
        idx = np.arange(self.popSize)
        for i in range(self.popSize//2):
            # 从种群中随机抽取一对个体进行交叉
            idx_i = np.random.choice(idx.shape[0], size = 2, replace=False)
            couple = idx[idx_i]
            idx = np.delete(idx, idx_i)
            # 以一定概率发生交叉
            if rd.uniform(0,1) < self.crosRate:
                # 随机抽取一段基于片段
                l = rd.randint(0, self.popSize-1)
                r = rd.randint(l, self.popSize)
                self.pop[couple, l:r] = self.pop[couple[::-1], l:r]
    # 突变
    def mutation(self):
        for i in range(self.popSize):
            for j in range(self.chromLen):
                # 以一定概率突变
                if rd.uniform(0, 1) < self.mutRate:
                    self.pop[i][j] = not self.pop[i][j]
    # 迭代
    def update(self):
        for gen in range(self.generation):
            self.select()
            self.crossover()
            self.mutation()
    # 输出
    def display(self):
        popPerform = self.translate()
        idx, best = 0, self.fitness(popPerform[0])
        for i in range(1, self.popSize):
            fx = self.fitness(popPerform[i])
            if fx > best:
                idx, best = i, fx
        print(popPerform[idx])
        print(best)

if __name__ == '__main__':
    Rosenbrock_GA = GA(nVar = 2, xMin = [-2.048, -2.048], xMax=[2.048, 2.048], geneLen = 10)
    Rosenbrock_GA.update()
    Rosenbrock_GA.display()

筛选出最优输出结果

1 2	[-2.04399609 -2.048 ] 3885.4739163295735