1.算法介绍

遗传算法(genetic algorithm)是借鉴生物界自然选择和遗传机制的自适应全局优化搜索算法，不要求目标函数连续或者可微，使用“自然选择”原理在潜在的解决方案里找到最优解，可以用于最大或者最小问题。

算法涉及到的关键词包括种群、个体、适应度、选择、染色体交换和染色体变异(或者基因突变)。

种群：可行解的集合

个体：种群里的每个可行解

适应度：反映了个体对环境的适应程度或者一个解的优劣程度，通常适应度是目标函数本身或者修改形式

选择：在当前群体里选择最优的个体作为当前最优解；选择下一代种群。选择策略包括轮盘赌法，锦标赛法等。

染色体交换：父代以一定概率交换部分基因产生子代的过程

染色体变异：父代部分染色体以一定概率发生变异产生新个体的过程，目的是为了防止算法陷入局部最优。

锦标赛法的流程是首先在当前种群中随机选出一定数量的个体，然后在选出来的个体里找到最优个体加入到下一代种群集合G，接着在当前种群集合执行染色体交换产生新的子代，循环直到下一代种群大小满足要求，然后再在下一代种群执行染色体变异操作。

2. 算法流程

上图展示遗传算法的主要流程，如果当前种群满足迭代终止条件就停止迭代，否则通过选择、交换和突变产生新的子代继续进行评估。

从本质上讲，GA可以应用于几乎任何优化问题，只要能定义出适应度函数。