1、133最新发布的 MATLAB 7.0 Release 14 已经包含了一个专门设计的遗传算法与直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox，GADS） 。使用遗传算法与直接搜索工具箱，可以扩展 MATLAB 及其优化工具箱在处理优化问题方面的能力，可以处理传统的优化技术难以解决的问题，包括那些难以定义或不便于数学建模的问题，可以解决目标函数较复杂的问题，比如目标函数不连续、或具有高度非线性、随机性以及目标函数没有导数的情况。本章 8.1 节首先介绍这个遗传算法与直接搜索工具箱，其余各节分别介绍该工具箱中的遗传算法工具及其使用方法。8.
2、1 遗传算法与直接搜索工具箱概述本节介绍 MATLAB 的 GADS（遗传算法与直接搜索）工具箱的特点、图形用户界面及运行要求，解释如何编写待优化函数的 M 文件，且通过举例加以阐明。8.1.1 工具箱的特点GADS 工具箱是一系列函数的集合，它们扩展了优化工具箱和 MATLAB 数值计算环境的性能。遗传算法与直接搜索工具箱包含了要使用遗传算法和直接搜索算法来求解优化问题的一些例程。这些算法使我们能够求解那些标准优化工具箱范围之外的各种优化问题。所有工具箱函数都是 MATLAB 的 M 文件，这些文件由实现特定优化算法的 MATLAB 语句所写成。使用语句type function_name
3、就可以看到这些函数的 MATLAB 代码。我们也可以通过编写自己的 M 文件来实现来扩展遗传算法和直接搜索工具箱的性能，也可以将该工具箱与 MATLAB 的其他工具箱或 Simulink结合使用，来求解优化问题。工具箱函数可以通过图形界面或 MATLAB 命令行来访问，它们是用 MATLAB 语言编写的，对用户开放，因此可以查看算法、修改源代码或生成用户函数。遗传算法与直接搜索工具箱可以帮助我们求解那些不易用传统方法解决的问题，譬如表查找问题等。遗传算法与直接搜索工具箱有一个精心设计的图形用户界面，可以帮助我们直观、方便、快速地求解最优化问题。8.1.1.1 功能特点 遗传算法与直接搜索工具箱
4、的功能特点如下：(1) 图形用户界面和命令行函数可用来快速地描述问题、设置算法选项以及监控进程。(2) 具有多个选项的遗传算法工具可用于问题创建、适应度计算、选择、交叉和变异。(3) 直接搜索工具实现了一种模式搜索方法，其选项可用于定义网格尺寸、表决方法和搜索方法。(4) 遗传算法与直接搜索工具箱函数可与 MATLAB 的优化工具箱或其他的MATLAB 程序结合使用。(5) 支持自动的 M 代码生成。8.1.1.2 图形用户界面和命令行函数134遗传算法工具函数可以通过命令行和图形用户界面来使用遗传算法。直接搜索工具函数也可以通过命令行和图形用户界面来进行访问。图形用户界面可用来快速地定义问题
5、、设置算法选项、对优化问题进行详细定义。遗传算法与直接搜索工具箱还同时提供了用于优化管理、性能监控及终止准则定义的工具，同时还提供大量标准算法选项。在优化运行的过程中，可以通过修改选项来细化最优解，更新性能结果。用户也可以提供自己的算法选项来定制工具箱。 8.1.1.3 使用其他函数和求解器遗传算法与直接搜索工具箱与 MATLAB 及优化工具箱是紧密结合在一起的。用户可以用遗传算法或直接搜索算法来寻找最佳起始点，然后利用优化工具箱或用 MATLAB 程序来进一步寻找最优解。通过结合不同的算法，可以充分地发挥 MATLAB 和工具箱的功能以提高求解的质量。对于某些特定问题，使用这种方法还可以得到
6、全局（最优）解。 8.1.1.4 显示、监控和输出结果遗传算法与直接搜索工具箱还包括一系列绘图函数用来可视化优化结果。这些可视化功能直观地显示了优化的过程，并且允许在执行过程中进行修改。工具箱还包括一系列绘图函数用来可视化优化结果。这些可视化功能直观地显示了优化的过程，并且允许在执行过程中进行修改。该工具箱还提供了一些特殊绘图函数，它们不仅适用于遗传算法，还适用于直接搜索算法。适用于遗传算法的函数包括函数值、适应度值和函数估计。适用于直接搜索算法的函数包括函数值、分值直方图、系谱、适应度值、网格尺寸和函数估计。这些函数可以将多个绘图一并显示，可直观方便地选取最优曲线。另外，用户也可以添加自己的
7、绘图函数。使用输出函数可以将结果写入文件，产生用户自己的终止准则，也可以写入用户自己的图形界面来运行工具箱求解器。除此之外，还可以将问题的算法选项导出，以便日后再将它们导入到图形界面中去。8.1.1.5 所需的产品支持遗传算法与直接搜索工具箱作为其他优化方法的补充，可以用来寻找最佳起始点，然后可以再通过使用传统的优化技术来进一步寻找最优解。 工具箱需要如下产品支持：(1) MATLAB 。(2) 优化工具箱。8.1.1.6 相关产品与遗传算法与直接搜索工具箱相关的产品有：(1) 统计工具箱应用统计算法和概率模式。(2) 神经网络工具箱设计和仿真神经网络。(3) 模糊逻辑工具箱设计和仿真基于模糊
8、逻辑的系统。(4) 金融工具箱分析金融数据和开发金融算法。8.1.1.7 所需的系统及平台遗传算法和直接搜索工具箱对于对于运行环境、支持平台和系统的需求，可随时通过访问网站 http:/ 了解最新发布的信息。这里介绍的 MATLAB 7.0 Release 14 所需的最低配置是：Windows 系列操作系统，Pentium III 500 CPU、64MB RAM，空闲硬盘空间 600MB 以上。8.1.2 编写待优化函数的M文件135为了使用遗传算法和直接搜索工具箱，首先必须编写一个 M 文件，来确定想要优化的函数。这个 M 文件应该接受一个行向量，并且返回一个标量。行向量的长度就是目标函
9、数中独立变量的个数。本节将通过实例解释如何编写这种 M 文件。8.1.2.1 编写 M 文件举例下面的例子展示了如何为一个想要优化的函数编写M文件。假定我们想要计算下面函数的最小值： 221121(,)6fxxxM文件确定这个函数必须接受一个长度为2的行向量X，分别与变量x1和x2相对应，并且返回一个标量X，其值等于该函数的值。为了编写这个M文件，执行如下步骤：(1) 在MATLAB的File菜单中选择New菜单项。(2) 选择M-File，将在编辑器中打开一个新的M文件。(3) 在该M文件中，输入下面两行代码：function z = my_fun(x)z = x(1)2 - 2*x(1)*
10、x(2) + 6*x(1) + x(2)2 - 6*x(2);(4) 在MATLAB路径指定的目录中保存该M文件。为了查看该M文件是否返回正确的值，可键入my_fun(2 3)ans =-5注意：在运行遗传算法工具或模式搜索工具时，不要使用编辑器或调试器来调试目标函数的M文件，否则会导致在命令窗口出现Java异常消息，并且使调试更加困难。8.1.2.2 最大化与最小化遗传算法和直接搜索工具箱中的优化函数总是使目标函数或适应度函数最小化。也就是说，它们求解如下形式的问题： minze()xf如果我们想要求出函数f(x )的最大值，可以转而求取函数 g(x)=f(x)的最小值，因为函数g(x)最小
11、值出现的地方与函数 f(x)最大值出现的地方相同。例如，假定想要求前面所描述的函数 的最大值，这时，22111(,)6fx我们应当编写一个M文件来计算，求函数 221211(),)(6)gxf x的最小值。8.1.2.3 自动代码生成遗传算法与直接搜索工具箱提供了自动代码生成特性，可以自动生成求解优化问题所需要的 M 文件。例如，图 8.1 所示的就是使用遗传算法工具的自动代码生成特性所产生的 M文件。另外，图形用户界面所输出的优化结果可以作为对来自命令行调用代码的一种解释，这些代码还用于使例程和保护工作自动化。136图8.1 遗传算法M文件代码的自动生成8.2 使用遗传算法工具初步遗传算法与
12、直接搜索工具箱包含遗传算法工具和直接搜索工具。从本节至章末，将主要介绍其中的遗传算法工具及其使用方法。本节主要介绍遗传算法工具使用的初步知识，内容包括：遗传算法使用规则，遗传算法工具的使用方式，举例说明如何使用遗传算法来求解一个优化问题，解释遗传算法的一些基本术语，最后阐述遗传算法的工作原理与工作过程。8.2.1 遗传算法使用规则遗传算法是一种基于自然选择、生物进化过程来求解问题的方法。遗传算法反复修改对于个体解决方案的种群。在每一步，遗传算法随机地从当前种群中选择若干个体作为父辈，并且使用它们产生下一代的子种群。在连续若干代之后，种群朝着优化解的方向进化。我们可以用遗传算法来求解各种不适宜于
13、用标准优化算法求解的优化问题，包括目标函数不连续、不可微、随机或高度非线性的问题。遗传算法在每一步使用下列三类规则从当前种群来创建下一代：(1) 选择规则（Selection rules） ，选择对下一代种群有贡献的个体，称为父辈。(2) 交叉规则（Crossover rules），将两个父辈结合起来构成下一代的子辈种群。(3) 变异规则（Mutation rules），施加随机变化给父辈个体来构成子辈。遗传算法与标准优化算法主要在两个方面有所不同，它们的比较情况归纳于表 8.1 中。表8.1 遗传算法与标准优化算法比较标准算法 遗传算法每次迭代产生一个单点，点的序列逼近一个优化解每次迭代产生
14、一个种群，种群逼近一个优化解通过确定性的计算在该序列中选择下一个点通过随机进化选择计算来选择下一代种群1378.2.2 遗传算法使用方式遗传算法工具有两种使用方式：(1) 以命令行方式调用遗传算法函数ga。(2) 使用遗传算法工具，从图形用户界面到遗传算法。本节对这些方式做一个简要的介绍。8.2.2.1 在命令行调用函数 ga 对于在命令行使用遗传算法，可以用下列语法调用遗传算法函数ga：x fval = ga(fitnessfun, nvars, options) 其中：fitnessfun 是适应度函数句柄；nvars 是适应度函数的独立变量的个数；options 是一个包含遗传算法选项参
15、数的结构。如果不传递选项参数，则ga使用它本身的缺省选项值。函数所给出的结果：fval适应度函数的最终值；x最终值到达的点。 我们可以十分方便地把遗传算法工具输出的结果直接返回到MATLAB的workspace（工作空间），或以不同的选项从M文件多次调用函数ga来运行遗传算法。调用函数ga时，需要提供一个选项结构options 。后面的有关章节对于在命令行使用函数ga和创建选项结构 options提供了详细的描述。8.2.2.2 通过 GUI 使用遗传算法遗传算法工具有一个图形用户界面 GUI，它使我们可以使用遗传算法而不用工作在命令行方式。为了打开遗传算法工具，可键入gatool打开的遗传算
16、法工具图形用户界面如图 8.2 所示。 138图8.2 遗传算法工具为了使用遗传算法工具，首先必须输入下列信息：(1) Fitness function（适应度函数）欲求最小值的目标函数。输入适应度函数的形式为fitnessfun，其中fitnessfun.m是计算适应度函数的 M文件。在前面“编写待优化函数的M文件”一节里已经解释了如何编写这种M文件。符号产生一个对于函数fitnessfun的函数句柄。(2) Number of variables（变量个数）适应度函数输入向量的长度。对于“编写待优化函数的M文件” 一节所描述的函数My_fun ，这个参数是2。点击Start按钮，运行遗传算
17、法，将在Status and Results （状态与结果）窗格中显示出相应的运行结果。在Options窗格中可以改变遗传算法的选项。为了查看窗格中所列出的各类选项，可单击与之相连的符号“+”。8.2.3 举例：Rastrigin函数本节介绍一个例子，讲述如何寻找 Rastrigin 函数的最小值和显示绘制的图形。Rastrigin函数是最常用来测试遗传算法的一个典型函数。Rastrigin 函数的可视化图形显示，它具有多个局部最小值和一个全局最小值，遗传算法可以帮助我们确定这种具有多个局部最小值函数的最优解。输入适应度函数输入适应度函数的变量数目开始遗传算法显示结果显示参数描述1398.2.
18、3.1 Rastrigin 函数具有两个独立变量的Rastrigin函数定义为 2112()00(cos2s)RasxxxRastrigin函数的图形如图8.3所示。工具箱包含一个M文件，即rastriginsfcn.m，是用来计算Rastrigin 函数值的。图8.3 Rastrigin函数图形如图 8.3 所示，Rastrigin 函数有许多局部最小值在图上显示为“谷底（valleys）”。然而，该函数只有一个全局最小值，出现在 x-y 平面上的点0，0处，正如图中竖直线指示的那样，函数的值在那里是 0。在任何不同于0，0 的局部最小点处， Rastrigin 函数的值均大于0。局部最小处
19、距原点越远，该点处 Rastrigin 函数的值越大。Rastrigin 函数之所以最常用来测试遗传算法，是因为它有许多局部最小点，使得用标准的、基于梯度的查找全局最小的方法十分困难。图 8.4 所示是 Rastrigin 函数的轮廓线，它显示出最大最小交替变化的情形。全局最小点0，0140图8.4 Rastrigin函数的轮廓线8.2.3.2 寻找 Rastrigin 函数的最小值本节解释如何使用遗传算法来寻找 Rastrigin 函数的最小值。注意：因为遗传算法使用随机数据来进行它的搜索，所以该算法每一次运行时所返回的结果会稍微有些不同。为了查找最小值，进行下列步骤：(1) 在命令行键入
20、gatool，打开遗传算法工具。(2) 在遗传算法工具的相应栏目，输入适应度函数和变量个数。在“Fitness function（适应度函数）”文本框中，输入rastriginsfcn；在“Number of variables（变量个数）”文本框中，输入 2，这就是 Rastrigin 函数独立变量的个数。这一步操作如图 8.5 所示。图8.5 输入适应度函数与变量个数(3) 在“Run solver（运行求解器 ）” 窗格中，单击 Start 按钮，如图 8.6 所示。图8.6 单击运行求解器Start按钮在算法运行的同时， “Current generation（当前代数） ”文本框中显
21、示出当前的代数。通过点全局最小点0，0局部最小点局部最小点141击“暂停（Pause） ”按钮，可以使算法临时暂停一下。当这样做的时候，该按钮的名字变为“Resume（恢复） ”。为了从暂停处恢复算法的运行，可单击这个“Resume ”按钮。当算法完成时， “Status and results”窗格出现如图 8.7 所示的情形。图8.7 状态与结果显示“Status and results”窗格显示下列信息：(1) 算法终止时适应度函数的最终值：Fitness function value: 0.0067749206244585025注意：所显示的值非常接近于 Rastrigin 函数的实际
22、最小值 0。 “遗传算法举例”一节描述了一些方法，可以用来得到更接近实际最小值的结果。(2) 算法终止的原因：Optimization terminated:maximum number of generations exceeded.即退出的原因是：超过最大代数而导致优化终止。在本例中，算法在100代后结束，这是 “Generations（代数）” 选项的缺省值，此选项规定了算法计算的最大代数。(3) 最终点，在本例中是0.00274 -0.00516。8.2.3.3 从命令行查找最小值为了从命令行查找Rastrigin函数的最小值，可键入x fval reason = ga(rastrig
23、insfcn, 2)这将返回x = 0.0027 -0.0052fval = 0.0068reason =Optimization terminated: maximum number of generations exceeded. 其中：x 是算法返回的最终点；fval 是该最终点处适应度函数的值；reason 是算法结束的原因。8.2.3.4 显示绘制图形“Plots（绘图）” 窗格可以显示遗传算法运行时所提供的有关信息的各种图形。这些信最终点的适应度函数值最终点142息可以帮助我们改变算法的选项，改进算法的性能。例如，为了绘制每一代适应度函数的最佳值和平均值，选中复选框“Best fi
24、tness（最佳适应度）”，如图 8.8 所示。图8.8 绘图对话框当点击Start按钮时，遗传算法工具显示每一代适应度函数的最佳值和平均值的绘制图形。当算法停止时，所出现的图形如图8.9所示。图8.9 各代适应度函数的最佳值和平均值在每一代中，图的底部的点表示最佳适应度值，而其上的点表示平均适应度值。图的顶部还显示出当前一代的最佳值 0.0067796 和平均值 0.014788。为了得到最佳适应度值减少到多少为更好的直观图形，我们可以将图中 y 轴的刻度改变为对数刻度。为此，需进行如下操作：(1) 从绘图窗格的 Edit（编辑）菜单中选择 “Axes Properties（坐标轴属性） ”，打开属性编辑器，如图 8.10 所示。最佳值 0.0067796 平均值 0.014788
