遗传算法

遗传算法是一类自适应的随机优化 算法，涉及搜索和优化。遗传算法最早由霍兰德 (Holland) 于 1975 年使用。

基本思想是尝试模拟自然选择的简单图景，以找到一个好的算法。第一步是变异或随机改变给定的样本程序集合。第二步是选择步骤，通常通过针对适应度函数进行衡量来完成。重复此过程，直到找到合适的解决方案。

有许多不同类型的遗传算法。涉及变异的步骤取决于样本程序的表示方式，以及程序员是否包含各种交叉技术。适应度测试也取决于程序员。

与梯度流优化类似，该过程可能陷入适应度函数的局部最大值。遗传算法的一个优点是它不需要适应度函数非常平滑，因为执行的是随机搜索而不是沿着最小阻力路径。但是，要获得成功，可修改参数与适应度之间需要存在某种良好的关系。一般来说，会遇到计算不可约性。

霍兰德创建了一个电子生物体作为二进制字符串（“染色体”），然后使用遗传和进化原理，通过与适应度成比例的选择进行繁殖（包括随机交叉和变异），以有效地搜索巨大的解空间。所谓的遗传编程语言应用相同的原理，使用表达式树而不是位串作为“染色体”。