您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识

什么是遗传算法，它有哪些实际应用？

算法,山峰,最优什么是遗传算法，它有哪些实际应用？

发布时间：2020-12-06加入收藏来源：互联网点击：

什么是遗传算法，它有哪些实际应用？

回答于 2019-09-11 08:43:50

回答于 2019-09-11 08:43:50

1简介

遗传算法（Genetic Algorithm, GA）来源于进化论和群体遗传学，由美国的 Holland 教授于 1975 年在他的专著《自然界和人工系统的适应性》[1]中首先提出。遗传算法作为一种非确定性的拟自然算法，为复杂系统的优化提供了一种新思路，对于诸多NP-Hard问题，遗传算法都有不错的表现。相对于传统算法而言，遗传算法有四大突出优点[2]：

1.遗传算法不需要描述问题的全部特点，不需要描述全部需要处理的情况。

2.遗传算法仅需要对参数编码集进行处理，无需针对问题本身进行约束。

3.相对于传统算法对模型线性、连续、可导的限制，遗传算法不存在这些限制条件。

4.快速求解。

遗传算法的相对不足：

1. 遗传算法的本质是随机搜索，不能保证所得解为全局最优解（参数足够大的情况下是可以求出全局最优解，但失去了算法本身的意义）。




2算法的发展与重心

经过多年的发展，遗传算法的研究热点及发展方向可以由图1进行展示[3]：

图1 遗传算法研究进展

遗传算法的搜索核心是遗传算子的选择，因此对于遗传算法的研究，其中最常见的内容与方向是遗传算子，遗传算子的选择多样性也导致了算法表现的多样性，常见的选择方式如图2所示：

图2 遗传算子的研究

遗传算法作为一种搜索算法，在诸多领域均有很好的表现[4]，如函数优化、组合优化、生产调度、自动控制、机器学习、图像处理、人工生命、遗传编程、机器学习、数据挖掘等。

3实例说明

为了更通俗地理解遗传算法，下面将通过一些实例进行描述：

如果想在一座连绵的大山上找到其最高点，正常情况下你需要爬遍整座山才可以找到最高峰，但大多数的智能算法并不需要搜索整个山峰，不同的智能算法有不同的求解思路，举几个简单例子：

1. 爬山算法（也称为贪心算法）。假设有一只猴子从山的任意一点出发，当它爬到第一个高峰值点的时候便停止前进，并认为当前的山峰为整座山最高的点。这种情况下，运气好可能会到达最高点，但是大概率情况下都不会是最高点。

2. 模拟退火算法。假设有一只神志不清的猴子，当它爬到山峰的时候，它有一定的概率继续出发，也有概率停止前进。这种情况下它也有可能通过有限的时间找到整座山的最高点。

3. 遗传算法。假设山上有一群猴子，猴子生存的食物只有在山峰处才有，而且山峰越高食物量越充裕。那么这些猴子为了生存，会不断聚集在各个山头上，而这些山峰可以理解为各种局部最优解（图3中类似绿色和蓝色的地方），如果种群规模足够大，势必会有一群猴子聚集在了整座山的最高点，也就是全局最优解（图3中红色位置）。

图3 山体示意图

基于以上三种算法的描述，我们可以对智能算法有一个简单的了解：无论是哪种算法，都具有一定的随机性，都不能保证最终选择的山峰为整座山的最高点。但是在实际生活中，有诸多类似的问题，如果要考虑所有的情况可能会花费大量的时间，而恰巧我们并不需要一个最好的结果，我们只需要快速找到一个相对较好的结果便可以满足要求的时候，智能算法的意义便得到了体现。

智能算法的核心：牺牲精度，保证效率。

通俗了解后，虽然心里有大概思路，但还是云里雾里，这个时候我们可以考虑结合一些实际的例子来理解遗传算法。

结语

虽然遗传算法有着一定的弊端和不足，但是遗传算法在诸多领域(特别是运筹学)还是有着很不错的表现并已经运用到实际生活中。为了不断适应各种问题，近年来不断有学者提出改进策略，以使遗传算法有更广泛的应用领域。

拓展阅读:

https://zhuanlan.zhihu.com/p/36212065

https://zhuanlan.zhihu.com/p/30140008

https://zhuanlan.zhihu.com/p/25579864

参考文献

[1] HOLLAND J H． Adaptation in natural and artificial systems: an introductory analysis with applications to biology，control，and artificial intelligence［M］．2nd ed．Cambridge: MIT Press，1992．

[2]葛继科,邱玉辉,吴春明,蒲国林.遗传算法研究综述[J].计算机应用研究,2008(10):2911-2916.

[3]马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(04):1201-1206+1210.

[4]吉根林.遗传算法研究综述[J].计算机应用与软件,2004(02):69-73.

[5] Nix A E , Vose M D . Modeling genetic algorithms with Markov chains[J]. Annals of Mathematics & Artificial Intelligence, 1992, 5(1):79-88.

回答于 2019-09-11 08:43:50

我们可以通过自然界的遗传原理来理解遗传算法。

简单来说，遗传算法是一种随机搜索算法，主要目的是用来优化。和自然界的遗传一样，遗传算法秉持的是适者生存、优胜劣汰的原则。通过选择、交叉和变异，不断迭代出更优秀的解法。

通过编码，将解空间变成编码空间，从中选择当前较为优秀的解当作“父母”，下一步则是将多种解的特征进行交叉，诞生下一代，最后经过变异成为“子嗣”。如果“子嗣”还是不能符合要求，那就再进行一次上述步骤，直到满足要求。过程中，较差的基因就会一步步被淘汰。总之，这是一个枚举的过程。就像长颈鹿的进化一样，树叶长在高处，每一只鹿都去尝试吃树叶，只有符合“标准”的长颈鹿能够吃到食物、生存下来并诞生后代。

但要注意的是，这种算法很多时候不会给出一个“最优解”，而是给出一些较为接近的次优解，从矮子里面拔将军。

有一款非常有趣的小游戏——Boxcar 2D，可以帮你理解遗传算法：

这款游戏的主要内容是用几何图形和圆形的轮子组成小汽车，不断走过一条有上下波动的“路”，看什么形状的小车可以走得更远。但和大部分游戏不一样的是，不用玩家自己手动拼装小车，整个过程完全由算法自动进行，每次随机生成小车，卡到路上了就重新来过。最后小车会越走越远，整个过程中小车的形状会越来越合适，一开始可能只是个“独轮车”，到后期则会很接近我们生活中摩托车的样子。

动图来源：BoxCar 2D官网




还可以通过实际场景中的应用来理解遗传算法的特点：

 1/2    1 2 下一页 尾页