一种基于育种思想的全局优化算法——原理、性能及应用

摘要

优化技术作为工程决策的定量分析方法，其目的是基于研究对象的某种指标寻找最优的变量取值。但是，对于采用某种优化算法所获得的优化结果，当问及是否存在比之更好的解或者其是否全局最优解时，现有的算法尚难作出令人满意的回答。包括遗传算法(Genetic Algorithm，GA)在内的诸多算法，可以在经历无穷代演化后以概率1收敛到全局最优，但实际操作往往只能是有限次计算。因此，寻找更为有效的算法或策略以提高优化计算的效率，并对优化算法有限次计算的结果进行评价，以为决策提供更为可靠的信息，似将成为优化技术研究领域所关注的重要课题。本文基于遗传算法对上述课题展开研究，其主要工作内容和贡献如下。 1.通过理论分析与实验研究，本文对常规遗传算法在优化计算的全局性和精确性等方面存在的问题进行了分析，指出遗传算法同时进行广度搜索和局部搜索的思想策略所存在的内在缺陷及其所面临的困境，为算法策略的进一步改进指出了合理可行的方向。 2.本文借鉴现代育种操作思想，提出一类新的进化算法—育种算法(Breeding Algorithm，BA)。算法将全局优化过程转化为种子的选择和培育两个阶段的操作。提出利用自由采样选种实现广度搜索，采用基因置换技术执行育种操作以实现局部搜索的新思想，指出算法实现全局优化的基本原理并建立相应的实施模型。实验结果表明，实现相同概率的全局优化，育种算法所需计算代价一般不到常规遗传算法的1/2，并且具有更高的计算精度。 3.根据育种算法的采样选种过程，本文提出采样探测灵敏度的概念，并结合采样得到的最优个体建立了解的全局性评价方法。 4.本文对基因置换技术实现局部搜索的机理进行了分析和描述。对于二进制编码遗传算法所出现的海明悬崖现象，根据基因置换完毕的编码特征，提出识别和修复方法，从而可以确保算法实现二进制编码的最高计算精度。与此同时，对基因置换操作实现局部搜索的计算代价进行分析估计，指出该操作函数值计算次数上限和经验估计。 5.本文对算法的实施和演化方式进行了研究，针对函数优化问题的性状及复杂函数的构造特征指出了算法的相应策略。对于约束优化问题，建立采用罚因子确定的经验方法。对40余例变量数1～50的经典测试函数进行实验和比较的结果表明，育种算法成功地刷新了现有部分最优解记录，其全局和局部搜索性能都优于常规遗传算法。 6.本文对平行育种算法应用于多目标优化问题的效果进行了研究。结果表明，在求取多目标优化问题的帕累托(Pareto)有效解集方面，采用平行育种算法结合随机权系数，一般可以获得多个有效解。另外，针对过程系统控制参数的不确定性所产生的多模态和敏感系统优化问题，提出了系统平均效果最优解的概念，并结合平行育种算法建立了相应的求解和评价方法，然后通过工程实例的求解，对该方法的实施过程进行了更为确切的描述。 7.最后，本文给出运用育种算法求解工程优化问题的基本实施流程，并对相关策略进行说明。 本文研究结果表明，和常规遗传算法相比，育种算法在全局优化的原理上更加明确，算法构造更为简单，且在优化计算的精确性和效率方面也具有明显优势，可作为一种实用的工程优化方法。

目录

文摘

英文文摘

声明

引 言

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小结

3 育种算法的实施策略及实验研究

3.1种子判断准则与采样终止

3.2单一种子育种模型(sBA)

3.3多种子平行育种模型(pBA)

3.4育种算法实验及结果分析

3.5函数优化问题的复杂性及其构造特点

3.6结合区域压缩技术的育种算法

3.7结语

4 育种算法求解约束优化问题的策略及实验研究

4.1约束条件的处理

4.2育种算法求解约束优化问题的实验研究

4.3约束优化的搜索特征及罚因子确定

4.4结语

5 平行育种算法在多目标及敏感系统优化的应用

5.1多目标优化问题

5.2敏感系统优化及其最优解的确定

5.3结语

6 育种算法求解工程优化问题的基本流程

6.1优化模型的构造和算法要求

6.2育种算法的程序构成和操作步骤

6.3算法结果及其评价

结论和展望

创新点摘要

参考文献

附录

攻读博士学位期间发表学术论文情况

致 谢