Matlab遗传算法工具箱（GADST）使用指南

Matlab遗传算法工具箱（GADST）使用指南

遗传算法（GA, Genetic Algorithm）是一种进化算法，其基本原理是将问题参数编码为染色体，进而利用优化迭代的方法进行选择、交叉和变异算子操作来交换种群中染色体的信息，最终生成符合优化目标的染色体。本文将详细介绍遗传算法的理论基础，并通过Matlab遗传算法工具箱（GADST）实现遗传算法的具体应用。

一、遗传算法的理论基础

为了更好地理解与运用遗传算法解决实际问题，结合求解如下所示二元函数的最小值为例，理解如下相关专业术语：

f(x_1, x_2) = (x_1+1)^2 + (2x_2-3)^2

• （1）个体（Individual）：个体就是问题的一个解，比如上式的
  (1,2)
  就是以个体，即
  x_1=1,x_2=2
  。

• （2）适应度函数（Fitness Function）与适应度函数值（Fitness Value）：适应度函数就是待优化的函数，比如上面的二元函数
  f(x_1, x_2)
  就是一个适应度函数。适应度函数值表示一个代优化问题一个解对应的函数值。比如，对于上面的适应度函数
  f(x_1,x_2)
  的一个解
  (1,2)
  ，对应的适应度函数值为
  f(1,2)=(1+1)^2+(2\times 2 -3)^2 = 5
  。因此，对于求解最小值的优化问题，某个个体的适应度数值越小，则该个体（解）越适应环境。

• （3）种群（Population）与种群大小（Population Size）：种群是由若干个体组成的集合；种群大小就是一个和种群所包含个体的数量，对于
  n
  行
  m
  列的种群，
  n
  表示种群的大小，
  m
  表示适应度函数的自变量个数。以上面的问题为例，矩阵
  [1,2;3,4;5,6;7,8;9,10]
  则表示一个大小为
  5
  的种群，其个体依次为
  (1,2)、(3,4)、(5,6)、(7,8)、(9,10)
  。

• （4）代（Generation）、父代（Parents）与子代（Children）：遗传算法作为一种迭代优化算法，每次迭代产生的新种群就是新的一代；子代为遗传算法每次迭代产生的新种群，而父代则为产生子代的种群。

• （5）选择（Selection）、交叉（Crossover）与变异（Mutation）：

• 选择：选取种群中适应度函数值较小的若干个体作为父代，进而作为父代为下一代繁衍子孙。对于适应度函数值太大的个体表示不适应环境，则会被淘汰；

• 交叉：是遗传算法中最重要的遗传操作，通过交叉操作可以得到新一代个体，新个体组合其父代的个体特性；

• 变异：在群体中随机选择一个个体，对其中个体以一定概率随机的改变串结构数据中某个基因值。

• （6）精英数目（EliteCount）与交叉后代比例（Crossover Fraction）：

• 精英数目：表示某个种群中适应度函数值最低的若干个体，为了保证算法收敛性，遗传算法采用精英保留策略，即父代中的精英直接传给子代，而不经过交叉与变异操作；

• 交叉后代比例：为一个
  (0,1)
  之间的数，表示子代中由交叉产生的个体占父代中非精英个体的比例。比如，如果种群大小为
  20
  ，精英数目为
  2
  ，交叉后代比例是
  0.8
  ，那么在子代中，将有
  2
  个保留的精英，则由交叉产生的后代将有
  (20-2) \times 0.8 = 14.4
  即
  14
  个。

二、使用GADST工具箱实现遗传算法实例

本文使用Matlab子代的遗传算法工具箱
GADST
，该工具箱目前已经继承到Global Optimization Toolbox中。该部分主要介绍如何使用该工具箱，具体使用细节可以参考本文第三部分。

2.1 问题描述

该小节使用
GADST
求解如下所示的非线性方程组：

\begin{cases} 4x_1^3 + 4x_1x_2 + 2x_2^2 - 42x_1 - 14 = 0 \newline 4x_2^3 + 4x_1x_2 + 2x_1^2 - 26x_1 - 22 = 0 \end{cases}

为了能够使用遗传算法，将上面的非线性方程组的求解转化为求解函数最小值的问题，如下所示：

\begin{cases} f_1(x_1,x_2) = 4x_1^3 + 4x_1x_2 + 2x_2^2 - 42x_1 - 14 \newline f_2(x_1,x_2) = 4x_2^3 + 4x_1x_2 + 2x_1^2 - 26x_1 - 22 \newline {\rm min} f(x_1,x_2) = f_1^2(x_1,x_2) + f_2^2(x_1,x_2) \end{cases}

2.2 基于GADST工具箱实现遗传算法的实现

本小节基于
GADST
工具箱实现遗传算法求解2.1部分的问题。

1、目标函数M文件编写

使用
GADST
求解优化问题首先需要编写适应度函数的M文件。对于上面的问题适应度函数
GA_FitFun.m
如下所示：

function f = GA_FitFun(x)
% 自适应度函数：待优化的目标函数
f1 = 4 * x(1).^3 + 4 * x(1) * x(2) + 2 * x(2).^2 - 42 * x(1) - 14;
f2 = 4 * x(2).^3 + 4 * x(1) * x(2) + 2 * x(1).^2 - 26 * x(1) - 22;
f = f1.^2 + f2.^2;
end

