数学建模十大算法之——遗传算法及Python实现

数维杯·赛事资讯·数模干货·辅助报名

文章结构如下：

1： 遗传算法理论的由来

2： 遗传算法定义

3： 遗传算法具体步骤

3.1 初始化（编码）

3.2 编码补充

3.3 适应度函数

3.3 选择

3.4 交叉

3.5 变异

4： 遗传算法应用

4.1 问题

4.2 创造染色体（编码）

4.3 个体、种群与进化

4.4 python实现

5： 参考文献

注：本文是根据参考文献几篇文章及个人理解整合而来

1：遗传算法理论的由来

我们先从查尔斯·达尔文的一句名言开始：

能够生存下来的往往不是最强大的物种，也不是最聪明的物种，而是最能适应环境的物种。

你也许在想：这句话和遗传算法有什么关系？其实遗传算法的整个概念就基于这句话。

让我们用一个基本例子来解释 ：

我们先假设一个情景，现在你是一国之王，为了让你的国家免于灾祸，你实施了一套法案：

• 你选出所有的好人，要求其通过生育来扩大国民数量。

• 这个过程持续进行了几代。

• 你将发现，你已经有了一整群的好人。

这个例子虽然不太可能，但是我用它是想帮助你理解概念。也就是说，我们改变了输入值（比如：人口），就可以获得更好的输出值（比如：更好的国家）。现在，我假定你已经对这个概念有了大致理解，认为遗传算法的含义应该和生物学有关系。那么我们就快速地看一些小概念，这样便可以将其联系起来理解。

2：遗传算法定义

首先我们回到前面讨论的那个例子，并总结一下我们做过的事情。

1. 首先，我们设定好了国民的初始人群大小。

2. 然后，我们定义了一个函数，用它来区分好人和坏人。

3. 再次，我们选择出好人，并让他们繁殖自己的后代。

4. 最后，这些后代们从原来的国民中替代了部分坏人，并不断重复这一过程。

遗传算法实际上就是这样工作的，也就是说，它基本上尽力地在某种程度上模拟进化的过程。

因此，为了形式化定义一个遗传算法，我们可以将它看作一个优化方法，它可以尝试找出某些输入，凭借这些输入我们便可以得到最佳的输出值或者是结果。遗传算法的工作方式也源自于生物学，具体流程见下图：

遗传算法的基本特征：

1. 智能式搜索：依据适应度（目标函数）进行只能搜索

2. 渐进式优化：利用复制、交换、突变等操作，使下一代结果优于上一代

3. 全局最优解：采用交换和突变操作产生新个体，使得搜索得到的优化结果逼近全局最优解

4. 黑箱式结构：根据问题的特性进行编码（输入）和确定适应度（输出），具有只考虑输入与输出关系的黑箱式就够，并不深究输入与输出关系的原因

5. 通用性强：不要求明确的数学表达式，只需要一些简单的原则要求，可应用于解决离散问题、函数关系不明确的复杂问题

6. 并行式运算：每次迭代计算都是对群体中所有个体同时进行运算，是并行式运算方式，搜索速度快

3：遗传算法具体步骤

为了让讲解更为简便，我们先来理解一下著名的组合优化问题「背包问题」。

比如，你准备要去野游 1 个月，但是你只能背一个限重 30 公斤的背包。现在你有不同的必需物品，它们每一个都有自己的「生存点数」（具体在下表中已给出）。因此，你的目标是在有限的背包重量下，最大化你的「生存点数」。

3.1 初始化（编码）

这里我们用遗传算法来解决这个背包问题。第一步是定义我们的总体。总体中包含了个体，每个个体都有一套自己的染色体。

我们知道，染色体可表达为二进制数串，在这个问题中，1 代表接下来位置的基因存在，0 意味着丢失。（译者注：作者这里借用染色体、基因来解决前面的背包问题，所以特定位置上的基因代表了上方背包问题表格中的物品，比如第一个位置上是 Sleeping Bag，那么此时反映在染色体的『基因』位置就是该染色体的第一个『基因』。）

现在，我们将图中的 4 条染色体看作我们的总体初始值。

3.2 编码补充

二进制编码

二进制编码由二进制符号0和1所组成的二值符号集。它有以下一些优点：1. 编码、解码操作简单易行 2. 交叉、变异等遗传操作便于实现 3. 合最小字符集编码原则 4. 利用模式定理对算法进行理论分析。

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

格雷码

格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。

二进制码转为格雷码：异或运算：同则为0，异则为1。公式如下：

由格雷码转二进制的转换公式为：

优点：增强遗传算法的局部搜索能力，便于对连续函数进行局部空间搜索。使用非常广泛。

浮点编码法

