巢湖学院计算机系2009届毕业设计（论文）
第二章 遗传算法概述
2.1、遗传算法的发展简介
遗传算法是基于Darwin的进化论和Mendel的遗传学说，在计算机上模拟生命进化机制而发展起来的一门新学科[4]
Darwin进化论最重要的是适者生存原理，认为每一物种在发展中越来越适应环境。目中的每个个体的基本特征由后代所继承，但后一代又会产生一些异于附带的新变化。在环境变化时，只有那些适应环境的个体特征方能保留下来。Mendel 遗传学说最重要的是基因遗传原理，认为遗传以密码方式存在细胞中，并以基因的形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境的某种适应性。基因突变和基因杂交可产生适应环境的后代，经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
把计算机科学与进化论结合起来的尝试开始于20世纪50年代末。但当时缺乏一种通用的编码方案，使得人们只能依赖变异而不是依赖交配来产生新的基因结构，故而收效甚微。到了60年代中期，美国Michigan大学的John Holland在Fraser和Bremermann等人的工作基础上提出了位串编码技术。这种编码既适合于变异又适合于交配（杂交，交叉）操作，并强调交配最为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行文的研究之中，并于1975年出版其开创性的著作Adaptation in Natural and Artificial Systems.后来Holland与他的学生们将该算法加以推广并应用到优化及机器学习等问题之中，并正式定名为遗传算法。GA的通用编码技术及其简单有效的遗传操作作为其广泛的应用和成功奠定了基础。
美国 De.Jong 博士首先将遗传算法应用于函数优化，为这一技术的应用奠定了基础。1980年，Smith教授首次将遗传算法应用于机器学习领域，并研制出一种称作分类器(Classifier)的系统。1989年，Goldberg撰写了《遗传算法在搜索优化和机器学习中的应用》一书，对GA的原理及应用作了比较详细、全面地论述。该书至今仍是遗传算法研究中广泛适用的经典之作。此后，许多学者对原来的遗传算法(或称简单遗传算法)进行了大量改进和发展，提出了许多成功的遗传算法模型，从而使遗传算法应用于更广泛的领域。进入90年代后，遗传算法作为一种实用、高效、鲁棒性(robustness)强的优化技术，发展极为迅速，在各种不同领域(如机器学习、模式识别、神经网络、控制系统优化及社会科学等)中得到广泛应用，引起了许多学者的关注，在最近兴起的人工生命、遗传编程、进化策略、进化计一算等领域中，研究人员将遗传算法于计算机科学相结合，试图模拟自然界的自适应、自组织和再生能力，设计出具有“生命”的人工系统。
3
巢湖学院计算机系2009届毕业设计（论文）
2.2、遗传算法的特点
近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用，取得了一些令人信服的结果，所以引起了很多人的关注，而且在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括:作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。由于遗传算法与传统方法截然不同的思想，使得遗传算法有着自己独有的特点[1]: (1) 智能性
遗传算法的智能性包括自组织，自适应和自学习性等。遗传算法的这种自组织，自适应特征同时也赋予了它根据环境的变化自动发现环境的特征和规律的能力。 (2) 本质并行性
GA的本质并行性表现在两个方面。一方面，GA是内在并行的，它本身非常适合于
大规模并行计算。另外一方面，GA内涵并行性。GA采用种群方式组织搜索，因而它可以同时搜素空间内的多个领域，并相互交流信息。这种搜索方式使得它虽然每次只执行与种群规模N成比例的计算，而实质上进行了大约O(N2)次有效搜索，能以较少的计算获得较大的收益。 (3) 过程性
遗传算法通过自然选择和遗传操作等自组织行为来增强群体的适应性。算法模拟的
是一个过程，算法实施的也是一个过程。在这个过程中，算法本身无法判定个体在解空间的位置，因此需要人为干预才能终止。 (4) 多解性
遗传算法的另一个基本特征是采用群体的方式组织搜索。它从多个点出发，通过这些点内部结构的调整和重组来形成新的点。Inertia每次都将提供多个近似解，对多目标搜索或有需要多个近似解作为参照的情况下是非常有用的。 (5) 不确定性
遗传算法的不确定性伴随其随机性而来的。GA的主要步骤都含有随机因素，从而算法的进化过程中，事件的发生与否带有很大的不确定性。 (6) 非定向性
自然选择和生殖过程这种非定向机制是遗传算法的关键。它没有确定的迭代方程，
也不依靠梯度下降法似的爬山策略，而是调整群体的内部结构的方法来增强对环境的适应度，以使得问题得到解决。 (7)内在学习性
学习是进化过程自身所具有的不可与其分割的行为方式。与自然进化过程类似，生物体为了生存就必须进行学习，通过不断地实践来积累知识和经验，以增强自身的适
4
巢湖学院计算机系2009届毕业设计（论文）
应性，遗传算法的个体学习方式是通过改变个体的基因结构来提高自己的适应度。 (8) 统计性
遗传算法的种群方式决定了它是一个统计过程。在每一进化代，都要进行统计，以确定个体的优劣并推动进化的进行。 (9) 稳健性
由于遗传算法利用个体的适应值推动种群的进化，而不管求解问题本身的结构特征，因而遗传算法在求解不同问题时，只需要设计相应的适应性评价函数，而无需修改算法的其他部分。 (10) 整体优化
传统的优化方法一般采用的梯度下降的爬山策略，从而使得对于多峰函数的情况往往容易陷入局部最优。遗传算法能同时在解空间的多个区域内进行搜索，并且能以较大的概率跳出局部最优，以找出整体最优解。 2.3、遗传算法的研究内容：
遗传算法的研究工作[5]主要集中在以下几个方面: 2.3.1、性能分析
遗传算法的性能分析一直是遗传算法研究领域中最重要的主题之一。在遗传算法中，群体规模、杂交和变异算子的概率等控制参数的选择是非常困难的。遗传算法还存在一个过早收敛问题，也就是说遗传算法的最后结果并不总是达到最优解，怎样阻止过早收敛也是人们感兴趣的问题之一。 2.3.2、并行遗传算法
遗传算法在操作上具有高度的并行性，探索在并行计算机上高效执行遗传算法的策略是研究人员感兴趣的领域之一。对于并行遗传算法的研究表明，只要通过保持多个种群和恰当地保持种群间的相互作用来模拟并行执行过程，即使不使用并行计算机，我们也可以提高算法的执行效率。 2.3.3、分类系统
分类系统属于基于遗传算法的机器学习中的一类，它包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。分类系统正在被人们越来越多地应用在科学、工程和经济领域。目前分类系统是遗传算法研究中的一个非常活跃的领域。
2.4、遗传算法的发展
GA在应用方面[5]取得的丰硕成果，使人们对它的发展前景充满信心。最近几 年，有关遗传算法的研究大都集中于GA的改进和应用方面。
(1) 控制参数的选择，原始GA中种群大小、交叉概率、变异概率等控制参数是人
5
巢湖学院计算机系2009届毕业设计（论文）
为事先给出，或者通过实验来调整，而一些改进的GA把这些参数也看作是优化的目标来考虑；
(2) 针对特殊问题来设计交叉和变异这两类最重要的算子，使之适应该问题而获得较好的效果；
(3) 将数理统计中假设检验等方法应用于GA，这为GA设计引入新的思想； (4) 并行GA和分布式GA的研究；
(5) 其他类型生物机制的模仿，如多种群进化、免疫、病毒、寄生等，以丰富GA的内容；
(6) 模糊逻辑、神经网络、模拟退火都是近几年来新兴的技术，而把这些技术和传统的GA融合在一起也必然是未来发展的趋势.相对于GA的改进和应用，而其相关的基础理论研究远落后于算法的发展。虽然近年来有关GA的渐进行为分析受到愈来愈广泛的注意，但到目前为止，还没有一套完整的理论可以准确、全面地阐述GA的收敛性，也没有找到一个恰当的度量与论证方法精确地刻画GA在不同实现下的收敛速度，从而对GA的各种改进做出统一、公正的评判。这种一般数学理论基础的缺乏限制着GA的进一步推广、改进和应用。 2.5、遗传算法的应用
(1) 数值优化
数值优化是GA的经典应用领域，也是GA进行性能评价的常用案例。例如旅行商问题(TSP)是经典的组合优化问题之一，已成为一种衡量算法优劣的标准。它是采用非标准编码GA求解最成功的一例，用推销员顺序经历的城市序号表示基因编码。由于使用标准交叉产生后代可能成为又重复或者丢失基因而成为非可行解，从而提出了非标准的交叉和变异方法。交叉主要采用重排方法——部分匹配重排序(PMC)，顺序交叉（OX），循环交叉(CX)等，变异主要采用位反转，对换和插入等方法。
(2) 自动控制
在自动控制领域中许多与优化相关的问题需要求解，GA的应用日益增加并显示了良好的效果，如基于GA的模糊控制器优化设计，基于GA的参数辨识，利用GA进行神经网络的结构优化设计和权值学习，基于ＧＡ的控制参数在线优化，ＧＡ滑模控制系统设计中的应用等。
(3) 机器学习
基于GA的机器学习，特别是分类器系统，在许多领域中得到了应用。例如，GA被应用于模糊控制规则的学习，基于GA的机器学习可用于调整神经网络的连接权和优化设计神经网络结构，分类器系统在多机器人路径规划中的应用等。
6
巢湖学院计算机系2009届毕业设计（论文）
(4) 经济学
应用遗传算法对经济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。
(5) 人工生命
人工生命是用计算机等人工媒体模拟或构造出具有自然生物系统特有行为的人工系统。自组织和自学习是人工生命的两大主要特征。基于ＧＡ的进化模型是研究人工生命现象的重要理论依据。
(6) 图像处理和模式识别
如何使误差最小是使计算机视觉达到实用化的重要要求，GA在图像处理中的优化计算方面是完全胜任的，目前已在图像恢复，图像边缘特征提取，几何形状识别，模糊模式识别等方面得到了应用
(7) 数据搜索与挖掘
用GA可完成Internet上的信息搜索，找出相关的链接，挖掘相关的链接和信息。
7