遗传算法的改进及其应用

论文摘要

遗传算法是一种模拟自然界生物进化的概率搜索算法,由于它不受搜索空间的限制性假设的约束,尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛,并且已在众多领域得到了实际应用,取得了令人瞩目的成果,引起了广大学者和工程人员的关注。遗传算法早在六十年代由J.H.Holland等人提出,并在八十年代得以完善,发展成为标准式的遗传算法,从九十年代中期得到广泛研究与应用。遗传算法具有全局优化性和易操作性。最初应用于非数值计算方面,直到近几年才转向全局优化问题,并取得了显著的成果。遗传算法是一种新兴的技术,正处于发展期。虽然在应用领域获得了丰收,但其理论基础还较薄弱,有许多地方需要研究和发展充实。论文的主要工作分如下三部分:(1)对标准遗传算法的发展概况、基本概念、基本原理、理论基础、收敛性、特点及其应用等方面作了简明扼要的介绍,并对遗传算法的实现技术作了较详细的总结。介绍了曲线拟合问题及其求解的基本方法,旅行商问题的数学模型及其求解的传统方法和智能优化方法,单亲遗传算法基本理论,以及基于单亲遗传算法求解旅行商问题。(2)针对简单遗传算法在拟合曲线中存在的易产生早熟收敛、得到的结果可能为非全局最优收敛解以及在进化后期搜索效率降低的缺陷,引入动态自适应策略调整交叉概率和变异概率,对简单遗传算法进行了改进,提高了收敛速度,又减小了拟合曲线的均方误差。(3)针对旅行商问题的数学模型及其基于单亲遗传算法的求解方法,提出了一种改进的单亲遗传算法。该算法引入“周期”的概念,在原有算法上加入了“解开算子”,模拟自然界存在的生物周期进化,进化退化并存的现象,每进化若干代才进行一次个体的选择淘汰并重组群体,以保证群体的稳定进化。计算实例证明,改进的单亲遗传算法具有较高的求解质量和求解效率。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 课题的背景及意义
• 1.2 本文的主要工作及章节安排
• 第2章 遗传算法
• 2.1 遗传算法发展简史
• 2.2 遗传算法的基本概念
• 2.3 遗传算法的理论基础
• 2.3.1 模式定理
• 2.3.2 积木块假设
• 2.3.3 隐含并行性
• 2.4 遗传算法的基本流程
• 2.5 应用遗传算法的关键技术
• 2.5.1 遗传编码
• 2.5.2 适应度函数和尺度变换
• 2.5.3 遗传操作
• 2.5.4 算法参数
• 2.5.5 遗传算法的终止条件
• 2.6 遗传算法的收敛性
• 2.6.1 早熟收敛
• 2.6.2 标准遗传算法的收敛性
• 2.7 遗传算法的特点及应用
• 2.7.1 遗传算法的特点
• 2.7.2 遗传算法的应用
• 2.8 本章小结
• 第3章 曲线拟合及改进遗传算法拟合曲线
• 3.1 曲线拟合问题描述
• 3.2 曲线拟合基本方法简介
• 3.2.1 拉格朗日（Lagrange）插值法
• 3.2.2 分段插值法
• 3.2.3 最小二乘法
• 3.2.4 样条拟合法
• 3.2.5 小结
• 3.3 改进的遗传算法拟合曲线
• 3.3.1 改进的遗传算法原理
• 3.3.2 改进遗传算法的元素设计
• 3.3.3 改进算法框架
• 3.3.4 数值实验
• 3.3.5 结论
• 3.4 本章小结
• 第4章 改进的单亲遗传算法求解TSP问题
• 4.1 旅行商问题概述
• 4.1.1 旅行商问题的定义和数学模型
• 4.1.2 研究旅行商问题的意义
• 4.2 解TSP问题的算法综述
• 4.2.1 精确算法
• 4.2.2 近似算法与启发式算法
• 4.3 单亲遗传算法
• 4.3.1 单亲遗传算法的基本思想
• 4.3.2 单亲遗传算法的遗传算子
• 4.3.3 单亲遗传算法的性能和收敛性
• 4.4 改进的单亲遗传算法求解TSP问题
• 4.4.1 PGA算法的设计思想
• 4.4.2 改进遗传算法的元素设计
• 4.4.3 PGA算法描述
• 4.4.4 数值实验
• 4.5 本章小结
• 第5章 结论
• 5.1 本文工作总结
• 5.2 展望
• 参考文献
• 作者在攻读硕士学位期间发表的学术论文
• 致谢