遗传算法及其仿真

第１６卷第４期　湖南工程学院学报　Ｖｏ１．１６．Ｎｏ．４　２００６年ｌ２月　Ｊｏｕｒｎａｌ　ｏｆ　Ｈｕｎａｎ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｄｅｃ．２００６　遗传算法及其仿真　阎　纲　（湖南财经高等专科学校，湖南长沙４１０２０５）　摘要：介绍了遗传算法的基本概念，并提出了一种基于ＭＡＴＬＡＢ遗传算法与直接搜索工具箱的遗传　算法仿真方法．仿真实验证明，该方法是简单、实用、高效的，　关键词：遗传算法；遗传算法与直接搜索工具箱　中图分类号：ＴＰ３０１．６　文献标识码：Ａ　文章编号：１６７１—１１９Ｘ（２００６）０４—００５６一ｏ３　搭配成对，对每一个个体，以某个概率（称为交叉概　１遗传算法　率）交换它们之间的部分染色体．交叉体现了信息　交换的思想．　遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ，简称ＧＡ）起源于　（３）变异．变异操作首先在群体中随机选择一　对生物系统所进行的计算机模拟研究．美国Ｍｉｃｈｉ—　个个体，对于选中的个体以一定的概率随机改变串　ｇａｎ大学的Ｈｏｌｌａｎｄ教授及其学生受到生物模拟技　结构数据中某个串的值，即对群体中的每一个个体，　术的启发，创造出了一种基于生物遗传和进化机制　以某一概率（称为变异概率）改变某一个或某一些　的适合于复杂系统优化的自适应概率优化技术——　基因座上的基因值为其他的等位基因．同生物界一　遗传算法．　样，遗传算法中变异发生的概率很低．变异为新个体　它与传统的优化算法不同，大多数古典的优化　的产生提供了机会．　算法是基于一个单一的度量函数（评估函数）的梯　遗传算法提供了一种求解复杂系统优化问题的　度或较高次统计，以产生一个确定性的试验解序列；　通用框架，它不依赖于问题具体的领域，对问题的种　遗传算法不依赖于梯度信息，而是通过模拟自然进　类有很强的鲁棒性，所以广泛应用于许多学科，近十　化过程来搜索最优解，它利用某种编码技术，作用于　年来，遗传算法得到了迅速发展．目前，遗传算法在　称为染色体的数字串，模拟由这些串组成的群体的　生物技术和生物学、化学和化学工程、计算机辅助设　进化过程．遗传算法通过有组织的、随机的信息交换　计、物理学和数据分析、动态处理、建模与仿真、医学　来重新组合那些适应性好的串，生成新的串的群体．　与医学工程、微电子学、模式识别、人工智能、生产调　遗传算法有三个基本操作：选择、交叉和变异．　度、机器人学、采矿工程、电信学、售货服务系统等领　（１）选择．选择的目的是为了从当前群体中选　域都得到应用，成为求解全局优化问题的有力工具　出优良的个体，使它们有机会作为父代为下一代繁　之一．　殖子孙．根据各个个体的适应度值，按照一定的规则　或方法从上一代群体中选择出一些优良的个体遗传　２遗传算法与直接搜索工具箱　’　到下一代群体中．遗传算法通过选择运算体现这一　思想，进行选择的原则是适应性强的个体为下一代　ＭＡＴＬＡＢ是Ｍａｔｈｗｏｒｋｓ公司推出的一套高性能　贡献一个或多个后代的概率大．这样就体现了达尔　的数值计算和可视化软件．它集数值分析、矩阵运　文的适者生存原则．　算、信号处理和图形显示于一体，构成一个方便的、　（２）交叉．交叉操作是遗传算法中最主要的遗　界面友好的用户环境．ＭＡＴＬＡＢ强大的扩展功能和　传操作．通过交叉操作可以得到新一代个体，新个体　影响力吸引各个领域的专家相继推出了许多基于　组合了父辈个体的特性，将群体内的各个个体随机　ＭＡＴＬＡＢ的专用工具箱．ＭＡＴＬＡＢ强大的科学运算、　收稿日期：２００６—０６—１３　作者简介：阉纲（１９７７一）。男，博士研究生，研究方向：最优控制　维普资讯 http://www.cqvip.com

