最新发布的MATLAB 7.0 Release 14已经包含了一个专门设计的遗传算法与直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox，GADS）。使用遗传算法与直接搜索工具箱，可以扩展MATLAB及其优化工具箱在处理优化问题方面的能力，可以处理传统的优化技术难以解决的问题，包括那些难以定义或不便于数学建模的问题，可以解决目标函数较复杂的问题，比如目标函数不连续、或具有高度非线性、随机性以及目标函数没有导数的情况。

本章8.1节首先介绍这个遗传算法与直接搜索工具箱，其余各节分别介绍该工具箱中的遗传算法工具及其使用方法。

8.1 遗传算法与直接搜索工具箱概述

本节介绍MATLAB的GADS（遗传算法与直接搜索）工具箱的特点、图形用户界面及运行要求，解释如何编写待优化函数的M文件，且通过举例加以阐明。

8.1.1 工具箱的特点

GADS工具箱是一系列函数的集合，它们扩展了优化工具箱和MATLAB数值计算环境的性能。遗传算法与直接搜索工具箱包含了要使用遗传算法和直接搜索算法来求解优化问题的一些例程。这些算法使我们能够求解那些标准优化工具箱范围之外的各种优化问题。所有工具箱函数都是MATLAB的M文件，这些文件由实现特定优化算法的MATLAB语句所写成。

使用语句

type function_name

就可以看到这些函数的MATLAB代码。我们也可以通过编写自己的M文件来实现来扩展遗传算法和直接搜索工具箱的性能，也可以将该工具箱与MATLAB的其他工具箱或Simulink结合使用，来求解优化问题。

工具箱函数可以通过图形界面或MATLAB命令行来访问，它们是用MATLAB语言编写的，对用户开放，因此可以查看算法、修改源代码或生成用户函数。

遗传算法与直接搜索工具箱可以帮助我们求解那些不易用传统方法解决的问题，譬如表查找问题等。

遗传算法与直接搜索工具箱有一个精心设计的图形用户界面，可以帮助我们直观、方便、快速地求解最优化问题。 8.1.1.1 功能特点

遗传算法与直接搜索工具箱的功能特点如下：

图形用户界面和命令行函数可用来快速地描述问题、设置算法选项以及监控进程。 具有多个选项的遗传算法工具可用于问题创建、适应度计算、选择、交叉和变异。

直接搜索工具实现了一种模式搜索方法，其选项可用于定义网格尺寸、表决方法和搜索方法。

遗传算法与直接搜索工具箱函数可与MATLAB的优化工具箱或其他的MATLAB程序结合使用。

支持自动的M代码生成。 8.1.1.2 图形用户界面和命令行函数

遗传算法工具函数可以通过命令行和图形用户界面来使用遗传算法。直接搜索工具函数也可以通过命令行和图形用户界面来进行访问。图形用户界面可用来快速地定义问题、设置算法选项、对优化问题进行详细定义。

133

遗传算法与直接搜索工具箱还同时提供了用于优化管理、性能监控及终止准则定义的工具，同时还提供大量标准算法选项。

在优化运行的过程中，可以通过修改选项来细化最优解，更新性能结果。用户也可以提供自己的算法选项来定制工具箱。 8.1.1.3 使用其他函数和求解器

遗传算法与直接搜索工具箱与MATLAB及优化工具箱是紧密结合在一起的。用户可以用遗传算法或直接搜索算法来寻找最佳起始点，然后利用优化工具箱或用MATLAB程序来进一步寻找最优解。通过结合不同的算法，可以充分地发挥 MATLAB 和工具箱的功能以提高求解的质量。对于某些特定问题，使用这种方法还可以得到全局（最优）解。 8.1.1.4 显示、监控和输出结果

遗传算法与直接搜索工具箱还包括一系列绘图函数用来可视化优化结果。这些可视化功能直观地显示了优化的过程，并且允许在执行过程中进行修改。

工具箱还包括一系列绘图函数用来可视化优化结果。这些可视化功能直观地显示了优化的过程，并且允许在执行过程中进行修改。该工具箱还提供了一些特殊绘图函数，它们不仅适用于遗传算法，还适用于直接搜索算法。适用于遗传算法的函数包括函数值、适应度值和函数估计。适用于直接搜索算法的函数包括函数值、分值直方图、系谱、适应度值、网格尺寸和函数估计。这些函数可以将多个绘图一并显示，可直观方便地选取最优曲线。另外，用户也可以添加自己的绘图函数。

使用输出函数可以将结果写入文件，产生用户自己的终止准则，也可以写入用户自己的图形界面来运行工具箱求解器。除此之外，还可以将问题的算法选项导出，以便日后再将它们导入到图形界面中去。 8.1.1.5 所需的产品支持

遗传算法与直接搜索工具箱作为其他优化方法的补充，可以用来寻找最佳起始点，然后可以再通过使用传统的优化技术来进一步寻找最优解。

工具箱需要如下产品支持：(1) MATLAB。(2) 优化工具箱。 8.1.1.6 相关产品

与遗传算法与直接搜索工具箱相关的产品有： 统计工具箱——应用统计算法和概率模式。 神经网络工具箱——设计和仿真神经网络。

模糊逻辑工具箱——设计和仿真基于模糊逻辑的系统。 金融工具箱——分析金融数据和开发金融算法。

8.1.1.7 所需的系统及平台

遗传算法和直接搜索工具箱对于对于运行环境、支持平台和系统的需求，可随时通过访问网站http://www.mathworks.com/products/gads了解最新发布的信息。

这里介绍的MATLAB 7.0 Release 14所需的最低配置是：Windows系列操作系统，Pentium III 500 CPU、64MB RAM，空闲硬盘空间600MB以上。

8.1.2 编写待优化函数的M文件

为了使用遗传算法和直接搜索工具箱，首先必须编写一个M文件，来确定想要优化的函数。这个M文件应该接受一个行向量，并且返回一个标量。行向量的长度就是目标函数中独

134

立变量的个数。本节将通过实例解释如何编写这种M文件。 8.1.2.1 编写M文件举例

下面的例子展示了如何为一个想要优化的函数编写M文件。假定我们想要计算下面函数的最小值：

2f(x1,x2)?x12?2x1x2?6x1?x2?6x2

M文件确定这个函数必须接受一个长度为2的行向量X，分别与变量x1和x2相对应，并且

返回一个标量X，其值等于该函数的值。为了编写这个M文件，执行如下步骤： 在MATLAB的File菜单中选择New菜单项。

选择M-File，将在编辑器中打开一个新的M文件。 在该M文件中，输入下面两行代码：

function z = my_fun(x)

z = x(1)^2 - 2*x(1)*x(2) + 6*x(1) + x(2)^2 - 6*x(2);

在MATLAB路径指定的目录中保存该M文件。

为了查看该M文件是否返回正确的值，可键入

my_fun([2 3]) ans = -5 注意：在运行遗传算法工具或模式搜索工具时，不要使用编辑器或调试器来调试目标函数的M文件，否则会导致在命令窗口出现Java异常消息，并且使调试更加困难。 8.1.2.2 最大化与最小化

遗传算法和直接搜索工具箱中的优化函数总是使目标函数或适应度函数最小化。也就是说，它们求解如下形式的问题：

minimizef(x)

x如果我们想要求出函数f(x)的最大值，可以转而求取函数g(x)=－f(x)的最小值，因为函数g(x)最小值出现的地方与函数f(x)最大值出现的地方相同。

2例如，假定想要求前面所描述的函数f(x1,x2)?x12?2x1x2?6x1?x2?6x2的最大值，这时，

我们应当编写一个M文件来计算，求函数

2g(x)??f(x1,x2)??(x12?2x1x2?6x1?x2?6x2)

的最小值。

8.1.2.3 自动代码生成

遗传算法与直接搜索工具箱提供了自动代码生成特性，可以自动生成求解优化问题所需

要的M文件。例如，图8.1所示的就是使用遗传算法工具的自动代码生成特性所产生的M文件。

另外，图形用户界面所输出的优化结果可以作为对来自命令行调用代码的一种解释，这些代码还用于使例程和保护工作自动化。

135

图8.1 遗传算法M文件代码的自动生成

8.2 使用遗传算法工具初步

遗传算法与直接搜索工具箱包含遗传算法工具和直接搜索工具。从本节至章末，将主要介绍其中的遗传算法工具及其使用方法。

本节主要介绍遗传算法工具使用的初步知识，内容包括：遗传算法使用规则，遗传算法工具的使用方式，举例说明如何使用遗传算法来求解一个优化问题，解释遗传算法的一些基本术语，最后阐述遗传算法的工作原理与工作过程。

