遗传算法（Genetic Algorithm，GA）

2023-09-09 16:37

短信预约 -IT技能 免费直播动态提醒

这是一篇关于遗传算法的总结博客，包括算法思想，算法步骤，python实现的两个简单例子，算法进阶（持续更新ing）。

1 算法思想

遗传算法的应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制，找圆心问题（在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心），TSP问题，生产调度问题，人工生命模拟等。

遗传算法起源于对生物系统所进行的计算机模拟研究，是一种随机全局搜索优化方法，它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体（Individual），从而求得问题的优质解。

举个已经举烂的例子：
我们把要求的函数曲线想象成一个一个山峰和山谷组成的山脉。那么我们可以设想每一个可能解都是一只袋鼠，我们希望它们不断的向更高处跳去，直到跳到最高的山峰（尽管袋鼠本身不见得愿意那么做）。

遗传算法是这样做的：有一大群袋鼠，有的跳跃能力强，喜欢往高处，有的跳跃能力弱，喜欢在低处。有一天它们被莫名其妙的零散地扔到喜马拉雅山脉，在那里艰苦的生活繁衍下去。海拔低的地方弥漫着一种无色无味的毒气，海拔越高毒气越稀薄。可怜的袋鼠们并不知道毒气的存在，还是活蹦乱跳。于是，不断有不善跳跃的袋鼠死于海拔较低的地方，而在海拔越高的善于跳跃的袋鼠活得越久，也越有机会生儿育女，把善于跳跃的基因传给后代。就这样经过许多年繁衍生息，这些袋鼠们渐渐聚拢到了一个个的山峰上。最终，只有最高的珠穆朗玛峰上的袋鼠被带回了美丽的澳洲。

术语介绍：

染色体(Chromosome)：染色体又可称为基因型个体(individuals)，一定数量的个体组成了群体(population)，群体中个体的数量叫做群体大小（population size）。
位串(Bit String)：其实就是遗传学中的染色体在计算机中的表示。
基因(Gene)：基因是染色体中的元素，用于表示个体的特征。例如有一个二进制串（即染色体）S=1011，则其中的1，0，1，1这4个元素分别称为基因。
特征值( Feature)：在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
适应度(Fitness)：各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数通常会被用来计算个体在群体中的优良等级。
基因型(Genotype)：或称遗传型，是指基因组定义遗传特征和表现。对应于位串。
表现型(Phenotype)：生物体的基因型在特定环境下的表现特征。对应于位串解码后的参数。

2 算法步骤

染色体编码，寻找一种对问题潜在解进行“数字化”编码的方案，建立表现型和基因型的映射关系。（建立袋鼠跳跃能力与基因的映射关系）
初始化种群（刚开始袋鼠们被零散地扔到喜马拉雅山脉）
用适应度函数对每一个个体进行适应度评估（袋鼠跳得越高毒气越稀薄，相当于适应度越大）
用选择算子按照某种规定择优选择（低处的袋鼠很快被毒死，也就是被淘汰掉，以保证袋鼠总体数目持平）
让个体基因变异，保持种群多样性。（让袋鼠随机地跳一跳，说不定就刚好跳到了珠穆朗玛峰附近呢）
然后产生子代（希望存活下来的袋鼠是善于跳向高处的，并生儿育女，把善于跳跃的基因传给后代）
达到迭代次数或最小误差，算法终止，否则转向步骤3.

3 第一个简单的例子（python实现）

跟着B站一位博主的学习视频敲下了我的第一个遗传算法
视频链接

题目：在一个长度为n的数组nums中选择10个元素，使得10个元素的和与原数组的所有元素之和的1/10无限接近。
比如n=50，sum（nums）=1000，选择的元素列表answer要满足sum（answer）-100的绝对值小于e，e要尽可能的小。

思路：

创建包含100个解的随机初始解集（用random.sample(list,number)从list中随机抽取number个元素）
对解集中每两个解（父体与母体）进行选择交换，问题：如何选择这两个解？那就是选择优秀的交换，用轮盘赌选择法。
每个解都对应有一个误差和一个适应度，误差越小的解适应度越大（反比例函数）。
这里的适应度=1/误差。
归一化，将每个解的适应度除以所有解的适应度之和，归一化后得到选择概率。
叠加化 a1=a1,a2=a1+a2,a3=a1+a2+a3…,叠加之后每个解的选择概率从0-1依次增长，得到累积概率。
在0-1中随机选取一个浮点数（如0.4），从选择概率中挑出一个最接近的。
选择一部分进行交叉重组。
随机变异，保持种群多样性。

