Genetic algorithm（GA）：遗传算法，是一种通过模拟生物进化的方式来寻找最优解的一类优化算法。这种算法主要依靠遗传、突变和自然选择的机制对问题求解进行高效的迭代搜索。
GA algorithm
Genetic algorithm（GA）：遗传算法，是一种通过模拟生物进化的方式来寻找最优解的一类优化算法。这种算法主要依靠遗传、突变和自然选择的机制对问题求解进行高效的迭代搜索。遗传算法的基本思想是将问题的解表示成一个个体，然后根据适应度函数的定义来评估每个个体的适应性并确定其在繁殖中的概率。经过交叉与变异等操作，新的代替原有的个体，继续与其他生成的个体竞争下去。这一过程不断迭代直至找到最优解或达到迭代次数上限。
遗传算法通过对群体中个体进行复制、交叉、变异等操作对个体进行多样化的重新组合，经适应度函数的筛选（评价）保留适应度较高的个体继而组成新的群体，反复迭代，指导群体的个体适应度不断提高或满足迭代终止条件。在迭代的过程中，新群体继承了父代群体的优良特征、而且得到不断优化。
关键：复制、交叉、变异
优点：多样性保持方面表现良好。
缺点：收敛速度慢，比其他算法需要更长的时间才能找到全局最优解。
复制Reproduction
- 复制(
Reproduction)：也被称为繁殖或再生，通常根据适应度函数(Fitness Function)计算结果，选择适应值较高的个体复制，因此有时也将初始化种群与复制过程一起叫做选择运算，而按照适应度函数计算值进行复制模仿了达尔文生物进化论“适者生存、优胜劣汰”的自然选择过程，其意义在于选择并继承了父（母）代优秀基因，繁殖优秀子孙的几率就更大。 - 遗传算法的选择策略主要有：**轮盘赌选择(
roulette wheel selection)**、排序选择、最优个体保存、随机联赛选择等等。- 轮盘赌选择：将种群中所有个体的适应度值加和，并把每个个体的适应度值与和的比值作为该个体选择的选择概率，从而个体适应度越高被选中概率越高。
- 排序选择：按照适应度值大小对所有个体进行排序，并根据排序确定个体被选中的概率。
- 最优个体保存：会将父代群体中的最优的个体直接保存入子代个体中，保证了优秀个体能够遗传到下一代。
- 随机联赛选择：设置固定值 k，每次随机取 k 个个体，将其中适应度最高的个体遗传入下一代。
交叉Crossover
- 交叉(
Crossover)：模拟生物进化过程的繁殖现象，通过两个染色体按照某种方式互相交换部分基因从而形成两个新的个体的过程，决定了算法的全局搜索能力。交叉的方式有单点交叉（One-point Crossover）、两点交叉/多点交叉（Two-point/Multi-point Crossover）、均匀交叉（Uniform Crossover，也称一致交叉）等。
变异Mutation
- 变异(
Mutation)：模拟生物的基因变异，同交叉操作一样，都用于产生新个体。变异操作主要是为了避免陷入局部最优解的困境，通常按概率对少量个体进行变异操作，对于群组中的每个个体生成 1 个 01 的随机数 $p_1$，假设预设变异概率为 $p_m$（一般设置在 0.010.1 之间）的情况下，如果 $p_1$ < $p_m$，则进行变异操作，否则不进行变异。
遗传算法中对种群操作
- 在遗传算法中，对种群的操作主要包括初始化和淘汰两类：
- 初始化（Initialization）：在遗传算法开始前，需要先生成一个初始的种群。一般来说，这个种群是由一些随机的个体组成的。随机程度要适当，不能过于杂乱，也不能过于单一。
- 淘汰（Survival of the fittest）：在遗传算法的迭代过程中，需要通过一些策略对种群进行淘汰，以避免种群陷入局部最优解。常见的淘汰策略有精英保留、种群大小控制、截断选择等。
- 精英保留：将前几代中表现最好的个体直接留用到下一代种群中，以保持种群中的优秀个体，提升算法的搜索效率。
- 种群大小控制：设定一个种群大小的上限，当种群中个体数目超过这个数值时，需要淘汰一部分个体，保持种群规模的合适。
- 截断选择：按一定比例将个体按照适应度的大小从高到低排序，只保留前面的几个个体，淘汰后面的个体。