百行Python代码教你认识遗传算法

发表于 | 更新于 | 评论数： | 阅读次数：

遗传算法是一种启发式搜索算法，其基本原理是模拟自然界物竞天择的演化法则。（说的这么高大上，其实就是比较高级的穷举法，不过穷举的时候给出穷举方向而已）。遗传算法具体步骤见下图（来自百度百科）：

名词介绍

染色体，个体，基因

这3个概念基本等价，遗传算法中每个个体都含有一个染色体\基因，遗传算法将在种群中选择优秀个体，将他们的染色体交叉、变异后产生新的下一代种群。

一下说了这么多新概念，你可能会有些晕，说到底，染色体就相当于自变量x，而我们的优化目标就相当于因变量y，他们之间有函数关系y=f(x)，这个函数f(x)就是评价一个染色体好坏、能否适应环境的适应度函数。

那么我们如何得到染色体呢？简单的方式是通过二进制编码。

编码、解码

编码的作用就是将解空间的解转换为染色体编码，比如你想花100块钱去吃东西，那解空间便是[0,100]，然后我们将此空间转化为一个8位的染色体编码

$$00000000 \rightarrow 11111111$$
$$0 \rightarrow 100$$

将染色体在解空间上平均分布，这样每个染色体与解空间的解都将存在一一对应的关系，如 $00000000 \rightarrow 0$ ，这也就是解码的过程。

总结下，对于二进制编码来说，编码是将实数转化二进制数，解码是将二进制数转化为实数。

遗传操作

选择

选择需要选择出更适应环境的个体，用于之后的交叉操作，适应环境的个体将更加容易被选中，产生更多后代。适应环境与否可以通过适应度函数，适应度函数类似目标函数，根据你优化求解的问题确定，本博选用的适应度函数为：
$$f(x)=x+5\sin(5x)+2\cos(3x)$$
函数图像如下所示：

根据适应度函数可以确定每次选择每个个体被选中的概率，计算公式如下：选中概率=个体适应度/总体适应度。可见，适应度越高，被选中概率越大
$$p_i = \frac{f(x_i)}{\sum\limits^n_{j=1}f(x_j)}$$

从上式可知，所有个体被选中的概率为1，假设p为概率数组，包含了每个个体被选中的概率，因此将个体被选中概率累加：

for i in range(len(p)): p[i]=p[i-1]+p[i]

然后随机生成0-1之间的随机数，依次在概率数组中比较，就可以找到被选中的个体。如下图所示：

交叉

对选择出的多个适应性优良个体，通过交叉操作产生下一代优良个体。如下所示：

$$A_{father}B_{father}+A_{mather}B_{mather}\rightarrow A_{father}B_{mother}(child_1)+A_{mother}B_{father}(child_2)$$
对二进制编码的基因而言，假设基因长度为8，父辈母辈各取长度4的基因，有：
$$\color{red}{11110000}\color{black}+\color{blue}{00001111}\color{black}\rightarrow \color{red}{1111}\color{blue}{1111}\color{black}{+}\color{blue}{0000}\color{red}{0000}$$

交叉将父辈、母辈的基因交叉产生子代，子代将继承上一代的优良基因。

变异

为了避免收敛到局部最优解，在遗传算法中加入变异属性，使优化程序有一定几率跳出局部最优解。群体中的每个个体都有一定几率发生变异，变异时任取个体的一段基因并将其改变，如：
$$\color{red}{11111111}\color{black}\rightarrow \color{red}{1111}\color{blue}{0}\color{red}{111}$$

代码实现

代码用到numpy以及matplotlib库。

详见Github

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#author:微石
#blog:akihoo.github.io
import numpy as np
import matplotlib.pyplot as plt
import math
plt.rcParams['font.sans-serif']=['SimHei'] #用来正常显示中文标签
plt.rcParams['axes.unicode_minus']=False #用来正常显示负号
def aimFunction(x):
    x=x/2**17*9#将染色体映射到解空间
    y=x+5*math.sin(5*x)+2*math.cos(3*x)
    return y
def Fitness(population):
    value=[]
    for i in range(len(population)):
        value.append(max(aimFunction(population[i]),0))
    return value
