MATLAB遗传算法工具箱在函数优化中的应用

2009年第7期福建电脑

MATLAB遗传算法工具箱在函数优化中的应用

金芬

（苏州市职业大学机电工程系江苏苏州215104)

【摘要】：本文介绍了遗传算法的运算流程，阐述了MATLAB遗传算法工具箱的主要函数及其功能。结合典型的二维和高维多峰测试函数，在MATLAB环境中有效地解决了用遗传算法求解函数优化问题，验证了MATLAB遗传算法工具箱的有效性和灵活性。

【关键词】：遗传算法；MATLAB；工具箱；函数优化

1、引言

遗传算法(Genetic Algorithm)[1,2]是一种借鉴生物界自然选择和遗传机制的高度并行、随机、自适应的全局优化概率搜索算法。近三十年来，遗传算法已广泛应用于函数优化、自动控制、机器学习、人工生命等众多领域，各领域的学者和专家对此进行了深入的研究，并用各种语言来实现这个算法。MATLAB是一种面向科学与工程计算的高效率高级语言，其中的MATLAB遗传算法工具箱提供了对各种优化问题的一个完整的解决方案。它具有函数表达简洁、遗传操作灵活、可任意选择多种编码方式和优化算子、算法参数设置自由等特点而受到用户的青睐，并为应用和研究遗传算法提供了稳定可靠、结构灵活、可扩展的开发平台。

函数优化问题是遗传算法的经典应用领域,也是对遗传算法进行性能评价的常用算例,本文利用MATLAB遗传算法工具箱，结合2个典型的测试函数，有效地实现了函数优化问题，并取得了较好的性能。

2、遗传算法的运算流程

遗传算法以适应度函数为依据，算法从一组随机产生的初始种群开始，反复经过选择、交叉和变异三种遗传操作，不断进化，是个迭代搜索过程。其基本流程如下：

（1）确定待优化的参数范围，并对搜索空间进行编码；

（2）随机产生包含各个个体的初始种群；

（3）将种群中各个个体解码成对应的参数值，用解码后的参数求解适应度函数，运用适应度函数评估各个个体的适应度；

（4）对收敛条件进行判断，如果已经找到最佳个体，则停止，否则继续进行遗传操作；

（5）按适应度进行选择操作，让适应度大的个体在种群中占有较大的比例，一些适应度较小的个体将会被淘汰；

（6）随机交叉，两个个体按一定的交叉概率进行交叉操作，并产生两个新的子个体；

（7）按照一定的变异概率变异，使个体的某个或某些位的性质发生改变；

（8）重复步骤（3）至（7），直至满足终止条件。

3、MATLAB遗传工具箱的主要函数及其功能

MATLAB遗传算法工具箱实现遗传算法的步骤和其他编程语言实现遗传算法的流程一样，也需要解决编码方式、初始群体的建立、选择算子、交叉算子、变异算子、评价函数及终止标准等问题。为解决这些问题，遗传算法工具箱提供了许多实用的函数，主要有种群创建函数、适应度计算函数、选择函数、变异算子、交叉算子、绘图函数和其它实用函数等[3,4]，这些函数都是MATLAB的M文件，用户也可以根据实际优化问题编写特定的M文件来实现、改进和扩展遗传算法工具箱的性能。

3.1初始化种群创建函数

由于GA不能直接处理空间的数据，必须通过编码将其表示成遗传空间的基因型串结构数据，随机产生的N个初始串结构数据构成一个初始种群。工具箱提供了3种创建初始种群的方法，它们为二进制编码、实值编码和整数编码函数，用户还可以自定义初始化函数。

3.2适应度函数

适应度是遗传算法引导搜索的主要依据，改变种群内部结构的遗传操作均要通过适应度函数加以控制。遗传算法工具箱总是使目标函数或适应度函数最小化，即，若要求函数的最大值，则要进行变换，取，转而求的最小值。工具箱提供了适应度的尺度变换函数，如排列(Rank)、线性变换(Shift linear)、比率(Proportional)等函数，也可以自定义。

3.3选择操作函数

选择操作是从当前个体中选出优良的个体，使其有机会作为父辈为下一代繁殖子孙。个体适应度越高，被选择的机会就越多。工具箱提供了随机均匀分布选择法(Stochastic uniform)、赌轮盘选择法(Roulette)、剩余选择法(Remainder)、锦标赛选择法(Tournament)，也可以自定义。

3.4交叉操作函数