8.2.1 遗传算法使用规则

遗传算法是一种基于自然选择、生物进化过程来求解问题的方法。遗传算法反复修改对于个体解决方案的种群。在每一步，遗传算法随机地从当前种群中选择若干个体作为父辈，并且使用它们产生下一代的子种群。在连续若干代之后，种群朝着优化解的方向进化。我们可以用遗传算法来求解各种不适宜于用标准优化算法求解的优化问题，包括目标函数不连续、不可微、随机或高度非线性的问题。

遗传算法在每一步使用下列三类规则从当前种群来创建下一代： 选择规则（Selection rules），选择对下一代种群有贡献的个体，称为父辈。 交叉规则（Crossover rules），将两个父辈结合起来构成下一代的子辈种群。 变异规则（Mutation rules），施加随机变化给父辈个体来构成子辈。

遗传算法与标准优化算法主要在两个方面有所不同，它们的比较情况归纳于表8.1中。

表8.1 遗传算法与标准优化算法比较

标准算法 每次迭代产生一个单点，点的序列逼近一个优化解 通过确定性的计算在该序列中选择下一个点 遗传算法 每次迭代产生一个种群，种群逼近一个优化解 通过随机进化选择计算来选择下一代种群 136

8.2.2 遗传算法使用方式

遗传算法工具有两种使用方式： 以命令行方式调用遗传算法函数ga。

使用遗传算法工具，从图形用户界面到遗传算法。 本节对这些方式做一个简要的介绍。

8.2.2.1 在命令行调用函数ga

对于在命令行使用遗传算法，可以用下列语法调用遗传算法函数ga：

[x fval] = ga(@fitnessfun, nvars, options)

其中：@fitnessfun 是适应度函数句柄；nvars 是适应度函数的独立变量的个数；options 是一个包含遗传算法选项参数的结构。如果不传递选项参数，则ga使用它本身的缺省选项值。

函数所给出的结果：fval——适应度函数的最终值；x——最终值到达的点。

我们可以十分方便地把遗传算法工具输出的结果直接返回到MATLAB的workspace（工作空间），或以不同的选项从M文件多次调用函数ga来运行遗传算法。

调用函数ga时，需要提供一个选项结构options。后面的有关章节对于在命令行使用函数ga和创建选项结构options提供了详细的描述。 8.2.2.2 通过GUI使用遗传算法

遗传算法工具有一个图形用户界面GUI，它使我们可以使用遗传算法而不用工作在命令行方式。为了打开遗传算法工具，可键入

gatool

打开的遗传算法工具图形用户界面如图8.2所示。

137

显示参数描述 输入适应度函数 输入适应度函数 的变量数目 开始遗传算法 显示结果

图8.2 遗传算法工具

为了使用遗传算法工具，首先必须输入下列信息： Fitness function（适应度函数）——欲求最小值的目标函数。输入适应度函数的形式为@fitnessfun，其中fitnessfun.m是计算适应度函数的M文件。在前面“编写待优化函数的M文件”一节里已经解释了如何编写这种M文件。符号@产生一个对于函数fitnessfun的函数句柄。

Number of variables（变量个数）——适应度函数输入向量的长度。对于“编写待优化函数的M文件”一节所描述的函数My_fun，这个参数是2。

点击Start按钮，运行遗传算法，将在Status and Results（状态与结果）窗格中显示出相应的运行结果。

在Options窗格中可以改变遗传算法的选项。为了查看窗格中所列出的各类选项，可单击与之相连的符号“+”。

8.2.3 举例：Rastrigin函数

本节介绍一个例子，讲述如何寻找Rastrigin函数的最小值和显示绘制的图形。Rastrigin函数是最常用来测试遗传算法的一个典型函数。Rastrigin函数的可视化图形显示，它具有多个局部最小值和一个全局最小值，遗传算法可以帮助我们确定这种具有多个局部最小值函数的最优解。

8.2.3.1 Rastrigin函数

138

具有两个独立变量的Rastrigin函数定义为

2Ras(x)?20?x12?x2?10(cos2?x1?cos2?x2)

Rastrigin函数的图形如图8.3所示。

工具箱包含一个M文件，即rastriginsfcn.m，是用来计算Rastrigin函数值的。

全局最小点[0，0]

图8.3 Rastrigin函数图形

如图8.3所示，Rastrigin函数有许多局部最小值——在图上显示为“谷底（valleys）”。然而，该函数只有一个全局最小值，出现在x-y 平面上的点[0，0]处，正如图中竖直线指示的那样，函数的值在那里是0。在任何不同于[0，0]的局部最小点处，Rastrigin函数的值均大于0。局部最小处距原点越远，该点处Rastrigin函数的值越大。

Rastrigin函数之所以最常用来测试遗传算法，是因为它有许多局部最小点，使得用标准的、基于梯度的查找全局最小的方法十分困难。

图8.4所示是Rastrigin函数的轮廓线，它显示出最大最小交替变化的情形。

139

局部最小点 局部最小点 全局最小点[0，0] 图8.4 Rastrigin函数的轮廓线

8.2.3.2 寻找Rastrigin函数的最小值

本节解释如何使用遗传算法来寻找Rastrigin函数的最小值。

注意：因为遗传算法使用随机数据来进行它的搜索，所以该算法每一次运行时所返回的结果会稍微有些不同。

为了查找最小值，进行下列步骤：

在命令行键入gatool，打开遗传算法工具。

在遗传算法工具的相应栏目，输入适应度函数和变量个数。在“Fitness function（适应度函数）”文本框中，输入@rastriginsfcn；在“Number of variables（变量个数）”文本框中，输入2，这就是Rastrigin函数独立变量的个数。这一步操作如图8.5所示。

图8.5 输入适应度函数与变量个数

在“Run solver（运行求解器）”窗格中，单击Start按钮，如图8.6所示。

图8.6 单击运行求解器Start按钮

在算法运行的同时，“Current generation（当前代数）”文本框中显示出当前的代数。通过点击“暂停（Pause）”按钮，可以使算法临时暂停一下。当这样做的时候，该按钮的名字变为

140

“Resume（恢复）”。为了从暂停处恢复算法的运行，可单击这个“Resume”按钮。

当算法完成时，“Status and results”窗格出现如图8.7所示的情形。

最终点的适应度函数值 最终点

图8.7 状态与结果显示

“Status and results”窗格显示下列信息： 算法终止时适应度函数的最终值：

Fitness function value: 0.0067749206244585025

注意：所显示的值非常接近于Rastrigin函数的实际最小值0。“遗传算法举例”一节描述了一些方法，可以用来得到更接近实际最小值的结果。 算法终止的原因：

Optimization terminated:

maximum number of generations exceeded.

即退出的原因是：超过最大代数而导致优化终止。

在本例中，算法在100代后结束，这是 “Generations（代数）” 选项的缺省值，此选项规定了算法计算的最大代数。

最终点，在本例中是[0.00274 -0.00516]。 8.2.3.3 从命令行查找最小值

为了从命令行查找Rastrigin函数的最小值，可键入

[x fval reason] = ga(@rastriginsfcn, 2)

这将返回

x =

0.0027 -0.0052 fval =

0.0068 reason =

Optimization terminated:

maximum number of generations exceeded.

其中：x是算法返回的最终点；fval是该最终点处适应度函数的值；reason是算法结束的原因。 8.2.3.4 显示绘制图形

“Plots（绘图）”窗格可以显示遗传算法运行时所提供的有关信息的各种图形。这些信息可以帮助我们改变算法的选项，改进算法的性能。例如，为了绘制每一代适应度函数的最佳值和平均值，选中复选框“Best fitness（最佳适应度）”，如图8.8所示。

141

图8.8 绘图对话框

当点击Start按钮时，遗传算法工具显示每一代适应度函数的最佳值和平均值的绘制图形。当算法停止时，所出现的图形如图8.9所示。

最佳值 0.0067796 平均值 0.014788

图8.9 各代适应度函数的最佳值和平均值

在每一代中，图的底部的点表示最佳适应度值，而其上的点表示平均适应度值。图的顶部还显示出当前一代的最佳值0.0067796和平均值0.014788。

为了得到最佳适应度值减少到多少为更好的直观图形，我们可以将图中y轴的刻度改变为对数刻度。为此，需进行如下操作：

(1) 从绘图窗格的Edit（编辑）菜单中选择“Axes Properties（坐标轴属性）”，打开属性编辑器，如图8.10所示。