第４期　阎纲：遗传算法及其仿真　５７　灵活的程序设计流程、高质量的图形可视化与界面　（４）遗传算法与直接搜索工具箱函数可与　设计、便捷的与其他程序和语言的接口功能，使之成　ＭＡＴＬＡＢ的优化工具箱或其他的ＭＡＴＬＡＢ程序结　为当今世界最有活力和最具影响力的可视化软件之　合使用．　—一●　（５）支持自动的Ｍ代码生成．　最新发布的ＭＡＴＬＡＢ７．０　Ｒｅｌｅａｓｅ　１４包含一个　专门设计的遗传算法与直接搜索工具箱（Ｇｅｎｅｔｉｃ　３应用举例　Ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ｄｉｒｅｃｔ　Ｓｅａｒｃｈ　Ｔｏｏｌｂｏｘ）．　使用遗传算法与直接搜索工具箱，可以扩展　遗传算法与直接搜索工具箱包含遗传算法工具　ＭＡＴＬＡＢ及其优化工具箱在处理优化问题方面的能　和直接搜索工具．下面，将通过一个具体的例子，介　力，可以处理传统的优化技术难以解决的问题，包括　绍其中的遗传算法工具及其使用方法．假定我们想　那些难以定义或不便于进行数学建模的问题，可以　要计算下面函数的最小值：　解决目标函数较复杂的问题，比如目标函数不连续　１，　２）＝　一２ｘ１　２＋６　１＋　２　一６ｘ２　或具有高度非线性、随机性以及目标函数不可微的　首先，必须编写一个Ｍ文件，来确定想要优化　情况．　的函数．在ＭＡＴＬＡＢ的Ｆｉｌｅ菜单中选择Ｎｅｗ／Ｍ—　遗传算法与直接搜索工具箱中的优化函数总是　Ｆｉｌｅ，打开一个新的Ｍ文件．在该Ｍ文件中，输入如　使目标函数或适应度函数最小化，也就是说，它们求　下两行代码：　解如下形式的问题：　ｆｕｎｃｔｉｏｎ　Ｚ＝ｍｙｆｕｎ（ｘ）　ｍｉｎｆ（ｘ）　Ｚ＝Ｘ（１）　一２　Ｘ（１）　Ｘ（２）＋６　Ｘ（１）＋Ｘ（２）　２　如果想要求出函数，（　）的最大值，可以转而求　—６’Ｘ（２）；　取函数ｇ（Ｘ）＝－ｆ（ｘ）的最小值，因为函数ｇ（　）最　文件确定这个函数必须接受一个长度为２的　小值与函数　）最大值出现的地方相同．　行向量　，分别与变量　和　：相对应；并且返回一　遗传算法与直接搜索工具箱的功能特点如下：　个标量＝，其值等于该函数的值．将该　文件保存为　（１）图形用户界面和命令行函数可用来快速地　ｍｙ———ｆｕｎ．ｍ．　描述问题、设置算法选项以及监控进程．　然后，打开遗传算法工具．在ＭＡＴＬＡＢ命令行　（２）具有多个选项的遗传算法工具可用于问题　输入以下命令即可：　创建、适应度计算、选择、交叉和变异．　ｇａｔｏｏｌ　（３）直接搜索工具实现了一种模式搜索方法，　遗传算法工具包括许多文本框、复选框和按钮　其选项可用于定义网格尺寸、表决方法和搜索方法．　选项，表１中对它们的功能做了一些简要的说明．　表１　遗传算法工具选项的功能说明　“Ｆｉｔｎｅｓｓ　ｆｕｎｃｔｉｏｎ（适应度函数）”文本框要求输　ｆｕｎ．１１１文件中定义的函数作为适应度函数．“Ｎｕｍｂｅｒ　入适应度函数，在此输入：＠ｍｙ—ｆｕｎ，表示把ｍｙ—　ｏｆ　ｖａｒｉａｂｌｅｓ（变量数目）”文本框要求输入适应度函　维普资讯 http://www.cqvip.com