交叉操作是遗传算法中的主要操作，它将群体内的每个个体随机搭配成对，对每一对个体按杂交概率交换它们之间的部分染色体，通过杂交可得到新一代个体，新个体组合了其父辈个体的特性。工具箱中提供的交叉函数有：离散重组(Scattered)、线性重组(Heuristic)、单点交叉(Simple point)等五种交叉方式，也可以自定义。

3.5变异函数

变异操作首先在群体中随机选择一个个体，对选中的个体以一定的概率随机地改变串结构数据中某个位的值。变异操作有利于保持种群的多样性、跳出局部极值，防止未成熟收敛。工具箱中提供的变异函数有高斯变异(Gaussian)、均匀变异(Uni-form)等，也可以自定义。

3.6终止条件

终止条件判断是指在什么情况下认为算法找到了最优解，从而可以终止算法。工具箱中设置的参数有最大代数(Genera-tion)、停止执行前的最大时间(Time limited)、适应度限(Fitness limited)、停滞代数(Stall generation)、停滞时间(Stall time)。

3.7主程序函数

主程序函数的作用是调用相应的遗传操作函数，完成遗传优化。工具箱中遗传算法的主函数为：

[x fval]=ga(@fitnessfcn，nvars，options)

输出参数：x为返回的最终点即最后变量值；fval为适应度函数在x点的值即最优值。

输入参数：@fitnessfcn是计算适应度函数值的M文件的函数；nvars是适应度函数中独立变量的个数；options是参数结构体，可以缺省。

每一个参数的值都存放在参数结构体options中，若参数值需要修改，则可通过函数options=gaoptimset设置。如参数

基金项目：苏州市职业大学科研资助项目（SZD09L14）

23

2009年第7期

福建电脑（下转第45页）

Populationsize 的值由缺省值20变为100，而其他参数仍为缺省

值，则编写：

options=gaoptimset(options,'PopulationSize',100)

再输入ga(@fitnessfun,nvars,options)，函数ga 将以种群的个体为100运行遗传算法。4、优化实例与仿真结果

选择了一个典型的二维多峰测试函数和一个高维多峰测试函数为优化对象，以测试MATLAB 遗传算法工具箱的有效性。4.1二维函数的优化4.1.1二维函数

Schaffer2Function [5]

该函数是一个多峰函数，有无数个局部极大点，但只有1个全局最大点，在点(0,0)处，最大值为-1。此函数的最大峰周围有两圈脊，它们的取值分别为0.990284和0.962776，因此优化过程中很容易停滞在这些局部极大点，其几何特性如图1所示。

图1函数f 1的几何特性

图2函数f 1最佳解的变化和平均值的的变化曲线

4.1.2MATLAB 程序

算法采用实数编码，变量维数为2，变量范围为[-10;10]，种群规模为100，最大遗传代数为200，停滞代数为50，锦标赛选择，交叉采用线性重组，交叉概率为0.9，高斯变异，其它参数使用缺省值。

1．函数f 1的M 文件

function z=Schaffer2(x)

z=-(0.5-((sin(sqrt(x(1)^2+x(2)^2)))^2-0.5)/(1+0.001*(x(1)^2+x(2)^2))^2);

文件取名Schaffer2.m ，并保存在MATLAB 路径指定的目录

中。

2．设置参数和调用遗传算法的主程序fitnessFunction=@Schaffer2;nvars=2;

options=gaoptimset(options,'PopInitRange',[-10;10]);options=gaoptimset(options,'PopulationSize',100)options=gaoptimset(options,'CrossoverFraction',0.9);options =gaoptimset(options,'Generations',200);options =gaoptimset(options,'SelectionFcn',{@selecttournament,2});

options =gaoptimset(options,'CrossoverFcn',{@crossoverheuristic,0.9});

options =gaoptimset(options,'MutationFcn',{@mutationgaussian,1.0,1.0});

[x fval]=ga(@fitnessFunction,nvars,options )4.1.3仿真结果

仿真运行到最后一代的最优解为f 1(X)=-1，种群平均值Mean f 1(X)=-1，获得最优解时2个变量取值分别为：(-2.93195e -9,8.26527e-9)，最佳解的变化和平均值的变化曲线如图2所

示。

4.2高维函数的优化

Generalized Rosenbrock ’s Function [5]:

它是一个非线性、对称、可分离、多峰的高维函数，有大量的局部极小值，但只有一个全局最小点（0,…,0），最小值为0。其三维几何特性如图3所示。

图3函数

f 2的三维几何特性

