遗传算法代码
魂部首-寡头垄断
2023年2月15日发(作者：进学解)遗传算法GA（GeneticAlgorithm）⼊门知识梳理
⼀、遗传算法进化论背景知识
作为遗传算法⽣物背景的介绍，下⾯内容了解即可：
种群(Population)：⽣物的进化以群体的形式进⾏，这样的⼀个群体称为种群。
个体：组成种群的单个⽣物。
基因(Gene)：⼀个遗传因⼦。
染⾊体(Chromosome)：包含⼀组的基因。
⽣存竞争，适者⽣存：对环境适应度⾼的、⽜B的个体参与繁殖的机会⽐较多，后代就会越来越多。适应度低的个体参与繁殖的机会⽐
较少，后代就会越来越少。
遗传与变异：新个体会遗传⽗母双⽅各⼀部分的基因，同时有⼀定的概率发⽣基因变异。
简单说来就是：繁殖过程，会发⽣基因交叉(Crossover)，基因突变(Mutation)，适应度(Fitness)低的个体会被逐步淘汰，⽽适应度
⾼的个体会越来越多。那么经过N代的⾃然选择后，保存下来的个体都是适应度很⾼的，其中很可能包含史上产⽣的适应度最⾼的那个个
体。
⼆、遗传算法思想
GA的组成:
编码（产⽣初始种群）
适应度函数
遗传算⼦（选择、交叉、变异）
运⾏参数
借鉴⽣物进化论，遗传算法将要解决的问题模拟成⼀个⽣物进化的过程，通过复制、交叉、突变等操作产⽣下⼀代的解，并逐步淘汰掉适应
度函数值低的解，增加适应度函数值⾼的解。这样进化N代后就很有可能会进化出适应度函数值很⾼的个体。
举个例⼦，使⽤遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为⼀串0-1字符串（0：不取，1：取）；⾸先，随机产⽣M
个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择⼀些字符串通过交叉、突变等操作产⽣下⼀代的M个
字符串，⽽且较优的解被选中的概率要⽐较⾼。这样经过G代的进化后就可能会产⽣出0-1背包问题的⼀个“近似最优解”。
2.1编码
需要将问题的解编码成字符串的形式才能使⽤遗传算法。最简单的⼀种编码⽅式是⼆进制编码，即将问题的解编码成⼆进制位数组的形式。
例如，问题的解是整数，那么可以将其编码成⼆进制位数组的形式。将0-1字符串作为0-1背包问题的解就属于⼆进制编码。
基因在⼀定能够意义上包含了它所代表的问题的解。基因的编码⽅式有很多，这也取决于要解决的问题本⾝。常见的编码⽅式有：
1.⼆进制编码，基因⽤0或1表⽰（常⽤于解决01背包问题）如：基因A：(代表⼀个个体的染⾊体)
2.互换编码（⽤于解决排序问题，如旅⾏商问题和调度问题）如旅⾏商问题中，⼀串基因编码⽤来表⽰遍历的城市顺序，如：
234517986，表⽰九个城市中，先经过城市2，再经过城市3，依此类推。
3.树形编码（⽤于遗传规划中的演化编程或者表⽰）
如,问题：给定了很多组输⼊和输出。请你为这些输⼊输出选择⼀个函数，使得这个函数把每个输⼊尽可能近地映射为输出。编码⽅法：基
因就是树形结构中的⼀些函数。
1.值编码（⼆进制编码不好⽤时，解决复杂的数值问题）
在值编码中，每个基因就是⼀串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他⼀些更复杂的东西。
2.2适应度函数
适应度函数(FitnessFunction)：⽤于评价某个染⾊体的适应度，⽤f(x)表⽰。有时需要区分染⾊体的适应度函数与问题的⽬标函数。例
如：0-1背包问题的⽬标函数是所取得物品价值，但将物品价值作为染⾊体的适应度函数可能并不⼀定适合。适应度函数与⽬标函数是正相
关的，可对⽬标函数作⼀些变形来得到适应度函数。
遗传算⼦：遗传算法有3个最基本的操作：选择，交叉，变异。
2.3选择
选择⼀些染⾊体来产⽣下⼀代。⼀种常⽤的选择策略是“⽐例选择”，也就是个体被选中的概率与其适应度函数值成正⽐。假设群体的个
体总数是M，那么那么⼀个体Xi被选中的概率为f(Xi)/(f(X1)+f(X2)+……..+f(Xn))。⽐例选择实现算法就是所谓的“轮盘赌算法”(
RouletteWheelSelection)。
轮盘赌算法
/*
*按设定的概率，随机选中⼀个个体
*P[i]表⽰第i个个体被选中的概率
*/
intRWS()
{
m=0;
r=Random(0,1);//r为0⾄1的随机数
for(i=1;i<=N;i++)
{
/*产⽣的随机数在m~m+P[i]间则认为选中了i
*因此i被选中的概率是P[i]
*/
m=m+P[i];
if(r<=m)returni;
2.4交叉
所谓交叉运算，是指对两个相互配对的染⾊体依据交叉概率按某种⽅式相互交换其部分基因，从⽽形成两个新的个体。交叉运算在GA中起
关键作⽤，是产⽣新个体的主要⽅法。
2.4.12条染⾊体交换部分基因，来构造下⼀代的2条新的染⾊体。例如：
交叉前：
00000||10000
11100||00101
交叉后：
00000||10000
11100||00101
染⾊体交叉是以⼀定的概率发⽣的，这个概率记为Pc。
2.4.2双交叉点法（⽤于⼆进制编码）
选择两个交叉点,⼦代基因在两个交叉点间部分来⾃⼀个⽗代基因,其余部分来⾃于另外⼀个⽗代基因.如：
交叉前：
01|0010|11
11|0111|01
交叉后：
11|0010|01
01|0111|11
2.4.3.基于“与/或”交叉法（⽤于⼆进制编码）
对⽗代按位"与”逻辑运算产⽣⼀⼦代A;按位”或”逻辑运算产⽣另⼀⼦代B。该交叉策略在解背包问题中效果较好.如：
交叉前：
01001011
11011101
交叉后：
01001001
11011111
还有其他交叉⽅法，参考
2.5变异
变异是指依据变异概率将个体编码串中的某些基因值⽤其它基因值来替换，从⽽形成⼀个新的个体。GA中的变异运算是产⽣新个体的辅助
⽅法，它决定了GA的局部搜索能⼒，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜
索。
注：变异概率Pm不能太⼩，这样降低全局搜索能⼒；也不能太⼤，Pm>0.5，这时GA退化为随机搜索。
在繁殖过程，新产⽣的染⾊体中的基因会以⼀定的概率出错，称为变异。变异发⽣的概率记为Pm。
2.5.1.基本位变异算⼦（⽤于⼆进制编码）
基本位变异算⼦是指对个体编码串随机指定的某⼀位或某⼏位基因作变异运算。对于基本遗传算法中⽤⼆进制编码符号串所表⽰的个体，若
需要进⾏变异操作的某⼀基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。
变异前：
000010000
变异后：
100010000
2.5.2.逆转变异算⼦（⽤于互换编码）
在个体中随机挑选两个逆转点，再将两个逆转点间的基因交换。如：
变异前：1346798205
变异后：1246798305
2.6运⾏参数
GA运⾏时选择的参数应该视解决的具体问题⽽定，到⽬前为⽌，还没有⼀个适⽤于GA所有应⽤领域的关于算法参数的理论。下⾯是⼀般情
况下使⽤GA时推荐的参数：
2.6.1交叉率
交叉率⼀般来说应该⽐较⼤，推荐使⽤80％-95％。
2.6.2变异率
变异率⼀般来说应该⽐较⼩，⼀般使⽤0.5％-1％最好。
2.6.3种群的规模
种群规模指的是群体中个体的个数。实验发现，⽐较⼤的种群的规模并不能优化遗传算法的结果。种群的⼤⼩推荐使⽤20-30，⼀些研究表
明，种群规模的⼤⼩取决于编码的⽅法，具体的说就是编码串（EncodedString）的⼤⼩。也就是说，如果说采⽤32位为基因编码的时候
种群的规模⼤⼩最好为32的话，那么当采⽤16位为基因编码时种群的规模相应应变为原来的两倍。
2.6.4遗传运算的终⽌进化代数
个⼈的想法是，设定⼀个计数器，如果连续N代出现的最优个体的适应度都⼀样时，（严格的说应该是，连续N代⼦代种群的最优个体适应
度都<=⽗代最优个性的适应度）可以终⽌运算。
三、SGA（基本遗传算法）的伪代码
SGA（基本遗传算法）中采⽤轮盘赌选择⽅法
3.1算法流程图
基本遗传算法伪代码
/*
*Pc：交叉发⽣的概率
*Pm：变异发⽣的概率
*M：种群规模
*G：终⽌进化的代数
*Tf：进化产⽣的任何⼀个个体的适应度函数超过Tf，则可以终⽌进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产⽣第⼀代种群Pop
do
{
计算种群Pop中每⼀个体的适应度F(i)。
初始化空种群newPop
do
{
根据适应度以⽐例选择算法从种群Pop中选出2个个体
if(random(0,1) { 对2个个体按交叉概率Pc执⾏交叉操作 } if(random(0,1) { 对2个个体按变异概率Pm执⾏变异操作 } 将2个新个体加⼊种群newPop中 }until(M个⼦代被创建) ⽤newPop取代Pop }until(任何染⾊体得分超过Tf，或繁殖代数超过G) 四、基本遗传算法的优化 下⾯的⽅法可优化遗传算法的性能。 4.1灾变 遗传算法的局部搜索能⼒较强，但是很容易陷⼊局部极值。引⽤⽹上的⼀段原话:“那么如何解决遗传算法容易陷⼊局部极值的问题呢？让 我们来看看⼤⾃然提供的⽅案。 六千五百万年以前，恐龙和灵长类动物并存，恐龙在地球上占绝对统治地位，如果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正 是恐龙的灭绝才使灵长类动物有了充分进化的余地，事实上地球⾄少经历了5次物种⼤灭绝，每次物种灭绝都给更加⾼级的⽣物提供了充分 进化的余地。所以要跳出局部极值就必须杀死当前所有的优秀个体，从⽽让远离当前极值的点有充分的进化余地。这就是灾变的思想。” 灾变就是杀掉最优秀的个体，这样才可能产⽣更优秀的物种。那何时进⾏灾变，灾变次数⼜如何设定？ 何时进⾏灾变，可以采⽤灾变倒计数的⽅式。如果n代还没有出现⽐之前更优秀的个体时，可以发⽣灾变。灾变次数可以这样来确定，如果 若⼲次灾变后产⽣的个体的适应度与没灾变前的⼀样，可停⽌灾变。 4.2精英主义(ElitistStrategy)选择： 当利⽤交叉和变异产⽣新的⼀代时，我们有很⼤的可能把在某个中间步骤中得到的最优解丢失。 精英主义的思想是,在每⼀次产⽣新的⼀代时，⾸先把当前最优解原封不动的复制到新的⼀代中。然后按照前⾯所说的那样做就⾏。精英主义 ⽅法可以⼤幅提⾼运算速度，因为它可以防⽌丢失掉找到的最好的解。 精英主义是基本遗传算法的⼀种优化。为了防⽌进化过程中产⽣的最优解被交叉和变异所破坏，可以将每⼀代中的最优解原封不动的复制到 下⼀代中。 4.3⽭盾 由上⾯看来,灾变与精英主义之间似乎存在着⽭盾.前者是将产⽣的最优个体杀掉,⽽后者是将最优秀个体基因直接保存到下⼀代. 应该辩证地看待它们之间的⽭盾,两者其实是可以共存的.我们在每⼀代进⾏交叉运算时,均直接把最优秀的个体复制到下⼀代;但当连续N代,都 没有更优秀的个体出现时,便可以猜想可能陷⼊局部最优解了,这样可以采⽤灾变的⼿段.可以说,精英主义是伴随的每⼀代的,但灾变却不需要 经常发⽣,否则算法可能下降为随机搜索了. 当然,每个算法中不⼀定要⽤精英主义和灾变的⼿段,应该根据具体的问题⽽定 4.4插⼊操作： 可在3个基本操作的基础上增加⼀个插⼊操作。插⼊操作将染⾊体中的某个随机的⽚段移位到另⼀个随机的位置。 五、GA算法特点 5.1遗传算法的优点: 群体搜索，易于并⾏化处理； 不是盲⽬穷举，⽽是启发式搜索； 适应度函数不受连续、可微等条件的约束，适⽤范围很⼴。 容易实现。⼀旦有了⼀个遗传算法的程序，如果想解决⼀个新的问题，只需针对新的问题重新进⾏基因编码就⾏；如果编码⽅法也相 同，那只需要改变⼀下适应度函数就可以了。 5.2遗传算法的缺点: 全局搜索能⼒不强,很容易陷⼊局部最优解跳不出来；(可结合SA进⾏改进,因为SA在理率上是100%得到全局最优的,但搜索代价⾼) 将遗传算法⽤于解决各种实际问题后，⼈们发现遣传算法也会由于各种原因过早向⽬标函数的局部最优解收敛，从⽽很难找到全局最优解。 其中有些是由于⽬标函数的特性造成的，例如函数具有欺骗性，不满⾜构造模块假说等等；另外⼀些则是由于算法设计不当。为此，不断有 ⼈对遗传算法提出各种各样的改进⽅案。例如：针对原先的定长⼆进制编码⽅案；提出了动态编码、实数编码等改进⽅案；针对按⽐例的选 择机制，提出了竞争选择、按续挑选等改进⽅案；针对原先的⼀点交算⼦，提出了两点交、多点交、均匀交等算⼦；针对原先遗传算法各控 制参数在进化过程中不变的情况，提出了退化遗传算法、⾃适应遗传算法等。另外，针对不同问题还出现了分布式遗传算法、并⾏遗传算法 等等。 六、遗传算法的实例 参考： 参考⽂献都是⼲货参考⽂献都是⼲货参考⽂献都是⼲货 1. 本⽂主要参考，推荐！感谢作者~ 2. July⼤神写的，通俗易懂，推荐 3. 博主语⾔轻松，⽤python描述了遗传算法求解⼀个函数最⼤值的例⼦。 4. 博主总结整理的内容，挺不错的，⽂中的链接有实例应⽤。 5. 袋⿏跳的例⼦来描述了GA算法，帮助理解GA。 6. 求下述⼆元函数的最⼤值的例⼦ 7. 欢迎来我的博客看看~