５８　湖南工程学院学报　２００６正　数的变量数目，在此输入：２．在“Ｏｐｔｉｏｎｓ”窗格中可　以改变遗传算法的参数选项．为了查看窗格中列出　的各类参数选项，可单击与之相连的符号“＋”．　在“Ｐｌｏｔｓ（绘图）”窗格中可以绘制遗传算法运　行时有关信息的各种图形．为了绘制每一代适应度　函数的最佳值和平均值，选中复选框“Ｂｅｓｔ　ｆｉｔｎｅｓｓ　（最佳适应度）”．单击“Ｓｔａｒｔ”按钮，运行遗传算法，　将在“Ｓｔａｔｕｓ　ａｎｄ　ｒｅｓｕｌｔｓ（状态和结果）”窗格中显示　出相应的运行结果，并绘制相关图形．　当算法完成时，“Ｓｔａｔｕｓ　ａｎｄ　ｒｅｓｕｌｔｓ”窗格如图１　所示．由图可知，算法终止时适应度函数的最终值是　一８．９９９９９９８９８６７８５６２．算法终止的原因是超过最大　代数而导致优化终止．最终点是［一１．０５３５７　１．　９４６７４］．　图２各代适应度函数的最佳值和平均值　因为　ｌ，　２）＝（　ｌ一　２＋３）　一９，可知ｆ（　ｌ，　了最优解，而且它的精度相当高．　）在　一　：＋３＝０时，取得实际最小值一９．可见，　遗传算法的计算结果非常接近于　，，　：）的实际最　４结束语　小值　实验证明，基于遗传算法与直接搜索工具箱的　遗传算法仿真方法，不仅操作简单，功能强大，而且　能求得令人满意的结果．　遗传算法的许多参数，如种群参数、选择参数、　变异参数、交叉参数等，对运算结果有着重要的作　用．为了得到遗传算法的最好结果，一般需要以不同　的参数试验，选择针对问题的最佳参数．如何选择遗　传算法的参数，以便在实际应用中获得最好的效果，　图１遗传算法的运行结果　是我们今后努力的方向．　ｔｉｏｎｓ（，　代数）”选项的缺省值。：苎　套　此选项规定了算法计　誓　：　蓥　：：　参考文献　，。　。　算的最大代数．各代适应度函数的最佳值和平均值　［１］蔡自兴．智能控制［Ｍ］．北京：电子工业出版社，２００４．　如图２所示．　［２］玄光男，程润伟・遗传算法与工程优化［Ｍ］・北京：清　图中，横坐标是代数，纵坐标是适应度值．在每　华　（学出版社，２００４・　，，　：点表示平均适应度值　！　煮　望　需萎　．图的顶部还显示出当前代的　一　～　一　～～一一　及其应用ｍ　最佳值和平均值．由图可知，遗传算法很快就搜索到　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｉｔｓ　Ｓｉｍｕｌａｔｉｏｎ　ＹＡＮ　Ｇａｎｇ　（Ｈｕｎａｎ　Ｆｉｎａｎｃｉａｌ　ａｎｄ　Ｅｃｏｎｏｍｉｃ　Ｃｏｌｌｅｇｅ，Ｃｈａｎｇｓｈａ　４１０２０５，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｅｓｓｅｎｔｉａｌ　ｃｏｎｃｅｐｔ　ｏｆ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ　ｉｓ　ｉｎｔｒｏｄｕｃｅｄ　ａｎｄ　ａ　ｓｉｍｕｌａｔｉｏｎ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ＭＡＴＬＡＢ　ｅＧｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ｄｉｒｅｃｔ　Ｓｅａｒｃｈ　Ｔｏｏｌｂｏｘ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｓｉｍｕｌａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔ　ｐｒｏｖｅｓ　ｔｈａｔ　ｈｔｅ　ｍｅｔｈｏｄ　ｉｓ　ｓｉｍｐｌｅ，　ｐｒａｃｔｉｃａｌ　ａｎｄ　ｅｆｉｆｃｉｅｎｔ．　Ｋｅｙ　ｗｏｒｄｓ：ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｈｔｍｓ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｄｉｅｒｃｔ　ｓｅａｒｃｈ　ｔｏｏｌｂｏｘ