二进制编码虽然简单直观，但明显地。但是存在着连续函数离散化时的映射误差。个体长度较短时，可能达不到精度要求，而个体编码长度较长时，虽然能提高精度，但增加了解码的难度，使遗传算法的搜索空间急剧扩大。

所谓浮点法，是指个体的每个基因值用某一范围内的一个浮点数来表示。编码长度等于决策变量的个数。在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。

优点：

1. 适用于在遗传算法中表示范围较大的数

2. 适用于精度要求较高的遗传算法

3. 便于较大空间的遗传搜索

4. 改善了遗传算法的计算复杂性，提高了运算交率

5. 便于遗传算法与经典优化方法的混合使用

6. 便于设计针对问题的专门知识的知识型遗传算子

7. 便于处理复杂的决策变量约束条件

符号编码法

符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如｛A,B,C…｝。

优点：

1. 符合有意义积术块编码原则

2. 便于在遗传算法中利用所求解问题的专门知识

3. 便于遗传算法与相关近似算法之间的混合使用。

3.3 适应度函数

接下来，让我们来计算一下前两条染色体的适应度分数。对于 A1 染色体 [100110] 而言，有：

类似地，对于 A2 染色体 [001110] 来说，有：

对于这个问题，我们认为，当染色体包含更多生存分数时，也就意味着它的适应性更强。因此，由图可知，染色体 1 适应性强于染色体 2。

3.4 选择

现在，我们可以开始从总体中选择适合的染色体，来让它们互相『交配』，产生自己的下一代了。这个是进行选择操作的大致想法，但是这样将会导致染色体在几代之后相互差异减小，失去了多样性。因此，我们一般会进行「轮盘赌选择法」（Roulette Wheel Selection method）。

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

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

现在，这个轮盘开始旋转，我们将被图中固定的指针（fixed point）指到的那片区域选为第一个亲本。然后，对于第二个亲本，我们进行同样的操作。有时候我们也会在途中标注两个固定指针，如下图：

通过这种方法，我们可以在一轮中就获得两个亲本。我们将这种方法成为「随机普遍选择法」（Stochastic Universal Selection method）。

3.5 交叉

在上一个步骤中，我们已经选择出了可以产生后代的亲本染色体。那么用生物学的话说，所谓「交叉」，其实就是指的繁殖。现在我们来对染色体 1 和 4（在上一个步骤中选出来的）进行「交叉」，见下图：

这是交叉最基本的形式，我们称其为「单点交叉」。这里我们随机选择一个交叉点，然后，将交叉点前后的染色体部分进行染色体间的交叉对调，于是就产生了新的后代。

如果你设置两个交叉点，那么这种方法被成为「多点交叉」，见下图：

3.5 变异

如果现在我们从生物学的角度来看这个问题，那么请问：由上述过程产生的后代是否有和其父母一样的性状呢？答案是否。在后代的生长过程中，它们体内的基因会发生一些变化，使得它们与父母不同。这个过程我们称为「变异」，它可以被定义为染色体上发生的随机变化，正是因为变异，种群中才会存在多样性。

下图为变异的一个简单示例：

变异完成之后，我们就得到了新为个体，进化也就完成了，整个过程如下图：

在进行完一轮「遗传变异」之后，我们用适应度函数对这些新的后代进行验证，如果函数判定它们适应度足够，那么就会用它们从总体中替代掉那些适应度不够的染色体。这里有个问题，我们最终应该以什么标准来判断后代达到了最佳适应度水平呢？

一般来说，有如下几个终止条件：1. 在进行 X 次迭代之后，总体没有什么太大改变。2. 我们事先为算法定义好了进化的次数。3. 当我们的适应度函数已经达到了预先定义的值。

4：遗传算法应用

这节将讲述如何利用遗传算法解决一个二元函数的最大值求解问题。

4.1 问题

二元函数如下：

# 画出图像如下frommpl_toolkits.mplot3dimportAxes3Dimportnumpyasnpfrommatplotlibimportpyplotaspltfigpltfigure(figsize(10,6))axAxes3D(fig)xnparange(10, 10, 0.1)ynparange(10, 10, 0.1)X, Ynpmeshgrid(x, y) Z0.5(npsin(npsqrt(X2Y2))20.5)(12y2)2)pltxlabel('x')pltylabel('y')axset_zlim([1,5])axplot_surface(X, Y, Z, rstride1, cstride1, cmap'rainbow')pltshow()

我们任务是找到

范围之内的最大值。

4.2 创造染色体（编码）

我们尝试为上文所述的函数f(x,y)的最大值所对应的 x 和 y 的值构造染色体。也就是说，要在一组二进制位中存储函数 f(x,y) 的定义域中的数值信息。

假如设定求解的精度为小数点后6位，可以将区间[-10,10]划分为

