【作者】 李宏；

【导师】 焦永昌；

【作者基本信息】 西安电子科技大学 ， 智能信息处理， 2009， 博士

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

【Abstract】 Complex optimization problems arise in almost every field such as engineering, science and business. A global optimal solution to these problems rather than a local optimal solution is desired. Evolutionary algorithms have been shown to be one kind of global and robust methods for solving highly nonlinear, nondifferentiable, multimodal and multivariate optimization problems. Furthermore, they are even suitable for problems whose derivatives are not available, affected by noise or whose objective functions cannot be expressed in explicit mathematical forms. These problems cannot be solved by traditional gradient-based optimization techniques. This dissertation is focused on evolutionary algorithms for several complex optimization problems, including unconstrained global optimization, constrained optimization, integer or mixed-integer programming, linear bilevel programming, convex quadratic bilevel programming, general nonlinear bilevel programming and discrete bilevel programming, and their applications. The main contributions on these subjects can be summarized as follows.1. For solving unconstrained global optimization, a hybrid genetic algorithm is proposed. First, based on a new mutation operator, a real-coded genetic algorithm is designed. The simplified quadratic interpolation (SQI) method is then integrated into the genetic algorithm to improve its local search ability and the accuracy of the minimum function value. The theoretic analysis and simulation results on 23 benchmark functions show that the hybrid genetic algorithm is more effective and find much better solutions with lower computational cost, compared to other existing algorithms. At last, the far-field radiation patterns of the conformal antenna array are synthesized using the hybrid genetic algorithm with satisfactory results.2. For solving constrained optimization, a hybrid differential evolution algorithm is proposed. By associating the exact penalty with all constraint violations, a constrained problem is transformed into an unconstrained problem. The SQI method is used as a local search operator for enhancing the performance of the standard differential evolution (DE) algorithm. 13 well-known benchmark problems are used to validate its efficiency. Simulation results show that the hybrid DE is superior to the standard DE. The results obtained are very competitive when comparing the proposed algorithm against other existing algorithms. At last, the algorithm is applied to four engineering design problems to demonstrate its effectiveness and applicability.3. For three types of discrete optimization, different evolutionary algorithms are proposed. Firstly, an orthogonal genetic algorithm based on the orthogonal experimental design is proposed for solving the multidimensional knapsack problems, a kind of 0-1 integer programming problems. A check-and-repair operator based on the greedy algorithm is used to handle constraints. Secondly, an integer-coded hybrid evolutionary algorithm is developed to solve general integer programming. In this algorithm, a differential mutation operator with random parameters is adopted. A crossover operator with the orthogonal array and factor analysis is used to generate the better offspring. A migration operator is employed to keep the population’s diversity. The SQI method is also taken as a local search operator. Moreover, a few of foreign chromosomes introduced into next population are generated by randomly perturbing the best chromosome in the current population. A rounding and truncation procedure is incorporated in the operations of the algorithm to ensure that the integer restrictions and box constraints imposed on the variables are satisfied. Finally, a mixed-coding scheme of hybrid evolutionary algorithm based on the orthogonal experimental design is developed to deal with the mixed-integer programming problems. Many numerical examples are used to validate their effectiveness. Two practical examples, the investment problem and the budget problem, are provided to demonstrate the effectiveness and applicability of the orthogonal genetic algorithm.4. For linear bilevel programming and convex quadratic bilevel programming problems (BLPPs), the orthogonal genetic algorithms are proposed. By using Karush-Kuhn-Tucker (KKT) conditions, these two BLPPs are replaced by two single-level complementary slackness problems respectively. In order to cope with the complementarity constraints, a binary encoding technology is adopted for KKT multipliers. Thus, two orthogonal genetic algorithms are presented to optimize the binary strings. Some numerical examples from the literature are used to test these methods. The theoretic analysis and experimental results show that the proposed methods are effective and can find global optimal solutions with less computation burden. At last, the price control problem is solved by the orthogonal genetic algorithm for the linear BLPP to demonstrate its effectiveness.5. For general nonlinear BLPPs with nonconvex and nondifferentiable upper level objective function, a hybrid genetic algorithm is presented. In this algorithm, the uniform design is used to generate initial population. The SQI method is taken as a local search operator to improve solution accuracy and computational efficiency. The theoretic analysis and the simulation results on many numerical examples show that the proposed algorithm is effective and can find high quality solutions. At last, the hybrid genetic algorithm is applied to the network design problem and the toll-setting problem.6. Two evolutionary algorithms for the discrete BLPP are presented. The discrete linear BLPP is firstly transformed into a 0-1 BLPP in which the lower level problem can be solved by the branch and bound algorithm, and then the problem is transformed into a single level 0-1 programming, which is solved by the orthogonal genetic algorithm. In addition, for the discrete nonlinear BLPP with discrete upper level variables and continuous lower level variables, the lower level problem can be solved by the traditional optimization algorithms. This bilevel problem is then transformed into a single level discrete programming problem, which is solved by the hybrid evolutionary algorithm. Some numerical examples are used to test their performance. The simulation results show that two evolutionary algorithms are effective.更多还原