!! ✨ Matlab版本为R2022b,与以前的版本兼容。
作为一种进化算法,遗传算法(GA, Genetic Algorithm)的基本原理是将问题参数编码为染色体,进而利用优化迭代的方法进行选择、交叉和变异算子操作来交换种群中染色体的信息,最终生成符合优化目标的染色体。
为了更好地理解与运用遗传算法解决实际问题,我们首先需要理解如下四个专业术语:
遗传算法的基本步骤如下所示:
个初始串结构数据,其中每一个串结构数据为一个个体,
个个体便构成了一个群体。
通过百度网盘下载Matlab第三方遗传算法Sheffield工具箱,下载解压后得到gatbx
文件夹。:
!! 链接: https://pan.baidu.com/s/1K-PB9-CXER6XeEnKG2260A?pwd=lxb1 提取码: lxb1
在Matlab命令行中输入matlabroot
可以得到系统中Matlab的根目录,我使用的是Ubuntu系统,输出结果如下图所示:
然后将下载的gatbx
文件夹放到/home/liang/Matlab/toolbox
文件夹中,然后在命令行中输入如下命令,将gatbx
添加到Matlab搜索路径中:
% 得到gatbx工具箱所在的完整滤镜
str = [matlabroot, '/toolbox/gatbx'];
% 将工具箱gatbx添加到Matlab搜索路径
addpath(str)
使用命令ver('gatbx')
查看工具箱是否安装成功:
对于Windows系统可以参考博文《谢菲尔德大学的MATLAB遗传算法工具箱(附代码文件)》,链接:https://blog.csdn.net/panmingqian/article/details/121813045。
利用遗传算法gatbx工具箱计算如下函数的最小值:
下面选择二进制编码遗传算法,其参数设置如下表所示:
种群大小 | 最大遗传代数 | 个体长度 | 代沟 | 交叉概率 | 变异概率 |
---|---|---|---|---|---|
遗传代码如下所示:
% 1. 绘制求解函数
figure(1); subplot(1,2,1); hold on;
% 设置自变量范围[1,2]
lb = 1; ub = 2;
ezplot('sin(10*pi*x)/x', [lb,ub]);
xlabel('自变量/x')
ylabel('函数值/y')
% 2. 定义遗传算法参数
NIND = 40; % 种群大小
MAXGEN = 20; % 最大的遗传代数
PRECI = 20; % 个体长度
GGAP = 0.95; % 代沟
px = 0.7; % 交叉概率
pm = 0.01; % 变异概率
trace = zeros(2, MAXGEN); % 寻优结果的初始值
FieldD = [PRECI;lb;ub;1;0;1;1]; % 区域描述器
Chrom = crtbp(NIND, PRECI); % 创建任意离散随机种群
% 3. 优化过程
gen = 0; % 迭代计数器
x = bs2rv(Chrom, FieldD); % 初始种群二进制到十进制转换
ObjV = sin(10*pi*x)./x; % 计算目标函数值
while gen<MAXGEN
FitnV = ranking(ObjV); % 分配适应度值
SelCh = select('sus', Chrom, FitnV, GGAP); % 选择
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
% 4. 绘制最优计算结果
plot(trace(1,:), trace(2,:), 'bo'); hold on; % 绘制出每一代最优点
grid on;
plot(x, ObjV, 'b*'); % 绘制最后一代的种群
% 5. 绘制进化图并输出最优解与最优值
% 绘制学习曲线
subplot(1,2,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'])
代码执行结果如下图所示:
计算得到的最优解与最优值如下图所示:
利用遗传算法计算如下函数的最大值:
下面选择二进制编码遗传算法,其参数设置如下表所示:
种群大小 | 最大遗传代数 | 个体长度 | 代沟 | 交叉概率 | 变异概率 |
---|---|---|---|---|---|
(个自变量,每个长) |
(
个自变量,每个长
)
% 1. 绘制求解函数
figure(1); subplot(1,2,1); hold on;
% 设置自变量范围[1,2]
lbx = -2; ubx = 2; % 函数自变量x的范围[-2,2]
lby = -2; uby = 2; % 函数自变量y的范围[-2,2]
ezmesh('y*sin(2*pi*x) + x*cos(2*pi*y)', [lbx,ubx,lby,uby],50);
hold on;
% 2. 定义遗传算法参数
NIND = 40; % 种群大小
MAXGEN = 50; % 最大的遗传代数
PRECI = 20; % 个体长度
GGAP = 0.95; % 代沟
px = 0.7; % 交叉概率
pm = 0.01; % 变异概率
trace = zeros(3, MAXGEN); % 寻优结果的初始值
FieldD = [PRECI PRECI;lbx lby;ubx uby;1 1;0 0;1 1;1 1]; % 区域描述器
Chrom = crtbp(NIND, PRECI*2); % 创建任意离散随机种群
% 3. 优化过程
gen = 0;
xy = bs2rv(Chrom, FieldD);
x = xy(:,1); y = xy(:,2);
ObjV = y.*sin(2*pi*x) + x.*cos(2*pi*y);
while gen<MAXGEN
FitnV = ranking(-ObjV);
SelCh = select('sus', Chrom, FitnV, GGAP);
SelCh = recombin('xovsp', SelCh, px);
SelCh = mut(SelCh, pm);
xy = bs2rv(SelCh, FieldD);
x = xy(:,1); y = xy(:,2);
ObjVSel = y.*sin(2*pi*x) + x.*cos(2*pi*y);
[Chrom, ObjV] = reins(Chrom, SelCh, 1, 1, ObjV, ObjVSel);
xy = bs2rv(Chrom, FieldD);
gen = gen + 1;
% 获取每代的最优解及其序号,y为最优解,i为个体序号
[y, i] = max(ObjV);
trace(1:2,gen) = xy(i,:);
trace(3,gen) = y;
end
% 4. 绘制最优计算结果
plot3(trace(1,:), trace(2,:), trace(3,:), 'bo'); hold on;
grid on;
plot3(xy(:,1), xy(:,2), ObjV, 'bo');
% 5. 绘制进化图并输出最优解与最优值
% 绘制学习曲线
subplot(1,2,2)
plot(1:MAXGEN, trace(3,:));
grid on
xlabel('遗传代数')
ylabel('解的变化')
title('进化图')
% 输出最优值与最优解
bestZ = trace(3, end);
bestY = trace(2, end);
bestX = trace(1, end);
fprintf(['最优解:\nx = ', num2str(bestX), '\ny = ', num2str(bestY), '\nZ = ', num2str(bestZ), '\n'])
代码运行解诂如下图所示:
计算得到的最优解与最优值如下图所示:
下面介绍gatbx
遗传工具箱的工具结构以及常用的遗传算法函数两方面内容。
gatbx
遗传算法工具箱的函数分类及主要相关函数如下所示:
crtbase
函数:创建基向量crtbp
函数:创建任意离散随机种群crtrp
函数:创建实之初始种群ranking
函数:基于序列的适应度分配scaling
函数:比率适应度计算reins
函数:一致随机与基于适应度的重插值rws
函数:轮盘选择select
函数:高级选择例程sus
函数:随机遍历采样recdis
函数:离散重组recint
函数:中间重组recline
函数:线性重组recmut
函数:具有变异特征的线性重组recombin
函数:高级重组算子xovdp
函数:两点交叉算子xovdprs
函数:减少代理的两点交叉xovmp
函数:通常多点交叉xovsh
函数:洗牌交叉xovshrs
函数:减少代理的洗牌交叉xovsp
函数:单点交叉xovsprs
函数:减少代理的单点交叉mut
函数:离散变异mutate
函数:高级变异函数mutbga
函数:实之变异migrate
函数:在子种群之间交换个体bs2rv
函数:二进制串到实值的转换rep
函数:矩阵的复制2.1 创建种群函数crtbp
的使用方法
功能:创建任意离散随机种群,其调用格式如下所示:
[Chrom, Lind, BaseV] = crtbp(Nind, Lind)
:创建一个大小为的随机二进制矩阵,Nind
表示种群个体的数量,Lind
为个体的长度。返回种群编码染色体Chrom
与染色体每个基因位的进制向量BaseV
,默认为二进制。
[Chrom, Lind, BaseV] = crtbp(Nind, Base)
:创建一个种群个体数量为Nind
的个体,个体的每位编码的进制数由Base
决定,Base
的列数为个体的长度。[Chrom, Lind, BaseV] = crtbp(Nind, Lind, Base)
:创建一个大小为的随机矩阵,个体各位的进制数由Base
决定,此时,输入参数Lind
可以省略,这是由于Base
的列数即为Lind
。
下面列举两个crtbp
函数的实用例子:
(1)、创建一个种群大小为
、个体长度为
的二进制随机种群的三种方法:
[Chrom, Lind, BaseV] = crtbp(5, 10)
[Chrom, Lind, BaseV] = crtbp(5, 10, [2 2 2 2 2 2 2 2 2 2])
[Chrom, Lind, BaseV] = crtbp(5, [2 2 2 2 2 2 2 2 2 2 ])
得到的输出结果如下图所示:
(2)、创建一个种群大小为
、个体长度为
,各位进制数分别为:{2,3,4,5,6,7}的种群方法:
[Chrom, Lind, BaseV] = crtbp(5, 6, [2,3,4,5,6,7])
[Chrom, Lind, BaseV] = crtbp(5, [2,3,4,5,6,7])
得到的输出结果如下图所示:
2.2 适应度计算函数ranking
的使用方法
功能:基于排序的适应度分配,其调用格式如下所示:
FitnV = ranking(ObjV)
:根据个体的目标值ObjV
(列向量)由小到大的顺序对个体进行排序,并返回个体适应度值FitnV
的列向量。FitnV = ranking(ObjV, RFun)
:RFun
包括如下三种情况:RFun(2)
参数:指定排序方法:0
表示为线性排序,1
表示非线性排序;RFun(1)
参数:对线性排序,标量指定的选择压差RFun(1)
必须在区间内;对于非线性排序,RFun(1)
必须在
区间;如果为NAN
,则RFun(1)
假设为2
。
RFun
是一个在区间内的标量,则采用线性排序,该标量指定选择的压差;
RFun
是一个具有两个参数的向量,则:RFun
是长度为length(ObjV)
的向量,则它包含对没一行的适应度值计算。FitnV = ranking(ObjV, RFun, SUBPOP)
:ObjV
、RFun
的格式与上述一致,参数SUBPOP
是一个任意参数,其知名在ObjV
中子种群的数量,默认SUBPOP=1
。在ObjV
中的所有子种群大小必须相等。如果ranking
被调用于多子种群,则ranking
独立地对每个子种群执行。考虑具有
个个体的种群,其目标函数如下所示:
ObjV = [2; 1; 5; 3; 4; 7; 10; 8; 9; 6]
下面列举三个ranking
函数的实用例子:
(1)、使用线性排序和压差为
估计适应度:
[FitnV] = ranking(ObjV)
[FitnV] = ranking(ObjV, [2,0])
[FitnV] = ranking(ObjV, [2,0], 1)
得到的输出结果如下图所示:
(2)、使用RFun
中的值计算适应度:
RFun
的值为:RFun = [10; 20; 30; 40; 50; 60; 70; 80; 90; 100]
FitnV = ranking(ObjV, RFun)
得到的输出结果如下图所示:
(3)、使用非线性排序,选择压差为
,在ObjV
中有两个子种群计算适应度:
FitnV = ranking(ObjV, [2,1], 2)
得到的结果如下图所示:
2.3 选择函数select
的使用方法
功能:从种群中选择个体(高级函数),其调用格式如下所示:
SelCh = select(SEL_F, Chrom, FitnV)
SelCh = select(SEL_F, Chrom, FitnV, GGAP)
SelCh = select(SEL_F, Chrom, FitnV, GGAP, SUBPOP)
其中:
SEL_F
是一个字符串,包含一个低级选择函数名,比如rws
(轮盘选择)、sus
(随机遍历采样);FitnV
是列向量,包含种群Chrom中个体的适应度值,该适应度值表明每个个体被选择的期望概率;GGAP
是一个可选参数,表示代沟部分种群被复制,默认值为;
SUBPOP
是一个可选参数,决定Chrom中子种群的数量,默认为,Chrom中所有种群必须有相同的大小。
下面列举一个select
函数的实用例子,考虑具有
个个体的种群Chrom,适应度值为FitnV:
构造一个个体数量为
个个体、每个个体长度为
的种群Chrom,且每个个体的适应为FitnV:
Chrom = [1 32 41; 2 43 12; 5 3 1; 56 11 78; 3 31 26; 14 67 86; 74 14 52; 10 91 19]FitnV = [1.8; 1.65; 1.35; 1.19; 0.94; 0.83; 0.68; 0.51]
下面使用随机遍历抽样方式(sus
)选择
个个体,代码如下所示:
SelCh = select('sus', Chrom, FitnV)
代码执行结果如下图所示:
2.4 交叉算子函数recombin
的使用方法
功能:重组个体(高级函数),recombin
完成种群Chrom
中个体的重组,在心的种群NewChrom
中返回重组后的个体。Chrom
与NewChrom
中的一行对应一个个体,其调用格式如下所示:
NewChrom = recombin(REC_F, Chrom)
NewChrom = recombin(REC_F, Chrom, RecOpt)
NewChrom = recombin(REC_F, Chrom, RecOpt, SUBPOP)
其中:
REC_F
是一个包含低级重组函数名的字符串,比如recdis
(离散重组)、xovsp
(单点交叉);RecOpt
是一个知名交叉概率的任选参数;SUBPOP
是一个可选参数,决定Chrom中子种群的数量,默认为,Chrom中所有种群必须有相同的大小。
下面列举一个recombin
函数的实用例子,对
个个体的种群进行重组:
使用crtbp
函数构造一个包含
个个体、每个个体长度为
二进制种群:
Chrom = crtbp(5, 10)
通过下面指令对种群进行重组:
NewChrom = recombin('xovsp', Chrom)
代码执行结果如下图所示:
Chrom
:NewChrom
:2.5 变异算子函数mut
的使用方法
功能:离散变异算子,其调用格式如下所示:
NewChrom = mut(OldChrom, Pm, BaseV)
其中,OldChrom
为当前种群,Pm
为变异概率(默认值为
),BaseV
表示染色体个体元素的进制数(默认为二进制编码)。
下面列举一个mut
函数的实用例子,使用mut
对当前种群进行变异得到心的种群:
首先使用crtbp
函数构造一个长度为
,个体数目为6的随机种群:BaseV = [10 10 10 8 8 8 2 2][Chrom, Lind, BaseV] = crtbp(6, BaseV)
使用mut
对Chrom
进行变异得到新的种群NewChrom
:
NewChrom = mut(Chrom, 0.7, BaseV)
代码执行结果如下图所示:
Chrom
:NewChrom
:2.6 重插入函数reins
的使用方法
功能:重插入子代到种群,并用子代代替父代,最终返回结果种群,Chrom
为父代种群,SelCh
为子代,没一行对应一个个体,其调用格式如下所示:
Chrom = reins(Chrom, SelCh)
Chrom = reins(Chrom, SelCh, SUBPOP)
Chrom = reins(Chrom, SelCh, SUBPOP, InsOpt, ObjVCh)
Chrom = reins(Chrom, SelCh, SUBPOP, InsOpt, ObjVCh, ObjVSel)
其中,
SUBPOP
:为一个可选参数,表示Chrom
和SelCh
中子种群的个数,默认值为1,另外Chrom和SelCh中每个子种群必须具有相同的大小;InsOpt
:为一个最多有两个参数的向量:InsOpt(1)
是一个标量,表示用子代代替父代的方法:表示均匀选择,子代代替父代使用均匀随机选择;
表示基于适应度的选择,子代代替父代中适应度最小的个体,其默认值为
;
InsOpt(2)
是一个在区间的标量,表示每个子种群中插入的子代个体在整个子种群中个体的比率,默认为
;
ObjVCh
是对于基于适应度重插入方法的一个可选列向量,包含Chrom中个体的目标值;ObjVSel
是一个包含SelCh
中个体的目标值的可选参数,如果子代的数量大于重插入种群中的子代数量,则ObjVSel
是必需的,这种情况子代将按他们的适应度大小选择插入。下面列举一个reins
函数的实用例子:
首先使用crtbp
函数构造一个长度为
,个体数目为5的随机二进制父代种群Chrom
与一个长度为
,个体数目为
二进制子代种群SelCh
:Chrom = crtbp(5, 10)SelCh = crtbp(2, 10)
然后使用reins
方法,重插入子代SelCh
到种群Chrom
中:
Chrom = reins(Chrom, SelCh)
2.7 实用函数bs2rv
的使用方法
功能:二进制到十进制的转换,bs2rv
根据译码矩阵FieldD
将二进制串矩阵Chrom
转换为实值向量,并返回十进制的矩阵,其调用格式如下所示:
Phen = bs2rv(Chrom, FieldD)
其中,FieldD
矩阵的结构如下所示:
其中,
len
表示在Chrom
中的每个子串的长度;lb
与ub
分别表示每个变量的下界与上界;code
表示子串是怎样编码的,表示标准的二进制编码,
表示格雷编码;
scale
表示每个子串所使用的刻度,表示算数刻度,
表示对数刻度;
lbin
与ubin
表示范围中是否包含边界,表示不包含边界,
表示包含边界。
下面列举一个bs2rv
函数的实用例子:
首先使用crtbp
构造二进制种群Chrom
,表示在
区间的一组简单变量,然后使用bs2rv
将二进制串转换为实值表现型。
Chrom = crtbp(4, 8) % 创建二进制串FieldD = [size(Chrom, 2); -1;10;1;0;1;1]; % 包含边界Phen = bs2rv(Chrom, FieldD) % 转换二进制到十进制
2.8 实用函数rep
的使用方法
功能:矩阵复制,完成矩阵MatIn
的复制,REPN
表示复制次数,返回复制后的矩阵MatOut
:
MatOut = rep(MatIn, REPN)
其中,REPN
包含每个方向复制的次数,REPN(1)
表示纵向复制次数;REPN(2)
表示水平方向复制次数。
下面列举一个rep
函数的实用例子:
MatIn = [1 1 1 1; 2 2 2 2]MatOut = rep(MatIn, [1,2])
代码执行结果如下图所示: