MATLAB遗传算法工具箱GADS优化及应用

郭海双，梁佳雯，张劭昀

（1.贵州师范大学 数学与计算机学院，贵州 贵阳550001；2.贵州师范大学 物理与电子科学学院，贵州 贵阳 550001）

MATLAB遗传算法工具箱GADS优化及应用

郭海双1，梁佳雯1，张劭昀2

（1.贵州师范大学 数学与计算机学院，贵州 贵阳550001；2.贵州师范大学 物理与电子科学学院，贵州 贵阳 550001）

为了解决复杂函数优化问题，简要对MATLAB遗传算法工具箱进行了介绍，并详细阐述了遗传算法的基本原理与方法，在此基础之上，介绍了MATLAB遗传算法工具箱GADS寻找最优值的工作过程，最后，结合测试函数，介绍了遗传算法工具箱编码方法，并验证了MATLAB遗传算法工具箱操作简单方便，具有较高可靠性的优点，为解决函数优化问题提供了一种强有力的工具。

遗传算法；优化；工具箱；MATLAB；GADS

遗传算法是对生物系统所进行的计算机模拟研究，最早是由美国密歇根大学的Holland教授首先提出来的优化方法，它是一种建立在自然选择和群体遗传学基础上的随机、迭代、进化的全局搜索方法，GA搜索以达尔文适者生存和随机信息交换为主旋律，根据评价函数消除适应度值低的解，利用原有解中的知识加快搜索过程，遗传算法具有鲁棒性强、效率高、多点并行搜索的优点，应用广泛，渗透到研究与应用的各个领域，如机器学习、规划设计、图像处理、人工生命、自动控制等科技领域[1]，并取得了良好的效果，最近吸引人眼球的是其在人工智能和人工生命领域的研究。

遗传算法的应用过程中需要编制大量的程序，这给无计算机编程基础的人员带来困难，作为使用者总希望有一个现成的程序框架，而matlab遗传算法工具箱正好满足这一要求,基于MATLAB的遗传算法工具箱主要有3种，出现较早较为完备的英国谢菲尔德(Sheffield)大学开发的GATBX，美国北卡罗莱纳州立大学开发的遗传算法优化工具箱GAOT，最近影响力较大的美国MathWork公司开发的MATLAB遗传算法与直接搜索工具箱GADS[2]，前两个工具箱在使用过程中都需要下载安装在matlab软件上，GADS在MATLAB7.0版本以后不需要，它是自带的，GADS扩展了优化工具箱和MATLAB数值计算环境的性能，应用较广泛，这些工具箱都是由实现特定优化算法的MATLAB语句写成的M文件，是一系列函数的集合[3]。

本文首先介绍了遗传算法的基本原理与方法，然后对MATLAB工具箱GADS进行了研究，详细叙述了GADS优化过程，并用二维函数证明了遗传算法工具箱的优越性。

1 遗传算法的基本原理与方法

遗传算法是按照生物界自然选择原理和自然遗传机理形成的一种迭代式自适应搜索算法，具有简单易懂、通用、鲁棒性强、并行处理的特点，适合解决各种优化问题，遗传算法在解决问题时将所有解看作是群体当中的一个个体或染色体，通过把每一个个体编码进行生物上的遗传、交叉和变异操作，模拟达尔文的生物进化过程，对群体反复进行循环操作，根据目标适应度函数评价，依据适者生存、优胜劣汰的进化规则进行筛选更新群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，以求得满足要求的最优解[4]。遗传算法基本流程如图1所示。

遗传算法主要流程：

1)编 码

是通过某种编码机制，把对象抽象为由特定符号排成的串，确定相应的编码方法，并产生一个确定长度的M个染色体组成的初始群体，基因值可用均匀分布的随机数来生成，例如二进制符号串编码[3]，其等位基因是由二值符号集{0,1}组成，串的长度取决于所求问题的精度，变量X1的区间是[a1, b1],X2的区间是[a2,b2],精度是小数点后三位，那么每个变量应该被分成至少(b1-a1)*103个部分，二进制串位数也就是染色体长度计算公式如下：

图1 遗传算法基本流程图Fig.1 The basic flowchart of genetic algorithms

染色体串长度是：

从二进制串返回一个实际的值，可用下面公式来实现：

其中decimal(substring si)是求二进制串转化的十进制值，substring si是已知的二进制串。

