基于Matlab的遗传算法程序设计及优化问题求解
 
摘要：遗传算法作为一种新的优化方法被广泛地应用于计算科学、模式识别和智能故障诊断等方面，它适用于解决复杂的非线性和多维空间寻优问题，近些年来也得到了较为广泛的应用。 本文介绍了遗传算法的起源、发展、工作原理、特点和应用场合，以及遗传算法的基本操作和求解步骤，再基于Matlab编写程序实现了“基于遗传算法和非线性规划的函数寻优算法”与“基于遗传算法的TSP问题”程序设计。实验表明，用Matlab语言进行的优化计算，具有编程语句简单，用法灵活，编程效率高等优点。经仿真验证，该算法是正确可行的。
 
关键词：遗传算法；Matlab；非线性规划；TSP问题
 Matlab-based genetic algorithm design and optimization of procedures for problem solving
 
Abstract：As a new genetic algorithm optimization method is widely used in computer science, pattern recognition and respect of intelligent fault diagnosis, it applies to solve complex and multidimensional nonlinear optimization problem, in recent years has been more widely applications. This paper describes the origin of the genetic algorithm development, basic operating working principles, features and applications, as well as genetic algorithms and solution steps, and then based on Matlab programming to achieve the "search function of genetic algorithm and nonlinear programming algorithm based on excellent" and "TSP based on Genetic algorithms" programming. Experimental results show that optimization using Matlab language, with programming statements simple, flexible usage, programming efficiency. The simulation shows that the algorithm is correct and feasible.
 
Keywords: Genetic algorithm;Matlab; nonlinear programming; Travelling Salesman Problem

目    录

 

一、 绪论 3

（一）遗传算法的起源 3

（二）遗传算法的发展 3

二、 算法概述 4

（一）遗传算法介绍 4

（二）遗传算法的工作原理 4

（三）遗传算法的特点 7

三、 算法应用1 7

（一）基于遗传算法和非线性规划的函数寻优算法 7

（二）算法流程 7

（三）算法实现 8

四、 算法应用2 14

（一）基于遗传算法的TSP算法 14

（三）算法实现 14

五、 结论 21

（一）主要发现 21

（二）启示21

六、 总结 21

七、 参考文献 22

一、绪论 

（一）遗传算法的起源

五十年代末到六十年代初，自然进化的理论被广泛接受。遗传算法是由生物学家Fraser在计算机上模拟自然界生物的遗传和选择而产生的。六十年代，L.J.Fogel在有限状态自动机的设计过程中提出了进化规划的观点。一九六六年，Fogel等出版了《基于模拟进化的人工智能》,该书更加详细的介绍了进化规划。六十年代中期，美国密歇根大学的Holland教授提出“借鉴生物的自然遗传原理来研究自然和人工系统的自适应行为技术”；一九六七年，Bagley博士在他的学生论文中初次提出了“遗传算法”一词；一九七五年，Holland教授发表了著名的“顺应自然和人工系统”，第一次明确提出了遗传算法的概念。该文章系统性的描述了遗传算法的基本原理和方法，并提出了相关模式来证实在遗传算法中子代会以几何倍数的方式增长是与其子选择、交叉以及变异的作用下具有低阶、短定义距的模式有关。遗传算法的提出是由于Holland在基于二进制表达下创建了概率搜索法，该遗传算法被称为标准遗传算法。

 

（二）遗传算法的发展

 (1)二十世纪六十年代，Holland教授和他的学生意识到自然遗传可以转化为人工遗传算法是因为受到了生物模拟技术的启发。两年后，荷兰教授提出了一种利用种群进化思想模拟适应性系统，介绍了其基本概念，适应人群，选择，变异，交叉值等

(2)一九六七年，Bagely首次提出了“遗传算法”的概念。

(3)一九七五年，Holland在其出版的《自然与人工系统中的适应性行为》一书中阐述了遗传算法的基本原理和方法，提出了遗传算法的基本定理，因而奠定了遗传算法的理论基础。

(4)二十世纪八十年代，Holland首次实现了由遗传算法开发而来的机器学习系统，开辟了“由遗传算法开发的机器学习”新时代。

 (5)一九九二年，John在其出版的《遗传编程》一书，提出了遗传编程的观念，并将遗传编程成功运用于人工生命、图像处理、数据挖掘等领域。伴随着遗传算法的不断发展，跟遗传算法有关的科研活动越来越多，遗传算法也已经成为多个重要学科与领域的研究方向。

二、算法概述

（一）遗传算法介绍

遗传算法是在根据达尔文的生物进化论中自然选择和自然遗传过程而开发的智能算法，其获得最优解的方法是根据自然进化演变而来过程。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体都带有特殊染色体。染色体作为遗传物质的主要载体，其内部的碱基排列顺序决定了个体形状和外部表现，如眼睛的颜色特征是由染色体中控制这一特征的某种基因组合决定的。所以，在一开始就必须把“表现型到基因型”的过渡工作给完成，即编码工作。但是，因为模拟基因编码的工作困难且复杂，为了更容易基因编码，我们便采取简化的方法——利用二进制编码在初代种群产生之后按照自然界生存的基本原则来逐代演化出愈来愈好的近似解，在每一代中借助自然遗传来模拟组合交叉与变异，从而产生新的解集群体，这个新的解集群体即可作为近似最优解。

