作为一种进化算法,遗传算法(GA, Genetic Algorithm)的基本原理是将问题参数编码为染色体,进而利用优化迭代的方法进行选择、交叉和变异算子操作来交换种群中染色体的信息,最终生成符合优化目标的染色体。
为了更好地理解与运用遗传算法解决实际问题,结合求解如下所示二元函数的最小值为例,理解如下相关专业术语:
就是以个体,即
。
就是一个适应度函数。适应度函数值表示一个代优化问题一个解对应的函数值。比如,对于上面的适应度函数
的一个解
,对应的适应度函数值为
。因此,对于求解最小值的优化问题,某个个体的适应度数值越小,则该个体(解)越适应环境。
行
列的种群,
表示种群的大小,
表示适应度函数的自变量个数。以上面的问题为例,矩阵
则表示一个大小为
的种群,其个体依次为
。
之间的数,表示子代中由交叉产生的个体占父代中非精英个体的比例。比如,如果种群大小为
,精英数目为
,交叉后代比例是
,那么在子代中,将有
个保留的精英,则由交叉产生的后代将有
即
个。
本文使用Matlab子代的遗传算法工具箱GADST
,该工具箱目前已经继承到Global Optimization Toolbox中。该部分主要介绍如何使用该工具箱,具体使用细节可以参考本文第三部分。
该小节使用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)以黑色线条表示。
当种群进化结束后,可以得到如上图第二个图片所示的最优个体的值
,则对应的最优适应度函数值为
。最优个体的值存储在x_best
变量中,最优适应度函数值存储在fval
变量中。
GADST遗传工具箱目前已经继承到Global Optimization Toolbox中,我们可以很方便地通过GUI界面或者命令行方式在Matlab中实现遗传算法,其位置在Matlab安装目录的/toolbox/globaloptim
文件夹中。GADST
是一个函数库,其中包含了遗传算法的主函数、各个子函数和一些绘图函数。GADST
的组织结构及各个函数之间的关系如下图所示:
由上图可以看出,GADST
的主函数为ga
,gacommon
函数可以确定优化问题的类型,ga
进而分别调用如下三个函数:
gaunc
函数:求解无约束优化问题;galincon
函数:求解线性约束优化问题;gacon
函数:求解非线性约束优化问题。遗传算法使用函数makeState
函数产生初始种群,然后判断是否退出算法,如果退出,则得到最优个体;如果不退出,则调用stepGA
函数使得种群进化到下一代,同时调用gadsplot
函数与isItTimeToStop
函数分别进行绘图与判断终止条件。
使用GADST
实现遗传算法非常简单只需要了解如下两个函数:
gaoptimset
函数:遗传算法参数设定函数;ga
函数:遗传算法实现函数。1、gaoptimset函数
调用方法如下所示:
options = gaoptimset('Param', value, ...);
其中,Param等是需要设定参数,常用的设置参数如下所示:
PopulationSize
:种群包含个体数目;EliteCount
:种群中精英个体数目;CrossoverFraction
:交叉后代比率;Generations
:迭代代数;StallGenLimit
:终止迭代代数;TolFun
:适应度函数偏差;PlotFcns
:绘图结果句柄:@gaplotbestf
:绘制最优适应度函数值;@gaplotbestindiv
:绘制最优个体值。2、ga函数
函数调用方法如下所示:
[x_best, fval] = ga(fitnessfcn, nvars, A, b, Aeq, beq, lb, ub, nonlcon, options);
其中,
ga
函数返回值:x_best
:遗传算法得到的最优个体;fval
:最优个体x_best
对应的适应度函数值;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
函数所设置的参数。