由于本文处理的是二维函数，采用二进制编码，具有较大的Hamming距离，染色体串长，算法效率低，所以采用实数编码，编码长度等于变量个数，个体的基因值与某一范围内的实数相对应，可以表示较大范围的数，精度高，便于处理优化多变量问题[5]。

2)确定个体评价方案

对群体中的每一个染色体计算它的适应度。

适应度，根据目标函数大小评定个体优劣的标准,适应度越大，个体越好，适应度越小，个体越差，适应度值总取非负值。例如线性排序的适应度函数，适应度值只取决于排序的位序，求目标函数最小值，目标函数值最小则分配的适应度值最大，被选出的概率越大，反之则分配的适应度值最小，最小值设定为0，保证适应度函数取值非负的条件。

3)判断是否满足收敛准则

若满足，则输出搜索结果，不满足，则继续执行以下操作。

4)选择

根据“适者生存”的自然选择原理，按照某种策略从父代中挑选个体进入下一代，如比例选择，单个个体被选中的概率等于单个个体适应度值与所有个体适应度之和的比。

5)交叉

模拟有性繁殖的基因重组操作，从种群中选择的每一对父代，以一定的交叉概率完成部分基因的交换，得到一个有N个染色体组成的群体。

6)变异

用某一较小的概率使染色体的基因发生变异，形成新种群，继续进行遗传操作。

交叉和变异操作都是为了得到新个体而进行的基因重组。

遗传算法形式上简单明了，具有显著的隐并行性和适应性，直接处理的对象是参数的编码而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有优化函数必须可导的要求[5]。

2 GADS寻优过程

使用遗传算法对函数进行优化，必须要编制大量的程序，如选择、杂交、变异等过程，这些都是针对染色体进行的，染色体实质是一个向量，而MATLAB处理数值运算的强大能力使得利用MATLAB编程可以节省大量的时间和精力。

GADS具有如下特点：

1)良好的图形用户界面，操作简单舒适，可以快速设置算法参数和观测运行进程。

2)参数提供多个选项，便于解决实际问题。

3)实现模式搜索，可定义网格大小，提供完全表决的搜索方式。

4)与其他程序语言兼容，如C,C++.

5)编写好目标文件后支持自动生成代码，免去繁琐的遗传算法编程描述。

遗传算法总是使目标函数或适应度函数最小化，如果想要求出函数f(x)的最大值，可以转而求取函数g(x)=-f(x)的最小值，因为g(x)最小值出现的地方与函数f(x)最大值出现的地方相同[3]。求测试函数Schaffer函数最大值：

该函数是一个多峰函数，有无数个局部极大点，但只有1个全局最大点，在点(0,0)处，最大值为1，此函数的最大峰周围有两圈脊，它们的取值分别为0.990 284和0.962 776，因此优化过程极易陷入局部最大值点[6-7]，其几何特性如图2所示。

图2 Schaffer函数几何特性图Fig.2 The geometry fig of Schaffer function

MATLAB遗传算法工具箱可以轻松快速的解决这一问题，为了使用遗传算法工具箱，首先必须编写一个M文件，来描述想要优化的函数，并且把写好的M文件保存在工作目录下[3]。该M文件代码如下所示：

运用遗传算法GADS的图形用户界面GUI对函数优化。在MATLAB工作窗口输入gatool,打开遗传算法工具，界面如图3所示。

图3 遗传算法工具图形界面Fig.3 Genetic algorithm tool graphical interface

输入Schaffer函数作为适应度函数，变量个数设置为2。

gatool使用参数介绍[3]：

1)Fitness function：欲求最小值的目标函数。在此输入编写好的M文件，格式：@fitnessfun，fitness是工作目录下的保存文件名，本文输入目标函数@Schaffer。

2)Number of variable：输入适应度函数向量的长度，也就是决策变量个数。

单击“Start”按钮，运行遗传算法，将在“Status and result”窗口中显示出当前的运行结果。

在右侧“Option”窗口中可以对遗传算法参数进行设置，单击与之相连的符号“+”可以查看窗格中所列出的各类选项。

例如Population参数选项中，Population type:编码方式，可以选择实数编码，或者是二进制编码,Population size:设置种群大小，默认是20。Creation function：创建函数。initial population:初始种群范围。initial score：初始得分，initial range：变量多样性初始范围，这些都是结合自变量来设置的。

仿真结果：

运行截止代数90时的仿真结果如图4所示。

