https://www.jianshu.com/p/ae5157c26af9
https://www.cnblogs.com/legend1130/archive/2016/03/29/5333087.html
https://blog.csdn.net/u012750702/article/details/54563515
https://blog.csdn.net/u010025211/article/details/49051921

遗传算法（GA） 是一种现代自启发优化算法，它简化并模拟了自然界中生物性状的演化过程，借鉴了 “适者生存” 的思想和孟德尔的遗传理论。由于在算法中加入了随机的因素，所以该算法能够有效的避免陷入局部最优。

然而，我又把这种算法称为 “欧洲人才能用的算法”，因为，运气好的欧洲细作，可以在 10代演化内获得最优结果；而运气差的非洲酋长，可能在服务器上演化个几万代，最终陷入局部最优（摊手~。

一旦陷入局部最优，性价比最高的方法就是————重启程序，重新演化。

1. 遗传算法的基本流程

1.1. 确定个体的基因型和表现型并建立联系

遗传算法的第一步就是——编码。好的编码方式可以有效提高算法的效率（欧洲人请无视！），逻辑正确的编码方式是遗传算法可以进行的基础。

什么是编码呢？编码就是将表现型转化为基因型，反之，从基因型转化到表现型就是解码。（有的人可能看到这里一头雾水，请耐心把这部分看完，后面将给出一个生动的实例！）

1.2. 确定环境的淘汰规则和个体的适应度算法

遗传算法秉承 “适者生存” 的思想，根据淘汰规则从种群中淘汰个体。

淘汰的标准是什么呢？这需要量化，根据优化目标设计个体适应度算法和淘汰规则。根据个体的表现型计算并处理个体的 适应度 \(w\)，若适应度满足淘汰规则，则杀死该个体（移出种群），反之则留下，适应度表现的最优越者，应该在种群中 重点培养！（种马？）

1.3. 种群淘汰

又称为选择，进行优胜劣汰。值得注意的是我们不能直接删除适应度表现的差的个体，因为自然界中也并非精准打击劣者，只是在概率上保证优者比劣者的存活几率更高，这里介绍几种常用的选择策略：

(1)轮盘赌算法

我们希望优秀个体被选中的概率越大越好，故而要对个体的适应度进行处理，使其满足越大越优秀的性质（对于本身不满足的可以通过求倒数的方法来实现）

假设当代种群中有 \(n\) 个个体，那么先计算所有个体的处理过后的适应度总和 \(W\)：

\[W=\sum_{i=1}^n w_i\\ \]

每个个体的被选中概率 \(P_{i}\) 为：

\[P_i=\frac{w_i}{W} \]

计算后的概率累积可以构成一个轮盘：

\[\left[ \begin{matrix} P_1 & P_2 & P_3 & ...&P_n\\ \end{matrix} \right] \]

生成 0-1 之间的随机数，看随机数击中轮盘的哪个概率区间，哪个个体就被留下。

(2)随机遍历抽样法

首先和 轮盘赌法 一样计算各个个体的概率并形成轮盘。若我们要选择 \(m\) 个个体留下，那么先生成一个 \([0,\frac{1}{m}]\) 的随机数 \(t\)，然后逐次进行 \(t=t+\frac{1}{m}\)，每次 \(t\) 击中的概率区间所对应的个体就是要被留下个体。

(3)锦标赛法

我更愿意把它称为 “养蛊法”，这个方法的核心是每一代都选出最好的一批个体，然后投入下一代的演化中。选择时只根据适应度，并不在选择中加入随机的因素。

这种不加入随机的策略会提高演化过程中陷入局部最优的概率，慎用！

1.4. 种群繁衍

种群在进行淘汰后，为了保证种群的规模，要进行繁衍，繁衍的过程中就会产生交叉和变异。交叉和变异的方法很多，这里不赘述了，可以看下面的链接。值得一提的是最好在其中加入随机的因素，比如每次交叉随机选择起点和终点。

https://blog.csdn.net/u012750702/article/details/54563515

https://blog.csdn.net/u010025211/article/details/49051921

1.5. 轮回

上述操作做完后，新一代的种群就诞生了。计算新种群中所有个体的适应度，然后继续淘汰、繁衍，周而复始。在演化的过程中，种群整体将会逐步进化，趋向于我们寻找的最优。

2. 实例

这里将以计算函数最小值作为例子来表现遗传算法的整个流程。

给出这样一个函数：

\[y=f(x)=x\sin(10πx)+2，x∈[-1,2] \]

它的图像是这样的：

我们现在的目标就是寻找 该函数的在指定区间的最小值