import random#1.创建初始解集def create_answer(numbers_set,n):    result=[]#存放解集的列表    for i in range(n):#循环n次，每次创建一个解集（包含10个元素）        result.append(random.sample(numbers_set,10))#从初始数组中随机抽取10个元素    return result#2.选择两个解#计算误差def error_level(new_answer,numbers_set):    error = []#存放适应度的列表    right_answer = sum(numbers_set)/10#正确答案，也就是原数组所有元素之和的1/10    for item in new_answer:        value = abs(right_answer-sum(item))#误差等于每个解与正确答案之差的绝对值        if value==0:#误差最小是0.1            error.append(10)#？？？？        else:            error.append(1/value)#用反比例函数计算适应度    return error#选择两个解def choice_selected(old_answer,numbers_set):    result=[]    error = error_level(old_answer,numbers_set)#调用计算误差函数    error_one = [item/sum(error) for item in error]#归一化，列表每个元素除以列表总体元素之和，选择概率error_one    for i in range(1,len(error_one)):#叠加化        error_one[i] += error_one[i-1]    for i in range(len(old_answer)//2):#整体选两波        temp = []#存放父体母体的列表        for j in range(2):#一波选两个            rand = random.uniform(0,1)#从0-1中随机选择一个浮点数            for k in range(len(error_one)):#遍历寻找最接近的答案                if k==0:                    if rand<error_one[k]:#如果该浮点数小于第一个数，选择出来放到temp中                        temp.append(old_answer[k])                else:                    if rand>=error_one[k-1] and rand<error_one[k]:#如果该浮点数处在两个数中间，将更大的选择出来放到temp中                        temp.append(old_answer[k])        #3.交叉(交换信息)？？？？？        rand = random.randint(0,6)        temp_1 = temp[0][:rand]+temp[1][rand:rand+3]+temp[0][rand+3:]#新子体temp1        temp_2 = temp[1][:rand]+temp[0][rand:rand+3]+temp[1][rand+3:]#新子体temp2        result.append(temp_1)        result.append(temp_2)    return result#4.随机变异def variation(old_answer,numbers_set,pro):    for i in range(len(old_answer)):        rand = random.uniform(0,1)        if rand<pro:#如果该随机浮点数小于0.1，就发生变异            rand_num = random.randint(0,9)#从该解中随便挑出一个元素，发生变异            old_answer[i] = old_answer[i][:rand_num]+random.sample(numbers_set,1)+old_answer[i][rand_num+1:]    return old_answernumbers_set = random.sample(range(0,1000),50)#从0-1000随机抽取50个元素，创建初始nums数组middle_answer = create_answer(numbers_set,100)#创建包含100个解的随机初始解集，每个解都是随机的10个元素first_answer = middle_answer[0]#随便找个原始解great_answer = []#最优解集for i in range(1000):#训练1000次    middle_answer = choice_selected(middle_answer,numbers_set)#选择交叉完的middle    middle_answer = variation(middle_answer,numbers_set,0.1)#变异完的middle    error = error_level(middle_answer,numbers_set)#生成适应度列表    index = error.index(max(error))#挑出该群体中适应度最大的下标    great_answer.append([middle_answer[index],error[index]])great_answer.sort(key=lambda x:x[1],reverse=True)#从大到小排序print('正确答案为',sum(numbers_set)/10)print('原始解为',sum(first_answer))print('最优解为',great_answer[0][0])print('最优解的和为',sum(great_answer[0][0]))print('选择系数为',great_answer[0][1])

这里迭代了1000次，可以看到随机初始化得到的原始解与正确答案相差4869-2554.9，经过1000次迭代后，得到的最优解2555与正确答案只相差0.1。

正确答案为 2554.9原始解为 4869最优解为 [87, 451, 249, 249, 205, 258, 285, 0, 133, 638]最优解的和为 2555选择系数为 10.000000000009095

4 二元函数例子（python实现）