def selection(population):
    #计算适应度函数
    fitness=Fitness(population)
    #轮盘赌选择
    sum_fitness=sum(fitness)#计算总体适应度
    fitness=[i/sum_fitness for i in fitness]#计算个体生存概率
    for i in range(1,len(fitness)):
        fitness[i]+=fitness[i-1]
    #优胜劣汰，重新选择10个种群，生存概率高的可能被选择多次
    population_new=[]
    for i in range(len(fitness)):
        rand=np.random.uniform(0,1)
        for j in range(len(fitness)):
            if rand<=fitness[j]:
                population_new.append(population[j]) 
                break          
    return population_new
def get_last_chrom(parent,copint):#计算染色体后几位
    s=''
    for i in range(copint):
        if(parent%2):
            s+='1'
        else:
            s+='0'
        parent=parent>>1
    return int(s,2)
def crossover(population_new,chrom_length, pc=0.6):
    #pc:交配概率
    #chrom_length:染色体长度
    #选择父辈、母辈，交叉染色体
    half=len(population_new)//2
    father,mother=population_new[:half],population_new[half:]
    np.random.shuffle(father)
    np.random.shuffle(mother)
    offspring=[]
    for i in range(half):
        if np.random.uniform(0,1)<=pc:
            copint = np.random.randint(1,chrom_length-1)
            son=(father[i]>>copint<<copint)+get_last_chrom(mother[i],copint)
            daughter=(mother[i]>>copint<<copint)+get_last_chrom(mother[i],copint)
        else:
            son,daughter=father[i],mother[i]
        offspring.append(son)
        offspring.append(daughter)
    return offspring
def mutation(offspring,chrom_length,pm=0.01):
    #pm:变异概率
    for i in range(len(offspring)):
        if np.random.uniform(0,1)<=pm:
            position=np.random.randint(0,chrom_length-1)
            offspring[i]=list(bin(offspring[i])[2:])
            offspring[i]=['0' * (chrom_length-len(offspring))]+offspring[i]
            offspring[i][position]='1' if offspring[i][position]=='0' else '0'
            offspring[i]=int(''.join(offspring[i]),2)
    return offspring
def one_generation(population,chrom_length):
    population=selection(population)#选择
    offspring=crossover(population,chrom_length)#交叉
    offspring=mutation(offspring,chrom_length)#变异
    return max([aimFunction(i) for i in offspring]),offspring
if __name__=='__main__':
    #初始化种群，生成100个种群，使用np.random.randint随机生成基因
    population=[] #储存基因数据
    pop_size=100 #种群规模
    chrom_length=17#基因长度
    for i  in range(pop_size):#随机生成种群
        population.append(np.random.randint(0,2**chrom_length))
    res,pop=[],[]
    for i in range(100):
        r,population=one_generation(population,chrom_length)
        res.append(r)
        if(i%5==0):
            pop.append(population)
    plt.plot(res)
    plt.show()
    x=[i/100 for i in range(900)]
    y=[i+5*math.sin(5*i)+2*math.cos(3*i) for i in x]
    colors=['b','r','g','y']
    for j in range(4):
        plt.subplot(221+j)
        plt.plot(x,y)
        plt.scatter([i/2**17*9 for i in pop[j]], [aimFunction(i) for i in pop[j]],color=colors[j],alpha=0.5)
        plt.title('第'+str(j*5)+'代种群')#显示图表标题
    plt.show()

结果分析

本文的算例相对比较简单，优化迭代图如图所示，算法最终收敛到12.9-13.05都是有可能的：

种群示意图如下图：

可以发现，初始种群随机分布在整个设计域内，随着迭代次数的增加，劣势种群逐步被淘汰，优势种群不断繁衍，造成剩下的种群逐步向目标函数极大值处集中。另外也有少部分种群发生变异，随机出现在图中的某一位置。

本文标题:百行Python代码教你认识遗传算法

文章作者:微石

发布时间:2018年06月12日 - 09:06

最后更新:2018年07月19日 - 17:07

原始链接:akihoo.github.io/posts/48cd5d7a.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。