个子区间。若用一组二进制位形式的染色体来表示这个数值集合，

，需要25位二进制数来表示这些解。换句话说，一个解的编码就是一个25位的二进制串。

现在，我们已经创建了一种 25 位长度的二进制位类型的染色体，那么对于任意一个这样的染色体，我们如何将其复原为[-10, 10]这个区间中的数值呢？这个很简单，只需要使用下面的公式即可：

例如 0000 0000 0000 0000 0000 0000 0000 0 和 1111 1111 1111 1111 1111 1111 1 这两个二进制数，将其化为 10 进制数，代入上式，可得 -10.0 和 10.0。这意味着长度为 25 位的二进制数总是可以通过上式转化为[-10, 10]区间中的数。

4.3 个体、种群与进化

染色体表达了某种特征，这种特征的载体，可以称为“个体”。例如，我本人就是一个“个体”，我身上载有 23 对染色体，也许我的相貌、性别、性格等因素主要取决于它们。众多个体便构成“种群”。

对于所要解决的二元函数最大值求解问题，个体可采用上一节所构造的染色体表示，并且数量为2个，其含义可理解为函数f(x, y)定义域内的一个点的坐标。许多这样的个体便构成了一个种群，其含义为一个二维点集，包含于对角定点为(-10.0, -10.0)和(10.0, 10.0)的正方形区域。

也许有这样一个种群，它所包含的个体对应的函数值会比其他个体更接近于函数f(x, y)的理论最大值，但是它一开始的时候可能并不比其他个体优秀，它之所以优秀是因为它选择了不断的进化，每一次的进化都要尽量保留种群中的优秀个体，淘汰掉不理想的个体，并且在优秀个体之间进行染色体交叉，有些个体还可能出现变异。种群的每一次进化后，必定会产生一个最优秀的个体。种群所有世代中的那个最优个体也许就是函数f(x, y)的最大值对应的定义域中的点。如果种群不休止的进化，它总是能够找到最好的解。但是，由于我们的时间是有限的，有可能等不及种群的最优进化结果，通常是在得到了一个看上去还不错的解时，便终止了种群的进化。

那么，对于一个给定的种群，通常上述讲过的选择、交叉、变异来进行进化。

4.4 python实现

importmathrandomclassPopulation
# 种群的设计
def__init__(self, size, chrom_size, cp, mp, gen_max):
# 种群信息合
selfindividuals[] # 个体集合
selffitness[] # 个体适应度集
selfselector_probability[] # 个体选择概率集合
selfnew_individuals[] # 新一代个体集合

self.elitist={'chromosome':[0, 0], 'fitness':0, 'age':0} # 最佳个体的信息

self.size=size # 种群所包含的个体数
self.chromosome_size=chrom_size # 个体的染色体长度
self.crossover_probability=cp # 个体之间的交叉概率
self.mutation_probability=mp # 个体之间的变异概率

self.generation_max=gen_max # 种群进化的最大世代数
self.age=0 # 种群当前所处世代

# 随机产生初始个体集，并将新一代个体、适应度、选择概率等集合以 0 值进行初始化
v=2**self.chromosome_size-1
foriinrange(self.size):
self.individuals.append([random.randint(0, v), random.randint(0, v)])
self.new_individuals.append([0, 0])
self.fitness.append(0)
self.selector_probability.append(0)

# 基于轮盘赌博机的选择
defdecode(self, interval, chromosome):
'''将一个染色体 chromosome 映射为区间 interval 之内的数值'''
d=interval[1]-interval[0]
n=float (2**self.chromosome_size-1)
return(interval[0]+chromosome*d/n)

deffitness_func(self, chrom1, chrom2):
'''适应度函数，可以根据个体的两个染色体计算出该个体的适应度'''
interval=[-10.0, 10.0]
(x, y)=(self.decode(interval, chrom1),
self.decode(interval, chrom2))
n=lambdax, y: math.sin(math.sqrt(x*x+y*y))**2-0.5
d=lambdax, y: (1+0.001*(x*x+y*y))**2
func=lambdax, y: 0.5-n(x, y)/d(x, y)
returnfunc(x, y)

defevaluate(self):
'''用于评估种群中的个体集合 self.individuals 中各个个体的适应度'''
sp=self.selector_probability
foriinrange (self.size):
self.fitness[i]=self.fitness_func (self.individuals[i][0], # 将计算结果保存在 self.fitness 列表中
self.individuals[i][1])
ft_sum=sum (self.fitness)
foriinrange (self.size):
sp[i]=self.fitness[i]/float (ft_sum) # 得到各个个体的生存概率
foriinrange (1, self.size):
sp[i]=sp[i]+sp[i-1] # 需要将个体的生存概率进行叠加，从而计算出各个个体的选择概率