142

单击Y表项 选择对数刻度

图8.10 绘图属性编辑器

(2) 点击Y表项。

(3) 在“Scale（刻度）”窗格，选择“Log (对数)”。 绘制的图形如图8.11所示。

最佳值0.0067796 平均值0.014788 143

图8.11 每一代适应度函数最佳值和平均值的对数图形

典型情况下，在早期各代中，当个体离理想值较远时，最佳值会迅速得到改进。在后来各代中，种群越接近最佳点，最佳值改进得越慢。

8.2.4 遗传算法的一些术语

本节解释遗传算法的一些基本术语，主要包括： ? 适应度函数（Fitness Functions）。 ? 个体（Individuals）。

? 种群（Populations）和代（Generations）。

? 适应度值（Fitness Values）和最佳适应度值（Best Fitness Values）； ? 父辈和子辈（Parents and Children）。 8.2.4.1 适应度函数

所谓适应度函数就是想要优化的函数。对于标准优化算法而言，这个函数称为目标函数。该工具箱总是试图寻找适应度函数的最小值。

我们可以将适应度函数编写为一个M文件，作为输入参数传递给遗传算法函数。 8.2.4.2 个体

一个个体是可以施加适应度函数的任意一点。一个个体的适应度函数值就是它的得分或评价。例如，如果适应度函数是

f(x1,x2,x3)?(2x1?1)2?(3x2?4)2?(x3?2)2

则向量（2, -3, 1）就是一个个体，向量的长度就是问题中变量的个数。个体（2, -3, 1）的得分是f(2, -3, 1) = 51。

个体有时又称为基因组或染色体组（genome），个体的向量项称为基因（genes）。 8.2.4.3 种群与代

所谓种群是指由个体组成的一个数组或矩阵。例如，如果个体的长度是100，适应度函数中变量的个数为3，我们就可以将这个种群表示为一个100×3的矩阵。相同的个体在种群中可以出现不止一次。例如，个体(2, -3, 1)就可以在数组的行中出现多次。

每一次迭代，遗传算法都对当前种群执行一系列的计算，产生一个新的种群。每一个后继的种群称为新的一代。 8.2.4.4 多样性

多样性或差异（Diversity）涉及一个种群的各个个体之间的平均距离。若平均距离大，则种群具有高的多样性；否则，其多样性低。在图8.12中，左面的种群具有高的多样性，亦即差异大；而右面的种群多样性低，亦即差异小。

144

图8.12 种群多样性比较

多样性是遗传算法必不可少的本质属性，这是因为它能使遗传算法搜索一个比较大的解的空间区域。

8.2.4.5 适应度值和最佳适应度值

个体的适应度值就是该个体的适应度函数的值。由于该工具箱总是查找适应度函数的最小值，所以一个种群的最佳适应度值就是该种群中任何个体的最小适应度值。 8.2.4.6 父辈和子辈

为了生成下一代，遗传算法在当前种群中选择某些个体，称为父辈，并且使用它们来生成下一代中的个体，称为子辈。典型情况下，该算法更可能选择那些具有较佳适应度值的父辈。

8.2.5 遗传算法如何工作

本节简要介绍遗传算法的工作原理或工作过程，内容包括：算法要点；初始种群；生成下一代；后一代的绘图；算法的停止条件。 8.2.5.1 算法要点

下面的要点总结了遗传算法是如何工作的： (1) 首先，算法创建一个随机种群。

(2) 接着，算法生成一个新的种群序列，即新的一代。在每一步，该算法都使用当前一代中的个体来生成下一代。为了生成新一代，算法执行下列步骤：

(a) 通过计算其适应度值，给当前种群的每一个成员打分。

(b) 确定原来的适应度值的比例尺度，将其转换为更便于使用的范围内的值。 (c) 根据它们的适应度选择父辈。

(d) 由父辈产生子辈。子辈的产生可以通过随机改变一个单个父辈，亦即变异（mutation）来进行，也可以通过组合一对父辈的向量项，亦即交叉（crossover）来进行。

(e) 用子辈替换当前种群，形成下一代。

(3) 最后，若停止准则之一得到满足，则该算法停止。关于停止准则，可参见“8.2.5.7 算法的停止条件”一节。

145

8.2.5.2 初始种群

遗传算法总是以产生一个随机的初始种群开始，如图8.13所示。

图8.13 初始种群

在本例中，初始种群包含20个个体，这恰好是“Population（种群）”选项中的“Population size（种群尺度）”的缺省值。

注意：初始种群中的所有个体均处于图上右上角的那个象限，也就是说，它们的坐标处于0和1之间，这是因为“Population”选项中的“Initial range（初始范围）”的缺省值是[0; 1]。

如果已知函数的最小点大约位于何处，就可以设置一个适当的“Initial range”，以便使该点处于那个范围的中间附近。例如，如果确信Rastrigin函数的最小值在点[0，0]附近，那么就可以直接设置“Initial range”为[-1;1]。然而，正如本例所显示的那样，即使没有给“Initial range”设置一个理想的值，遗传算法也还是能够找到那个最小值。 8.2.5.3 产生下一代

在每一步，遗传算法使用当前种群来产生子辈，即获得下一代。算法在当前种群中选择一组个体，称为父辈，这些个父辈将其genes——亦即其向量中的项——贡献给它们的子辈。遗传算法通常选择那些具有较好适应度值的个体作为父辈。我们可以在“Selection（选择）”选项的“Selection function（选择函数）”文本框中指定遗传算法用来选择父辈的函数。

遗传算法对于下一代产生三类子辈：

? 优良子辈（Elite children），是在当前代中具有最佳适应度值的那些个体。这些个体子辈存活到下一代。 ? 交叉子辈（Crossover children），是由一对父辈向量组合产生的。 ? 变异子辈（Mutation children），是对一个单个父辈引入随机改变即变异产生的。 图8.14表示了这三个类型的子辈。

146

优良子辈 交叉子辈 变异子辈 图8.14 三类子辈

在“8.3.3.5变异与交叉”一节解释如何指定遗传算法产生的每一类子辈的数目，以及用来执行完成交叉和变异的函数。 8.2.5.4 交叉子辈

算法通过组合当前种群中的父辈对（Pair）来产生交叉子辈。在子辈向量的每一个相同位置处，缺省的交叉函数在两个父辈之一的相同位置处随机选择一项，即基因，并将它指派给其子辈。 8.2.5.5 变异子辈

算法通过随机改变个体父辈中的基因而产生变异子辈。按照缺省，算法给父辈增加一个高斯分布的随机向量。

图8.15表示出初始种群的子辈，也即第二代种群，并且指出它们是否为优良子辈、交叉子辈或变异子辈。

147

图8.15 初始种群的子辈

后代图形绘制

图8.16展示出在迭代60次, 80次, 95次, 100次时的种群的图形。 148

8.2.5.6

图8.16 在迭代60, 80, 95, 100次时的种群

随着代数的增加，种群中的个体靠近在一起，且逼近最小值点[0，0]。 8.2.5.7 算法的停止条件

遗传算法使用下列5个条件来确定何时停止：

? Generations（代数）——当产生的代的数目达到规定的代数的值时，算法停止。

? Time limit（时限）——在运行时间的秒数等于时限时，算法停止。

149

? Fitness limit（适应度限）——当适应度函数的值对于当前种群的最佳点小于或等于适应度限时，算法停止。

? Stall generations（停滞代数）——在连续繁殖的时间序列中，若长时间不繁殖新代，亦即目标函数无改进，到达停滞代数规定的代数时，则算法停止。

? Stall time limit（停滞时限）——在秒数等于停滞时限的时间间隔期间，若目标函数无改进，则算法停止。

若这5个条件中任何一个条件一旦满足，则该算法停止。我们可以在遗传算法工具的“Stopping criteria（停止标准）”选项中指定这些标准的值。它们的缺省值如图8.17所示。

图8.17 停止标准的缺省值

当运行遗传算法时，“Status（状态）”面板显示这些导致算法停止的标准。

“Time limit（时限）”选项与“Stall time limit”选项可以用来防止算法运行过长的时间。如果算法由于这两个条件之一而停止，则可以通过相应增加“Time limit”或“Stall time limit”的值来改善运行的结果。

8.3 使用遗传算法工具求解问题

本节首先概括使用遗传算法工具GUI的一般步骤，然后介绍如何从命令行使用遗传算法工具，最后通过例子，详细说明如何使用遗传算法工具来求解优化问题。

8.3.1 使用遗传算法GUI

