什么是遗传算法?
遗传算法是一种基于自然选择(推动生物进化的过程)的解决约束和无约束优化问题的方法。遗传算法反复修改个体解的种群。在每个步骤中,遗传算法都会从当前种群中选择个体作为父代,并利用它们来繁育代的孩子。经过代连续不断的进化,种群逐渐向最优解“进化”。您可以应用遗传算法来解决各种不太适合标准优化算法的优化问题,包括目标函数不连续、不可微、随机或高度非线性的问题。遗传算法可以解决混合整数规划问题,其中一些分量被限制为整数值。
该流程图概述了主要的算法步骤。有关详细信息,请参阅遗传算法的工作原理。
遗传算法在每个步骤中使用三种主要类型的规则从当前种群中创建代:
选择规则选出对代种群有贡献的个体被称为父代。选择通常是随机的,并且取决于个体的分数。
交叉规则将两个父代结合起来形成代的孩子。
变异规则对个体父代施加随机变化以形成子女。
遗传算法与经典的基于导数的优化算法主要有两点不同,如下表所示:
经典算法 | 遗传算法 |
---|---|
每次迭代都会生成一个点。点序列趋近于最优解。 | 在每次迭代中生成种群点。种群中的最佳点趋近于最优解。 |
通过确定性计算选择序列中的下一个点。 | 使用随机数生成器通过计算来选择下一个种群。 |
通常会快速收敛到局部解。 | 通常需要多次函数计算才能收敛。可能会或可能不会收敛到局部或全局最小值。 |