2
2
2
Ξ
第 22 卷第 3 期
2005 年 8 月
Jou rnal of X in jiang U n iversity (N atu ral Science Edition)
新疆大学学报 (自然科学版)
V o l. 22, N o. 3
A ug. , 2005
M A TLAB 环境下遗传算法优化工具箱的应用
刘万林, 张新燕, 晁勤
(新疆大学 电气工程学院, 新疆 乌鲁木齐 830008)
摘 要: 用M A TLAB 语言及M A TLAB 语言编制的优化工具箱进行优化设计具有语言简单、函数丰富、用法比
较灵活、编程效率高等特点. 本文对遗传算法和基于M A TLAB 的遗传算法优化工具箱 (GAO T ) 作了简要的介
绍、分析了优化工具函数, 并结合非线性、多峰值函数问题的优化实例, 说明了遗传算法是一种具有良好的全局
寻优性能的优化方法.
关键词: M A TLAB; 遗传算法; 优化; 全局寻优
中图分类号: T P301. 6 文献标识码: A 文章编号: 1000
2839 (2005) 03
0357
04
The Appl ica tion of Genetic A lgor ithm O ptim iza tion Toolbox in M ATLAB
L IU W an
lin, ZHAN G X in
yan, CHAO Q in
(Colleg e of E lectrica l E ng ineering , X inj iang U n iversity , U rum qi, X inj iang 830008, Ch ina)
Abstract: T he op tim ization design in M A TLAB and M atlab op tim ization too lbox have sim p le language 、
abundan t function s、flex ib le m ethod and h igh p rogramm ing efficiency. T he p ap er in troduces genetic algo rithm
(GA ) and genetic algo rithm op tim ization too lbox and analyses the op tim ization too lbox function. T he function
op tim ization p rob lem of non linear and m u lti p eak has been given to dem on strate that genetic algo rithm is a
better global op tim ization m ethod.
Key words: M A TLAB; Genetic A go lrithm ; O p tim ization; Global op tim ization
M atlab 语言是一种高效率的用于科学工程计算的高级语言, 与 B asic、Fo rtran、V isual C 等语言比
较,M atlab 语言的语法规则简单、更加贴近人的思维方式, 易学易用. M atlab 语言有着丰富的由世界著
名专家、学者开发出的各种工具箱,M atlab 的优化工具箱提供了对各种优化问题的一个完整的解决方
案. 遗传算法优化工具箱就是其中之一, 遗传算法 (GA ) 是一类借鉴生物界自然选择和遗传机制的随机
优化搜索算法, 其主要特点是群体搜索策略和群体中个体之间的信息交换、搜索不依赖于梯度信息. 由
于不受函数约束条件 (如连续性、可微性、单极值) 的限制, 因而具有广泛的适应能力. 它尤其适用于处理
传统搜索方法难以解决的复杂和非线性问题, 因此, 采用M A TLAB 语言设计的遗传算法优化工具箱将
它应用于实际中, 不仅具有简单、易用、易于修改的特点, 而且为解决许多传统的优化方法难以解决的象
非线形、多峰值之类的复杂问题提供了有效的途径, 为遗传算法的研究和应用提供了很好的应用前景.
1 遗传算法
1. 1 遗传算法 (Geneticalgo rithm s: GA ) 是由美国M ich igan 大学的 JohnHo lland 教授在 20 世纪 60 年代
提出的, 它是一种自然适应优化方法, 该算法是基于自然遗传和自然优选机理形成的一种全局寻优方
法. 遗传算法是将问题的求解表示成“染色体”, 将它们置于问题的“环境”中, 根据适者生存的原则, 从中
选择出适应环境的“染色体”进行复制, 即再生 ( rep roduction, selection) , 通过交叉 (cro ssover)、变异
(m u tation) 两种基因操作产生出新一代更适合环境的“染色体”群, 这样一代代不断改进, 最后收敛到一
个最适合环境的个体上 (当然也有其他的收敛准则) , 求得问题的最佳解. 由于最好的染色体不一定出现
收稿日期: 2004
作者简介: 刘万林 (1978
09
17
) , 男, 硕士研究生. 从事电力系统综合自动化方面的研究.
853
新疆大学学报 (自然科学版)
2005 年
在最后一代, 开始时保留最好的染色体, 如果在新的种群又发现更好的染色体, 则用它代替原来的染色
体, 进化完成后, 这个染色体可以看作是最优化的结果. 遗传算法几乎渗透到从工程到社会科学的诸多
领域, 必须要编制遗传算法的程序进行计算, 作为使用者希望找一个现成的程序, 而M A TLAB 的遗传算
法工具箱正好满足要求.
1. 2 遗传算法的基本构成要素和 GA 的流程图见图 1.
输入参数: 染色体个数 N , 交叉概率 P c, 变异概率 Pm ; 通过初始化过程产生 N 个染色体; 计算所有
染色体的评价函数; 根据评价函数抽样选择染色体; 对染色体进行交叉和变异操作; 重复若干次 (下一代
的代数) 计算评价函数、选择、交叉和变异.
图 1 GA 的流程
1. 3 GA 有如下 3 个基本算子: ①再生 (rep roduction
selection). 再生算子从群体中按某一概率选择个
体, 某个体 X i 被选择的概率 P i 与其适应值成正比. 最通常的实现方法是轮盘赌 (rou lettew heel) 模型. ②
交叉 (cro ssover). 交叉算子将被选中的 2 个个体的基因链按概率 P c 进行交叉, 生成 2 个新的个体, 交叉
位置是随机的. 其中 P c 是一个系统参数, 即交叉概率. ③变异 (m u tation). 变异算子按一定概率 Pm 将新
个体的基因链的各位进行变异, 对二值基因链 (0, 1 编码) 来说即是取反. Pm 也是一个系统参数, 即变异
概率. 以上各种算子的实现方法是多种多样的, 而且许多高级算子正不断提出, 以改进 GA 的某些性能.
由于 GA 的性能具有一定的脆弱性 (b rittleness) , 因此 GA 本身的参数 (即系统参数) 的选取对 GA 的运
行效果有很大影响.
1. 4 系统参数的选取一般遵循以下原则: ①种群数目 N . 种群数目会影响 GA 的有效性. N 太小, GA 会
很差或根本找不出问题的解, 因为太小的种群数目不能提供足够的采样点; N 太大, 会增加计算量, 使收
敛时间延长. 一般种群数目在 20~ 160 之间比较合适. ②交叉概率 P c. 此参数控制着交叉操作的频率. P c
太大, 会使高适应值的结构很快破坏掉; P c 太小, 搜索会停滞不前. 一般 P c 取 0. 25~ 0. 75. ③变异概率
Pm. 它是增大种群多样性的第二因素. Pm 太小, 不会产生新的基因块; Pm 太大, 会使 GA 变成随机搜
索. 一般 Pm 取 0. 01~ 0. 20.
2 遗传算法工具箱 (GA Toolbox)
2. 1 遗传算法函数
遗传算法工具箱 GAO T 包括了许多实用的函数, 这些函数按照功能可以分为以下几类: 主界面函
数、选择函数、演化函数、其它的一些终止函数、二进制表示函数、演示程序等等.
2. 2 遗传算法函数的参数
M A TLAB 的遗传算法工具箱核心函数 GAO TV 5 其主程序 ga. m 提供了遗传算法工具箱与外部的
接口. 在M A TLAB 环境下, 执行 ga 并设定相应的参数, 就可以完成优化. 它的格式如下:
3
第 3 期
刘万林, 等: M A TLAB 环境下遗传算法优化工具箱的应用
953
(1) function [pop = in itializega (num , bound s, eevalFN , eevalO p s, op tion s) —初始种群的生成函
数; 输出参数 ]pop —生成的初始种群; 输入参数 ]num —种群中的个体数目; bound s—代表变量的上下
界的矩阵; eevalFN —适应度函数; eevalO p s—传递给适应度函数的参数; op tion s—选择编码形式 (浮点
编码或是二进制编码) [p recision F - o r- B , 如 p recisi on—变量进行二进制编码时指定的精度 F - o r-
B —为 1 时选择浮点编码, 否则为二进制编码, 由 P recision 指定精度.
(2) function [x, endPop , bPop , trace Info =
term FN , termO p s, selectFN , selectO p s, xO verFN s, xO verO p s, m u tFN s, m u tO p s).
[ 输 出 参 数 ] x、endPop、bPop、trace Info; 输 入 参 数 ] bound s、evalFN、evalO p s、startPop、op ts、
ga (bound s, evalFN , evalO p s, startPop , op ts, ……
term FN、termO p s、selectFN、selectO p s、xO verFN s、xO verO p s、m u tFN s、m u tO p s.
3 应用实例
[ 问题 1 求 f (x ) = 1
≤2.
[ (x - 0. 2) ^ 2+ 0. 01 + 1
[ (x - 0. 8) ^ 2+ 0. 04 - 4 的最大值, 其中- 1≤x
[ 分析 1 选择二进制编码, 种群中的个体数目为 10, 二进制编码长度为 20, 交叉概率为 0. 6, 变异概
率为 0. 1.
[ (x - 0. 8) ^ 2+ 0. 04 - 4;
[ (x ·- 0. 8) ^ 2+ 0. 04 - 4 ’, - 1 2 )
’fbgalw ’,
,
in itPop , 1 e - 6 1 1 ,
’m axGenT erm ’, 80,
’nonU n ifM u tation’, 2 80 3 ) ;
(1) 编写目标函数存储为 fbgalw. m 文件.
function [ so l, val = fbgalw (so l, op tion s)
x = so l (1) ;
[ (x - 0. 2) ^ 2+ 0. 01 + 1
val= 1
(2) 调用主函数 ga. m 程序如下:
clc
fp lo t (’1
ho ld on
in itPop = in itializega (10, - 1 2 ,
p lo t (in itPop (: , 1) , in itPop (: , 2) , ’b
x label (’x ’) ; ylabel (’f (x ) ’) ;
ho ld on
[ x endPop bpop trace =
[ (x - 0. 2) ^ 2+ 0. 01 + 1
’)
’fbgalw ’) ;
ga ( - 1 2 ,
’arithXover’ , 2 ,
’)
’no rm Geom Select’, 0. 1 ,
’)
p lo t (endPop (: , 1) , endPop (: , 2) , ’y
figu re (2)
p lo t (trace (: , 1) , trace (: , 3) , ’y -
ho ld on
p lo t (trace (: , 1) , trace (: , 2) , ’r-
x label (’generation’) ; y label (’F ittness’) ;
legend (’ 解的变化 ’, ’ 种群平均值的变化 ’) ;
运行结果如图 2 和图 3 所示, 图 2 中标有“
= 0. 200 38, fm ax= 98. 501 409.
’)
X
”记号的点为初始值, 标有“+ ”的点为最优值. 最优解为
[ 问题 2 求 f (x ) = x + 9
[ 分析 2 选择二进制编码, 种群中的个体数目为 10, 二进制编码长度为 20, 交叉概率为 0. 95, 变异
co s (4x ) 的最大值, 其中 0≤x ≤9
sin (5x ) + 7
概率为 0. 08.
(1) 编写目标函数存储为 fitness. m 文件.
063
新疆大学学报 (自然科学版)
2005 年
图 2 100 次迭代后的寻优结果 图 3 遗传算法的寻优性能
function [ so l, eval = fitness (so l, op tion s)
x = so l (1) ;
x ) + 7
eval= x + 9
(2) 调用主函数 ga. m 程序
运行结果如图 4 和图 5 所示, 图 4 中标有“
= 7. 857 2, fm ax= 23. 855.
co s (4
sin (5
5x ) ;
X
”记号的点为初始值, 标有“+ ”的点为最优值. 最优解为
图 4 25 次迭代后的寻优结果 图 5 遗传算法的寻优性能
由上两例从寻优结果和寻优性能图可以看出遗传算法对非线形、多峰值函数完全可以避免陷入局
部最优而找到全局最优解, 从解的变化可以看出迭代次数不须太多就能达到最优解.
4 结 语
随着遗传算法作为一种全局优化算法在各个领域的应用越来越广泛, 笔者在M A TLAB 环境下应用
遗传算法及采用M A TLAB 语言编制的遗传算法优化工具箱对传统优化算法难以实现全局最优解的非
线性、多峰值函数最值问题进行了优化, 结果表明对于非线形、多峰值函数的寻优问题, 遗传算法不仅不
会陷入局部最优点, 有较强的搜索能力、收敛速度快、精度也较高, 而且其用法也比较灵活. 完全避免了
一般优化算法的局部最优、收敛较慢等问题的不足, 并取得了令人满意的效果.
参考文献:
1 C. R. Houck, JJo inesandM. Kay. A genetical go rithm fo r function op tim ization: A M atlab im p lem en tation [M . A CM
T ran saction son M athm atical Softw are, 1996.
2 张志涌, 刘瑞桢, 杨祖英. 精通和掌握M A TLAB [M . 北京: 北京航空航天大学出版社, 1998.
3 飞思科技产品研发中心. M A TLAB6. 5 辅助优化计算与设计[M . 北京: 电子工业出版社, 2003.
责任编辑: 陈 勇