在前面一章，已经介绍了使用遗传算法工具的初步知识。本节将简要归纳使用遗传算法工具GUI来求解优化问题的一般步骤，内容包括：打开遗传算法工具；在遗传算法工具中定义问题；运行遗传算法；暂停和停止运算；图形显示；创建用户图形函数；复现运行结果；设置选项参数；输入输出参数及问题；从最后种群继续运行遗传算法。 8.3.1.1 打开遗传算法工具

在MATLAB窗口中输入gatool，打开、进入遗传算法工具，初启时的界面显示如图8.18所示。

150

图8.18 遗传算法工具初启时的界面

8.3.1.2 在遗传算法工具中定义问题

在下列两个文本框中定义所要解决的问题：

(1) 适应度函数——求解的问题是求目标函数的最小值。输入一个计算适应度函数的M文件函数的句柄。

(2) 变量个数——适应度函数的独立变量个数。

注意：当运行遗传算法工具时不要用“Editor/Debugger（编辑/调试）”功能来调试目标函数的M文件，而要从命令行直接调用目标函数或把M文件输入到遗传算法函数ga。为了方便调试，可以在遗传算法工具中把问题输出到MATLAB工作窗中。

如图8.19所示，输入前面章节所介绍的Rastrigin函数或my_fun函数作为适配度函数，它们的变量个数为2。

图8.19 输入适应度函数与变量个数

8.3.1.3 运行遗传算法

151

要运行遗传算法，在“ Run solver（运行求解器）”中单击Start按纽，如图8.20所示。

图8.20 单击Start按钮

这时，在“Current generation（当前代）”文本框中显示当前代的数目，在Status and results”窗格显示“GA running”等信息，如图8.23所示。

图8.21 当前代数和状态与结果窗格

当遗传算法停止时，“Status and results”窗格显示： ? “GA terminated（GA终止）”信息。 ? 最后一代最佳个体的适应度函数值。 ? 算法停止的原因。 ? 最终点的坐标。

图8.22显示当运行例子“Rastrigin 函数”遗传算法停止时的信息。

图8.22 Rastrigin函数的遗传算法运行结果

在遗传算法工具中，当遗传算法运行时可以更改多个参数设置。所做的改变将被应用到下一代，即在下一代将按照新设置的参数运行。在下一代开始但尚未应用改变的参数之前，在“Status and results”窗格显示信息“Changes pending”。而在下一代开始且应用了改变的参数时，在“Status and results”窗格显示信息“Changes applied”。这样在遗传算法运行时更改了参数

152

设置产生的输出信息如图8.23所示。

图8.23 遗传算法运行时更改了参数设置

8.3.1.4 暂停和停止运算

遗传算法的暂停和停止运行，可以通过下面操作继续运行：

? 单击按钮“Pause（暂停）”，算法暂停运行。该按钮上的文字变为“Resume（恢复）”。单击这个“Resume” 按钮，即恢复遗传算法继续运行。

? 单击按钮“Stop”，算法停止运行。“Status and results”窗口显示停止运行时当前代最佳点的适应度函数值。

注意：如果单击按钮“Stop”，然后通过单击按钮“Start”再次运行时，遗传算法将以新的随机初始种群或在“Initial population（初始种群）”文本框中专门指定的种群运行。如果需要在算法停止后能再次恢复运行，则可以通过交替地单击按钮“Pause”和“Resume”来控制算法暂停或继续运行。

遗传算法的停止运行常常是通过设置算法停止准则来进行控制的。使用停止准则，设置停止准则参数，可以解决遗传算法在何时停止运行的控制问题。这样，也就不用通过单击“Stop” 按钮来人为地控制算法运行的停止。遗传算法有五个停止准则或条件，其中任何一个条件满足，算法即停止运行。这些停止准则是：

? 代数——算法运行到规定的代数。 ? 时限——算法运行到规定的时间。

? 适应度限——当前代的最佳适应度值小于或等于规定的值。 ? 停滞代数——适应度函数值在运行规定的代数后没有改进。 ? 停滞时限——适应度函数值在运行规定时间后没有改进。

如果想使算法一直运行到按下按钮“Pause”或“Stop”时才停下来，可以改变这些停止准则的参数值：

? 设置“Generations（代数）”为 Inf。 ? 设置“Time”为 Inf。

? 设置“Fitness limit”为 –Inf。 ? 设置“Stall generations”为 Inf。 ? 设置“Stall time limit”为 Inf。 图8.24显示了这些更改后的设置。

153

图8.24 改变停止准则参数

注意：在命令行中调用遗传算法函数ga时，并不使用这些参数设置，就好像是不按下 “Ctrl + C”键，函数就会永远运行而不会停止。其实相反，可以设置“Generations”或者“Time”做为限值来控制算法停止运行。 8.3.1.5 图形显示

图8.25为“Plots（绘图）”窗格，可以用来控制显示遗传算法运行结果变化的图形。

图8.25 在绘图窗格选择输出项

选择所要显示的图形参数的复选框。例如，如果选择“Best Fitness（最佳适应度）”和“Best individual（最佳个体）”，运行例子“Rastrigin 函数”，其显示输出如图8.26所示。

154

图8.26 Rastrigin函数最佳适应度与最佳个体

图8.28上部离散点为每一代的最佳适应度值和平均适应度值，下部柱型图表示当前代最佳适应度值对应的点的坐标。

注意：当要想显示两个以上参数项的图形时，可选择相应参数项的复选框，单独打开一个较大的图形窗口即可。

8.3.1.6 举例——创建用户绘图函数

如果工具箱中没有符合想要输出图形的绘图函数，用户可以编写自己的绘图函数。遗传算法在每次运行时调用这个函数，画出图形。这里举例说明怎样创建一个用户绘图函数来显示从前一代到当前代最佳适应度值的变化情形，内容包括：创建绘图函数，使用绘图函数，绘图函数如何作用。

（1）创建绘图函数

为了创建绘图函数，在MATLAB编辑器中复制、粘贴下列代码到一个新的M文件。

Function state = gaplotchange(options, state, flag)

% GAPLOTCHANGE Plots the change in the best score from the % previous generation.

persistent last_best % Best score in the previous generation if (strcmp(flag,'init')) % Set up the plot

set(gca,'xlim',[1, options.Generations],'Yscale'，'log'); hold on;

xlabel Generation

title('Change in Best Fitness Value') end

best = min(state.Score)； % Best score in the current generation if state.Generation == 0 % Set last_best to best。

155

last_best = best； else

change = last_best - best；% Change in best score last_best = best；

plot(state.Generation,change,'.r')； title(['Change in Best Fitness Value'])

end

然后在MATLAB 路径下将其存为M文件gaplotchange.m。 （2）使用绘图函数

为了使用用户绘图函数，在”绘图（Plots）”窗格中选择“Custom function（定制函数）”，并且在其右边的文本框中输入函数名@gaplotchange。为了对用户绘图函数输出的最佳适应度值图形进行比较，在这里也选择“Best Fitness”。现在，如果运行例子函数Rastrigin，显示出来的图形如图8.27所示。

最佳值 0.0021904 平均值 0.49832 最佳适应度值的变化

图8.27 用户绘图函数输出的Rastrigin函数运行结果

注意：因为图中下半部的y-轴为对数刻度，所以图形中的离散点仅仅显示大于零的点。对数刻度能显示适应度函数的微小变化，而上面的图形则不能显示出微小变化。

（3）绘图函数如何作用

绘图函数使用包含在下面结构体中的信息，它们由遗传算法传递给绘图函数作为输入参数：

? options（参数）— 当前参数设置。 ? state（状态）— 关于当前代的信息。

? flag（曲线标志）— 曲线表示为对数等的当前状态。 绘图函数的主要作用可以描述如下：

persistent last_best

生成永久变量last_best ——即前一代的最佳值。永久变量保存着多种图形函数调用类型。

156

set(gca, 'xlim'，[1，options.Generations], 'Yscale', 'log')；

在遗传算法运行前建立图形。options.Generation为代数的最大值。

best = min(state.Score)

state.Score包含当前代中所有个体的得分值，变量best是其中最小的得分值。结构体状态文本框的完整描述可参见“8.4.1.1 图形参数”一节。

change = last_best - best

变量change是前一代的最佳值减去当前代的最佳值。

plot(state.Generation，change，'.r')

画出当前代的变化曲线，变量维数包含在state.Generation中。

函数gaplotchange的代码包含了函数gaplotbestf代码中许多相同成分，函数gaplotbestf生成最佳适应度图形。 8.3.1.7 复现运行结果

