遗传算法的基本原理是什么？

本文为学习笔记，内容来自文献2.1节：张丽. 基于多目标优化算法的柔性作业车间调度问题研究[D]. 山东:山东农业大学,2019.

1.遗传算法简述

遗传算法（GA）是一种借助生物遗传学思想，模拟自然界优胜劣汰、适者生存的寻优算法。通常用于解决NP-hard问题，在作业车间调度问题中应用较多。（其他具体可参考百度百科）

图源参考文献2.遗传操作编码和解码编码：将求解问题的解空间映射到编码空间的过程。编码对遗传算子的运算方法有重要影响。解码：将染色体复原为实际问题解的过程。如在求解FJSP（柔性作业车间调度）问题时，将染色体还原为实际问题中某道工序在某台机器上的过程即解码。种群初始化：初始化的目的时保证算法寻优的效率和质量，使解空间中的种群尽量均匀分布。常用的初始化有：随机初始化，用某种启发式算法初始化。适应度函数评价：淘汰适应度值低的个体，保留适应度值高的个体。在工程问题中，一般采用时间或成本作为适应度函数。交叉：交叉的目的是为了产生新的解，最简单的交叉为单点交叉，如下图所示。

图源参考文献

5.变异：变异通过改变父代染色体中的部分基因，形成新的子代，使种群的进化朝着更广的方向进行。下图为一条染色体的第四个基因进行了取反变异。

取反变异，图源参考文献

6.选择：选择是将适应度高的个体以较高的概率遗传给下一代，适应度低的个体以较大的概率淘汰。常见的选择方法有轮盘赌、锦标赛。下图为锦标赛法选择思想：

图源参考文献3.参数设置种群数量N：种群数量对算法最终的优化目标和效率都有影响。种群太小，会由于不能提供足

够的样点而导致算法的性能很差；种群太大，降低算法的收敛速度，算法难度增加。一般设置大小为 100 ~ 200。

2.交叉概率 p^{c} :交叉概率用于控制交叉操作的频率。交叉概率过大会使种群适应度高的个体不被选择，交叉概率太小也不容易得到更优的个体。一般设置交叉概率大小为0.6~0.95。

3.变异概率 p^{m}

变异为新个体的产生提供了机会。变异概率太大会成为随机搜索基于遗传算法的随机优化搜索，太小会降低全局搜索能力。一般设置大小为0.001~0.2。

4.遗传算法的优缺点

遗传算法的特点：

遗传算法主要包括如下特点（陈旭忠，2015；胡鑫楠，2016）：

遗传算法不是对参数本身进行操作，而是对问题的编码进行操作； 遗传算法并不是从单个解进行搜寻，而是从问题的一组解开始的，这一组解中会出现某些远远优于其它个体的个体，在选择过程中一直处于较优状态，易出现局部最优现象； 在概率的指导下，遗传算法完成了对问题的解空间搜索过程，初始化操作使得解均匀分布在整个解空间中，选择、交叉、变异等操作使种群朝着多样性的方向发展，保留适应度高的个体。优点：具有快速随机的搜索能力。变异操作为新个体的产生创造了更多条件，使种群多样性增加，进化方向增多，搜索空间变大； 使用具有随机性的概率机制，采用交叉概率、变异概率等指导种群朝着正确方向进行； 遗传算容易与其它算法结合。通过与粒子群算法融合可以防止遗传算法早期出现局部最优的问题，通过与禁忌搜索算法融合可以提高收敛速度和局部搜索能力，由此可以看出遗传算法具有较强的通用性，可以根据不同需要与其它算法进行融合，实现更好的优化效果。缺点：

遗传算法存在如下缺点：

遗传算法的编码和初始化操作很重要，也使编码难度增大，在求解某个问题时，需要对该问题进行编码，编码方式的选择表示了该问题能否可解，找到最优解后还需要对问题进行解码； 遗传操作的实现需要设置诸多参数，如交叉率和变异率等参数对解的质量具有重要影响，但这些参数的设置大多是人为设置，例如，交叉概率会影响种群的稳定性，若设置不合理，有可能使得问题的最优解并不符合实际的需要，变异概率会影响种群的多样性，若设置不合理，会影响种群的进化速度； 算法的搜寻速度比较慢，需要较多的时间才能得到最优解集； 容易出现“早熟”现象，易在早期出现局部最优现象，特别是当算法的参数设置不合理时，在种群中会出现适应度值远远大于种群的平均个体适应度，使该个体保持了绝对的优势，种群的多样性缺失，算法停滞不前。

遗传算法自提出以来应用较为广泛，如：旅行商问题、柔性作业车间调度问题。此外，遗传算法和其它算法的融合优化算法在求解组合优化等问题时效果较好。然而，如何快速得到最优解且不会尽早陷入局部最优，如何保留优良个体以找到问题求解的最优解，如何维持群体的多样性等问题，一直是遗传算法中较难解决的问题。

（编辑：成都站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!