人工智能算法：基于Matlab遗传算法的实现示例

!! ✨ Matlab版本为R2022b，与以前的版本兼容。

一、遗传算法的理论基础

作为一种进化算法，遗传算法（GA, Genetic Algorithm）的基本原理是将问题参数编码为染色体，进而利用优化迭代的方法进行选择、交叉和变异算子操作来交换种群中染色体的信息，最终生成符合优化目标的染色体。

为了更好地理解与运用遗传算法解决实际问题，我们首先需要理解如下四个专业术语：

• （1）染色体：在遗传算法中，染色体通常是由一维串状结构数据（数据或数组）来表示，且串上各个位置对应基因的值。基因组成的串就是染色体，也就是我们常说的基因型个体（Individuals）；
• （2）群体：一定数量的个体组成了群体（Population）；
• （3）群体大小：群体中个体的数目称为群体大小（Population Size），也成为群体规模；
• （4）适应度：各个个体对环境的适应度程度成为适应度（Fitness）。

遗传算法的基本步骤如下所示：

• 1、编码：遗传算法在进行最优解搜索之前，会将解空间的解数据表示为遗传空间的基因型串结构数据。
• 2、群体的初始化：随机生成

个初始串结构数据，其中每一个串结构数据为一个个体，

个个体便构成了一个群体。

• 3、适应度评估：表明个体或解的优劣性，不同的问题，适应度函数的定义不同；
• 4、选择：从当前群体中选择出优良的个体，进而作为父代为下一代繁衍子孙；
• 5、交叉：其是遗传算法中最重要的遗传操作，通过交叉操作可以得到新一代个体，新个体组合其父代的个体特性；
• 6、变异：在群体中随机选择一个个体，对其中个体以一定概率随机的改变串结构数据中某个基因值。

二、遗传算法工具箱gatbx的安装

通过百度网盘下载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应用实例

3.1 一元函数优化

利用遗传算法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'])

代码执行结果如下图所示：

计算得到的最优解与最优值如下图所示：

3.2 多元函数优化

利用遗传算法计算如下函数的最大值：

下面选择二进制编码遗传算法，其参数设置如下表所示：

(

个自变量，每个长

)

% 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遗传工具箱的工具结构以及常用的遗传算法函数两方面内容。

1. gatbx遗传工具箱的结构

gatbx遗传算法工具箱的函数分类及主要相关函数如下所示：

• 1、创建种群函数：
  • (1) crtbase函数：创建基向量
  • (2) crtbp函数：创建任意离散随机种群
  • (3) crtrp函数：创建实之初始种群
• 2、适应度计算：
  • (1) ranking函数：基于序列的适应度分配
  • (2) scaling函数：比率适应度计算
• 3、选择函数：
  • (1) reins函数：一致随机与基于适应度的重插值
  • (2) rws函数：轮盘选择
  • (3) select函数：高级选择例程
  • (4) sus函数：随机遍历采样
• 4、交叉算子：
  • (1) recdis函数：离散重组
  • (2) recint函数：中间重组
  • (3) recline函数：线性重组
  • (4) recmut函数：具有变异特征的线性重组
  • (5) recombin函数：高级重组算子
  • (6) xovdp函数：两点交叉算子
  • (7) xovdprs函数：减少代理的两点交叉
  • (8) xovmp函数：通常多点交叉
  • (9) xovsh函数：洗牌交叉
  • (10) xovshrs函数：减少代理的洗牌交叉
  • (11) xovsp函数：单点交叉
  • (12) xovsprs函数：减少代理的单点交叉
• 5、变异算子：
  • (1) mut函数：离散变异
  • (2) mutate函数：高级变异函数
  • (3) mutbga函数：实之变异
• 6、子种群的支持：
  • migrate函数：在子种群之间交换个体
• 7、实用函数：
  • (1) bs2rv函数：二进制串到实值的转换
  • (2) rep函数：矩阵的复制

2. gatbx遗传工具箱常用函数

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)必须在

  [1,2]

  区间内；对于非线性排序，RFun(1)必须在

  [1,length(ObjV)-2]

  区间；如果为NAN,则RFun(1)假设为2。

  • 如果RFun是一个在

  [1,2]

  区间内的标量，则采用线性排序，该标量指定选择的压差；

  • 如果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)是一个标量，表示用子代代替父代的方法：

  0

  表示均匀选择，子代代替父代使用均匀随机选择；

  1

  表示基于适应度的选择，子代代替父代中适应度最小的个体，其默认值为

  0

  ；

  • InsOpt(2)是一个在

  [0,1]

  区间的标量，表示每个子种群中插入的子代个体在整个子种群中个体的比率，默认为

  1

  ；

• 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])

代码执行结果如下图所示：