论文部分内容阅读
在工程设计、科学计算、经济领域中存在着各种类型的复杂优化问题,通常需要求解它们的全局最优解而不是局部最优解。进化算法是一类鲁棒性强的全局搜索算法,对基于梯度的传统优化方法无法或难以处理的高度非线性、不可微、多峰、多变量问题,尤其是目标函数的导数无法求出,受噪声影响或没有明确的数学形式这样的问题,进化算法具有很大的优势。本文对几类复杂优化问题,包括无约束全局优化、约束优化、整数规划和混合整数规划、线性两层规划、凸二次两层规划、一般的非线性两层规划以及离散两层规划进行了系统深入的研究,根据不同类型的问题,设计和开发了不同的进化算法,并将所设计的部分算法应用到实际问题中,以验证算法的有效性和实用性。论文的主要研究成果可概括为以下几个方面:1.在设计新变异算子的基础上提出了一种实数编码遗传算法,结合一种局部搜索算子——简化的二次插值法,提出了求解无约束全局优化问题的混合遗传算法。还分析了该算法的收敛性,对23个标准测试函数作了数值实验。与文献中其它进化算法的比较结果表明了算法的有效性。最后,将该算法应用于圆柱共形天线阵方向图优化综合,获得了良好的效果。2.采用精确罚函数法,把约束优化问题转化为无约束优化问题,将简化的二次插值法作为局部搜索算子,合并到差分进化算法中,提出了一种求解约束优化问题的混合差分进化算法。采用该算法求解了13个标准测试问题,并与文献中已有的进化算法作了比较,结果表明混合差分进化算法性能优良。最后,采用该算法优化设计了4个著名的工程问题,所得结果表明了算法的有效性和实用性。3.对不同类型的离散优化问题提出了不同的进化算法。首先,对一类0-1整数规划——多维背包问题,将正交试验设计应用到杂交算子中,结合一种基于贪婪思想的约束处理,提出了一种0-1编码的正交遗传算法。其次,对一般的整数规划问题,设计了一种整数编码的混合进化算法。该算法中采用带有随机参数的差分变异算子;将正交表和因素分析引入杂交过程,设计了杂交算子;设计了一种迁移算子来增加种群的多样性;把简化的二次插值法用作局部搜索算子;通过对每一代中最好染色体的基因进行微调,来跳出局部最优解。对所有算子产生的染色体均使用了一种取整和截断操作过程,以保证所求问题的变量满足整数要求和边界约束条件。最后,对混合整数规划,设计了一种整数和实数混合编码的混合进化算法。对所提出的三个进化算法作了大量的数值实验,并与文献中的其它进化算法作了比较,结果表明了三个算法的有效性。采用正交遗传算法求解了投资决策和成本预算问题,进一步说明了算法的有效性和实用性。4.对线性两层规划和凸二次两层规划问题分别提出了一种正交遗传算法。采用KKT最优性条件将这两类两层问题分别转化为单层互补松弛问题,并对KKT乘子进行0-1二进制编码,将互补松弛问题分别转化为一系列线性规划或凸二次规划,其最优解就对应原两层规划的一个可行解。在此基础上,分别设计了求解两类单层互补松弛问题的正交遗传算法。理论分析和数值实验结果表明,求解这两类两层问题的正交遗传算法是有效的,能以较少的计算代价求出问题的全局最优解。最后,采用线性两层规划的正交遗传算法求解了价格控制问题。5.对上层规划是非凸、不可微的非线性两层规划问题,采用均匀设计法产生初始种群,结合局部搜索算子——简化的二次插值法,提出了一种混合遗传算法。分析了算法的收敛性,大量的数值实验结果验证了算法的有效性,也表明了算法能找到高质量的最优解。最后,采用该算法求解了交通网络设计和公路通行费设置问题,进一步验证了算法的有效性和实用性。6.对离散两层规划问题提出了两种进化算法。对整数线性两层规划问题,首先将其转化为等价的0-1线性两层规划问题,对给定的每一个上层变量,采用分支定界法求解下层问题的最优解,然后将其转化为单层隐规划问题,设计了一种正交遗传算法来求解。对上层变量是整数变量,下层变量是连续变量的混合整数非线性两层规划问题,对给定的每一个上层变量,采用传统优化算法求解下层问题的最优解,可以将两层规划转化为整数变量的单层隐规划问题,设计了一种混合进化算法来求解。数值实验结果验证了两种算法的有效性。