智能优化算法—遗传算法（GA）

人工智能与优化算法

遗传算法是 20世纪从60年代开始 , 密切根大学教授Holland开始研究自然和人工系统的自适应行为，在1975年出版的专著中阐述了遗传算法（GA）的理论和方法。获取源代关注公众号回复“GA”或“遗传算法”。

01算法理论基础

生物在其进化过程中，多以群体形式存在，遵循达尔文的“自然选择，适着生存”的法则。遗传和变异是决定生物进化的内在因素。其中，遗传能使生物的性状不断地传送给后代，因此保持了物种的特性：变异能够使生物的性状发生改变,从而适应新的环境而不断地向前发展。人们正是通过对环境选择、基因交叉和变异这一生物演化迭代过程的模仿，才提出了能够用于求解最优化问题的强鲁棒性和自适应性的遗传算法。生物遗传和进化的规律有:

生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状。染色体是由基因及其有规律的排列所构成的。

生物的繁殖过程是由其基因的复制过程来完成的。同源染色体的交叉或变异会产生新的物种，使生物呈现新的性状。

对环境适应能力强的基因或染色体,比适应能力差的基因或染色体有更多的机会遗传到下一代。

02 算法流程

遗传算法通过使用群体搜索技术,对当前群体施加选择、交叉、变异等一系列遗传操作,从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。

遗传编码

遗传算法不能直接处理问题空间的决策变量，必须转换或由基因按一定结构组成的染色体，所以就有了编码操作；反之将编码空间向问题空间的映射称为译码。如下图所示：

图1 编码和译码示图

种群初始化

种群初始化最常用的两种方法：一种是随机产生数值的方法，它适用于对问题的解无预知的情况;另一种则是根据一些经验知识求出最初需满足要求的解，接着在满足这些解中再随机地选取样本。

适应度函数

适应度函数是指用来评价个体的值,其适应度值越大的个体越符合算法要求，还会直接影响遗传算法的收敛速度以及能否找到全局最优解，因此适应度函数至关重要。

选择策略

     选择策略的原理是基于达尔文的自然选择学说，是将遗传搜索引导到搜索空间中有前途的区域。通常采用的选择方法有轮盘赌法、随机采样法和确定性选择法等。

交叉算子

交叉是指把两个父代个体的部分结构加以替换生成新个体的操作，这样可以提高搜索力。目前最常用的配对策略是随机配对，即将群体中的个体以随机方式两两配对，交叉操作是在配对个体之间进行的。

变异算子

变异就是将染色体编码串中的某些基因替换。它是遗传算法中不可缺少的部分，目的就是改善遗传算法的局部搜索能力，维持群体的多样性，防止出现早熟现象。

03 流程图及伪代码

遗传算法流程图，如图1所示：

图1 遗传算法流程图

遗传算法伪代码，如下：

04 参考文献

[1]Bremermann.H.J.. Optimization Through Evolution and Recombination.in Self-Organizing Systems,Yovits,M.C.,Jacobi.G.T.and Goldstine，G.D.. Eds.,Spartan Books.1962,93-106.

[2]Holland J H.Outline for a logical theory of adaptive systems[J].Journal of the ACM,1962,9(3):297-314.