知乎链接：https://zhuanlan.zhihu.com/p/77445003 遗传算法总体**： 一. 产生一个初始种群 二. 根据问题的目标函数构造适值函数 三. 根据适应值的好坏不断的选择和繁殖 四. 若干代后得到的适应值最好的个体即为最优解 构成要素： ①种群和种群大小： 种群由染色体构成，每个个体也就是一个染色体，也同时对应着问题的一个解。 种群中个体的数量称为种群大小或种群规模，记作NP,一般情况下，种群规模通常设置为一个常量，这个值也一般越大越好，但一味地增大也会增大计算机运算的负担，一般设置为100~1000。有的时候根据实际情况的需要也会将种群规模设置为与遗传代数相关的变量，来获得更好的优化效果。 ②编码方法： 编码方法也称为基因表达方法。 每个染色体可以表示为X=(x_1,x_2,x_3,……,x_n)，染色体的每一位都是一个基因，每一位的取值成为位值，n称为染色体的长度，原始GA采用固定长度的0.1字符串来表示一个染色体，例如X=(0110010)，这种方法称为0-1编码或者是二进制编码。 二进制编码适用于以下三种情况：背包问题，实优化问题(但当精度要求高时，编码就会很长，就不会采用这种编码方法，而是直接采用实数编码)，指派问题(一类特殊的线性规划问题。其中工作对资源的需求是一对一的，每样资源(雇员，机器，时间段)唯一的指派给一件工作(任务，位置，事件)。同时，资源i指派给工件j也会产生一个相应费用C_ij，问题的目标是如何指派可使总费用达到最小)。 此外，仍有 顺序编码：用1到n的自然数来编码，此种编码不允许重复，又称为自然数编码，例如n=7的染色体X=(2 3 1 5 4 6 7)，此类编码可以用于解决旅行商问题，指派问题等，i.e.上面7个序号可以理解为7个城市的游览路线 实数编码：染色体上的位置为实数，这种编码方式具有精度高，便于大空间搜索，运算简单的特定，特别适合实优化问题但是反映不出基因的特征。 整数编码：对于染色体X=(x_1,x_2,x_3,……,x_n),1<=x_i<=n_i,n_i为基因的最大取值。整数编码适用于新产品投入，时间优化，伙伴挑选的问题(每个项目都有挑选伙伴的数量的上限)。 ③遗传算子： 交叉：单切点交叉，双切点交叉。单切点交叉随机选取一个切点，对于两个亲本，将该切点后的基因进行交叉互换。双切点则是选两个切点，将两个切点之间的基因进行交叉互换。这里会涉及一个交叉概率Pc。在遗传运算中，我们会通过选择策略进行选优进入遗传池，但并不是所有进入遗传池的个体都会发生交叉，于是引入了交叉概率Pc。Pc定义为各代交叉产生的后代数与种群个体数的比。(p.s.显然，较高的交叉率将达到更大的解空间，从而减少停留在非最优解的机会，但交叉率太高则会因过多搜索不必要的解空间而耗费大量的计算时间。一般设置为0.9。) 变异：染色体上单个基因发生变异，这里涉及一个变异概率Pm，一般设定为一个比较小的数，在5%以下。 这里就会涉及一个问题，如果在发生交叉变异后，染色体不合法了怎么办？ 当然对于不合法状态有两种应对策略：拒绝或修复。拒绝策略需要保证不合法子代占比很小，修复策略则会导致父代基因丢失。 #顺序编码的合法性修复： 交叉修复策略： ①部分映射交叉（PMX）： a:选切点X,Y b：交换中间部分 c：确定映射关系 d：将未交换部分按照映射关系恢复合法性 ################################# # X Y # # P_1:2 1 | 3 4 5 | 6 7 # # P_2:4 3 | 1 2 5 | 7 6 # #-------------------------------# #映射关系：3-1 4—2 5-5 # #交叉互换： # # P_1:2 1 | 1 2 5 | 6 7 # # P_2:4 3 | 3 4 5 | 7 6 # #不满足顺序编码的不重复性 # #利用交换子串的映射关系进行修复 # # P_1:4 3 | 3 4 5 | 6 7 # # P_2:2 1 | 1 2 5 | 7 6 # ################################# 这样使得重复的位置被换掉，而交换的子串保持不变 ②顺序交叉（OX）： 可以看做是PMX的变式 a:选择切点X，Y b：交换中间部分 c：从第二个切点Y后第一个基因起列出（###）原顺序（###），去掉已有基因 d：从第二个切点Y后第一个位置起，将获得的无重复顺序填入 该方法较好的保留了相邻关系，先后关系，满足了TSP问题的需要，但是不保留位值特征。 ③循环交叉（CX）：书上也不明白，用链接：https://www.cnblogs.com/gambler/p/9124862.html 变异修复策略： ①换位变异：随机选取两个位置交换基因的位值 ②移位变异：随意选择一位基因移位到最前面 #实数编码的合法性修复： 交叉： ①单切点交叉 ②双切点交叉 ③凸组合交叉：简单的交叉操作（单切点交叉和双切点交叉）很容易造成解的不可行性 所以采用凸集合理论： Z_1=a*X+(1-a)*Y z_2=(1-a)X+aY 若约束是个凸集，虽然可行性得到了保持，但是这样的操作将导致种群的分散性不好，基因的取值向中间汇集，染色体覆盖的区域越来越小。 变异： ①位值变异：x=x+z，z为扰动 ②向梯度方向变异：Z=X+/-grad(f(X))*a 我理解为降低损失函数 ④选择策略： 最常用的选择策略是正比选择策略，轮盘赌法。 此外有，顺序选择。 ⑤停止准则：一般是达到迭代次数，或者看是不是收敛（根据平均适应值是不是和max差不多） #想了很久的一个地方是，轮盘赌选择好与父代一样数目的个体后，再进行交叉运算和变异运算，假设交叉概率Pc=0.6，则为每个个体产生一个0-1的随机数，所有小于0.6的个体与随机一个个体进行交配，交叉点随机确定。