深度学习经典算法 | 遗传算法详解

墨明棋妙27

发布于 2022-09-23 11:14:49

7210

发布于 2022-09-23 11:14:49

文章被收录于专栏：1996

遗传算法生物学基础

在一定的时间内，有一群兔子，其中一些比另外一些兔子跑得快，而且更聪明，这些兔子被狐狸吃掉的可能性比较小，因此它们中的多数就存活下来并繁殖更多的兔子。当然，一些跑得慢而愚蠢的兔子也会存活下来，只是因为它们比较侥幸，这些存活的兔子群开始生育。生育的结果是兔子遗传材质的充分融合：一些跑得慢的兔子生出了跑得快的兔子，一些跑得快的兔子生出跑得更快的，一些聪明的兔子生出了愚蠢的兔子，等等。在最顶层，自然界不时地变异一些兔子的基因材质。所产生的小兔子平均来说要比原始的群体更快更聪明，因为从狐狸口中生存下来的父代多数是跑得更快、更聪明的兔子。同样，狐狸也经历相似的过程，否则兔子可能跑得太快又太聪明以致狐狸根本抓不到了。

兔子的生存哲学就是以自然选择学说为核心的现代生物进化理论，其基本观点是：种群是生物进化的基本单位，生物进化的实质是种群基因频率的改变。基因突变和基因重组、自然选择及隔离是物种形成过程的三个基本环节，通过它们的综合作用，种群产生分化，最终导致新物种的形成。在这个过程中，基因突变和基因重组产生生物进化的原材料.自然选择使种群的基因频率定向改变并决定生物进化的方向，隔离是新物种形成的必要条件。

新物种形成的途径和方式有两种：渐变式和爆发式。渐变式主要通过变异的逐渐积累而成亚种，再由亚种形成一个物种或多个新种。遗传算法杂交了渐变式和爆发式两种思想。

遗传算法的实现步骤

GA由解编码、个体适应度评估和遗传算法三大模块构成，而遗传算法又包括染色体复制、交叉、变异甚至倒位等。改良的遗传算法和融合新型技术的遗传算法都是SGA的变异形式。在遗传算法中，定义种群或群体为所有编码后的染色体集合，表征每个个体的是其相应的染色体。

1、编码

遗传算法的编码有浮点编码和二进制编码两种，这里只介绍二进制编码规则。二进制编码既符合计算机处理信息的原理，也方便了对染色体进行遗传、编译和突变等操作。设某一参数的取值范围为(L，U)，使用长度为k的二进制编码表示该参数，则它共有

2^{k}

种不同的编码。该参数编码时的对应关系为 000000000000000000=0→L 000000000000000001=1→L+

\delta

000000000000000010=2→L+2

\delta

000000000000000011=3→L+3

\delta

…………

111111111111111111→

2^{k}

→U

易知：

\frac{U-L}{2^{k}-1}

2、解码

解码的目的是为了将不直观的二进制数据串还原成十进制。设某一个体的二进制编码为

b_{k}b_{k-1}b_{k-2}b_{k-3}…b_{2}b_{1}

，则对应的解码格式为：

x=L+(\sum_{i=1}^{k}b_{i}2^{i-1)})\frac{U-L}{2^{k}-1}

遗传算法的编码和解码在宏观上可以对应生物的基因型和表现型，在微观上可以对DNA的转录和翻译两个过程。

3、交配

“交配运算”是使用单点或多点进行交叉的算子。首先用随机数产生一个或多个交配点位置，然后两个个体在交配点位置互换部分基因码，形成两个子个体。例如，有两条染色体

S_{1}

=01000101100101101001011，

S_{2}

=10010101交换其后4位基因，如下图所示。下图染色体基因交配范S'1=01000101，S'2=10011011可以被看做是原染色体

S_{1}

和

S_{2}

的子代染色体。

4、突变

“突变运算”是使用基本位进行基因突变。为了避免在算法迭代后期出现种群过早收敛，对于二进制的基因码组成的个体种群，实行基因码的小几率翻转，对于二进制编码即0变为1，而1变为0。例如，将染色体S=110$01101第3位上的0变为1，即S=11001101→11101101=S'.S'可以被看做是原染色体Ｓ的子代染色体。

5、倒位

除了交配和突变之外，对于复杂的问题可能需要用到“倒位”，其对应的运算亦被称为“倒位运算”。倒位是指一个染色体某区段正常排列顺序发生180°的颠倒，造成染色体内的DNA序列重新排列，它包括臂内倒位和臂间倒位。倒位纯合体不影响个体的生活力，只是改变了染色体上的相邻基因位置，从而某些表现型发生位置效应，同时也改变了与相邻基因的交换值。倒位杂合体则不然，其生育力降低。染色体上的区段可能一次又一次发生倒位·且通过自交出现不同的倒位纯合体，致使它们与其原来的物种不能交配，形成生殖隔离，结果产生新族群或变种。

倒位运算是与倒位概念相似的运算规则。例如.染色体S'就是S经过倒位运算以后得到的染色体基因编码，其中倒位的部分即S中标记下画粗的部分。

S=1001011011101110011010101001→

S^{'}

=1001011001011001110111101001

6、个体适应度

自然界中能够适应环境的生物有更多的机会存活下来，这种筛选机制类似下图所示象：在由正六边形搭建的三角形区域的顶部投掷一些光滑的木块，这些木块经由白色的缝隙坠落底部，显然落在底部中间的木块要比落在两端的木块多，因为木块有更多的路径坠落在底部的中间区域，所以有更大的几率落在中间。落在各个区域的几率对应遗传算法中各条染色体被遗传到下一代的几率，其坠落的位置对应自变量取值。遗传算法依照与个体适应度成正比的几率决定当前种群中各个个体遗传到下一代群体中的机会。个体适应度大的个体更容易被遗传到下一代。通常，求目标函数最大值的问题可以直图5-2正六边形筛选机制接把目标函数作为检测个体适应度大小的函数。

正六边形筛选机制

7、复制

复制运算是根据个体适应度大小决定其下代遗传的可能行。若设总群中个体总数为N，个体i的适应度为

f_{i}

,则个体i被选取的几率：

P_{i}=\frac{f_{i}}{\sum_{i=1}^{k}f_{k}}

当个体复制的几率决定后，在产生[0,1]区间随机数来决定哪些个体参加复制。若个体适应度高，则被选取的几率

P_{i}

就大，则可能被多次选中，它的遗传基因就会在种群中扩散；若个体的复制几率小，则会被逐渐淘汰。

程序设计流程

遗传算法伪代码

matlab GA工具箱求解多约束非线性规划问题

举例如下所示：

matlab实现

主函数：

%主程序：本程序采用遗传算法接力进化，
%将上次进化结束后得到的最终种群作为下次输入的初始种群
clc;
close all;
clear all;
%进化的代数
T=100;
optionsOrigin=gaoptimset('Generations',T/2);
[x,fval,reason,output,finnal_pop]=ga(@ch14_2f,2,optionsOrigin);
%进行第二次接力进化
options1=gaoptimset('Generations',T/2,'InitialPopulation',finnal_pop,...
    'PlotFcns',@gaplotbestf);
[x,fval,reason,output,finnal_pop]=ga(@ch14_2f,2,options1);
Bestx=x
BestFval=fval

子函数

%子函数：适应度函数同时也是目标函数,函数存储名称为ch14_2f.m
function f=ch14_2f(x)
g1=1.5+x(1)*x(2)-x(1)-x(2);
g2=-x(1)*x(2);
if(g1>0|g2>10)
    f=100;
else
    f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);
end