遗传算法是一种基于自然选择机制的搜索算法。其本质是定义了一种框架，在这种框架下人为干预和随机信息交换相结合，进而产生出有可能的最优结果。由于是基于自然界的选择机制，在遗传算法的这种框架下，每一次新的个体的产生是基于上一代个体的信息以及有可能的突变或者交换信息进而得到的结果。尽管是随机产生的突变结果，然而遗传算法得到的结果并不仅仅是随机查找的结果。遗传算法能够有效地探索新个体上一代的信息，进而演化得到更加优化的下一代，并且在这种基础之上，提高了计算性能。
遗传算法包括以下几个步骤:
- 确定初始个体数量。
- 设计一种方式来确定如何选择个体的后代，一般情况下是设计出适应性函数来确定后代的健康程度。
- 选取出的个体将产生后代，并且替代健康程度不佳的个体。
- 此过程会不断迭代直到某种事先设计好的标准达成,一般情况下是设计迭代次数。
[描述来源: Goldberg,D. (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company. ]
发展历史
在十九世纪七十年代，John Holland改进了并且极大增强了他在适应系统上的工作，Holland在1975年发表于Adaptation in Natural and Artificial Systems中提出一种系统框架用于如何评测遗传算法中的进化机制。
John Koza延续了Holland的工作，作为Holland的博士生，Koza尝试了将遗传算法的商业开发，并且成立了商业公司。
在十九世纪九十年代，由于计算能力受限制，遗传算法只能应用于比较简单的问题上。随着时代的进步以及科技的发展，遗传算法展现出了自己的活力。更多的基于遗传算法的商业应用以及科学研究不断涌现。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1962 | Holland提出适应性系统概念 | Holland, J. H. (1962). Outline for a logical theory of adaptive systems. Journal of the ACM (JACM), 9(3), 297-314. |
| 1967 | Rosenberg在生物学适应性系统上提出一种化学分子模型 | Rosenberg, R. S. (1970). Stimulation of genetic populations with biochemical properties: I. the model. Mathematical Biosciences, 7(3-4), 223-257. |
| 1972 | Frantz将遗传算法应用于搜索领域 | Frantz, D. R. (1972). Non-linearities in genetic adaptive search. |
| 1975 | De Jong进行了进一步的开创性质的研究,将遗传算法应用在连续优化领域. | De Jong, K. A. (1975). Analysis of the behavior of a class of genetic adaptive systems. |
| 1989 | Goldberg提出了一套系统的研究方法,将遗传算法与机器学习理论相结合 | Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning, 3(2), 95-99. |
| 2002 | Goldberg撰写了遗传算法,以及将其拓展到优化理论范围上的综述 | Goldberg, D. E. (2013). The design of innovation: Lessons from and for competent genetic algorithms (Vol. 7). Springer Science & Business Media. |
发展分析
瓶颈
遗传算法得到的结果可能并不是最有结果。
参数选取困难,很难估计个体数量以及迭代时间。
算力消耗大,时间复杂度过高。
未来发展方向
量子计算和遗传算法相结合。遗传算法与其他优化理论相结合，比方说蚁群优化（Ant colony optimization）:将大量的个体与遗传算法模型相结合，对解空间进行完整的遍历查找以达到可用的解决方案。
另外一个大量应用的场景是将遗传算法和粒子群优化（Particle Swarm Optimization）相结合，这种启发式算法会在解空间不断搜索以达到最优解。
Contributor: Yixin Zhang