为了复现遗传算法前一次的运行结果，选择“Use random states from previous run（使用前一次运行的随机状态）”复选框。这样就把遗传算法所用的随机数发生器的状态重新设置为前一次的值。如果没有改变遗传算法工具中的所有设置，那么遗传算法下一次运行时返回的结果与前一次运行的结果一致。

正常情况下，不要选择“Use random states from previous run”这个复选框，可以充分利用遗传算法随机搜索的优点。如果想要分析特定的运行结果或者显示相对个体的精确结果，可以选择“Use random states from previous run”复选框。 8.3.1.8 设置选项参数

设置遗传算法工具使用时的选项参数有两种方法：一种是在遗传算法工具GUI的“Options”窗格中直接进行设置，另一种是在MATLAB工作窗口中通过命令行方式进行设置。

在参数“Options”窗格中设置遗传算法的各种运行参数，如图8.28所示。每一类参数对应有一个窗格，单击该类参数时，对应窗格展开。例如，点击“Population”参数选项，种群窗格展开来，可以逐一设置其中的参数项，如Population type（种群类型）、Population size（种群尺度）、Creation function（创建函数）、Initial population、Initial score（初始得分）、Initial range（初始范围）等。

此外，其他选项参数类还有：Fitness scaling（适应度测量）、selection、Reproduction、Mutation、Crossover、Migration（迁移）、Hybrid function（混合函数）、Stopping criteria、Output function（输出函数）、Display to command window（显示到命令窗口）、Vectorize（向量化）等。这些参数类各自对应一个参数窗格，点击后相应窗格随即展开，可以进行参数项的设置。

所有变量参数的含义及详细描述可参见“8.4.1 遗传算法参数”一节。

157

图8.28 选项参数窗口

在MATLAB工作窗口中，可以将遗传算法的运行参数设置为变量。

对于数值参数的设置，可以直接在相应编辑框中输入该参数的值，或者在包含该参数值的MATLAB工作窗口中输入相应变量的名字，就可以完成设置。例如，可以利用下面两种方法之一设置“Initial point（初始点）”为[2.1 1.7]：

? 在“Initial point”文本框输入[2.1 1.7]。

? 在MATLAB工作区输入变量x0 = [2.1 1.7]，然后在“Initial point” 文本框输入变量

的名字x0。

因为选项参数是比较大的矩阵或向量，所以在MATLAB工作窗口中把参数的值定义为变量一般是比较方便的，也就是说，如果需要，很容易改变矩阵或向量的项。 8.3.1.9 输入输出参数及问题

参数和问题结构可以从遗传算法工具被输出到MATLAB的工作窗口，也可以在以后的某个时间再反过来把它们从MATLAB的工作窗口输入给遗传算法工具。这样就可以保存对问题的当前设置，并可以在以后恢复这些设置。参数结构也可以被输出到MATLAB工作窗口，并

158

且可以再把它们用于命令行方式的遗传算法函数ga。

输入和输出信息通常包含下列各项：

? 问题定义，包括“Fitness function”和“Number of variables（变量个数）”。 ? 当前指定的选项参数。 ? 算法运行的结果。

下面解释如何输入和输出这些信息。 （1）输出参数和问题

参数和问题可以被输出到MATLAB工作空间，以便以后在遗传算法工具中应用它们。也可以以命令行方式，在函数ga中应用这些参数和问题。

为了输出参数和问题，单击“Export to Workspace（输出到工作空间）”按钮或从File菜单中选择“Export to Workspace”菜单项，这将打开如图8.29所示的对话框。

图8.29 输出对话框

对话框提供下列参数：

① 为了保存问题的定义和当前参数的设置，选择“Export problem and options to a MATLAB structure named（输出问题与参数到已命名的MATLAB结构）”，并为这个结构体输入一个名字。单击OK按钮，即把这个信息保存到MATLAB工作空间的一个结构体。如果以后要把这个结构体输入到遗传算法工具，那么当输出这个结构时，所设置的“Fitness function”和“Number of variables”，以及所有的参数设置都被恢复到原来值。

注意：输出问题之前，如果在“Run solver（运行求解器）” 窗格选中“Use random states from previous run（使用前一次运行的随机状态）”选项，则遗传算法工具将保存上一次运行开始时随机数产生函数rand和randn的状态。然后，在选择了“Use random states from previous run”选项的情况下，输入问题且运行遗传算法，那么输出问题之前的运行结果就被准确地复现了。

② 如果想要遗传算法在输出问题之前从上一次运行的最后种群恢复运行，可选择“Include information needed to resume this run（包括所需信息以恢复本次运行）”。然后，当输入问题结构体并单击Start按钮，算法就从前次运行的最后种群继续运行。为了恢复遗传算法产生随机初始种群的缺省行为，可删除在“Initial population”字段所设置的种群，并用代之以空的中括号‘[ ]’。

注意：当选择了“Include information needed to resume this run”选项，则选择“Use random states from previous run”选项对于输入问题和运行遗传算法时创建的初始种群将不再有任何作用。后者的选项只是指定从新的一次运行开始时再一次复现结果，而不是为了恢复算法的继续运行。

③ 如果只是为了保存参数设置，可选择“Export options to a MATLAB structure named（输出参数到已命名的MATLAB结构）”，并为这个参数结构体输入一个名字。

④ 为了保存遗传算法最近一次运行的结果，可选择“Export results to a MATLAB structure named”，并为这个结果结构体输入一个名字。

159

（2）举例——用输出问题运行函数ga

输出一个问题可参见“8.2.3 举例：Rastrigin函数”一节，在命令行运行遗传算法函数ga，其步骤如下：

① 单击“Export to Workspace”按钮，打开相应对话框。

② 在“Export To Workspace”对话框中的“Export problem and options to a MATLAB structure named”右面的文本框，输入问题结构体的名称，假设为my_gaproblem。

③ 在MATLAB窗口，以my_gaproblem为参数调用函数ga：

[x fval] = ga(my_gaproblem)

则返回结果：

x =

0.0027 -0.0052 fval =

0.0068

调用函数ga可参见 “8.3.2 从命令行使用遗传算法” 一节。 （3）输入参数

为了从MATLAB工作窗中输入一个参数结构体，可从“File”菜单选择“Import Options（输入参数）”菜单项。在MATLAB工作窗中打开一个对话框，列出遗传算法参数结构体的一系列选项。当选择参数结构体并单击“Import（输入）”按钮，在遗传算法工具中的参数域就被更新，且显示所输入参数的值。

创建参数结构体有两种方法：

? 调用函数gaoptimset，以参数结构options作为输出。

? 在遗传算法工具中，从“Export to Workspace（输出到工作空间）”对话框保存当前参数。 （4）输入问题

为了从遗传算法工具输入一个以前输出的问题，可从“File”菜单选择“Import Problem（输入问题）”菜单项。在MATLAB工作窗中，打开一个对话框，显示遗传算法问题结构体的一个列表。当选择了问题结构体并单击OK按钮，遗传算法工具中的下列文本框被更新：

? 适应度函数。 ? 变量个数。 ? 参数域。 8.3.1.10 举例——从最后种群中继续遗传算法

下面的例子显示如何输出一个问题，以便当输入问题并按下Start按钮时，遗传算法能从该输出问题所保存的最后种群继续运行。现在运行一个例子，在遗传算法工具中输入下面的信息：

? 设置适应度函数为@ackleyfcn，它是计算函数Ackley，是工具箱提供的一个测试函数。 ? 设置“Number of variables”为 10。 ? 在“Plots”窗格选择“Best fitness”。 ? 单击按钮“Start”。 显示的结果如图8.30所示。

160

图8.30 函数ackleyfcn的最佳适应度

假定想要实验利用其它的参数运行遗传算法，接着利用当前参数设置，此后再从最后种群重新运行算法。为此，进行以下步骤：

① 单击“Export to Workspace”按钮。 ② 在出现的对话框中：

- 选择“Export problem and options to a MATLAB structure named”。 - 在文本框中输入问题和参数的名称，例如ackley_uniform。

- 选择“Include information needed to resume this run（包括所需信息以恢复本次运行）”。

做了这些选择后的对话框如图8.31所示。

图8.31 在输出窗口对话框中做适当选择

③ 单击OK按钮。

问题和参数被输出到MATLAB工作空间的一个结构体中。在MATLAB命令窗口输入下面的信息就可以观察这个结构体：

161

ackley_uniform ackley_uniform =

fitnessfcn： @ackleyfcn genomelength： 10 options： [1x1 struct]

