遗传算法（Genetic Algorithm, GA）学习，基于MATLAB和Sheffield工具箱
本文内容主要参考《MATLAB智能算法30个案例分析（第2版）》
遗传算法的原理：
遗传算法是从一组随机产生的初始解（种群）开始的，这个种群由经过基因编码的一定数量的个体组成，每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，其内部表现（基因型）是某种基因的组合，它决定了个体的外部表现。因此，从一开始就需要实现从表现型到基因型的映射，即编码工作。初始种群产生后，按照优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代种群更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。（主观解释：遗传算法是一种模拟自然界生物进化的算法，通过选择、交叉和变异等操作，逐步演化数据以获得近似最优解的算法）
遗传算法的基本步骤：
开始
S1.初始化，输入原始参数及给定参数
S2.数据编码，产生初始种群
S3.适应度评估
while S4.终止条件的判断
S5.选择
S6.交叉
S7.变异
S8.新种群
S9.代计数器增加
end
S10.输出结果
结束
名词解读：
编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据,这些串结构数据的不同组合便构成了不同的点。（主观解释：将十进制数据转化为二进制数据）
初始群体：随机产生N个初始串结构数据,每个串结构数据称为一个个体,N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始进化。（主观解释：随机生成N个可能数据）
适应度评估：适应度表明个体或解的优劣性。不同的问题,适应性函数的定义方式也不同。（主观解释：求最小值的问题中，值越小适应度评估数据就越大）
选择：选择的目的是为了从当前群体中选出优良的个体,使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想,进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择体现了达尔文的适者生存原则。（主观解释：适应度越强被选择的概率越大）
交叉：交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体﹐新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。（主观解释：现有两个字节分别为：11110000、00001111设交叉点在第五位交叉操作后的两个数据为：11111111、00000000）
变异：变异首先在群体中随机选择一个个体,对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样,GA中变异发生的概率很低,通常取值很小。（主观解释：00000000使其中一位变异后为00010000）
Sheffield遗传算法工具箱中常用函数：
（通过学习这个工具箱中的函数，你可以更好地理解遗传算法的原理和应用。这个工具箱的函数源代码是开放的，你可以随时查看和修改。这样，你就可以把学习的重点放在算法的原理和效果上，而不是代码的编写和调试上。工具箱安装方法）
1.创建种群函数——crtbp
功能：创建任意离散随机种群。
调用格式：
[Chrom,lind,BaseV] = crtbp(Nind,Lind)
[Chrom,lind,BaseV] = crtbp(Nind,Base)
[Chrom,lind,BaseV] = crtbp(Nind,Lind,Base)
本文仅使用：[Chrom,lind,BaseV] = crtbp(Nind,Lind)（若要了解其他调用格式，参考工具箱安装文件中的gatbxa2.pdf）。此格式为Nind×Lind的随机二进制矩阵,其中,Nind 为种群个体数，Lind为个体长度。返回种群编码Chrom和染色体基因位的基本字符向量 BaseV。（主观解释：生成Nind×Lind的随机二进制矩阵）
举例：
>> [Chrom,lind,BaseV] = crtbp(4,5)
Chrom =
1 1 1 0 1
0 1 0 0 0
1 1 1 0 1
1 0 0 1 0
lind =
5
BaseV =
2 2 2 2 2
>> NIND = 4;PRECI = 5;
>> Chrom = crtbp(NIND,PRECI);
>> Chrom
Chrom =
1 0 0 0 0
0 0 1 1 1
0 1 1 0 1
1 1 0 0 0
2.适应度计算函数——ranking
功能：基于排序的适应度分配。
调用格式：
FitnV = ranking(ObjV)
FitnV = ranking(ObjV,RFun)
FitnV = ranking(ObjV,RFun,SUBPOP)
本文仅使用：FitnV = ranking(ObjV)。此格式是按照个体的目标值ObjV(列向量)由小到大的顺序对个体进行排序的,并返回个体适应度值FitnV的列向量。（主观解释：给定一组目标值，当目标值越大时，适应度越小，最小值为0；当目标值越小时，适应度越大，最大值为2）
举例：
>> ObjV = [1;2;5;4;3]
ObjV =
1
2
5
4
3
>> FitnV = ranking(ObjV)
FitnV =
2.0000
1.5000
0
0.5000
1.00003.选择函数——select
功能：从种群中选择个体（高级函数）。
调用格式：
SelCh = select(SEL_F,Chrom,FitnV)
SelCh = select(SEL_F,Chrom,FitnV,GGAP)
SelCh = select(SEL_F,Chrom,FitnV,GGAP,SUBPOP)
本文仅使用：SelCh = select(SEL_F,Chrom,FitnV)。SEL_F是一个字符串,包含一个低级选择函数名,如rws或sus。FitnV是列向量,包含种群Chrom中个体的适应度值。这个适应度值表明了每个个体被选择的预期概率。GGAP是可选参数,指出了代沟部分种群被复制。如果GGAP省略或为NAN,则GGAP假设为1.0。SUBPOP是一个可选参数,决定Chrom中子种群的数量。如果SUBPOP省略或为NAN,则 SUBPOP=1。Chrom中所有子种群必须有相同的大小。（主观解释：轮盘赌的实现，看举例来理解）
举例：
>> Chrom = [1,11,21;2,12,22;3,13,23;4,14,24;5,15,25]
Chrom =
1 11 21
2 12 22
3 13 23
4 14 24
5 15 25
>> FitnV = [1.5;1.35;1.21;1.07;0.92]
FitnV =
1.5000
1.3500
1.2100
1.0700
0.9200
>> SelCh = select('sus',Chrom,FitnV)
SelCh =
2 12 22
3 13 23
1 11 21
1 11 21
4 14 24
4.交叉算子函数——recombin
功能：重组个体（高级函数）。
调用格式：
NewChrom = recombin(REC_F,Chrom)
NewChrom = recombin(REC_F,Chrom,RecOpt)
NewChrom = recombin(REC_F,Chrom,RecOpt,SUBPOP)
本文仅使用：NewChrom = recombin(REC_F,Chrom,RecOpt)。recombin完成种群Chrom中个体的重组,在新种群NewChrom中返回重组后的个体。Chrom和 NewChrom中的一行对应一个个体。REC_F是一个包含低级重组函数名的字符串,例如recdis或xovsp。RecOpt是一个指明交叉概率的任选参数,如省略或为NAN,将设为缺省值。SUBPOP是一个决定Chrom中子群个数的可选参数,如果省略或为NAN,则 SUBPOP为1。Chrom中的所有子种群必须有相同的大小。（主观解释：以RecOpt的概率对Chrom中的个体进行单点交叉操作——REC_F的值要为'xovsp'）
举例：
>> Chrom = [0,0,0,0;1,1,1,1;1,0,1,0;0,1,0,1]
Chrom =
0 0 0 0
1 1 1 1
1 0 1 0
0 1 0 1
>> NewChrom = recombin('xovsp',Chrom,0.7)
NewChrom =
0 0 1 1
1 1 0 0
1 0 1 0
0 1 0 1
5.变异算子函数——mut
功能：离散变异算子。
调用格式：
NewChrom = mut(OldChrom,Pm,BaseV)
本文仅使用：NewChrom = mut(OldChrom,Pm)。OldChrom为当前种群,Pm为变异概率(省略时为0.7/Lind), BaseV指明染色体个体元素的变异的基本字符(省略时种群为二进制编码)。（主观解释：使种群中的个体以一定概率发生变化）
举例：
>> OldChrom = [1,1,1,1,1,1,1,1]
OldChrom =
1 1 1 1 1 1 1 1
>> NewChrom = mut(OldChrom,0.5)
NewChrom =
0 1 0 0 1 0 1 06.重插入函数——reins
功能：重插入子代到种群。
调用格式：
Chrom = reins(Chrom,SelCh)
Chrom = reins(Chrom,SelCh,SUBPOP)
Chrom = reins(Chrom,SelCh,SUBPOP,InsOpt,ObjVCh)
Chrom = reins(Chrom,SelCh,SUBPOP,InsOpt,ObjVCh,ObjVSel)
本文仅使用：Chrom = reins(Chrom,SelCh,SUBPOP,InsOpt,ObjVCh,ObjVSel)。reins完成插入子代到当前种群,用子代代替父代并返回结果种群。Chrom为父代种群，SelCh为子代,每一行对应一个个体。
SUBPOP是一个可选参数,指明Chrom和 SelCh中子种群的个数。如果省略或者为NAN,则假设为1。在 Chrom和 SelCh中每个子种群必须具有相同大小。
InsOpt是一个最多有两个参数的任选向量。
InsOpt(1)是一个标量,指明用子代代替父代的方法。0为均匀选择,子代代替父代使用均匀随机选择。1为基于适应度的选择,子代代替父代中适应度最小的个体。如果省略InsOpt(1)或InsOpt(1)为NAN,则假设为0。
InsOpt(2)是一个在[0,1]区间的标量,表示每个子种群中重插入的子代个体在整个子种群中个体的比率。如果InsOpt(2)省略或为NAN,则假设InsOpt(2)=1.0。
ObjVCh是一个可选列向量,包括Chrom中个体的目标值。对基于适应度的重插入，ObjVCh是必需的。
ObjVSel是一个可选参数,包含SelCh中个体的目标值。如果子代的数量大于重插入种群中的子代数量,则ObjVSel是必需的。这种情况子代将按它们的适应度大小选择插入。（主观解释：将SelCh的值插入到Chrom中）
举例：
>> Chrom = [1,1,1,1;0,0,0,0;1,1,0,0;0,0,1,1]
Chrom =
1 1 1 1
0 0 0 0
1 1 0 0
0 0 1 1
>> SelCh = [1,0,1,0;0,1,0,1]
SelCh =
1 0 1 0
0 1 0 1
>> Chrom = reins(Chrom,SelCh)
Chrom =
1 1 1 1
0 0 0 0
1 0 1 0
0 1 0 1
7.实用函数——bs2rv
功能：二进制到十进制的转换。
调用格式：
Phen = bs2rv(Chrom,FieldD)
bs2rv根据译码矩阵FieldD将二进制串矩阵Chrom 转换为实值向量,返回十进制的矩阵。
矩阵FieldD有如下结构：
FieldD =
len %包含在Chrom中的每个子串的长度,注意，sum(len)=size(Chrom,2)
lb %变量的下界
ub %变量的上界
code %指明子串如何编码，0为标准二进制，1为格雷编码
scale %指明每个子串所使用的刻度，0表示算术刻度,1表示对数刻度
lbin %下界是否包含边界，0表示不包含边界,1表示包含边界
ubin %下界是否包含边界，0表示不包含边界,1表示包含边界举例：
>> Chrom = [1,1,1,1;0,0,0,0;1,1,0,0;0,0,1,1]
Chrom =
1 1 1 1
0 0 0 0
1 1 0 0
0 0 1 1
>> FieldD = [size(Chrom,2);0;16;0;0;1;1];
>> X = bs2rv(Chrom,FieldD);
>> X
X =
16.0000
0
12.8000
3.20008.实用函数——rep
功能：矩阵复制。
调用格式：
MatOut = rep(MatIn,REPN)
函数rep完成矩阵MatIn的复制,REPN指明复制次数,返回复制后的矩阵 MatOut。REPN包含每个方向复制的次数,REPN(1)表示纵向复制次数,REPN(2)表示水平方向复制次数。（本文未使用此函数）
举例：
>> MathIn = [1,2,3,4;5,6,7,8]
MathIn =
1 2 3 4
5 6 7 8
>> MathOut = rep(MathIn,[1,2])
MathOut =
1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8
具体例子：
简单一元函数优化：利用遗传算法计算以下函数的最小值：
![f(x)=\frac{sin(10\pi x)}{x},x\epsilon [1,2]](https://images2.imgbox.com/5c/e6/hBw8TLhH_o.png)
选择二进制编码，遗传算法参数设置如表所示：
| 种群大小 | 最大遗传代数 | 个体长度 | 代沟 | 交叉概率 | 变异概率 |
| 40 | 20 | 20 | 0.95 | 0.7 | 0.01 |
遗传算法优化程序代码：
clc
clear
close all
%%画出函数图
figure(1);
hold on;
lb = 1;ub = 2; %函数自变量范围[1,2]
fplot(@(X)sin(10 * pi * X)./X,[lb,ub]); %画出函数曲线
xlabel('自变量/X')
ylabel('函数值/Y')
%%定义遗传算法参数
NIND = 40; %种群大小
MAXGEN = 20; %最大遗传函数
PRECI = 20; %个体大小
px = 0.7; %交叉概率
pm = 0.01; %变异概率
trace = zeros(2,MAXGEN); %寻优结果的初始值
FieldD = [PRECI;lb;ub;0;0;1;1]; %区域描述器
Chrom = crtbp(NIND,PRECI); %创建任意离散随机种群
%%优化
gen = 0;
X = bs2rv(Chrom,FieldD);
ObjV = sin(10 * pi * X) ./ X;
while gen < MAXGEN
FitnV = ranking(ObjV); %分配适应值
SelCh = select('sus',Chrom,FitnV);
%选择
SelCh = recombin('xovsp',SelCh,px); %重组
SelCh = mut(SelCh,pm); %变异
X = bs2rv(SelCh,FieldD); %子代个体的十进制转换
ObjVsel = sin(10 * pi * X) ./ X; %计算子代的目标函数值
[Chrom,ObjV] = reins(Chrom,SelCh,1,1,ObjV,ObjVsel);
%重插入子代到父代，得到新种群
X = bs2rv(Chrom,FieldD);
gen = gen + 1; %代计数器增加
%%获取每代的最优解及其序号，Y为最优解，I为个体的序号
[Y,I] = min(ObjV);
trace(1,gen) = X(I); %记下每代的最优值
trace(2,gen) = Y; %记下每代的最优值
end
plot(trace(1,:),trace(2,:),'bo'); %画出每代的最优点
grid on;
plot(X,ObjV,'b*'); %画出最后一代的种群 hold off
%%画进化图
figure(2);
plot(1:MAXGEN,trace(2,:));
grid on
xlabel('遗传代数')
ylabel('解的变化')
title('进化过程')
bestY = trace(2,end);
bestX = trace(1,end);
fprintf(['最优解：\nX = ',num2str(bestX),'\nY=',num2str(bestY),'\n'])
程序运行后的结果：
最优解：
X = 1.1491
Y=-0.8699
左图所示为目标函数图,其中○是每代的最优解，*是优化20代后的种群分布。从图中可以看出○和*大部分都集中在一个点,该点即为最优解。
右图所示是种群优化20代的进化图。
结尾：
小伙的第一篇博客，谢谢观看，欢迎大佬指正