遗传算法主要运用在：、组合优化、机器人智能控制、生产调度问题、自动控制、机器学习、图像处理和模式识别、遗传程序设计、人工生命、数据挖掘等领域。

 

（二）遗传算法的工作原理

Holland教授在一九七五年首次提出了由模仿生物界“适者生存、优胜劣汰”演变而来的随机搜索方法——遗传算法。其主要特点是不存在求导和函数连续性的限定；遗传算法具有潜在的隐蔽性和更强大的寻优能力；能自动获取和指导优化的搜索空间，不需要确定的规则。遗传算法的这些特征，已被人们广泛地应用在函数优化、机器人智能控制、图像处理、生产调度问题和人工生命等领域。它在现代有关智能计算中占有重要地位。

在自然界，个体之间之所以存在对环境有不同的适应与生存能力，是因为组成生物群体之间存有差异。遵从自然界“适者生存、优胜劣汰”的基本法则，通过交配将父代优秀的基因遗传给子代，通基因重组产生各方面更为强大的新的个体并由它们组成的新群体从而淘汰那些劣质的子代。但某些时候基因会发生突变，突变所产生新基因会使新个体具有更强大的生命力。

遗传算法是一种迭代算法，它在每一次迭代时都拥有一组解，这组解最初是随机生成的，在每次迭代时又有一组新的解由模拟进化和继承的遗传操作生成，每个解都有一目标函数给与评判，一次迭代成为一代。

 结论

（一） 主要发现
遗传算法的研究归纳起来分为理论与技术研究、应用研究两个方面。理论与技术研究主要从遗传操作、群体大小、参数控制、适应度评价以及并行实现技术等方面来提高遗传算法的性能。并且Matlab软件有功能强大的数学函数支持编程效率高，语句简单，功能齐备利用Matlab来编写遗传算法程序简单而且易于操作。
 
（二） 启示
任何事物之前都存在着必然的因果联系，比如遗传算法。遗传算法的原理本就来自于我们所处自然界当中的“遗传与选择”过程。现在，在人工生命、生产调度、函数优化、机器学习、组合优化、动控制、机器人智能、数据挖掘等领域已经广泛使用了遗传算法。所以，在日常的生活与学习中我们要善于利用世间普遍存在的哲学观去发现事物、认知事物并且找到解决问题的最好方法。

 参考文献

[1]周勇等. 非数值并行算法--遗传算法[M]. 北京:科学出版社,2003:20-25.
[2]周明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出版社,1995:10-20.
[3]徐宗本, 李国. 解全局优化问题的仿生类算法(I)[J]. 运筹学杂志,1995,6(12):70-72.
[4]张文修. 遗传算法的数学基础[M]. 成都：西安交通大学出版社,2001:34-44.
[5]王小平. 遗传算法-理论、应用与软件实现[M]. 成都：西安交通大学出版社,2002:58-60.
[6]张铃、张钹. 遗传算法的机理研究[J]. 软件学报,2000,15(2):5-7.
[7]李敏强. 遗传算法的基本理论与应用[M]. 北京: 科学出版社,2001:83-87.
[8]吉根林. 遗传算法研究综述[J]. 计算机应用与软件, 2004,13(5):11-13.
[9]玄光男，程润传. 遗传算法与工程设计[M]. 北京: 科学出版社,2000:67-74.
[10]马玉明. 遗传算法的理论研究综述[J]. 山东轻工业学院学报,2004:18(3):46-53.
[11]张丽萍, 柴跃廷. 遗传算法的现状及发展动向[J]. 信息与控制,2001,18(5):23-17.
[12]戴晓晖, 李敏强, 寇纪凇. 遗传算法理论研究综述[J]. 控制与决策,2000,16(2):27-30.
[13]席裕庚, 柴天佑, 恽为民. 遣传算法综述[J]. 控制理论与应用,1996,13(4):33-39.
[14]唐穗欣. 标准遗传算法的原理及算例[J]. 软件导刊,2007,17(6):22-27.
[15]俆小龙，王文国. 遗传算法的原理与应用[J]. 沿海企业与科技,2005,20(3):34-38.
[16]张文修，梁怡. 遗传算法的数学基础[M]. 成都：西南交通大学出版社,2000:104-112.
[17]潘正君，康立山. 演化计算[M]. 北京：清华大学出版社,1998:84-89.
[18]李敏强, 寇纪凇,林丹,李书全. 遗传算法的基本理论与应用[M]. 北京:科学出社,2002:77-84.
[19]孙祥，徐流美. matlab7.0 基础教程[M]. 北京: 清华大学出版社,2005:94-102.