利用不同的参数设置，甚至是不同的适应度函数，在运行遗传算法之后，都能够按照如下步骤来恢复问题：

① 从“File”菜单，选择“Import Problem ”菜单项。打开的对话框如图8.32所示。

图8.32 GA问题输入窗口

② 选择ackley_uniform。 ③ 单击按钮“Import”。

这样就把“Population”选项中的“Initial population”字段设置成输出问题之前运行的最后种群。在运行期间，所有其它参数恢复它们的设置。当单击Start按钮时，遗传算法从被保存的最后种群重新运行。图8.33所示为初始运行和重新运行的最佳适应度图形。

第一次运行 从这里继续运行

图8.33 初始运行和重新运行的最佳适应度

162

注意：如果在利用所导入问题运行遗传算法之后，想要恢复遗传算法生成一个随机初始种群的缺省行为，可删除“Initial population”字段中设置的种群，而代之以空的中括号‘[ ]’。 8.3.1.11 生成M文件

在遗传算法工具中，要利用特定的适应度函数和参数生成运行遗传算法的M文件，可从“File”菜单选择“Generate M-File（生成M文件）”菜单项，并把生成的M文件保存到MATLAB路径的一个目录。

在命令行调用这个M文件时，返回的结果与利用在遗传算法工具中生成M文件时的适应度函数和参数所得到的结果一致。

8.3.2 从命令行使用遗传算法

使用遗传算法，也可以从命令行运行遗传算法函数ga。这方面的内容主要包括：利用缺省参数运行ga；在命令行设置ga的参数；使用遗传算法工具的参数和问题结构；复现运行结果；以前一次运行的最后种群重新调用函数ga；从M文件运行ga。 8.3.2.1 利用缺省参数运行ga

利用缺省参数运行遗传算法，以下面语句调用ga

[x fval] = ga(@fitnessfun,nvars)

其中：

? @fitnessfun — 计算适应度函数值的M文件的函数句柄。 ? nvars —适应度函数中独立变量的个数。 ? x — 返回的最终点。

? fval — 返回的适应度函数在x点的值。 例如，运行例子Rastrigin函数，从命令行输入

[x fval] = ga(@rastriginsfcn,2)

这将返回

x =

0.0027 -0.0052 fval =

0.0068

为了得到遗传算法更多的输出结果，可以用下面语句调用ga

[x fval reason output population scores] = ga(@fitnessfcn, nvars) 除了输出变量x和fval之外，增加了以下输出变量 ? “reason（原因）”— 算法停止的原因。

? “output（输出）”— 包含关于算法在每一代性能的结构体。 ? “population（种群）”— 最后种群。 ? “scores（得分）”— 最终得分值。 8.3.2.2 在命令行设置ga的参数

遗传算法工具中的参数可以指定为任何有效的参数值，设置参数使用下面语句：

[x fval] = ga(@fitnessfun,nvars,options) 使用函数gaoptimset生成一个参数结构体。

options = gaoptimset

返回带有缺省值的参数结构体：

options =

163

PopulationType： 'doubleVector' PopInitRange： [2x1 double] PopulationSize： 20 EliteCount： 2

CrossoverFraction： 0.8000 MigrationDirection： 'forward' MigrationInterval： 20 MigrationFraction： 0.2000

Generations： 100 TimeLimit： Inf fitnessLimit： -Inf StallLimitG： 50 StallLimitS： 20 InitialPopulation： [ ] InitialScores： [ ] PlotInterval： 1

CreationFcn： @gacreationuniform fitnessScalingFcn： @fitscalingrank

SelectionFcn： @selectionstochunif CrossoverFcn： @crossoverscattered MutationFcn： @mutationgaussian HybridFcn： [ ] Display： 'final' PlotFcns： [ ] OutputFcns： [ ] Vectorized： 'off'

如果没有给某一参数项输入新的值，则函数ga使用其缺省值。

每一个参数的值都存放在参数结构体中，例如options.PopulationSize。可以通过输入参数的名称显示参数的值。例如，显示遗传算法种群的大小，可输入

options.PopulationSize ans =

20

改变参数结构体中成员值，例如，设置PopulationSize值等于100，代替它的缺省值20，可输入

options = gaoptimset('PopulationSize',100)

参数结构体中，PopulationSize为100，其它值都为缺省值或当前值。

这时，再输入

ga(@fitnessfun,nvars,options)

函数ga将以种群中个体为100运行遗传算法。

如果想接着改变参数结构体其它成员的值，例如设置PlotFcns为@gaplotbestf，画出每一代最佳适应度函数值图形，则可用下面语句调用函数gaoptimset

options = gaoptimset(options,'PlotFcns',@plotbestf)

这里保持了参数的所有当前值，除PlotFcns之外，它改变为@plotbestf。注意，如果省略输入自变量参数options，那么函数gaoptimset重新置PopulationSize为它的缺省值20。

也可以利用一个语句来同时设置两个参数PopulationSize和PlotFcns：

options = gaoptimset('PopulationSize',100,'PlotFcns',@plotbestf)

164

8.3.2.3 使用遗传算法工具的参数和问题结构

利用函数gaoptimset创建一个参数结构体，在遗传算法工具中设置参数的值，然后在MATLAB工作窗中输出参数给结构体。如果想在遗传算法工具中输出缺省值，则导出的结构体的参数与由命令行得到的缺省结构体的参数一致。

options = gaoptimset

如果想从遗传算法工具输出一个问题结构体ga_problem，可用下面的语句调用函数ga

[x fval] = ga(ga_problem)

问题结构体包含：

? fitnessfcn — 适应度函数。 ? nvars — 问题的变量数。 ? options — 参数结构体。 8.3.2.4 复现运行结果

因为遗传算法是随机性方法，也就是说，产生随机机率，即每次运行遗传算法得到的结果都会略有不同。算法利用MATLAB随机数产生器函数rand和randn，在每一次迭代中，产生随机机率。每一次函数ga调用rand和randn，它们的状态都可能发生改变，以便下一次再被调用时，它们返回不同的随机数。这就是为什么每次运行后ga输出的结果会略有不同。

如果需要准确复现运行结果，可以在调用函数ga时包含rand和randn的当前状态。在又一次运行ga之前，重新设置这些值的状态。例如，要复现Rastrigin函数的ga的输出，可以利用下面的语句调用ga

[x fval reason output] = ga(@rastriginsfcn,2)；

假设某次运行的返回结果为

x =

0.0027 -0.0052 fval =

0.0068

则随机函数rand和randn两者的状态被保存在output结构中。

output =

randstate： [35x1 double] randnstate： [2x1 double] generations： 100 funccount： 2000

message： [1x64 char]

然后，重新设置状态，输入

rand('state',output.randstate)； randn('state',output.randnstate)；

如果现在再次运行ga，就会得到相同的结果。

注意：如果没有必要复现运行结果，最好不要设置rand和randn的状态，以便能够得到遗传算法随机搜索的益处。

8.3.2.5 以前一次运行的最后种群重新调用函数ga

缺省情况下，每次运行ga时都生成一个初始种群。然而，可以将前一次运行得到的最后种群作为下一次运行的初始种群，这样做能够得到更好的结果。这可以利用下面语句实现：

[x,fval,reason,output,final_pop] = ga(@fitnessfcn,nvars)；

最后一个输出变量final_pop返回的就是本次运行得到的最后种群。将final_pop再作为初始种群运行ga，语句为：

165

options = gaoptimset('InitialPop',final_pop)；

[x,fval,reason,output,final_pop2] = ga(@fitnessfcn,nvars)；

还可以将第二次运行ga得到的最后种群final_pop2作为第三次运行ga的初始种群。 8.3.2.6 从M文件运行ga

利用命令行可以运行遗传算法。使用M文件可以有不同的参数设置。例如，可以设置不同的交叉概率来运行遗传算法，观察、比较每次运行的结果。下面的代码是运行ga函数21次，变量options.CrossoverFraction从0到1，间隔为0.05，所记录的运行结果。

options = gaoptimset('Generations',300)；

rand('state',71)； % These two commands are only included to randn('state',59)； % make the results reproducible. record=[ ]； for n=0 : .05 : 1

options = gaoptimset(options,'CrossoverFraction',n)； [x fval]=ga(@rastriginsfcn,10,options)； record = [record；fval]； end

可以利用下列语句，以不同概率画出fval值的曲线图形：

plot(0 : .05 : 1,record)；

xlabel('Crossover Fraction')； ylabel('fval')

显示结果参见图8.34所示。

图8.34 从M文件运行遗传算法时fval值的曲线图形