图4 Schaffer函数最佳适应度与最佳个体的流程图Fig.4 Flow chart of the best fitness and individual

运行截止代数100时的仿真结果如图5所示。

图5 Schaffer函数最佳适应度与最佳个体的流程图Fig.5 Flow chart of the best fitness and individual

根据反复试验，当种群初始规模设置为20，最大遗传代数为100，停滞代数为100，交叉概率为0.8，高斯变异，其他参数使用缺省值时，Schaffer函数优化结果最好。

图4图5上半部分图中底部的点代表最佳适应度值，而其上的点代表平均适应度值，顶部显示的是当前代的最佳值和平均值[7]。平均适应度值在遗传代数为90时达到收敛，收敛较缓慢，并且出现摆动，图中所示结果是多次仿真后的最佳结果。下图表示当前代最佳适应度值对应的点坐标变量，图4中X坐标是(0.003 16,-0.001 18)，图5中X坐标是(0.000 22,0.002 18)，非常接近于理论值（0,0）运行到最后一代的最优解是f(x) =-1,种群平均值是：-0.999 58。Schafer函数取了相反数，所以所求Schaffer函数最大值是1。

3 结论

主要介绍了MATLAB遗传算法工具箱GADS图形用户界面GUI寻找最优值的工作过程，采用基本遗传算法，遗传进化操作简单，容易理解，最大特点是只需编写目标函数的M文件，免去编程麻烦，把编程过程用图形界面体现出来，给编程能力不好的工作人员提供一种快速解决函数优化问题的新思路[7]。测试结果显示，在解决低维函数时，MATLAB遗传算法工具箱具有很强的处理能力，在处理高维函数优化问题时，快要接近最优解时收敛较慢，可以和其智能算法相结合，以使遗传算法工具箱收敛性能更佳[8]。

[1]李延梅.一种改进的遗传算法及应用[D].广东:华南理工大学,2012.

[2]罗述全.传统优化算法与遗传算法的比较[J].湖北工业大学学报,2007(6):32-35.LUO Shu-quan.Comparision between readitional optimized algorithm and heredity algotithm[J].Hubei University of Technology Journal,2007(6):32-35.

[3]雷英杰，张尚文，李续武等.MATLAB遗传算法工具箱及应用[M].西安：西安电子科技大学出版社，2005.

[4]金芬.MATLAB遗传算法工具箱在函数优化中的应用[J].福建电脑,2009(7):23-25.JIN Fen.MATLAB genetic algorithm toolbox in function optimization[J].Fujian Computer,2009(7):23-25.

[5]陈广洲，解华明，鲁祥友，等.Matlab遗传算法工具箱在非线性优化中的应用[J].计算机技术与发展，2008(3):247-248.CHEN Guang-zhou,XIE Hua-ming,LU Xiang-you,et al.Nonlinear optimization based on genetic algorithm toolbox of matlab[J].Computer Technology and Development,2008(3): 247-248.

[6]金芬.遗传算法在函数优化中的应用研究[D].苏州：苏州大学,2008.

[7]石丽娟.遗传算法求解函数优化问题的Matlab实现[J].福建电脑,2010(6):72-74.SHI Li-juan.Matlab achieve for genetic algorithm function optimization[J].Fujian Computer,2010(6):72-74.

[8]陈超.精通Matlab2008应用程序接口编程技术[M].北京:电子工业出版社,2009.

Optimization and examples in M atlab GA Toolbox GADS

GUO Hai-shuang1,LIANG Jia-wen1,ZHANG Shao-yun2
（1.College of Computer Science&Mathematics,Guizhou Nomal University,Guiyang 550001,China; 2.College of Physics and Electronics Science,Guizhou Nomal University,Guiyang 550001,China）

In order to solve the complex function optimization problem，the Genetic Algorithm Toolbox for MATLAB were briefly introduced,and the basic principles and methods of genetic algorithms were also elaborated，on this basis,introduced the work process of MATLAB genetic algorithm toolbox GADS to find the optimal value,at last,tested and verified the MATLAB genetic algorithm toolbox easy,high reliability advantages with combine application examples.

genetic algorithm;optimization;toolbox;MATLAB;GADS

TN911.1

A

1674－6236（2015）10-0027-03

2014-09-21 稿件编号：201409179

郭海双(1989—)，男，河北迁安人，硕士研究生。研究方向：软件工程学的应用。