吾等菜鸡，皆需代码之实践
问题：求下列函数的最大值和最小值，定义域为 $x \in [- 3, 3], y \in [- 3, 3]$
$F(x,y)=3(1-x)^2*e^{(-(x^2)-(y+1)^2)}- 10(\frac{x}{5} - x^3 - y^5)e^{(-x^2-y^2)}- \frac{1}{3^{e^{(-(x+1)^2 - y^2)}}}$
这么复杂的函数…拿GA解最适合不过了，开干！
该函数图像如下：
在这里插入图片描述
很直观的可以看到，最大值是当x ≈ 0 , y ≈ 1.5 时，那个深红色的尖尖，最小值是当x ≈ 0.2 , y ≈ -1.7 时，蓝色的尖尖，这两个就是全局最优解。另外两个小山包是极大值，是局部最优解，我们的目的就是求得那两个全局最优解，避免陷在局部最优解里。

先计算最大值。首先生成200个随机的（x,y）对，将(x, y)坐标对带入要求解的函数F(x,y)中，根据适者生存，我们定义使得函数值F(x,y)越大的(x,y)对越适合环境，从而这些适应环境的(x,y)对被保留下来的概率越大，而那些不适应该环境的(x,y)则有很大概率被淘汰，保留下来的点经过繁殖产生新的点，如此进化下去最后留下的大部分点都是适应环境的点，即在最高点附近。

最小值的计算过程同上，区别在于函数值F(x,y)越小的(x,y)对越适合环境。

import numpy as npimport matplotlib.pyplot as pltfrom matplotlib import cmfrom mpl_toolkits.mplot3d import Axes3DDNA_SIZE = 24POP_SIZE = 200CROSSOVER_RATE = 0.8MUTATION_RATE = 0.005N_GENERATIONS = 50X_BOUND = [-3, 3]Y_BOUND = [-3, 3]def F(x, y):return 3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)def plot_3d(ax):X = np.linspace(*X_BOUND, 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()def get_fitness(pop):     x,y = translateDNA(pop)pred = F(x, y)return (pred - np.min(pred)) + 1e-3 #减去最小的适应度是为了防止适应度出现负数，通过这一步fitness的范围为[0, np.max(pred)-np.min(pred)],最后在加上一个很小的数防止出现为0的适应度def translateDNA(pop): #pop表示种群矩阵，一行表示一个二进制编码表示的DNA，矩阵的行数为种群数目x_pop = pop[:,1::2]#奇数列表示Xy_pop = pop[:,::2] #偶数列表示y#pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1)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]return x,ydef crossover_and_mutation(pop, CROSSOVER_RATE = 0.8):new_pop = []for father in pop:#遍历种群中的每一个个体，将该个体作为父亲child = father#孩子先得到父亲的全部基因（这里我把一串二进制串的那些0，1称为基因）if np.random.rand() < CROSSOVER_RATE:#产生子代时不是必然发生交叉，而是以一定的概率发生交叉mother = pop[np.random.randint(POP_SIZE)]#再种群中选择另一个个体，并将该个体作为母亲cross_points = np.random.randint(low=0, high=DNA_SIZE*2)#随机产生交叉的点child[cross_points:] = mother[cross_points:]#孩子得到位于交叉点后的母亲的基因mutation(child)#每个后代有一定的机率发生变异new_pop.append(child)return new_popdef mutation(child, MUTATION_RATE=0.003):if np.random.rand() < MUTATION_RATE: #以MUTATION_RATE的概率进行变异mutate_point = np.random.randint(0, 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()) )    return pop[idx]def print_info(pop):fitness = get_fitness(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]))if __name__ == "__main__":fig = plt.figure()ax = Axes3D(fig)plt.ion()#将画图模式改为交互模式，程序遇到plt.show不会暂停，而是继续执行plot_3d(ax)pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE*2)) #matrix (POP_SIZE, DNA_SIZE)for _ in range(N_GENERATIONS):#迭代N代x,y = translateDNA(pop)if 'sca' in locals(): sca.remove()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))#F_values = F(translateDNA(pop)[0], translateDNA(pop)[1])#x, y --> Z matrixfitness = get_fitness(pop)pop = select(pop, fitness) #选择生成新的种群print_info(pop)plt.ioff()plot_3d(ax)

算法的运行过程如下，可以看到随着迭代的进行，散落在各地的解渐渐向最高处聚集：
在这里插入图片描述

运行结果：

max_fitness: 0.10333042920383484最优的基因型： [1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1](x, y): (0.04820019294024647, 1.571304832178642)