Evolutionary Algorithms For Several Complex Optimization Problems And Their Applications

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.