遗传算法的基本代码介绍
什么是遗传算法,它有哪些实际应用?
什么是遗传算法,它有哪些实际应用?
1简介
遗传算法(Genetic Algorithm, GA)来自美国的进化论和群体遗传学 Holland 教授于 1975 首先在他的专著《自然与人工系统的适应性》[1]中提出。遗传算法作为一种不确定的自然算法,为优化复杂系统提供了新的思路,对许多系统提供了新的思路NP-Hard问题,遗传算法表现良好。与传统算法相比,遗传算法具有四大突出优势[2]:
1.遗传算法不需要描述问题的所有特征,也不需要描述所有需要处理的情况。
2.遗传算法只需要处理参数编码集,不需要限制问题本身。
3.与传统算法对模型线性、连续、可导的限制相比,遗传算法没有这些限制。
4.快速求解。
相对不足的遗传算法:
1. 基因算法的本质是随机搜索,不能保证获得的解为全局最优解(当参数足够大时,可以找到全局最优解,但算法本身的意义已经丧失)。
算法的发展与重心
经过多年的发展,图1可以展示遗传算法的研究热点和发展方向[3]:
图1 研究遗传算法的进展
遗传算法搜索的核心是遗传算子的选择。因此,遗传算法最常见的内容和方向是遗传算子。遗传算子的选择多样性也导致了算法性能的多样性。常见的选择方法如图2所示:
图2 研究遗传算子
作为一种搜索算法,遗传算法在函数优化、组合优化、生产调度、自动控制、机器学习、图像处理、人工生命、遗传编程、机器学习、数据挖掘等诸多领域都有很好的表现。
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.