求解动态优化问题的遗传算法的研究与实现

论文摘要

动态优化问题存在于当前各行各业中。一般动态优化问题的最优解会因为目标函数、环境参数或者约束条件的变化而随时发生变化,使生产调度等遭遇到相应的问题与损失。本文基于已经比较成熟的遗传算法提出了新的算法。目的就是要让该算法能随着上述条件的变化快速有效地找到待求问题的最优解,并且在实际应用中减少上述变化所带来的损失。本文的主要工作包括以下几个方面:1.本文对动态环境中的各种进化计算方法进行了详细地介绍。阐述了动态优化问题的研究要素和目前进化算法求解动态优化问题的研究进展与策略。2.介绍了遗传算法的思想,并且讨论了遗传算法的原理、理论基础以及相应的技术实现。遗传算法是一种稳健性较强的进化算法。3.针对传统遗传算法求解动态优化问题面临的挑战:多样性缺失,对求解动态优化问题的原对偶遗传算法（Primal-Dual GA, PDGA）进行研究,提出了一种新的自适应的双概率原对偶遗传算法,并通过测试表明所提算法比原始PDGA有较好的性能。4.针对动态背包问题提出了一种基于贪婪近似法的遗传算法,通过仿真结果进一步证明了本文所提出的基于贪婪近似法的双概率原对偶遗传算法求解动态优化问题能力。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 动态优化问题求解方法研究进展
• 1.3 进化算法
• 1.4 动态进化计算的研究综述
• 1.4.1 动态优化问题的要素
• 1.4.2 进化算法求解动态优化问题的研究进展与策略
• 1.5 本文的组织结构
• 第二章 遗传算法原理及其实现
• 2.1 遗传算法的产生与发展
• 2.2 遗传算法的基本思想与特点
• 2.2.1 遗传算法基本思想
• 2.2.2 遗传算法的特点
• 2.3 遗传算法基本原理
• 2.4 基本遗传算法的理论基础
• 2.4.1 模式定理
• 2.4.2 积木块假设
• 2.4.3 遗传算法数学描述
• 2.5 基本遗传算法的实现
• 2.5.1 基本遗传算法的实现步骤
• 2.5.2 基本遗传算法的技术实现
• 2.6 本章小结
• 第三章 自适应的双概率原对偶遗传算法研究
• 3.1 概述
• 3.2 原对偶映射机制
• 3.3 原对偶遗传算法基本规则设计
• 3.4 双概率原对偶映射机制
• 3.4.1 设计思想
• 3.4.2 双概率计算
• 3.5 自适应的双概率的原对偶遗传算法
• 3.6 几种对偶机制比较
• 3.7 动态环境测试
• 3.7.1 静态优化问题
• 3.7.2 动态测试环境的产生
• 3.8 实例仿真结果与分析
• 3.8.1 位匹配问题的实验结果
• 3.8.2 欺骗函数的实验结果
• 3.8.3 Royal Road 函数的实验结果
• 3.8.4 实验结论
• 3.9 本章小结
• 第四章 基于贪婪近似法的遗传算法在动态背包问题中的应用与研究
• 4.1 动态背包问题描述
• 4.2 贪婪近似法
• 4.3 算法基本规则设计
• 4.3.1 算法设计思想
• 4.3.2 基于贪婪近似法的双概率原对偶遗传算法
• 4.4 实例仿真
• 4.4.1 动态测试函数
• 4.4.2 实验设置
• 4.5 实例仿真结果与分析
• 4.6 本章小结
• 第五章 总结与展望
• 5.1 本文研究成果
• 5.2 研究展望
• 参考文献
• 致谢
• 攻读硕士学位期间已发表的论文