智能算法之遗传算法

不念不忘少年蓝@ 2023-10-05 16:19 25阅读 0赞

### 目录 ###

*  
 *   *  
     *   *  
     *  1.定义
     *  2.基本步骤
     *  3.算法过程图解
     *  4 .大体实现过程

#  #

##  ##

###  ###

## 1.定义 ##

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

## 2.基本步骤 ##

**编码**

GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。

**初始群体的生成**  
随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始进化。

**适应度评估**  
适应度表明个体或解的优劣性。不同的问题，适应度函数的定义方式也不同。

**选择**  
选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应度强的个体为下一代贡献一个或多个后代的概率大。选择体现了达尔文的适者生存原则。

**交叉**  
交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。

**变异**  
变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的的值。同生物界一样，GA中变异发生的概率很低，通常取值很小。

## 3.算法过程图解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ExMzY4MDg5MzIz_size_16_color_FFFFFF_t_70_pic_center]

## 4 .大体实现过程 ##

遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。遗传算法的实现过程实际上就像自然界的进化过程那样。

下面我们用袋鼠跳中的步骤一一对应解释，以方便大家理解：

1.  首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系）
2.  随机初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上），种群里面的个体就是这些数字化的编码。
3.  接下来，通过适当的解码过程之后（得到袋鼠的位置坐标）。
4.  用适应性函数对每一个基因个体作一次适应度评估（袋鼠爬得越高当然就越好，所以适应度相应越高）。
5.  用选择函数按照某种规定择优选择（每隔一段时间，射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平。）。
6.  让个体基因变异（让袋鼠随机地跳一跳）。
7.  然后产生子代（希望存活下来的袋鼠是多产的，并在那里生儿育女）。

遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！）

由此我们可以得出遗传算法的一般步骤：

1.  随机产生种群。
2.  根据策略判断个体的适应度，是否符合优化准则，若符合，输出最佳个体及其最优解，结束。否则，进行下一步。
3.  依据适应度选择父母，适应度高的个体被选中的概率高，适应度低的个体被淘汰。
4.  用父母的染色体按照一定的方法进行交叉，生成子代。
5.  对子代染色体进行变异。

**由交叉和变异产生新一代种群，返回步骤2，直到最优解产生。**

参考链接： https://www.cnblogs.com/dengfaheng/p/9245623.html https://www.jianshu.com/p/9c1d5eaf1c0c

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ExMzY4MDg5MzIz_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201222234345897.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ExMzY4MDg5MzIz,size_16,color_FFFFFF,t_70#pic_center