实数编码遗传算法机理分析及算法改进研究

摘要

工程和科学计算中的很多优化问题从最初的低维优化发展为高维、大规模复杂优化，或常常带有比较复杂的约束条件，因而比较难以求解。以遗传算法为代表的各类进化算法在求解该类复杂问题时越来越受到重视。然而有关实数编码遗传算法（RCGA）的工作机理的研究比较少，不能有效地指导算法的改进。本文研究了RCGA的工作机理，分析了RCGA种群漂移的规律，提出了一些改进算法，用高维优化和约束测试函数进行了数值实验，验证了本文算法的有效性。具体创新性成果如下： 1、本文指出适应度函数设计存在不合理性，提出一个种子的适应度值理论上应该和该种子到全局最优点的欧氏距离成负相关性；提出了基本交叉算子实质上就是基于差分法的一维搜索。在进化后阶段，当两父体种子在同一邻域内时，该搜索在整个进化过程中成为有效搜索的可能性比较大，当两父体种子距离比较远时，成为有效搜索的可能性逐渐减小。单重均匀或非均匀变异算子在种群空间里其变异都不是均匀的； 2、本文提出优势种群（块）的概念，通过研究优势块在种群中种子个数的期望值增长规律提出了标准RCGA种群漂移块式定理：遗传算法的进化过程中，新的优势块不断出现排挤了原来的优势块直到最后一个优势块出现不再被排挤为止。如果RCGA各参数设置合理，RCGA中的新的优势块规模期望值具有近似按指数级增长的趋势。在此基础上阐述了RCGA的参数设置规则，分析了RCGA提前收敛的原因，解释了一些改进算法之所以有效的原因，结合算子作用机制提出了RCGA工作机理。从微观上来说，遗传算法是一种基于差分法的邻域搜索、局部搜索和全局搜索自适应结合的算法；邻域搜索、局部搜索和全局搜索所占比例受种群中优势块的个数以及各个优势块种子个数的变化而变化。从宏观上来说，遗传算法是一种以一定概率选择多个区域（面向搜索块）的迭代算法。优势种子邻域内种子浓度增大有利于加快优势块收敛速度。 3、本文提出了一种多精英保存策略遗传算法（GAEP），通过求解三个经典的连续函数优化问题与当前一些改进进化算法数值结果对比，验证了GAEP算法的有效性。分析了该算法的局限性并改进提出了基于物种选择的遗传算法（GASS）。通过模拟生物进化的阶段性对GASS算法进行了改进，得到了改进算法（IGASS）。三个算法都通过最优种群的隔离来保持选择压力，最优种群边界的自适应收缩和最优种群规模的不定期减小至1保持了种群的多样性，比较好地平衡选择压力和种群多样性，算法IGASS既对种群划分（横向划分），又对进化代数自适应的划分（纵向划分），消除了参数（最大进化代数）对均匀变异算子的步长在整个进化过程不均匀的影响，从而性能更稳定。通过标准的高维和超高维数值实验分析了IGASS算法的动态性能，并对算法IGASS与CEC2008国际会议技术报告里提供的十个参照算法进行比较，结果表明，IGASS算法适应度函数计算次数、求解精度以及算法稳定性基本上都优越于参照算法。算法IGASS尤其适合于求解变量可分离的超高维问题。 4、本文指出以往的约束处理策略都没有很好地与精英保存策略结合起来。通过对惩罚因子的局部分析，提出了一种与精英保存策略相结合的惩罚函数法约束处理策略，结合IGASS算法提出了一种混合算法（MGASS），算法MGASS将种群划分为三个子种群，此三子种群按不同策略进化。标准的约束测试函数数值实验表明该算法性能比较好。

目录

文摘

英文文摘

声明

第一章绪论

1.1引言

1.2遗传算法的生物学背景

1.2.1遗传变异理论

1.2.2进化论

1.3遗传算法的起源与发展

1.4遗传算法的基本结构及主要特点

1.4.1遗传算法的基本结构

1.4.2遗传算法的主要特点

1.5遗传算法理论研究

1.5.1模式定理和积木块假设

1.5.2编码策略

1.5.3收敛性与收敛速度分析

1.5.4问题难解性预测与算法性能评价指标

1.5.5No Free Lunch定理

1.6遗传算法的研究现状及发展趋势

1.7本文主要研究内容

第二章实数编码遗传算法机理研究—块式理论

2.1引言

2.2优化问题假设及RCGA算法描述

2.2.1优化问题描述及分析

2.2.2 RCGA算法描述

2.3以往研究局限性分析

2.4实数编码遗传算法算子作用机制分析

2.4.1选择算子作用机制分析

2.4.2基本交叉算子作用机制分析

2.4.3变异算子作用机制分析

2.4.4交叉算子与变异算子作用比较

2.5优势块规模增长理论——种群漂移块式定理

2.5.1最优块与优势块

2.5.2选择算子对最优块的影响分析

2.5.3交叉算子对最优块规模的影响分析

2.5.4变异算子对最优块的影响分析

2.5.5精英保存策略对最优块规模的影响

2.5.6种群漂移与RCGA参数设置分析

2.5.7 RCGA遗传漂移块式定理

2.6 RCGA提前收敛原因分析

2.7块式理论对一些改进遗传算法的解释

2.8小结

第三章基于物种选择的遗传算法

3.1引言

3.2基于多精英保存策略的遗传算法

3.2.1算法思想来源

3.2.2算法参数及有关说明

3.2.3算法描述

3.2.4数值实验

3.3基于物种选择的遗传算法

3.3.1算法GAEP的几点考虑

3.3.2算法GASS生物学背景

3.3.3算法GASS描述

3.3.4算法GAEP与算法GASS性能比较

3.3.5参数分析

3.4小结

第四章GASS的改进算法及性能研究

4.1引言

4.2算法GASS进一步研究

4.3 IGASS算法

4.3.1算法参数说明

4.3.2算法描述

4.4数值实验

4.4.1算法IGASS与算法GASS性能比较

4.4.2高维函数IGASS算法与PHEP算法性能比较

4.4.3算法动态特性分析

4.4.4超高维函数IGASS算法与CEC2008算法性能比较

4.5与常见改进算法设计思想的比较

4.6算法性能分析

4.7小结

第五章求解约束优化问题的一种混合算法

5.1引言

5.2约束处理技术综述

5.2.1惩罚函数法

5.2.2多目标法

5.3约束处理技术几个问题的分析

5.3.1有关Pareto前沿分析

5.3.2约束处理技术局限性分析

5.3.3精确惩罚因子存在性分析

5.4算法MGASS求解约束优化问题

5.4.1算法思想

5.4.2惩罚因子设计

5.4.3种群划分

5.4.4参数说明

5.4.5算法描述

5.5数值实验与结论

5.6小结

第六章总结与展望

6.1总结

6.2展望

参考文献

附录：

致谢

攻读学位期间主要的研究成果