基于Matlab遗传算法工具箱的函数优化问题求解

MODERN COMPUTER2006.12 实践与经验 现 代 计 算 机 (总 第 二 四 九 期 ) 引 言 遗传算法(Genetic Algorithm)是建立在自然选择 和群体遗传学基础上的一种非数值计算优化方法。遗 传算法作为一种实用、高效、鲁棒性强的优化技术,广 泛地应用于函数优化、机器学习、自动控制、图像处理 以及人工智能领域。Matlab是MathWorks公司推出的 一套高性能的数值计算可视化软件,它集数值分析、 矩阵运算、信号处理和图形显示于一体,构成了一个 方便的、界面友好的用户环境。遗传算法工具箱使用 Matlab矩阵函数,为实现广泛的遗传算法应用建立了 一套通用的工具,这个工具是使用M文件编写的命 令行函数,是实现遗传算法大部分重要功能的程序的 集合。用户可以根据实际需要,通过调用这些命令行 函数编写出功能强大的遗传算法程序。 1 遗传算法 遗传算法将问题的解表示成字符串,并把这样的 字符串当作人工染色体或称为个体,多个个体构成一 个种群,随机产生若干个个体构成初始种群,通过对 种群的不断进化,利用“优胜劣汰”的自然选择机制, 使种群中的个体不断朝着最优解的方向移动,最终搜 索到问题的最优解。 遗传算法的基本流程如图1所示。算法的主要运 算过程如下: ①编码:在用遗传算法求解问题时,首先遇到的 是编码问题。将问题的解以适合于遗传算法求解的形 式进行编码,称为遗传算法的表示。而交叉、变异等操 作与编码的形式有关,因此在进行编码时要考虑到交 叉和变异问题。最简单的编码方式是二进制编码,此 外,编码的方式还有整数编码、实数编码、树编码等。 图1遗传算法流程图 ②初始种群的生成:产生初始种群是在求解之 前,在解的备选空间中选择若干个体组成初始种群, 通常产生初始种群采用的是随机法。 ③适应度评价:根据生物进化“适者生存”的原 则,需要对每个个体适应环境的能力进行刻画,从而 引入适应度。适应度是遗传算法在群体进化过程中用 到的唯一的信息,它为字符串如何进行复制给出了定 量的描述。适应度函数通过计算个体的适应值,来比 较个体的适应度。适应度函数分为无约束条件的适应 度函数和有约束条件的适应度函数。 基于 Matlab遗传算法工具箱 的函数优化问题求解 周琛琛 (安徽大学计算机学院,合肥 230039) 摘 要:介绍了遗传算法的基本原理和求解流程,详细阐述了Matlab遗传算法工具箱的使用方法,并 通过使用遗传算法工具箱对一个典型的函数优化问题进行求解,验证了该工具箱在解决函数 优化问题上的有效性和实用性。 关键词:遗传算法;函数优化;Matlab !!! !!!!!! ! ! ! ! ! !!!! !!!!!! ! ! ! ! ! !" 现 代 计 算 机 (总 第 二 四 九 期 ) MODERN COMPUTER2006.12 实践与经验 ④选择:种群中的个体在进行交叉之前,要进行 选择。选择的目的是获得较优的个体作为父代,进行 下一步的交叉。选择的依据是个体的适应度,适应度 值高的个体被选中的可能性大,适应度低的个体被选 中的概率小。适应度高的个体可能被多次复制,而适 应度低的个体可能一次也未被选中。选择算子有时也 叫复制算子。常用的选择方法是适应度比例法,也叫 轮盘赌法,它的基本原则是按照个体的适应度大小比 例进行选择。 ⑤交叉:交叉也称为交配,即将两个父代个体的 编码串的部分基因进行交换,产生新的个体。交叉算子 是种群遗传算法中的重要算子,是种群产生新个体的 主要手段。对于二进制编码,具体实施交叉的方法有单 点交叉、两点交叉、多点交叉、一致交叉等。对于实数编 码,交叉的方法有离散重组、中间重组、线性重组等。 ⑥变异:变异操作首先在种群中随机选择一个个 体,对于选中的个体按照一定的概率随机改变串结构 中的某个值,即对种群中的每一个个体,以某一概率 改变某一个或某一些基因座上的值为其他的基因。同 生物界一样,遗传算法中发生变异的概率很低。变异 操作为新个体的产生提供了机会。 ⑦终止条件判断:终止条件判断是指在什么情况 下认为算法找到了最优解,从而可以终止算法。由于 通常使用遗传算法解决具体问题时,并不知道问题的 最优解是什么,也不知道其最优解的目标函数值,因 而需要通过算法终止,并获得最优解。 2 Matlab遗传算法工具箱 Matlab7.0中包含一个专门设计的遗传算法与直 接搜索工具箱 (GeneticAlgorithmandDirectSearch Toolbox)。使用该工具箱可以扩展优化工具箱在处理 优化问题方面的能力,可以处理传统优化技术难以解 决的问题,包括难以定义或不方便数学建模的问题, 还可以解决目标函数复杂的问题,比如目标函数不连 续或具有高度的非线性、随机性以及目标函数不可微 的情况。 GADS工具箱中遗传算法的主函数为: [xfval]=ga(@fitnessfcn,nvars,options) 其中,输出参数: ①x:返回的最终点; ②fval:适应度函数在x点的值。 输入参数: ①@fitnessfun:计算适应度函数的M文件的函数 句柄; ②nvars:适应度函数中变量个数; ③options:参数结构体。 输入参数结构体options具有缺省值,可以利用 缺省参数运行遗传算法,调用语句如下: [xfval]=ga(@fitnessfcn,nvars) 每一个参数的值都存放在参数结构体 options 中,例如 options.Populationsize在结构体中的缺省值 为20,如果需要设置Populationsize的值等于100,可 以通过下面的语句进行修改: options=gaoptimset('PopulationSize',100) 这样,参数 Populationsize的值为 100,其他参数 的值为缺省值或当前值。这时,再输入: ga(@fitnessfun,nvars,options) 函数ga将以种群中个体为100运行遗传算法。 为了得到遗传算法更多的输出结果,可以使用下 面的语句调用ga: [xfvalreasonoutputpopulationscores]=ga(@fitnessfcn, nvars) 除了x和fval之外增加了四个输出变量: ①reason:算法停止的原因; ②output:算法每一代的性能; ③population:最后种群; ④scores:最后得分值。 3 优化实例 具有两个独立变量的Rastrigin函数定义为: Ras(x)=20+x12+x22-10(cos2πx1+cos2πx2) Rastrigin函数具有许多局部最小值。然而,该函 数只有一个全局最小值,出现在[0,0]点处,函数在该 点的值为0,Rastrigin函数的值均大于0。局部最小点 距离原点越远,该点的函数值越大。Rastrigin函数是 最常用于遗传算法测试的函数之一,因为它有许多局 部最小点,使得使用标准的、基于梯度的查找全局最 小值的方法十分困难。 问题:求Rastrigin函数的最小值,其中-5≤x1, x2≤5。参数设置:种群大小=25,交叉率=0.85,变异 率=0.15,最大代数=50,其他参数使用缺省值。 ①编写Rastrigin函数的M文件rastrigin.m: functionz=rastrigin(x) z=20+x(1)^2+x(2)^2-10*(cos(2*pi*x(1))+cos(2*pi *x(2))); !" MODERN COMPUTER2006.12 实践与经验 现 代 计 算 机 (总 第 二 四 九 期 ) ②设置参数和调用遗传算法的程序的主体部分 如下: fitnessFunction=@rastrigin; nvars=2; options=gaoptimset; options=gaoptimset(options,'PopulationSize',25); options=gaoptimset(options,'PopInitRange',[-5;5]); options=gaoptimset(options,'CrossoverFraction',0.85); options=gaoptimset(options,'MigrationFraction',0.15); options=gaoptimset(options,'Generations',50); [X,FVAL]=ga(fitnessFunction,nvars,options); 程序运行返回结果为:X=[0.00809,0.00155], Fval=0.01344728697355535。50次迭代过程中最佳适 应度变化如图2所示,图3所示的是迭代过程中种群 的平均适应度的变化。由实验结果可以看出,使用 Matlab遗传算法工具箱求解函数优化问题,函数可以 有效地收敛到全局最优点,并且具有收敛速度快和结 果直观的特点。 图2最佳适应度变化 图3平均适应度变化 结 语 遗传算法具有通用性、智能性、鲁棒性、全局性和 并行性的特点,函数数值优化是遗传算法最常应用的 领域之一。本文在Matlab环境下使用遗传算法工具 箱对Rastrigin函数进行优化,实验结果表明对于函数 的寻优问题,遗传算法不仅不会陷入局部最优点,而 且具有较快的收敛速度和较高的收敛精度。 参考文献 [1]王小平,曹立明.遗传算法—理论、应用与软件实现.西 安:西安交通大学出版社, 2002 [2]雷英杰,张善文等. Matlab遗传算法工具箱及应用.西 安:西安电子科技大学出版社, 2005 [3]飞思科技产品研发中心. Matlab7基础与提高.北京:电 子工业出版社, 2005 [4]王末然. Matlab与科学计算.北京:电子工业出版社, 2004 (收稿日期:2006- 10- 20) Function Optimization based on Matlab Genetic Algorithm Toolbox ZHOUChen-chen (College ofComputer Science, Anhui University, Hefei 230039 China) Abstract: The principle and the solving procedure of the genetic algorithm are presented, and a Matlab genetic algorithmtoolboxis expatiated. Then, a typical simulation example about function optimization problem is given toverifythe toolbox' s efficiencyand practicability. Key words: Genetic Algorithm;Matlab;Function Optimization !"