gatbx遗传算法工具箱之gaSVMcgForClass详细例子讲解

遗传算法

1. 遗传算法的简单原理

遗传算法(Genetic Algorithm, GA)是一种基于自然群体遗传演化机制的高效

探索算法，它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。

我们先通过一个例子来了解遗传算法的原理： 假定我们要求函数f(x)?x2的极大值，其中x为自然数，0?x?31。现在，我们将每一个数看成一个生命体，通过进化，我们看谁能最后生存下来，谁就是我们所寻找的数。

①．编码:我们将每一个数作为一个生命体，那么必须给其赋予一定的基因，这个过程叫做编码。我们可以把变量x编码成5位长的二进制无符号整数表示形式，比如x?13可表示为01101的形式，也就是说，数13的基因为01101。

②．初始群体的生成: 由于遗传的需要，我们必须设定一些初始的生物群体，让其作为生物繁殖的第一代，需要说明的是，初始群体的每个个体都是通过随机方法产生的，这样便可以保证生物的多样性和竞争的公平性。

③．适应度评估检测: 生物的进化服从适者生存，优胜劣汰的进化规则，因此，我们必须规定什么样的基因是“优”的，什么样的基因是“劣”的，在这里，我们称为适应度。显然，由于我们要求的最大值，因此，能使函数值较大的基因是优的，．．．使函数值较小的基因是劣的，因此，我们可以将原函数f(x)?x2定义为适应度函数，用来衡量某一生物体的适应程度。

④．选择：接下来，我们便可以进行优胜劣汰的过程，这个过程在遗传算法里叫做选择。注意，选择应该是一个随机的过程，基因差的生物体不一定会被淘汰，只是其被淘汰概率比较大罢了，这与自然界中的规律是相同的。因此，我们可以采取赌轮的方式来进行选择。

⑤．交叉操作：接下来进行交叉繁殖，随机选出两个生物体，让其交换一部分基因，这样便形成了两个新的生物体，为第二代。

⑥．变异：生物界中不但存在着遗传，同时还存在着变异，在这里我们也引入变异，使生物体的基因中的某一位以一定的概率发生变化，这样引入适当的扰动，能避免局部极值的问题。

以上的算法便是最简单的遗传算法，通过以上步骤不断地进化，生物体的基因便逐渐地趋向最优，最后便能得到我们想要的结果。

2． 遗传算法的步骤

1

从上面的例子中，我们便能得到遗传算法的一般步骤，如下图所示：

3． 遗传算法的应用

遗传算法主要是用来寻优，它具有很多优点：它能有效地避

免局部最优现象，有及其顽强的鲁棒性，并且在寻优过程中，基本不需要任何搜索空间的知识和其他辅助信息等等。为了介绍遗传算法的应用，我们将前面的例子进行完，整个过程如下：

初始群体 01101 11000 01000 10011 x的值 13 24 8 19 适应度f(x) 169 576 64 361 选择概率 0.14 0.49 0.06 0.31 选择上的计数（来自赌轮） 1 2 0 1

2

交叉处 0110|1 1100|0 11|000 10|011 下一代群体 01100 11001 11011 10000 x的值 12 25 27 16 适应度 144 625 729 256

求解过程：将自变量在给定的范围内进行编码，得到种群编码，按照所选择的适应度函数并通过选择复制，交叉重组与变异对个体进行筛选与进化，使适应度值大的个体被保留，适应度小的个体被淘汰，新的群体继承了上一代的信息，同时又优于上一代，这样反复循环，直到满足条件，最后留下来的个体集中分布在最优解周围，筛选出其中的个体作为问题的解。

4．遗传算法的程序设计

（1）谢尔菲德遗传算法工具箱----英国谢尔菲德大学开发

①特点：1）使用MATLAB高级语言编写；

2）对问题使用M文件编写，可以看见源代码； 3）为用户提供了广泛多样的实用函数。

②安装：1）解压谢尔菲德遗传算法工具箱，得到谢尔菲德遗传算法工具箱文件夹，内含DOC文件夹与gatbx文件夹；

2）将谢尔菲德遗传算法工具箱文件夹拷贝到MATLAB\\bin目录下；

3）为谢尔菲德遗传算法工具箱文件设置工作路径：双击MATLAB，运行MATLAB，在MATLAB窗口中选择路径设置窗口：Set path； 4)在Set path中选择 Add folder项； 5）设置如下： …\\谢尔菲德遗传算法工具箱文件； …\\谢尔菲德遗传算法工具箱文件\\DOC； …\\谢尔菲德遗传算法工具箱文件\\gatbx；

…\\谢尔菲德遗传算法工具箱文件\\gatbx\\test_fns。 点击SAVE保存，再点击CLOSE关闭Set path窗口。

6）将文件夹的所有字母改为小写字母。

7）测试：在Command Window窗口键入：help crtbp。

③谢尔菲德遗传算法工具箱中主要函数

函数分类 创建 种群 适应度计算 函数 crtbase crtbp crtrp ranking scaling 功能 创建基向量 创建离散的随机种群 创建实数随机种群 基于排序的适应度分配 比率适应度计算 3

选择函数 交叉算子 变异算子 子种群的支持 实用函数 reins rws select sus recdis recint recline recmut recombin xovdp xovdprs xovmp xovsh xovshrs xovsp xovsprs mut mutate mutbga migrate bs2rv rep 一致随机和基于适应度的重插入 轮盘选择 高级选择例程 随即便利采样 高级重组 中间重组 线性重组 具有变异特征的线性重组 高级重组算子 两点交叉算子 减少代理的两点交叉 通常多点交叉 洗牌交叉 减少代理的洗牌交叉 单点交叉 减少代理的单点交叉 离散变异 高级变异函数 实值变异 在子种群间交换个体 二进制串到实值的转换 矩阵的复制 ④常用函数

1．创建离散的随机种群

[Chrom, Lind,BaseV]=crtbp(Nind,Lind) [Chrom, Lind,BaseV]=crtbp(Nind,Base)

[Chrom, Lind,BaseV]=crtbp(Nind,Lind,Base) （注意：Base 的列数就是Lind,即染色体的长度） [Chrom, Lind,BaseV]=crtbp(5，10)

[Chrom, Lind,BaseV]=crtbp(5，[2 3 4 5 6 7 8 9]) 2．适应度计算函数 FitnV=ranking(ObjV) 3.选择算子select 4.交叉算子recombin 5.变异算子mut 6.重插入函数reins 7.实用函数bs2rv

Phen=bs2rv(Chrom,FieldD),其中

FieldD=[len;lb;ub;code;scale;lbin;ubin] 8.实用函数rep

4