首先，我们要确定 表现型 和 基因型

很明显，表现型就是 \(x\) ；基因型是表现型的编码，这里我们采用二进制编码。

如何进行二进制编码呢？众所周知，计算机的精度是有限的，区间 \([-1,2]\) 之间有无数个 \(x\)，我们不可能取这么多。假设我要进行 4 位二进制编码，那么就可以选择 \(2^4=16\) 个数，每个数的间隔为 \(step=\frac{2-(-1)}{2^4}\)

二进制基因型如何解码为表现型呢？假设4位二进制编码规则下的一个基因型为：

\[ \left[ \begin{matrix} 0 & 1 & 1 &0\\ \end{matrix} \right] \]

它的解码方式为：计算该基因型的十进制数 \((0110)_{bin}=(6)_{dec}\)，它的表现型为该十进制数乘以 \(step\) 加区间下界：

\[x=dec×step+min=6×\frac{2-(-1)}{2^4}+(-1)=0.125 \]

我将以 16 位二进制编码规则为例，\(step=\frac{2-(-1)}{2^{16}}\)

然后，我们要确定 适应度算法 和 淘汰规则

由于我们要获得函数的最小值，所以，适应度算法应该为（并不完善，下一步还要做出调整）：

\[w=f(x)=x\sin(10πx)+2，x∈[-1,2] \]

淘汰规则为尽量选最小的。

根据上面的步骤随机初始化一个初始种群后，对该种群进行淘汰

我将以轮盘赌法为例。由于我们的目标是选取最小值，所以值越小越好，故而要对适应度进行倒数转换，使值越小的个体适应度越高，故而适应度算法应该修改为：

\[w=\frac{1}{f(x)}=\frac{1}{x\sin(10πx)+2}，x∈[-1,2] \]

接下来就很简单了，计算每个个体的概率，并将概率累积为轮盘，生成 \([0,1]\) 随机数，看击中区间是哪个就留下哪个。

其实还有一种思路，那就是不进行倒数转换，随机数击中哪个区间就淘汰哪个（值越大的数被击中的概率越大）。

交叉

我将选择如下交叉算法，假设有两个序列为：

\[X=\left[ \begin{matrix} x_1 & x_2 & x_3 & x_4 & ... & x_{16} \\ \end{matrix} \right]\\ Y=\left[ \begin{matrix} y_1 & y_2 & y_3 & y_4 & ... & y_{16} \\ \end{matrix} \right] \]

生成两个 \([1,16]\) 间不相同的随机整数 \(max\) 和 \(min\) ，这两个序列以它们为起终点进行交叉：

\[X=\left[ \begin{matrix} x_1 & x_2 & ...& x_{min-1} & x_{min} &...&x_{max}&x_{max+1} & ... & x_{16} \\ \end{matrix} \right]\\ Y=\left[ \begin{matrix} y_1 & y_2 & ...& y_{min-1} & y_{min} &...&y_{max} & y_{max+1}& ... & y_{16} \\ \end{matrix} \right]\\ ↓\\ Z_{new}=\left[ \begin{matrix} x_1 & x_2 & ...& x_{min-1} & y_{min} &...&y_{max}&x_{max+1} & ... & x_{16} \\ \end{matrix} \right]\\ \]

变异

我这里使用最简单的变异规则。

生成 \(n\) 个 \([1,16]\) 间的随机整数，将对应位置上二进制数取反即可。

Python 代码模拟结果为：

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 30 09:35:31 2019

