⑴ [1] 遗传算法--附Python代码
遗传算法（Genetic Algorithm, GA）是一种模拟生物在自然界中遗传和进化的适者生存的搜索算法。这种算法是在 1975 年由美国的 Holland 教授首次提出，是一种全局优化概率搜索算法。生物可以通过遗传、变异和自然选择而不断地进行演化，遗传算法就是从达尔文的自然选择理论中发展而来。就像是不同的基因，不同的染色体会形成不同的物种。
在遗传算法中，每一个染色体都是一个解决方案，一系列染色体聚集在一起就是所谓的种群。种群根据“生物间相互竞争，能够适应者存活”的原则进行个体淘汰。
从初始种群开始，利用适值函数对种群中每一个染色体进行适应度计算，根据个体适应值占总体适应值的比例，设计合适的选择策略在当前种群中挑选优秀个体，并将这些优秀个体进行交叉和变异产生新的种群。参考物种的演化历程，这些个体一代又一代的进行进化，直至达到所满足期望的结束条件后从中挑选出最优秀的个体作为最终解。
编码是设计遗传算法首先需要解决的问题。由于遗传算法不能直接处理解空间的解数据，因此必须通过编码的方式将这些解表示为遗传空间的基因型串结构数据。遗传算法的编码方式有许多，最典型的是二进制编码和实数编码。其中，二进制编码是人们常选择的编码方式。
二进制编码将待求解问题的解空间用二进制数 0,1 表示，每个个体基因型都是一个二进制编码符号串，其串长取决于求解的精度。因此，在求解适应度值时需将其解码后再进行求解。实数编码则是利用实值来直接表示染色体上的基因，无需进行解码，可以直接求取个体的适应度值。
随机产生一定数量的个体，构成初始解的种群，并设置进化代数。产生初始种群的方法通常有两种：一种是在对问题的解无任何经验知识的情况下，随机产生样本；另一种是在具有某些经验知识的情况下，将其转换成需要满足的要求，在满足要求的解中随机的选取样本。初始群体也要选择适当的个体数量，如果挑选个体数量的过小则会降低种群的多样性，而群体的选择过大就会导致计算复杂、部分高适值的个体有可能被淘汰，影响杂交性能。
适应度函数是对染色体适应能力进行评价的函数，显示着个体或解的优劣。遗传算法评判解的优劣并不在于该解的构造，而是在于该解的适应度值大小。
适应度函数的确立对遗传算法计算的收敛速度及最优解的寻找产生极大的影响。这是由于遗传算法在进化搜索中基于适应度函数，通过计算种群中每个个体的适应度来搜索寻找。此外，在遗传算法中，适应度函数的复杂性占主导地位，因此在求解过程中要尽量简化适应度函数，以减少运算的复杂程度。
在遗传算法流程的每个循环的开始，利用选择算子从当前种群中选出部分个体作为新产生子代的父代。该选择是基于概率的，并且被选中的个体的概率与其适应度相关联，从而有较高适应度的个体具有更高优势。任意的选择两个染色体进行杂交。当前常见的选择算子主要有轮盘选择、排序选择法、精英选择、随机遍历抽样这几种。
遗传算法的重组算子里包含交叉算子等其他重组算子，由于遗传算法中有二进制编码、实值编码、排列编码、树编码等编码方式，因此也必须有与编码方式相适应的不同的交叉算子。二进制编码中常见的有一点交叉、二点交叉等重组算子。交叉概率通常用 [公式] 来表示，它是指两个染色体之间发生交叉重组的概率。交叉概率的取值一般选取 0.25 到 1.00 之间。
变异是指种群中的染色体在进行复制时，产生极低的概率使得这一过程中发生了变化，从而产生了变异，即该染色体上的某个基因点或部分基因发生了突变，突变后的基因将会表现出新的特征。
变异概率通常用 [公式] 来表示，受染色体长度和种群大小的影响。此外， [公式] 的取值也会对算法的收敛性以及最终的最优解取值产生较大的影响，当变异概率较小时，解的稳定性较高，但容易陷入局部最优，且难以跳出局部最优解的区间，若变异概率较大，则可丰富解的空间，跳出局部最优区间，最终趋向全局最优解，因此在设计程序的时候应多次尝试确定合适的变异概率。
停止准则的定义方式主要有三种，即最优个体的适应能力达到指定的阈值、最优个体的适应度和群体总适应度保持稳定不变以及达到预设的最大迭代次数。
遗传算法解决问题时，对约束条件的处理方法有四种方法：
（1）在开始设计编码规则时，让解码后的染色体就只可能落在可行区域内；
（2）设计合理的交叉算子和变异算子，使得在满足所设计算子本身特性的前提下，让运算后的染色体也在可行域内；
（3）采用罚函数的方法，将惩罚值加入适值函数中，降低不满足约束条件个体的生存概率；
（4）在遗传操作后加入判断语句，判断是否满足约束条件，如果是则继续，不满足可将其超出边界的放到边界上或重新初始化操作。
使用遗传算法求解 TSP 问题，首先导入基本库，设置遗传算法参数
接着构建遗传算法模型
构建 TSP 实验场景
运行主函数，求解并绘制最优路径
求解结果如下