遗传算法以基因和染色体为基本元素,搜索寻求最优解的优化算法

遗传算法

genetic algorithm

定义：一种以基因和染色体为基本元素，模仿生物进化过程（涉及遗传、变异、选择和交叉等操作）并通过搜索寻求最优解的优化方法。

学科：计算机科学技术_人工智能_机器学习

相关名词：人工智能 大数据 机器学习

【延伸阅读】

在几十亿年的演化过程中，自然界中的生物体已经形成了一种优化自身结构的内在机制，它们能够不断地从环境中学习，以适应不断变化的环境。对于大多数生物体，这个过程是通过自然选择和有性生殖来完成的。自然选择决定了群体中哪些个体能够存活并繁殖，有性生殖保证了后代基因的混合与重组。

遗传算法模拟了达尔文生物进化论的自然选择和遗传学机理的生物进化过程，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的中心思想就是“优胜劣汰，适者生存”。在初始群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异操作对个体进行筛选，使适应度高的个体被保留下来，组成新的群体。得到的新群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。

遗传算法首先要解决的就是编码问题，优化问题的解被称为个体，它表示为一个变量序列，叫作染色体。染色体通常使用二进制串进行编码，不过也有一些针对特殊问题的特定编码方式，如：排列编码、符号编码法等。基于染色体的操作有三种：复制、交叉和变异。复制是模拟无性繁殖，在旧种群产生新种群的时候，一般会选择那些适应度比较高的个体，这种操作只能选择出优秀者，但不能创造新的染色体；交叉模拟了生物进化过程中的有性繁殖现象，通过染色体的交换组合，产生新的优良品种；变异模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，以很小的概率随机地改变遗传基因，具体的表现就是随机改变染色体中一位或多位的值。

遗传算法被提出以来得到了广泛的应用，特别是在组合优化、机器学习、信号处理和自适应控制等领域发挥了很大的作用，提高了一些问题求解的效率。尽管最原始的遗传算法存在一些问题，但是近年来各界学者一直在探索着对遗传算法的改进，渐渐地衍生出很多遗传算法的变体。

（作者：大连理工大学计算机学院教授 杨鑫 ）