遗传算法原理研究及应用

遗传算法原理研究及应用

2007届毕业生 毕业论文

题 目: 遗传算法原理研究及应用 院系名称： XXXXXXXXXX 专业班级： XXXXXXXXXXXXXXXXXX 学生姓名： 号：指导教师： XXXXX 教师职称： XXXXX

2011年4月28号

遗传算法原理研究及应用

遗传算法的原理与应用

摘 要: 遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处理复杂的非线性问题,因此有着广阔的应用前景。

关键词: 遗传算法; 化学计量学; 优化

THEORY AND APPL ICATION OF GENETIC AL GORITHM ABSTRACT: Genetic Algorithm( GA) is a kind of recursive computational procedure based on the simulation of principle principles of evaluation of living organisms in nature1Based on brief int roduction of the principle ,the beginning and development of the algorithms ,the paper reviewed its applications in the fields of optimization ,fitting and calibration,structure analysis and spectra interpretation variable selection ,and it s usage in combination with othersThe application of GA needs no initiating knowledge of the system ,and therefore is a comprehensive optimization method with extensive application in terms of processing complex nonlinear problems。

KEY WORDS : Genetic Algorithm( GA) ; Chemometrics ; Optimization

遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法，它于1962年被提出，直到1989年才最终形成基本框架。 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 由美国J. H. Ho llad教授提出, 其主要特点是群体搜索策略和群体中个体之间的信息交换。该算法尤其适用于处理传统搜索方法难以解决的复杂和非线性问题, 可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。

顾名思义,遗传算法(Genetic Algorithm ,GA)是模拟自然界生物进化机制的一种算法 ,即遵循适者生存、优胜劣汰的法则 ,也就是寻优过程中有用的保留 ,无用的则去除。在科学和生产实践中表现为 ,在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法 ,即找出一个最优解。这种算法是 1960 年由Holland提出来的 ,其最初的目的是研究自然系统的自适应行为 ,并设计具有自适应功能的软件系统。它的特点是对参数进行编码运算 ,不需要有关体系的任何

遗传算法原理研究及应用

先验知识 ,沿多种路线进行平行搜索 ,不会落入局部较优的陷阱 ,能在许多局部较优中找到全局最优点 ,是一种全局最优化方法。近年来 ,遗传算法已经在国际上许多领域得到了应用。1985 年召开了第 1 届有关遗传算法的国际会议 ,第 1 部关于这方面的专著在 1989 年问世。遗传算法是一种有广泛应用前景的算法 但是它的研究和应用在国内尚处于起步阶段 。遗传算法是一种基于生物的自然选择和群体遗传机理的搜索算法。它模拟了自然选择和自然遗传过程中发生的繁殖、交配和突变现象。它将每个可能的解看做是群体（所有可能解）中的一个个体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，给出一个适应度值。开始时总是随机地产生一些个体（即候选解），根据这些个体的适应度利用遗传算子对这些个体进行操作，得到一群新个体，这群新个体由于继承了上一代的一些优良性状，因而明显优于上一代，这样逐步朝着更优解的方向进化。遗传算法在每一代同时搜索参数空间的不同区域，然后把注意力集中到解空间中期望值最高的部分，从而使找到全局最优解的可能性大大增加。

作为进化算法的一个重要组成部分，遗传算法不仅包含了进化算法的基本形式和全部优点，同时还具备若干独特的性能：

(1)在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有函数导数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常复杂的优化函数求解问题。

(2)若遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约O（n3）个模式，具有很高的并行性，因而具有明显的搜索效率。

(3)在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局最优解求解能力。

(4)对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够较好地解决一类复杂问题，因而具有较好的普适性和易扩充性。

(5)遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。 1算法原理

1.1基本遗传算法

在自然界 ,由于组成生物群体中各个体之间的差异 ,对所处环境有不同的适应和生存能力 ,遵照自然界生物进化的基本原则 ,适者生存、优胜劣汰 ,将要淘汰那些最差个体 ,通过交配将父本优秀的染色体和基因遗传给子代 ,通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下 ,基因会发生突变 ,产生新基因和生命力更强的新个体;但突变是非遗传的 ,随着个体不断更新 ,群体不断朝着最优方向进化 ,遗传算法是真实模拟自然界生物进化机制进行寻优的。在此算法中 ,被研究的体系的响应曲面看作为一个群体 ,相应曲面上的每一个点作为群体中的一个个体 ,个体用多维向量或矩阵来描述 ,组成矩阵和向量的参数相应于生物种组成染色体的基因 ,染色体用固定长度的二进制串表述 ,通过交换、突变等遗传操作 ,在参数的一定范围内进行随机搜索 ,不断改善数据结构 ,构造出不同的向量 ,相当于得到了被研究的不同的解 ,目标函数值较优的点被保留 ,目标函数值较差的点被淘汰。由于遗传操作可以越过位垒 ,能跳出局部较优点 ,到达全局最优点。

遗传算法原理研究及应用

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

(1)初始化 ,即随机生成一个符号串群体;

(2)基于适度函数对符号串进行评价;

(3)应用一组遗传操作生成一个新的符号串群体;

(4)重复步骤(2)和(3)直至结果收敛。

基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发了许多种不同的遗传算子来模仿不同环境下的生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法（simple genetic alg …… 此处隐藏：8409字，全部文档内容请下载后查看。喜欢就下载吧 ……