从图形显示可以看出，options.CrossoverFraction的值为0.6~ 0.95时，可得到最好结果。 取每次运行得到的fval的平均值，就可以画出fval的光滑曲线，如图8.35所示。

166

图8.35 从M文件运行遗传算法时fval平均值的曲线图形

曲线最凹的部分对应options.CrossoverFraction的值为0.7~ 0.9。

8.3.3 遗传算法举例

为了得到遗传算法的最好结果，一般需要以不同的参数实验。通过不断实验，选择针对问题的最佳参数。有效参数的完整描述可参见 “8.4.1 遗传算法参数”一节。

本节介绍几种能够提高运算效果的参数改变方法，内容包括：种群多样性；适应度测量；选择；复制参数；变异与交叉；设置变异大小；设置交叉概率；相对于全局的局部最小值；使用混合函数；设置最大代数；向量化适应度函数。 8.3.3.1 种群的多样性

决定遗传算法的一个重要性能是种群的多样性。个体之间的距离越大，则多样性越高；反之，个体之间的距离越小，则多样性越低。由试验得到种群的适当多样性。如果多样性过高或者过低，遗传算法都可能运行不好。这里介绍如何设置种群的初始范围来控制种群的多样性，并介绍如何设置种群尺度。

? 举例——设置初始范围

遗传算法工具在默认情况下利用生成函数随机生成一个初始种群。使用者可以在“Population”的“Initial range”文本框中指定初始种群的向量范围。

注意：初始范围仅仅限制在初始种群中的点的范围。后续各代包含的点可以不在初始种群的范围之内。

如果知道问题解的大概范围，计算时就可以指定包含问题解的初始范围。但是，假设种群具有足够的多样性，遗传算法就可以找到不在初始范围的解。下面的例子显示初始范围对遗传算法性能的影响。这个例子利用Rastrigin函数，函数在原点取得最小值为0。运行之前在遗传算法工具中设置下列参数：

? 设置适应度函数为 @Rastriginsfcn。

167

? 设置“Number of variables”为 2。

? 在“Plots”窗格选择“Best fitness（最佳适应度）”。 ? 在“Plots”窗格选择“Range”。 ? 设置“Initial range”为 [1；1.1]。

然后，单击Start按钮。遗传算法返回最佳适应度值为2，其显示图形如图8.36所示。

图8.36 初始范围为[1; 1.1]时最佳适应度值和平均距离

图8.38上面为每代最佳适应度值变化图，下面为每代个体之间平均距离图，它可以很好地用来衡量种群的多样性。对于初始范围的设置，由于多样性太小，算法进展很小。

第二次，尝试设置“Initial range”为 [1; 100] ，运行算法，得到最佳适应度值大约为3.9，如图图8.37所示。

168

图8.37 初始范围为[1; 100]时最佳适应度值和平均距离

这次，算法进展较快。但是，由于个体之间的平均距离太大，最佳个体远离最优解。 第三次，设置“Initial range”为 [1; 2] ，运行算法。得到最佳适应度值大约为0.012，如图8.38所示。

169

图8.38 初始范围为[1; 2]时最佳适应度值和平均距离

这次由于多样性比较适合这个问题，所以算法得到的结果比前两次都好。 （2）设置种群尺度

在“种群（Population）”参数域中“Size”决定每代种群的大小。增加种群的大小，遗传算法能够搜索更多的点，因此，能够得到较好结果。但是，种群越大，遗传算法每代运行时间越长。

注意：至少应该设置“尺度（Size）”的值为“Number of variables”，以便在每一种群中使个体超出搜索范围。

进行实验时，可以设置不同的种群尺度，不限制运行时间，以期得到最好结果。 8.3.3.2 适应度测量

适应度测量把适应度函数返回的原始适应度得分值转换为适合选择函数的范围内的值。选择函数根据适应度值的大小，选择下一代的父体。选择函数分配大选择概率给适应度值大的个体。适应度测量值的范围影响遗传算法的性能。如果测量值变化范围太大，则具有高测量值的个体复制的速度很快，取代种群基因池的速度很快，防碍了遗传算法搜索解空间的其它区域。相反，如果测量值变化太小，所有个体复制机会基本相同，则搜索过程进展缓慢。

缺省的适应度尺度变换函数为Rank（排序），根据每个个体的顺序而不是它的得分值来变换原始得分值。个体的顺序是它在分类后的位置。最适应的个体的序号为1，次之为2，依次类推。排序尺度变换函数分配尺度值有下列目的：

? 个体的尺度值与n成正比。

? 整个种群的尺度值的和等于要求生成下一代父体的数目。 排序适应度尺度变换函数避免了初始值的界限的影响。

图8.39所示为具有20个个体的一个典型种群的初始得分值，按升序排序。

170

图8.39 具有20个个体的一个典型种群的初始得分值

图8.40所示为使用尺度变换函数的初始尺度值。

图8.40 使用尺度变换函数的初始尺度值

因为算法按适应度函数的最小化处理，所以低的初始值具有高的尺度值。又因为排序尺度变换只根据个体的顺序分配值的大小，对于一个大小为20、父辈数等于32的群体，显示的

171

尺度值可以是相同的。

可以把排序尺度变换（Rank scaling）与顶级尺度变换（Top scaling）进行比较。为了观察尺度变换的效果，可以把遗传算法利用排序尺度变换得到的结果与利用其它函数（如顶级变换）得到的结果相比较。默认情况下，顶级尺度变换分配4个最佳适应度个体相同的尺度值，等于父辈数除以4，而分配其它个体的尺度值为0。利用默认的选择函数，只有4个最佳适应度个体能被选为父辈。图8.41为比较排序尺度变换与顶级尺度变换得到的尺度值，种群尺度为20，父辈数为32。

图8.41 比较排序尺度变换与顶级尺度变换得到的尺度值

因为Top scaling限制父辈为最佳适应度个体，它产生的种群类型比Rank scaling产生的种群类型少。图8.42所示为每一代Rank scaling与Top scaling得到的个体之间的距离变化的比较。

172

图8.42 排序与顶级尺度变换各代个体之间距离变化之比较

8.3.3.3 选择

选择函数根据个体由适应度尺度变换函数得到的尺度值，为下一代选择父辈。当一个个体为多个子辈贡献它的基因时，它就可能多次被选做父辈。默认的选择函数为Stochastic uniform（随机均匀函数）——在每一父辈画出一条与选择线对应的直线，长度与它的尺度值成比例。算法以等步长在线上移动。在每一步，算法从落入线上的部分分配父辈。

一个比较确定的选择函数是Remainder，由下列两步运行：

首先，函数按照尺度值的整数部分为每个个体选择父辈。例如，假设一个个体的尺度值是2.3，函数选择这个个体两次作为父辈。

其次，在随机均匀选择时，选择函数利用尺度值的小数部分选择剩余的父辈。函数落入选择线内，即长度与个体尺度值的小数部分成比例，在线上按等步长移动来选择父辈。注意，如果尺度值的小数部分都等于0，就象顶级尺度变换一样，选择是完全确定的。 8.3.3.4 复制参数

复制参数控制遗传算法怎样生成下一代。这些参数有：

elite count（优良计数）— 在当前种群中，具有最佳适应度值的个体遗传到下一代的个体数。这些个体称为优良子辈（elite children）。elite count的默认值为2。

当优良计数至少为1时，最佳适应度值可能从一代到下一代减少。这是人们希望的，因为遗传算法使适应度函数最小化。设置elite count为一个大数，可以使得最适应个体控制种群，但可能减小搜索的有效性。

Crossover fraction（交叉概率）— 下一代个体的一小部分，它不是elite children（优良子辈），而是由交叉产生的部分。参见“8.3.3.7 设置交叉概率”一节。 8.3.3.5 变异与交叉

遗传算法运用当前代的个体生成子代个体，构成下一代。除了elite children外，算法还生成下列子代个体：

173

? 从当前代中选择两个个体，交换两个个体的某个或某些位（基因），结合后形成交叉子个体。

? 随机改变当前代的单个个体形成变异子个体。

这两个过程是遗传算法的主要过程。交叉能够使遗传算法从不同的个体中提取更好的基因，结合到具有优势的子个体中。变异增加了种群的多样性，因而增大了算法生成更高适应度值的个体的可能性。没有变异，算法只能产生由初始种群结合基因的子集构成的个体。

算法生成的子个体类型如下：

? Elite count，在“Reproduction”文本框，指定elite children的数目。