@author: yzn
"""
import random
import math
import matplotlib.pyplot as plt
import numpy as np

def bin2dec(s):  # 函数：二进制字符串转十进制整型
    s=s[::-1]
    total=0
    for i in range(len(s)):
        total=total+int(s[i])*(2**i)
    return total

def random_bin_generate(size): # 函数：伪随机二进制流发生器
    s=""
    for i in range(size):
        x=random.randint(0, 100)
        if x%2==0:
            s=s+'0'
        else:
            s=s+'1'
    return s


class individual:# 类：个体
    def __init__(self,gene_size):
        self.gene="" # 个体基因型
        self.phenotype=0 # 个体表现型
        self.fitness=0 # 个体适应度
        self.gene_size=gene_size # 个体基因型规模
        self.P=0 # 适应度所占权重（概率）
        self.alive=False # 个体存活状况
    
    def live(self): # 函数：使个体存活
        self.alive=True
    def die(self): # 函数：使个体死亡
        self.alive=False
    
    
    def gene_random_generate(self): # 函数：生成随机基因型
        self.gene=random_bin_generate(self.gene_size)
    
    def cal_phenotype(self,max_border,min_border): # 计算表现型
        step=(max_border-min_border)/(2**self.gene_size)
        self.phenotype=bin2dec(self.gene)
        self.phenotype=self.phenotype*step+min_border    
    def cal_fitness(self):# 函数：计算适应度
        self.fitness=self.phenotype*math.sin(10*math.pi*self.phenotype)+2
        
        
        
class population:# 类：种群
    def __init__(self,max_size,max_border,min_border):
        self.max_size=max_size # 种群大小
        self.individuals_dict={} # 种群个体字典
        self.max_border=max_border # 区间上边界
        self.min_border=min_border # 区间下边界
        self.best_individual_key=0 # 最佳个体的 key
        self.worst_individual_key=0 # 最差个体的 key
    
    def first_population_generate(self): # 第一代种群生成
        for i in range(self.max_size):
            new_individual=individual(16) # 生成基因为16位的新个体
            new_individual.gene_random_generate() # 生成随机基因
            new_individual.cal_phenotype(self.max_border,self.min_border) # 解码表现型
            new_individual.cal_fitness() # 计算适应度
            new_individual.live() # 使个体存活
            self.individuals_dict[i]=new_individual # 加入字典
        
    def show_population_detail(self): # 显示种群中个体信息
        print("\n========================\n")
        for key in self.individuals_dict:
            print("key：\t"+str(key))
            print("个体存活状况：\t"+str(self.individuals_dict[key].alive))
            print("个体基因型规模：\t"+str(self.individuals_dict[key].gene_size)+'位')
            print("个体基因型：\t"+str(self.individuals_dict[key].gene))
            print("个体表现型：\t"+str(self.individuals_dict[key].phenotype))
            print("个体适应度：\t"+str(self.individuals_dict[key].fitness))
            print("个体适应度权重：\t"+str(self.individuals_dict[key].P))
            print("---------------------------------------------------------")
        print("\n========================\n")
    
    
    def show_individual(self,key): # 显示种群内某个个体的信息
        print("\n========================\n")
        print("key：\t"+str(key))
        print("个体存活状况：\t"+str(self.individuals_dict[key].alive))
        print("个体基因型规模：\t"+str(self.individuals_dict[key].gene_size)+'位')
        print("个体基因型：\t"+str(self.individuals_dict[key].gene))
        print("个体表现型：\t"+str(self.individuals_dict[key].phenotype))
        print("个体适应度：\t"+str(self.individuals_dict[key].fitness))
        print("个体适应度权重：\t"+str(self.individuals_dict[key].P))
        print("---------------------------------------------------------")
        print("\n========================\n")        
    
    
    def show_population_figure(self,title): # 在图中显示当前种群的情况
        x_ori=np.arange(self.min_border,self.max_border+0.1,0.01,dtype=np.float)
        y_ori=x_ori*np.sin(10*math.pi*x_ori)+2
        
        x_die=[]
        y_die=[]
        x_live=[]
        y_live=[]
        for key in self.individuals_dict:
            if self.individuals_dict[key].alive:
                x_live.append(self.individuals_dict[key].phenotype)
                y_live.append(self.individuals_dict[key].fitness)
            else:
                x_die.append(self.individuals_dict[key].phenotype)
                y_die.append(self.individuals_dict[key].fitness)                
        
        
        
        plt.figure(figsize=(16,8))
        plt.plot(x_ori,y_ori,'-')
        plt.plot(x_live,y_live,'*',label = 'Living ones')
        plt.plot(x_die,y_die,'*',label = 'Died ones')

        plt.plot(self.individuals_dict[self.best_individual_key].phenotype
                 ,self.individuals_dict[self.best_individual_key].fitness
                 ,'o'
                 ,label='Best Individual')
        plt.plot(self.individuals_dict[self.worst_individual_key].phenotype
                 ,self.individuals_dict[self.worst_individual_key].fitness
                 ,'o'
                 ,label='Worst Individual')
             
        
        plt.legend(loc='best')
        plt.title(title)
        #plt.savefig("./image/"+str(title)+".png") 
        plt.show()
        
    
    def weed_out(self,nums_weed_out): # 函数：淘汰， nums_weed_out 淘汰个数
        ### 采用轮盘赌法，适应度越高，被击中概率越大，击中则淘汰
        rest_num=self.max_size+nums_weed_out # 种群剩余数量
        # 计算适应度总量
        total=0
        for key in self.individuals_dict:
            total=total+self.individuals_dict[key].fitness
        # 计算个体适应度所占权重
        for key in self.individuals_dict:
            self.individuals_dict[key].P=self.individuals_dict[key].fitness/total
        # 挑选出最佳个体直接保留,最差个体直接淘汰
        for key in self.individuals_dict:
            if self.individuals_dict[key].P<self.individuals_dict[self.best_individual_key].P:
                self.best_individual_key=key
            
            if self.individuals_dict[key].P>self.individuals_dict[self.worst_individual_key].P:
                self.worst_individual_key=key
        
        self.individuals_dict[self.worst_individual_key].die()
        nums_weed_out=nums_weed_out-1
        self.individuals_dict[self.best_individual_key].die() # 暂时让最佳个体死亡，轮盘淘汰后再进行复活
        '''
        print("全场最佳：")
        self.show_individual(self.best_individual_key)
        print("全场最菜：")
        self.show_individual(self.worst_individual_key)     
        '''
        
        ## 开始淘汰！
        while(nums_weed_out>0):
            # 再次计算活个体适应度权重
            total=0
            for key in self.individuals_dict:
                if self.individuals_dict[key].alive:
                    total=total+self.individuals_dict[key].fitness
            # 计算活个体适应度所占权重
            for key in self.individuals_dict:
                if self.individuals_dict[key].alive:
                    self.individuals_dict[key].P=self.individuals_dict[key].fitness/total        
            
            r=random.randint(0, 100000)/100000
            before_r=0
            current_r=0
            for key in self.individuals_dict:
                if self.individuals_dict[key].alive:
                    before_r=current_r
                    current_r=current_r+self.individuals_dict[key].P
                    if r>before_r and r<=current_r:
                        self.individuals_dict[key].die() # 淘汰被击中的个体
                        nums_weed_out=nums_weed_out-1
                        break
            
        # 淘汰结束，复活最佳个体
        self.individuals_dict[self.best_individual_key].live()
    
    def cross(self): # 函数：交叉
        gene_size=self.individuals_dict[0].gene_size
        while True:
            flag=True
            for key in self.individuals_dict:
                if self.individuals_dict[key].alive==False:
                    ## 该个体死亡，随机选择两个个体进行交叉生成新个体
                    flag=False
                    parent=[]
                    ## 以 50% 的概率随便挑选两个活母体
                    while True:
                        for key_parent in self.individuals_dict:
                            if self.individuals_dict[key_parent].alive:
                                rand=random.randint(0, 100)
                                if rand>50:
                                    parent.append(key_parent)
                            if len(parent)==2:
                                break
                        if len(parent)==2:
                            break              
                    ## 母体挑选完毕，开始进行交叉
                    Min=random.randint(int((1/4)*gene_size),int(gene_size/2))
                    Max=random.randint(int(gene_size/2),int((3/4)*gene_size))
                    self.individuals_dict[key].gene=self.individuals_dict[parent[0]].gene[0:Min]\
                                                    +self.individuals_dict[parent[1]].gene[Min:Max+1]\
                                                    +self.individuals_dict[parent[0]].gene[Max+1:]
                    self.individuals_dict[key].live()
            if flag:
                break
    def variation(self,rate): # 函数：变异 rate:变异率
        gene_size=self.individuals_dict[0].gene_size
        for key in self.individuals_dict:
            if self.individuals_dict[key].alive:
                rand=random.randint(0, 10000)/10000
                if rand<=rate:
                    rand=random.randint(0, gene_size-1)
                    s=list(self.individuals_dict[key].gene)
                    if s[rand]=='0':
                        s[rand]='1'
                    else:
                        s[rand]='0'
                    s=''.join(s)
                    self.individuals_dict[key].gene=s
    def run(self): # 函数：种群运转
        for key in self.individuals_dict:
            if self.individuals_dict[key].alive:
                self.individuals_dict[key].cal_phenotype(self.max_border,self.min_border) # 解码表现型
                self.individuals_dict[key].cal_fitness() # 计算适应度
        

                    
            
            
            
        
        

def main():
    max_size=100 # 设置种群规模
    genetation_nums=100 # 设置演化代数
    # 初始化种群
    current_population=population(max_size,2,-1)
    current_population.first_population_generate()
    
    for i in range(genetation_nums):
        current_population.run() # 种群运转
        current_population.weed_out(int(max_size/2))# 淘汰
        current_population.show_population_figure("Generation "+str(i+1)) # 显示本代情况
        current_population.cross() # 交叉
        current_population.variation(0.3) # 变异


if __name__ == '__main__':
  main()

【算法】遗传算法