一文让零基础的你轻松理解遗传算法

2021-01-28 09:37

遗传算法

概述

遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出，该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式，利用计算机仿真运算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时，相对一些常规的优化算法，通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

大致了解

遗传算法属于启发式算法的一种，大家理解启发式算法的时候可以将其与枚举法类比。举个简单的例子，我们在求解某一函数f（x）的最大值时，通常的方法是通过求导，找到极值点。但是大家一定还知道另外一种最笨的办法，就是枚举法。假设x的可行域在［0，1］之间，x最大值的精确度是0．01，那就可以把［0，1］之间所有的可行解（0．01， 0．02， 0．03，．．． 0．98， 0．99， 1．00）都拿出来代入f（x），计算比较它们的大小，找到最大值对应的x＇即为最优解，f（x＇）为最大值。但是这种方法的求解效率太低了，为了解决这一问题，各路大神就根据各种学科的不同原理，比如生物界的遗传、鱼群、蚁群、冶金学的退火等，将这些理论应用在求解中，以提高求解效率。同样是不断地尝试找到最优解，利用这些原理可以让尝试的过程没那么盲目，而是按照一定的规律去寻找最优解，可以有效地提高求解效率，让我们更快地寻找到f（x）的最优解。

总之，为了更容易理解遗传算法，大家首先可以有一个大致的思维：遗传算法是枚举法的升级版本。

简单算例

问题：求解函数 f（x）＝ x ＋ 10＊sin（5＊x）＋ 7＊cos（4＊x）在区间［0，9］的最大值。

p．s． f（x）函数大致图像如上图

流程：??????????????遗传算法（Genetic Algorithm）遵循『适者生存』、『优胜劣汰』的原则，是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法模拟一个人工种群的进化过程，通过选择（Selection）、交叉（Crossover）以及变异（Mutation）等机制，在每次迭代中都保留一组候选个体，重复此过程，种群经过若干代进化后，理想情况下其适应度达到＊＊＊近似最优＊＊＊的状态。