粗粒度并行遗传算法的计算性能及其应用研究

论文摘要

遗传算法是一种随机性的全局优化算法。粗粒度并行遗传算法作为遗传算法的一个重要改进型,具有比经典遗传算法更好的计算性能,可以比较有效地平衡未成熟收敛和局部收敛速度过慢这对矛盾。本文主要讨论粗粒度并行遗传算法。作为一种启发式搜索算法,遗传算法的计算结果具有不稳定性和不可重现性。现在学术界对遗传算法中的某些遗传操作的作用机制还不十分清楚,遗传算法的许多性能特点无法在数学上严格证明。遗传算法的计算过程也会受到各种随机因素的影响。但是大量的实际计算表明,遗传算法的计算结果具有一定的规律性,在统计意义上具有一定的可靠性。本文采用了对同一参数组合进行多次重复计算的方法,提高实证分析的准确性和可信度。多次重复计算所得的最优解的均方差和产生这些最优解的代数的平均值来评价计算结果的稳定性和收敛性。通过遗传算法和随机遍历搜索算法的对比分析,评价遗传算法的计算效率。通过对多个具有不同典型数学特性的经典测试函数进行实际计算以及计算结果的对比分析,得到了遗传算法计算性能的特点和最佳参数设置的相关结论;通过从统计学角度对多次重复计算的结果进行分析,得到了遗传算法的稳定性和可信度方面的相关结论,这说明可以利用分析遗传算法及其改进型求解解析问题的计算效果所得到的结论,使遗传算法在求解复杂的大型实际工程优化问题时获得更好的计算效果。为了改善变异操作的性能,本文提出了三种不同的思路共六种具体实施方法对遗传算法的变异操作进行改进。实证分析表明这六种改进方法的计算结果都明显优于不采用任何改进措施的经典遗传算法,其中每隔一定进化代数再随机产生新个体的方法为最优。对粗粒度并行遗传算法的子种群个数、种群规模和进化代数进行了实证分析,总结出这三个参数对算法的计算效果和计算效率的实际影响的结论。并通过与经典遗传算法的计算结果的比较和分析,论证了粗粒度并行遗传算法拥有较为理想的计算结果和运行过程,具有较高的种群多样性和计算稳定性。对同步迁移和异步迁移这两种迁移方式进行了统一描述,并对同步迁移和不同参数设置的异步迁移的具体计算性能进行了实证分析。计算结果表明:同步迁移作为异步迁移的一种特例,既不是异步迁移中最优的形式,也不是最差的形式;想要使算法达到最佳的计算效果,关键在于基础迁移间隔和迁移概率这两个参数的设置;单峰问题比多峰问题更适合采取同步迁移方式。本文对各子种群使用不同参数设置的改进型粗粒度并行遗传算法进行了讨论和实证分析,这种经过改进的新方法通过提高各个子种群之间进化行为的差别来提高整个种群的多样性,使粗粒度并行遗传算法能真正达到不同子种群搜索不同的局部最优解的目的,提高了粗粒度并行遗传算法的种群多样性和计算性能。实算显示这种改进具有实际效果,对多峰问题效果尤为明显。以往为了提高应用遗传算法求解实际工程优化问题的计算性能所采取的措施都必须了解待求解问题的具体特性后,才能找到合适的进化策略设定方法,这种改进的新型粗粒度并行遗传算法可以避免这种缺陷,为求解实际工程优化问题带来了方便,提高了遗传算法的实用性和可行性。用粗粒度并行遗传算法对澜沧江上的梯级水电站的短期调度问题这一实际案例进行求解计算。本文首先对问题建模,根据遗传算法的特点对模型进行变换,然后利用已得到的进化策略设定方法用粗粒度并行遗传算法对模型进行优化求解,并对计算结果进行分析讨论。通过对工程实际问题的求解,说明粗粒度并行遗传算法可以很好地解决工程实际问题,特别是对于需要对不同初始数据进行多次求解的模型,遗传算法是具有优势的。通过本文中的实证分析研究,为使用遗传算法对大型复杂的工程实际问题进行计算提供了进化策略设定方法的参照依据,对遗传算法的推广和更有效地应用具有实际价值;理论上,本文对遗传算法的实证分析和参数设置研究为遗传算法的机理研究提供了可信实算数据支持。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景、目的和意义
• 1.2 优化问题和测试函数
• 1.3 遗传算法
• 1.4 并行遗传算法
• 1.5 遗传算法和其他搜索算法的计算性能的比较
• 1.6 研究内容和论文结构
• 1.7 论文研究方法
• 2 遗传算法运行过程和计算性能研究
• 2.1 遗传算法的执行步骤和具体操作
• 2.2 遗传算法的模式机理
• 2.3 遗传算法的进化过程
• 2.4 遗传算法的实验方法
• 2.5 遗传算法计算效率和随机遍历搜索的比较
• 2.6 遗传算法的定义域和值域
• 2.7 本章小结
• 3 基于变异操作的遗传算法改进型研究
• 3.1 遗传算法改进型概论
• 3.2 变异操作对遗传算法计算性能的影响
• 3.3 自适应型变异操作
• 3.4 变异操作方式的改进
• 3.5 多次种群初始化
• 3.6 各种变异操作改进型的计算结果分析和结论
• 3.7 本章小结
• 4 粗粒度并行遗传算法的计算性能研究
• 4.1 粗粒度并行遗传算法的运行步骤
• 4.2 粗粒度并行遗传算法的机理
• 4.3 粗粒度并行遗传算法的未成熟收敛问题
• 4.4 粗粒度并行遗传算法的参数
• 4.5 粗粒度并行遗传算法的实验方法
• 4.6 实验结果和结论
• 4.7 遗传算法计算性能的统计分析
• 4.8 本章小结
• 5 迁移操作对粗粒度并行遗传算法的影响
• 5.1 迁移操作的机理
• 5.2 迁移操作和变异操作的比较
• 5.3 迁移方式
• 5.4 迁移操作的执行步骤和执行方法
• 5.5 迁移操作的实验方法
• 5.6 实验结果及其分析
• 5.7 本章实验结论
• 5.8 本章小结
• 6 一种改进型粗粒度并行遗传算法
• 6.1 粗粒度并行遗传算法的运行机理
• 6.2 粗粒度并行遗传算法的改进方法
• 6.3 实验方法
• 6.4 计算结果及其分析
• 6.5 本章实验结论
• 6.6 本章小结
• 7 案例:梯级水电站群短期优化调度研究
• 7.1 梯级水电站群短期调度问题概述
• 7.2 梯级水电站短期调度模型的建立
• 7.3 用于计算的模型初始数据和遗传算法参数
• 7.4 模型计算结果及其分析
• 7.5 本章小结
• 8 全文总结与展望
• 8.1 全文总结
• 8.2 研究展望
• 致谢
• 参考文献
• 附录1
• A.攻读博士学位期间公开发表的学术论文
• B.公开发表的学术论文与博士学位论文的关系
• 附录2 本文中的部分详细计算结果