人工智能之遗传算法(GA)

人工智能之遗传算法(GA)

原创   张志荣

今天我们重点探讨一下遗传算法（GA）。 ^_^

人们一提到遗传算法（GA），就会联想到达尔文的生物进化论。遗传算法（GA）是一类借鉴生物界的进化规律演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出。目前，遗传算法（GA）已成为进化计算研究的一个重要分支。 

概念和定义：

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

遗传算法（GA）是从代表问题可能潜在的解集的一个种群（population）开始，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。

由于仿照基因编码的工作很复杂，往往进行简化，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解。

框架与术语：

1）编码—把问题空间的参数转换成遗传空间的由基因按一定结构组成的染色体或个体的操作过程。目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等，最常用的是二进制编码。评估编码策略有3个规范：a)完备性(completeness)；b)健全性(soundness)；c)非冗余性(nonredundancy)。

2）适应度函数—表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。适应度函数设计直接影响到遗传算法的性能，因此适应度函数的设计需要满足以下条件：a）单值、连续、非负、最大化；b) 合理、一致性；c）计算量小；d）通用性强。

3）初始群体选取—初始群体中的个体是随机产生的。初始群体的设定可采取如下策略:a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。

4）染色体—又叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。

5）基因—串中的元素，基因用于表示个体的特征。

6）基因位置—简称基因位，在算法中表示一个基因在串中的位置称为基因位置(Gene Position)。

7）特征值—在用串表示整数时，基因的特征值与二进制数的权一致。

8）选择—从群体中选择优胜的个体，淘汰劣质个体的操作。选择算子有时又称为再生算子(reproduction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。目前常用的选择算子有：适应度比例方法、随机遍历抽样法、局部选择法、锦标赛选择和轮盘赌选择法（最简单、最常用）等。

9）交叉—把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的是遗传操作的交叉算子。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。通过交叉，遗传算法的搜索能力得以飞跃提高。最常用的交叉算子为单点交叉(one-point crossover)。

10）变异—变异算子是对群体中的个体串的某些基因座上的基因值作变动。利用变异算子的局部随机搜索能力可以加速向最优解收敛；利用变异算子可维持群体多样性，防止出现未成熟收敛现象。依据个体编码表示方法的不同，可以有：a)实值变异；b)二进制变异。变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值。

11）终止条件—当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。

遗传操作进行的是高效有向的搜索。遗传操作包括3个基本遗传算子(genetic operator):选择(selection)；交叉(crossover)；变异(mutation)。遗传操作的效果和3个遗传算子所取的操作概率、编码方法、群体大小、初始群体以及适应度函数的设定密切相关。3个基本遗传算子的作用：a)选择的作用：优胜劣汰，适者生存；b)交叉的作用：保证种群的稳定性，朝着最优解的方向进化；c)变异的作用：保证种群的多样性，避免交叉可能产生的局部收敛。

遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。

运算过程：

1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

2）个体评价：计算群体P(t)中各个个体的适应度。

3）选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

4）交叉运算：将交叉算子作用于群体。遗传算法中交叉算子起核心作用。

5）变异运算：将变异算子作用于群体。对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

6）终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

可把遗传算法的运算过程看作是一个在多元函数里面求最优解的过程。如下图所示，这个多维曲面里面有数不清的“山峰”，而这些“山峰”所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。

算法优点：

1）遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。遗传算法从串集开始搜索，覆盖面大，利于全局择优。

2）遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。

3）遗传算法不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。

4）遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。

5）具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。

6）算法本身也可以采用动态自适应技术，在进化过程中自动调整算法控制参数和编码精度，比如使用模糊自适应法。

简而言之，主要优点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。同时也缩短了整个搜寻额时间，整体上效率更高、结果更接近最优解。实现简单，没有复杂的数学计算。

算法缺点：

1）遗传算法编码和解码比较复杂，在进化前需要做复杂的编码工作，而在得到最优解后还要做复杂的解码工作，比较繁琐和复杂；

2）编码不规范及编码存在表示的不准确性，在遗传操作过程中，遗传算法编、解码不易掌控，容易出错；

3）遗传算法对初始种群的选择有一定的依赖性；

4）遗传算法通常的效率比其他传统的优化方法低；

5）遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优；也容易过早收敛；

6）遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。

研究动向与应用前景：

遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：

1）基于遗传算法的机器学习，这是把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。

2）遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。

3）并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。

4）遗传算法和人工生命的崭新研究领域正不断渗透。

5）遗传算法和进化规划（EP）以及进化策略（ES）等进化计算理论日益结合。这三者之间的比较研究和彼此结合的探讨正形成热点。

由于遗传算法的整体搜索策略和优化搜索方法在计算时不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，适用于非常复杂和困难的环境。所以广泛应用于许多科学和领域。

目前，遗传算法已被人们广泛地应用于生产调度、组合优化、通信网络设计、机器学习、机器人学、图象处理与模式识别、运动估计、信号处理、遗传编码、自适应控制和人工生命等领域。遗传算法也是人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。

结语:

遗传算法模拟生物繁殖的突变、交换和达尔文的自然选择（适者生存）。它把问题可能的解编码为一个向量（个体），向量的每一个元素称为基因，并利用目标函数（选择标准）对群体（个体集合）中的每一个个体进行评价，根据评价值（适应度）对个体进行选择、交换、变异等遗传操作，从而得到新的群体。遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，适用于非常复杂和困难的环境。所以广泛应用于许多科学和领域。遗传算法特别在人工智能领域有突出表现，对推动人工智能发展具有重要意义！

---------------------------------------------------------------

更多有关AI/ML文章，敬请关注“科技优化生活”微信公众号，谢谢！