[数据结构与算法]【人工智能】遗传算法

前言

本文参考书籍：《人工智能原理及其应用》第四版

?你好啊，我是“ 怪& ”，是一名在校大学生哦。
🌍主页链接：怪&的个人博客主页
??博文主更方向为：课程学习知识、作业题解、期末备考。随着专业的深入会越来越广哦…一起期待。
??一个“不想让我曾没有做好的也成为你的遗憾”的博主。
💪很高兴与你相遇，一起加油！

一、遗传算法

进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它以达尔文的“物竞天择，适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的繁殖、变异、竞争、选择引入到了算法中。

二、学术名词解释

1、生物学基础名词

（1）、基因型：遗传因子组合的模型。
（2）、表现型：由染色体决定形状的外部表现。
（3）、基因座：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因成为等位基因。
（4）、个体：指染色体带有特征的实体。
（5）、种群：个体的集合，该集合内个体数成为种群大小。

2、遗传算法术语

（1）、适应度：某个物种对于生存环境的适应程度。（适应度高着有更多的繁殖机会，适应度低者繁殖机会较少、甚至灭绝）
（2）、进化：生物在延续生存的过程中，逐渐适应生存环境，使得其品质不断得到改良。
（3）、编码：表现型到基因型的映射。
（4）、解码、从基因型到表现型的映射。
（5）、选择：以一定的概率从种群中选择若干个体的操作。
（6）、交叉：在两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。（基因重组、杂交）
（7）、变异：在细胞复制时小概率的复制出错，产生出新的染色体，随即表现新的性状。

遗传操作：指作用于种群而产生新的种群的操作。标准的遗传操作包括选择（或复制）、交叉（或重组）、变异三种基本形式。

三、基本结构与流程详解

四、程序结束

当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时(收敛于一值)，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。

五、遗传编码

常用：二进制编码、格雷编码、实数编码。

该用多大的编码来描述数据呢？以二进制为例。
假设定义域为[0,31]为整数，则可取到0、1、2……30、31共32个数，所以需要5位二进制数来表示。原因：2⁵=32恰巧等于定义域内取值个数32。
如果定义域内取值个数在16到32（不包括16但包括32）之间则仍取5位。因为2⁵=32，但2⁴=16，四位二进制数最多表示16个数。

六、适应度函数

常用：最大、最小、极大、所求式子本身。

适应度函数用于以数据来描述某个物种对于生存环境的适应程度。

七、遗传操作

1、选择操作

常用：比例选择-轮盘赌选择（按相对适应度比例划分轮盘，随机抽取）

2、交叉操作（二进制）

（1）、单点交叉：随机抽取一个点，对该点前面或后面的部分基因交换。

例如：
X=x₁ x₂ x₃ ……x_n
Y=y₁ y₂ y₃……y_n
随机点为k，则交叉结果为：
X=x₁ x₂……xk y_k+1 y_k+2 …… y_n
Y=y₁ y₂……yk x_k+1 y_k+3 …… x_n

（2）、两点交叉:随机抽取两个交叉点，后将两交叉点间的基因交换。

（3）、多点交叉：随机生成多个交叉点，按这些交叉点分段进行部分基因交换。
（4）、均匀交叉：随机生成与父串等长的二进制串，此串位置为0则双亲该位置基因不交换，若此串位置为1则双亲相应位置的基因交换。
（5）、实值交叉：选中部分进行交叉互换。（实数编码）

八、变异操作

（1）、二进制变异，选中位置取反。（0变1.1变0）
（2）、实值变异：用另外一个在规定范围内的随机实数去替换原变异位置上的基因值。

性质：变异概率极低，否则其不会收敛（接近最优解时，却发生变异至离散）。

九、案例

体验上述算法过程。



这时，函数的最大值已经出现，其对应染色体为11111，经解码后可知，问题的最优解是在点x=31处。

结束语

🍉🍉🍉忙碌的敲代码也不要忘了浪漫鸭！
🌟🌟🌟要学习、工作与生活兼得哦。