采用实数编码，种群规模为150，变量维数为30，最大遗传代数为1000，停滞代数为100，交叉概率为0.9，变量范围为[-5.12;5.12]，均匀变异，变异概率为0.02，其它参数使用缺省值。

该函数的M 文件Rosenbrock.m 为：

function z=f (Chrom);%Chrom 为种群的染色体z=sum((Chrom .*Chrom -10*cos(2*pi*Chrom)+10)')';

函数f 2的参数设置和主程序的编写与函数f1类似，可直接

调用工具箱内相应的函数或自定义有关函数，并设置相关参数。经仿真计算得到最后一代的最优解为f 2(X)=2.0536e-005，种群平均值Mean f 2(X)=4.758，也达到相当高的精度。函数f 2最佳解的变化和平均值的变化曲线如图4所示。

获得最优解时30个变量取值分别为：

(x 1,x 2,…,x 30)=(-2.27358e-5,2.12366e-5,-1.454e-6,-8.

96816e-5,-7.02918e-6,6.4986e-7,-1.75947e-4,-3.84475e-6,9.36530e-5,1.95297e-5,1.65986e-4,1.83856e-5,-2.79653e-5,2.3970e-5,-6.6609e-5,-1.04362e-5,9.48163e-5,2.3233e-5,-2.36429e-5，5.2159e-5,1.37547e -5,-2.15606e-5,4.86753e -5,1.27874e -5,-5.51713e -5,-1.64925e -5,-2.42034e -5,-1.65108e-5,9.1642e-8,-2.00846e-5)。

图4函数f 2

最佳解的变化和平均值的变化曲线

24

2009年第7期福建电脑

（上接第24页）

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

5、结束语

MATLAB具有强大的矩阵运算能力，利用MATLAB的遗传算法工具箱可以对传统优化算法难以实现全局优化的非线性多峰函数进行优化，本文的实验结果验证了MATLAB遗传算法优化工具箱能有效、灵活地求解复杂函数的优化问题，而且所求解能达到或以相当高的精度逼近最优解。

参考文献：

1.Holland J H.Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan press,1975,1-22

2.陈国良，王煦法等.遗传算法及其应用[M].北京:人民邮电出版社,1996. 06,10-14

3.苏金明，张莲花，刘波等.MATLAB工具箱应用[M].北京：电子工业出版社，200

4.01

4.雷英杰，张善文等.MATLAB遗传算法工具箱及其应用[M].西安:西安电子科技大学出版社,200

5.04

5.李敏强，寇纪凇，林丹等.遗传算法的基本理论及其应用[M].北京:科学出版社,2002.03,399-403

提出了许多设计开发模式和方法。这些都为我们进行准确判断并解决"教"与"乐"的平衡点，设计出优质的教育游戏奠定了基础。

（4）制定教育游戏标准，以规范教育游戏软件开发

对于教育游戏这样一个争议性较强的新生事物，应该有一个公开、权威、统一的规范来保证其健康发展。根据规范对这类游戏软件在技术性、娱乐性，教育性等方面进行全面审查与评价，给出一个权威性意见，这样可以保证进入教学领域的这类软件的质量，笔者[4]在这里给出一个参考意见：①教育游戏应当以教育为目的；②教育游戏应当具有特定的教学目标；③教育游戏的内容应当与教学有关；④教育游戏应当具有娱乐性；⑤教育游戏内容应当符合社会伦理规范；⑥教育游戏应当符合学校的课程模式和规则；⑦教育游戏需要通过教育当局审核；⑧教育游戏应具有阶段性；⑨教育游戏的开发应符合一般教育软件开发程序。

（5）运用教育游戏的功能，补充传统教育的不足

学生需要掌握的知识技能有很多种，终身必备的最重要的知识技能在学校都以课程尤其是学科课程的形式开设。面对大量的学科知识，班级讲授式教学是最有效率的方式。因此教育游戏软件不能替代学校教育、课堂教育的作用，只是某种形式的补充。既然教育游戏仅仅是学校教育、课堂教育的一种补充，就没必要重复学校教育、课堂教育的内容，而应当补充其不足的部分。

譬如，目前学校教育太重视学科知识，而与社会生活联系很少，学生眼界不开阔，缺乏生活常识、生活经验和生活能力，教育游戏就应侧重在百科知识、生活常识等方面。又譬如，环境教育、性健康（包括爱滋病防护）、公民行为准则、心理健康教育、生存教育以及人文精神等都非常重要，关乎学生的一生，学校也开设这些课程或讲座，但由于不属于学科考试内容，并没有得到学校、教师和学生的充分重视，教育游戏就应该加强这方面的内容等等。

2、有效教育游戏软件设计与开发的基本方法

综上所述，要开发出有效的教育游戏软件，笔者认为在设计与开发过程中应当把握以下方法：

（1）选题新颖有益智性。应该尽量选择比较新颖的游戏题材，如果游戏题材比较老旧的话，也应该试图从一个全新的角度来阐述一个古老的故事。要让游戏者在不同的方面领略到新意。教育游戏创设的情景要尽可能地反映社会学习、生活的不同方面，使学生在游戏中不仅能掌握知识，还能增加生活体验，积累职业经验，开阔视野，提高分析问题、解决问题的能力，发展多元智能。

（2）循序渐进，引人入胜。一方面从游戏本身来说，上手要容易，操作要简单；另一方面从知识内容设置来说，应该从最基本的内容开始入手。这样游戏使用者可以比较容易的学会游戏的操作并且能够以原有的知识为基础，在游戏中取得成功，从而激发兴趣，为进一步参与游戏奠定了基础。

（3）注重知识与技能、训练与巩固相结合。游戏使用者在熟悉游戏和对原有知识内容复习的基础上，可以进行下一步的游戏。此时，要为游戏使用者设计一些比较困难的任务来完成，在完成的过程中既需要游戏使用者对游戏的操作进一步的熟悉，又需要相关知识的支持。可以把相关知识的获取放在游戏的各个关卡之中，这样游戏使用者在一个探索的过程中来获取各种信息与知识，同时把获得的信息与知识应用于游戏过程中，达到巩固与熟练的目的。

（4）提倡积极互动，竞争合作。当游戏使用者对游戏的熟悉程度和知识的理解情况，达到一定的水平之后，就要为其提供一个交流的平台,使之能够在游戏的过程中与其他的游戏使用者进行交流,通过合作与竞争得到其他游戏使用者的认可。此时,游戏使用者可以在游戏的过程中得到其在现实中期望得到的荣誉与尊重,这也是游戏过程中最高的一个境界。

（5）建立科学而又有效的评估系统。[5]教育游戏的评价系统应该分为两部分:一是一般游戏中的过关升级，即完成一个任务就可以进入下一个任务,或者获得一些有用的工具、宝贝,或者得到能力的提升；二是一个任务完成后的反思总结,这区别于一般游戏玩过了就不用再管的特点。我们可以让学生把游戏中的感想记录下来,采用的方式可以灵活多样,可以作为战略库、智囊团的形式存在于游戏任务中,也可以作为日记本的形式放在游戏任务外,记录下今天游戏的心得体会。这就类似于学习档案的建立,通过学生在游戏过程中以及完成整个游戏后的反思总结,教师可以评价学生在整个学习过程中的表现,实现过程性评价,同时教师也应该做出回应,对学生的学习进行总结。

（6）建立导师或同伴帮助模块。游戏者在游戏中可以有向导师寻求帮助的部分。现在的网络游戏在这方面已经做得很好,通过游戏平台游戏者可以获得多方面的帮助,而在教育游戏中我们也应该添加一个专家系统,提供教师的专业指导。同时通过跟踪学生过关斩将的过程,导师系统应该指出学生对知识的掌握程度,以及继续学习的建议。

当然，除了以上的设计方法思路外，还可以根据具体的教育游戏软件的需求，适当的增加其系统模块，如奖惩系统，防作弊系统，职业管理系统，考验系统，答疑系统等等。

四、结语

我国教育游戏软件刚刚起步，现有的教育游戏软件开发与设计中存在一些问题。作为教育游戏软件的设计者应该分析现有教育游戏软件的不足，根据学习者的具体需求，结合应用过程中遇到的问题，加以改进，设计出更好的更适合于学习者学习的教育游戏软件。我们相信游戏软件具有广阔的发展前景，在快乐教育和愉悦教育的思想的引导下，教育游戏软件在教育过程中，必将发挥其重要的作用。

参考文献：

1.陈卫东.教育游戏的设计与应用策略思考[J].吉林广播电视大学学报, 2008,(1):17-20.

2.蔡进,赵呈领.浅谈我国教育游戏的现状、问题及开发原则[J].教育信息化,2005,(10):21-2

3.

3.刘巍,徐鑫.教育游戏软件的开发原则和方法[J].中小学电教,2006,(8): 16-18

4.蒋立兵.教育游戏应用绩效探讨[J].远程教育杂志,2008,(3):71-74.

5.许黎黎,曾祥霖.新课改背景下的教育游戏设计[J].当代教育论坛,2005, (11):51-52

45