《基于matlab遗传算法优化工具箱的优化计算》由会员分享，可在线阅读，更多相关《基于matlab遗传算法优化工具箱的优化计算（4页珍藏版）》请在金锄头文库上搜索。
1、基于 MATLAB 遗传算法优化工具箱的优化计算高 尚?摘 要 采用Matlab语言 编制的遗传 算法工 具箱(GAOT )可实现二进制编码和真值编码的模拟进化计算。此工具箱在遗传操作方面非常灵活。介绍了用遗传算法工具箱解决了连续优化问题和旅行商问题, 并给出了两个实例。关键词 遗传算法 优化 旅行商问题一、 遗传算法遗传算法( Genetic algorithms: GA ) 是由美国 Michigan大学的John Holland教授在 60 年代提出的, 它是一种自然适应优化方法, 该算法是基于自然遗传和自然优选机理的寻优方法。 所谓自然遗传和自然优选来自于达尔文的进化论学说,该学说认为
2、在生物进化过程中, 任一动植物经过若干代的遗传和变异, 使之能够适应新的环境, 是优胜劣汰的结果, 这种自然遗传思想也适用于求解优化问题。GA 采用选择(selec-tion) 、 交叉(crossover)和变异(mutation) 运算来实现“ 物竞天择, 适者生存” 这一自然法则的模拟。 遗传算法的一般框架2,3, 4 :输入参数: 染色体个数 N, 交叉概率 Pc, 变异概率 Pm;通过初始化过程产生 N 个染色体;计算所有染色体的评价函数;根据评价函数抽样选择染色体;对染色体进行交叉和变异操作;重复若干次( 下一代的代数) 计算评价函数、 选择、 交叉和变异。由于最好的染色体不一定出
3、现在最后一代, 开始时保留最好的染色体, 如果在新的种群又发现更好的染色体, 则用它代替原来的染色体, 进化完成后, 这个染色体可以看作最优化的结果。遗传算法几乎渗透到从工程到社会科学的诸多领域, 必须要编制遗传算法的程序进行计算, 作为使用者希望找一个现成的程序, 而M AT LAB的遗传算法工具箱正好满足要求。我们主要对遗传算法工具箱的用法和技巧作一点探讨。二、 遗传算法工具箱MATLAB 语言简单, 但功能强大, 程序移植性比较好。MATLAB的遗传算法工具箱的下载地址:http: / /www.ie.ncsu.edu/mirage/GAT oolBox/gaot/GAOT.zip其主程
4、序是 ga. m, 其用法如下:functionx, endPop, bPop, traceInfo= ga(bounds, evalFN, e-valOps,startPop,opts,termFN,termOps,selectFN,selec-tOps, xOverFNs, xOverOps, mutFNs, mutOps)输出部分:x运行中最好的结果endPop最后一代染色体(可选择的)bPop最好染色体的轨迹(可选择的)traceInfo每一代染色体中最好的个体和平均结果矩 阵(可选择的)输入参数:bounds变量上限和下限组成的矩阵evalFN评价函数的文件名, 通常是.m文件eva
5、lOps运 行 评 价 函 数 的 输 入 选 项, 默 认 值 为 NULL( 可选择的)startPop调用 initialize. m 文件得到的初始染色体( 可 选择的)opts一个向量epsilon prob-ops display , 这里 epsilon 表示两代之间的差距; prob-ops 取 0 表示采用二进制编码, 取 1 表示采用实数 本身; display 取 is 1 表示运行中显示、 当前 染色体和最好结果, 取 0 表示运行中不显 示。默认值为 le- 6 1 0( 可选择的)termFN终 止 函 数 的 名 称, 默 认 值 为 maxGen- T erm
6、( 可选择的)termOps终止函数的输入选项, 默认值为 100 (可选 择的)selectFN选择函数的.m的文件名, 默认值为 norm- GeomSelect (可选择的)selectOpts向选择函数传递的参数, 串默认值为0. 08 (可选择的)xOverFNS一个包括空格的字符串的 Xover. m 文件, 实 数编码默认值为 arithXover heuristicXover simplxXover , 二 进 制 编 码 默 认 值 为 simpleXover (可选择的)52Microcomputer Applications Vol. 18,No. 8, 2002 技术交
7、流 微型电脑应用 2002年第 18 卷第 8 期?高 尚 华东船舶工业学院电子与信息系 讲师 硕士 镇江 212003xOverOpsXover.m的输入参数矩阵, 实数编码默认值 为 2 0; 2 3; 2 0, 二进制编码默认值为0. 6 ( 可选择的)mutFNs一个包括空格的字符串的 mutation. m 文 件, 实数编码默认值为 boundaryMutation multiNonUnifMutation nonUnifMutation u- nifMutation , 二 进 制 编 码 默 认 值 为 binaryM utation (可选择的)mutOpsXover. m
8、的输入矩阵, 类似与变异, 实数编 码默认值为 4 0; 6 100 3; 4 100 3; 4 0 0, 二 进制编码默认值为 0. 05( 可选择的)三、 解决连续变量优化问题以一个简单地连续性优化例子来说明, 例如求 maxf =x+ 10 sin(5x) + 7 cos(4x)采用GAOT的步骤如下:( 1) 首先编制目标函数文件, 如gaDemolEval.mfunction sol, val = gaDemolEval(sol, options)x= sol(1);val=x+10*sin(5*x)+ 7*cos(4*x) ; ( 2) 调用主程序ga.m, 程序如下:clear
9、allclf;figure(gcf) ;hold onfplot( x+ 10* sin(5* x)+ 7* cos(4* x) , 0 9)initPop= initializega(10, 0 9, gademolevall );plot(initPop(: , 1),initPop(: , 2) , g+ ) x endPop bestPop trace =ga( 0 9, gademolevall , ,initPop, le- 6 1 1 , maxGenTerm , 25, normGeomSelect , 0. 08, arithXover , 2, nonUnifM u-tat
10、ion , 2 25 3) ;xplot (endPop( : , 1) , endPop(: , 2), ro )figure( 2)plot(trace( : , 1),trace(: , 2) );hold onplot(trace( : , 1), trace(: , 3) );运行结果如图 1 和图 2 所示, 图 1 中标有“ + ” 记号的点为初始值, 标有“ 0” 的点为最优值。最优解为x*=7. 8564,fmax =24. 8553。四、 解决 TSP 问题旅行商问题(Traveling Salesman Problem:TSP)是一个图 1 目标函数形状及最优结果图 2
11、每一代中的最好解与平均值典型的组合优化问题, 设有 n 个城市和各城市距离 dij(i, j =1, 2, , n) , dij表示城市i 到城市 j 的距离, 问题是找遍访每个城市恰好一次的一条回路, 且其路径长度为最短。 目前解决此问题的方法较多, 遗传算法是其中一种方法, 下面用遗传算法工具箱编制的程序如下:clear allglobal distMatrixt= 1304 2312; 3639 1315; 4177 2244; 3712 1399; 34881535; 3326 1556; 3238 1229; 4196 1044; 4312 790; 4386 570; 3007 1
12、970;2562 1756; 2788 1491;2381 1676;1332 695;3715 1678;39182179; 4061 2370; 3780 2212; 3676 2578; 4029 2838; 4263 2931; 34291908; 3507 2376; 3394 2643; 3439 3201; 2935 3240; 3140 3550; 25452357; 2778 2826; 2370 2975 ;sz= size(t, 1);distMatrix= dists(t, t);xFns = cyclicXoveruniformXoverpartmapXoverord
13、er-basedXoverxFns= xFns, singleptXover linerorderXover ;xOpts= 2; 2; 2; 2; 2; 2 ; % 2; 2; 2; 2; 2; 2; 2 ;53Microcomputer Applications Vol. 18,No. 8, 2002 技术交流 微型电脑应用 2002年第 18 卷第 8 期mFns= inversionMutation adjswapMutation shiftMutationswapMutation threewapMutation ;mOpts= 2; 2; 2; 2; 2 ;termFns= max
14、GenTerm ;termOps= 100;selectFn= normGeomSelect ;selectOps= 0. 08;evalFn= tspEval ;evalOps= ;bounds= sz ;gaOpts= le- 6 1 1 ;startPop=initialixeoga( 80,bounds, tspEval , le- 6 1) ; x endPop bestPop trace = ga ( bounds, evalFn, evalOps,startPop, gaOpts, termFns,termOps,selectFn,selectOps,xFns,xOpts,mFn
15、s,mOpts) ;bestPoptraceplot(trace( : , 1),trace(: , 2) );hold onplot(trace( : , 1), trace(: , 3) );figure( 2)clfA= ones(sz, sz);A= xor(triu(A) , tril(A) );xg yg= gplot(A, t);clfh= gca;hold onap=x;plot(t(x(1:sz), 1) ,t(x(1: (sz) , 2, ) , r- )plot(t(x( 1) , x(sz) , 1), t( x(1), x(sz) , 2, ) r- )plot(xg, yg, b. , MarkerSize , 24);上面的程序是解决中国 31个直辖市和省会城市的CTSP问题,t矩阵记录各城市的相对坐标 1 。 运行的结果如图 4 和图 5 所示。图 3 是中国 31 个城市的 CT SP 目前最好的解, 它通过复杂的改进的模拟退火算法得来的 1 , 本程序的结果与接近, 但程序编程简单。五、 结束语通过两个实例说明了遗传算法工具箱的强大的功能, 是学习和利用遗传算法的好工具。 其用法比较灵活, 对其有关模块作适当修改, 可解决许多实际问题。图 3 中国 31 城市的CTSP目前最好的解图 4 中国 31城市的CT SP本算法的解图 5