# 轮盘赌博机（选择）
defselect(self):
(t, i)=(random.random(), 0)
forpinself.selector_probability:
ifp>t:
break
i=i+1
returni

# 交叉
defcross(self, chrom1, chrom2):
p=random.random() # 随机概率
n=2**self.chromosome_size-1
ifchrom1!=chrom2andp<self.crossover_probability:
t=random.randint(1, self.chromosome_size-1) # 随机选择一点（单点交叉）
mask=n<<t # << 左移运算符
(r1, r2)=(chrom1&mask, chrom2&mask) # & 按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0
mask=n>>(self.chromosome_size-t)
(l1, l2)=(chrom1&mask, chrom2&mask)
(chrom1, chrom2)=(r1+l2, r2+l1)
return(chrom1, chrom2)

# 变异
defmutate(self, chrom):
p=random.random ()
ifp<self.mutation_probability:
t=random.randint (1, self.chromosome_size)
mask1=1<<(t-1)
mask2=chrom&mask1
ifmask2>0:
chrom=chrom&(~mask2) # ~ 按位取反运算符：对数据的每个二进制位取反,即把1变为0,把0变为1
else:
chrom=chrom^mask1 # ^ 按位异或运算符：当两对应的二进位相异时，结果为1
returnchrom

# 保留最佳个体
defreproduct_elitist(self):
# 与当前种群进行适应度比较，更新最佳个体
j=-1
foriinrange (self.size):
ifself.elitist['fitness']<self.fitness[i]:
j=i
self.elitist['fitness']=self.fitness[i]
if(j>=0):
self.elitist['chromosome'][0]=self.individuals[j][0]
self.elitist['chromosome'][1]=self.individuals[j][1]
self.elitist['age']=self.age

# 进化过程
defevolve(self):
indvs=self.individuals
new_indvs=self.new_individuals
# 计算适应度及选择概率
self.evaluate()
# 进化操作
i=0
whileTrue:
# 选择两个个体，进行交叉与变异，产生新的种群
idv1=self.select()
idv2=self.select()
# 交叉
(idv1_x, idv1_y)=(indvs[idv1][0], indvs[idv1][1])
(idv2_x, idv2_y)=(indvs[idv2][0], indvs[idv2][1])
(idv1_x, idv2_x)=self.cross(idv1_x, idv2_x)
(idv1_y, idv2_y)=self.cross(idv1_y, idv2_y)
# 变异
(idv1_x, idv1_y)=(self.mutate(idv1_x), self.mutate(idv1_y))
(idv2_x, idv2_y)=(self.mutate(idv2_x), self.mutate(idv2_y))
(new_indvs[i][0], new_indvs[i][1])=(idv1_x, idv1_y) # 将计算结果保存于新的个体集合self.new_individuals中
(new_indvs[i+1][0], new_indvs[i+1][1])=(idv2_x, idv2_y)
# 判断进化过程是否结束
i=i+2 # 循环self.size/2次，每次从self.individuals 中选出2个
ifi>=self.size:
break

# 最佳个体保留
# 如果在选择之前保留当前最佳个体，最终能收敛到全局最优解。
self.reproduct_elitist()

# 更新换代：用种群进化生成的新个体集合 self.new_individuals 替换当前个体集合
foriinrange (self.size):
self.individuals[i][0]=self.new_individuals[i][0]
self.individuals[i][1]=self.new_individuals[i][1]

defrun(self):
'''根据种群最大进化世代数设定了一个循环。在循环过程中，调用 evolve 函数进行种群进化计算，并输出种群的每一代的个体适应度最大值、平均值和最小值。'''
foriinrange (self.generation_max):
self.evolve ()
print(i, max (self.fitness), sum (self.fitness)/self.size, min (self.fitness))if__name__=='__main__':
# 种群的个体数量为 50，染色体长度为 25，交叉概率为 0.8，变异概率为 0.1,进化最大世代数为 150
pop=Population (50, 24, 0.8, 0.1, 150)
pop.run()5：参考文献

一文读懂遗传算法工作原理（附Python实现）

# emerge -e world

【算法】超详细的遗传算法(Genetic Algorithm)解析

本文来源：知乎整理

2022第七届数维杯夏令营报名火热进行中，本届夏令营限报200人，专家授课，零基础教学，参培人员获奖率高达80％，点击下方图片了解详情！

温馨提示：小编每天都在为大家用心甄选优质数模内容，更多数模干货已分类收录于往期合集【国赛、美赛】【数维杯】【常用软件】【算法模型】【经验分享】等，同学们于公众号内自行搜索即可，更多数模相关服务请移步【数模乐园官方旗舰店】了解详情,笔芯~

进入数模乐园官方旗舰店

看似寻常最奇崛，成如容易却艰辛。

王安石《题张司业诗》