? Crossover fraction，在Reproduction文本框，指定种群中交叉子个体的概率，它不同于elite children。例如，假设Population size（种群尺度）为20， Elite count为 2，Crossover fraction为 0.8，则下一代子个体类型如下： ? 有2个优良子辈。

? 除优良子辈以外，还有18个个体。所以计算 0.8*18 = 14.4取整得14，得到14个交叉

子个体。

? 还有4个个体，它们不是elite children，而是变异子个体。 8.3.3.6 设置变异大小

遗传算法应用变异函数（Mutation function）字段中指定的函数进行变异操作。默认的变异函数为高斯函数Gaussian，它把一个从高斯分布选择的随机数，即mutation，加到父辈向量的每一个项上。典型情况下，与分布的标准差成比例的变异大小，在每一后代中都是减小的。通过参数尺度（Scale）和压缩（Shrink），可以控制每一代变异的平均数量。

Scale控制第一代变异的标准差。标准差是Scale乘以初始种群的范围——该范围是使用者由Initial range参数指定的。

压缩（Shrink）控制变异的平均数量的减少率。标准差线性减小，以便标准差等于1 – Shrink乘以它在第一代的值。例如，假设Shrink缺省值为1，则变异数在最后一步减小到0。通过选择绘图函数Distance（距离）和Range能够观察到变异的效果。Rastrigin函数的遗传算法的运行结果如图8.43所示。

图8.43 压缩值为1时Rastrigin函数的距离和范围

图8.45的上部图形显示每一代各点之间的平均距离。当变异数减小时，个体之间的平均距离也减小，在最后一代大约减小到0。图8.45下部图形中的垂直线表示每一代适应度值由最小

174

到最大的范围以及适应度值的平均值。当变异数减小时，适应度值的范围也减小。这些图形显示减少变异数，也就减小了子辈的多样性。

作为比较，图8.44显示当Shrink取为0.5时的Distance和Range的图形。

图8.44 压缩值为0.5时Rastrigin函数的距离与范围

当Shrink设置为0.5时，最后一代的平均变异数减小了一半。同样，个体之间的平均距离也大约减小了一半。 8.3.3.7 设置交叉概率

在Reproduction选项中，由Crossover fraction文本框指定每一种群的一部分，它们不是elite children，而是组成的交叉子个体。取交叉概率等于1，意味着所有子个体都是交叉子个体；取交叉概率等于0，意味着所有子个体都是变异子个体。下面的例子说明，这两个极端设置，都不是有效的函数优化策略。

在这个例子中，定义适应度函数为：

f(x1,x2,,xn)?x1?x2??xn

即点的适应度函数值为所有点的坐标的绝对值之和。

通过设置Fitness function 为@(x) sum(abs(x))，就可以定义为一个无名函数。 运行这个例子时，有关参数设置如下：

? 设置Fitness function为 @(x) sum(abs(x))。 ? 设置Number of variables为10。 ? 设置Initial range为[-1; 1]。

? 在Plots窗格，选择Best fitness和Distance。 首先设置Crossover fraction为缺省值0.8，运行算法，得到最佳适应度值大约为0.2，如图8.45所示。

175

图8.45 交叉概率为0.8时函数的适应度值与平均距离

（1）无变异的交叉

为了观察没有变异时遗传算法怎样运行，设置Crossover fraction为1.0，并单击Start按钮，得到的最佳适应度值约等于1.3，如图8.46所示。

最佳个体在第8代产生 所有个体都是相同的

图8.46 无变异的交叉下函数的适应度值与平均距离

在这种情况下，算法选择初始种群中的个体基因，并把它们重新结合起来。因为没有变

176

异，所以算法不能产生任何新的基因。算法利用这些第8代的基因来产生最好的个体，这时最佳适应度图形呈现为水平。此后，它从紧接着的一代选择最佳个体，产生新的最佳个体的副本。到了第17代，种群中的所有个体都相同，也就是说，都变成了最佳个体。当这种情形出现时，个体之间的平均距离为0。由于算法在第8代之后不能改善最佳适应度值，它在50代过后就陷于停滞，因为Stall generations（停滞代数）设置为50。

（2）无交叉的变异

为了查看遗传算法在没有交叉的情形下是如何工作的，设置Crossover fraction为0，并单击Start按钮，得到的最佳适应度值约等于3.5，如图8.47所示。

图8.47 无交叉的变异下函数的适应度值与平均距离

在这种情况下，算法应用的随机变化没有改善第一代最佳个体的适应度函数值。但是，它改善了其它个体的个体基因，可以由图8.49中的上部图形看到适应度函数的平均值逐渐减少，这些改善的基因没有和最佳个体基因结合，因为没有交叉。结果，最佳适应度图形是水平的，并且算法在50代停滞。

（3）比较遗传算法取不同交叉概率时的运行结果

在工具箱有一个演示函数deterministicstudy.m，Crossover fraction分别设置为0、0.2、0.4、0.6、0.8、1，把遗传算法应用到Rastrigin函数，比较不同的运行结果。遗传算法运行10代。对于交叉概率的每一个值，画出每一代之前的所有代的最佳适应度值的均值和标准差。在MATLAB 命令窗口，输入deterministicstudy，当演示结束时，画出图形，如图8.48所示。

177

图8.48 不同交叉概率下最佳适应度值的均值和标准差

图8.48中下面的图形显示10代不同的交叉概率下最佳适应度值的均值和标准差，上边图形的颜色显示每一代的最佳适应度值。对于这个适应度函数，当Crossover fraction等于0.8时得到最好结果。但是，对于其它适应度函数，交叉概率可能取另外的值，才能得到最好结果。 8.3.3.8 举例——相对于全局的局部最小值

有时，优化的目的是要找到函数的全局最小值或最大值——一个点的函数值比搜索空间中其他任何点上的函数值都要小或都要大。但是，最优化算法有时得到的是局部最小值——该点的函数值比它的附近点的函数值小，但是可能比搜索空间的其它点的函数值大。为了克服这个不足，遗传算法的参数必须设置适当。例如，考虑下面的函数

x2?当x?20 ??exp[?()],f(x)??20???exp(?1)?(x?20)(x?22),当x?20函数f (x)的图形如图8.49所示。

178

局部最小值

图8.49 函数f (x)的图形

这个函数有两个局部最小值，当x = 0时，函数值f (x)＝-1；当x = 21时，函数值f (x)为

f (x)＝-(1+1/e)≈-1.36787944117144

所以，全局最小值是当x = 21时的函数值。

以下列步骤运行遗传算法：

(1) 用MATLAB编辑器将下面的代码复制、粘贴到一个新M文件。

function y = two_min(x) if x<20

y = -exp(-(x/20).^2); else

y = -exp(-1)+(x-20)*(x-22); end

(2) 用MATLAB将这个文件保存为two_min.m。 (3) 在遗传算法工具中，进行如下设置： ? 设置Fitness function为@two_min。 ? 设置Number of variables等于1。 (4) 单击Start按钮。

遗传算法返回的值，接近局部最小值点x = 0，如图8.50所示。

179

图8.50 函数f (x)的局部最优解

图8.51说明为什么算法得到的是局部最小值，而不是全局最小值。该图画出了每代个体的范围以及最优个体。

最佳值 0.00028487

图8.51 初始范围为[0; 1]时每代个体的范围及最优个体

注意：所有个体的范围为-2~2.5。由于变异，这个范围比缺省Initial range [0;1]大，但是没有大到搜索全局最小值点x = 21的附近。

使遗传算法搜索更大范围的点的一个方法是增加种群的多样性，即增大Initial range。初始范围不一定包含点x = 21，但是它必须足够大，以便算法能产生x = 21附近的个体。设置Initial range为[0;15] ，如图8.52所示。

180

图8.52 设置初始范围为[0; 15]

设置初始范围为[0; 15] 然后，单击Start按钮。遗传算法返回的值非常接近于x＝21时的函数值，如图8.53所示。

图8.53 函数f (x)的全部最优解

这一次，图形显示个体更大的范围。在第二代，有大于21的个体，在第12代，算法找到大约等于21的最优个体，如图8.54所示。

181

最佳值 20.9876

图8.54 初始范围为[0; 15]时每代个体的范围及最优个体

8.3.3.9 使用混合函数

混合函数是一个最优化函数。在遗传算法停止后，为了改善适应度函数值，可以使用混合函数。混合函数将遗传算法得到的最后点作为它的初始点。可以在Hybrid function（混合函数）参数域指定混合函数。

作为一个例子，Rosenbrock函数定义为

22f(x1,x2)?100(x2?x1)?(1?x1)2 该函数的图形如图8.55所示。

182