编写好适应度函数M文件后，就可以使用
GADST
工具箱使用遗传进行优化了。

2、遗传算法代码编写

具体的参数含义可以参考本文第三部分。

fitness_fun = @GA_FitFun;    % 适应度函数句柄
nvars = 2;                   % 个体所包含的变量数目
% 下面设置参数
options = gaoptimset('PopulationSize', 100, ...     % 种群包含个体数目
                     'EliteCount', 10, ...          % 种群中精英个体数目
                     'CrossoverFraction', 0.75, ... % 交叉后代比率
                     'Generations', 500, ...        % 迭代代数
                     'StallGenLimit', 500, ...      % 停止代数
                     'TolFun', 1e-100, ...          % 适应度函数偏差
                     'PlotFcns', {@gaplotbestf, @gaplotbestindiv}); % 绘制最优个体适应度函数与最优个体
% 调用函数ga，计算最优解x_best与最优值fval
[x_best, fval] = ga(fitness_fun, nvars, [], [], [], [], [], [], [], options);

注意：适应度函数
GA_FitFun.m
文件必须在当前目录文件内。

3、结果分析

在遗传算法的运行过程，
GADST
调用
gadsplot
函数绘制名为
Genetic Algorithm
的图，且随着种群不断进化，该图也实时更新。当遗传算法完成时，得到如下图所示的最优个体适应度函数值变化曲线及最优个体。

上图中第一个图片最优个体适应度函数变化曲线的横坐标为进化代数（Generation），纵坐标为适应度函数值包括：种群的平均适应度函数值（Mean fitness）以蓝色点表示；最优个体对应的适应度函数值（Best fitness）以黑色线条表示。

当种群进化结束后，可以得到如上图第二个图片所示的最优个体的值
[2.8917, 2.3698]
，则对应的最优适应度函数值为

0.0429
。最优个体的值存储在
x_best
变量中，最优适应度函数值存储在
fval
变量中。

三、GADST遗传算法工具箱用法

3.1 GADST遗传工具箱简介

GADST遗传工具箱目前已经继承到Global Optimization Toolbox中，我们可以很方便地通过GUI界面或者命令行方式在Matlab中实现遗传算法，其位置在Matlab安装目录的
/toolbox/globaloptim
文件夹中。

GADST
是一个函数库，其中包含了遗传算法的主函数、各个子函数和一些绘图函数。
GADST
的组织结构及各个函数之间的关系如下图所示：

由上图可以看出，
GADST
的主函数为
ga
，
gacommon
函数可以确定优化问题的类型，
ga
进而分别调用如下三个函数：

• gaunc
  函数：求解无约束优化问题；
• galincon
  函数：求解线性约束优化问题；
• gacon
  函数：求解非线性约束优化问题。

遗传算法使用函数
makeState
函数产生初始种群，然后判断是否退出算法，如果退出，则得到最优个体；如果不退出，则调用
stepGA
函数使得种群进化到下一代，同时调用
gadsplot
函数与
isItTimeToStop
函数分别进行绘图与判断终止条件。

3.2 GADST函数命令行使用方法

使用
GADST
实现遗传算法非常简单只需要了解如下两个函数：

• gaoptimset
  函数：遗传算法参数设定函数；
• ga
  函数：遗传算法实现函数。

1、gaoptimset函数

调用方法如下所示：

options = gaoptimset('Param', value, ...);

其中，Param等是需要设定参数，常用的设置参数如下所示：

• （1）
  PopulationSize
  ：种群包含个体数目；
• （2）
  EliteCount
  ：种群中精英个体数目；
• （3）
  CrossoverFraction
  ：交叉后代比率；
• （4）
  Generations
  ：迭代代数；
• （5）
  StallGenLimit
  ：终止迭代代数；
• （6）
  TolFun
  ：适应度函数偏差；
• （7）
  PlotFcns
  ：绘图结果句柄：
• @gaplotbestf
  ：绘制最优适应度函数值；
• @gaplotbestindiv
  ：绘制最优个体值。

2、ga函数

函数调用方法如下所示：

[x_best, fval] = ga(fitnessfcn, nvars, A, b, Aeq, beq, lb, ub, nonlcon, options);

其中，

• （1）
  ga
  函数返回值：
• x_best
  ：遗传算法得到的最优个体；
• fval
  ：最优个体
  x_best
  对应的适应度函数值；
• （2）
  ga
  函数的输入参数：
• fitnessfcn
  ：适应度函数句柄；
• nvars
  ：变量数目；
• A、b、Aeq、beq
  ：线性约束，可以表示为
  A*X <= b, Aeq * X = beq;
  ；
• lb、ub
  ：为上下限约束，可以表述为
  lb<=X<=ub
  ；
• nonlcon
  ：为非线性约束，需要使用M文件编写，该M文件返回的是
  C
  和
  Ceq
  ，非线性约束可以表示为
  C(X)<=0, Ceq(X)=0
  。当没有约束时可使用
  []
  表示；
• options
  ：为
  gaoptimset
  函数所设置的参数。