Font Size: a A A

Research On Evolutionary Algorithms And Applications For Two Kinds Of Complex Optimization Problems

Posted on:2017-05-26Degree:DoctorType:Dissertation
Country:ChinaCandidate:M Z WangFull Text:PDF
GTID:1108330488457217Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Global optimization and mult-objective optimization are two types of complex optimization problems that are widely used in mathematics, engineering, management, military and many other fields. However, when problems become nonlinear global optimization and nonlinear non-convex multi-objective optimization, it will be difficult to solve them. Research on efficient solving algorithm is not only theoretically significant, but with extensive value in use. Evolutionary algorithm is an intelligent optimization algorithm to solve the complex optimization problems, and it has successfully settled many complicated optimization issues in practice. With the increasingly profound research on evolutionary algorithm, evolutionary algorithm by organic coordination of multiple mechanisms has been an effective way to enhance algorithm efficiency and improve the adaptability. Particularly, it is appropriate for solving high-dimensional, nonlinear, indifferentiable, local optimization, multi-objective, dynamic uncertain and other complex optimization problems. This dissertation has carried out a profound research on the efficient evolutionary algorithm of high-dimensional nonlinear global optimization and nonlinear non-convex multi-objective optimization issues, and provides several efficient evolutionary algorithms. Additionally, the dissertation takes the divisible task scheduling under the parallel and distributed systems as the application background to establish a task optimization scheduling model, and designs the corresponding evolutionary algorithm to solve the model. Details are as follows:1. NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithm-Ⅱ) has been one of the most efficient representative evolutionary algorithms for multi-objective optimization problems. Crowding distance in NSGA-Ⅱ plays an important role in convergence and uniform distribution of the solutions, However, the algorithm cannot make full use of the micro individual or macro population overall information. To estimate reasonably region density so as to make the solution set more uniformly converge to the Pareto optimal front, we designed an uniformly crowding distance operator based on uniformly crowding range and Gini weight, and proposed an improved NSGA-Ⅱ algorithm. Finally, by experiment of 10 standard multi-objective test questions, validity of the algorithm is verified.2. The weighted sum methods is one of the simplest and most widely used algorithms in evolutionary algorithms for multiobjective optimization problems. However, such methods can not find the solutions in non-convex part of the Pareto front and the uniformly distributed solutions on the entire Pareto front for nonconvex and complex multiobjective programming. In this dissertation, a novel evolutionary algorithm based on adaptive multiple fitness functions and adaptive objective space division is proposed to overcome this shortcoming. The objective space is divided into multiple regions of about the same size by uniform design, and one fitness function is defined on each region by the weighted sum of objective functions to search for the Pareto solutions in this region. Once a region contains fewer Pareto solutions, it is divided into several sub-regions and one additional fitness function is defined on each sub-region. The search will be carried out simultaneously in these sub-regions, and it is hopeful to find more Pareto solutions in such a region. As a result, the Pareto solutions in each region are changed adaptively, and eventually are uniformly distributed on the entire Pareto front. Finally, make a comparison between the provided algorithm and 10 existing algorithms by solving the 13 standard test function. The results show that the proposed algorithm can effectively handle nonconvex and complex problems, generate widely spread and uniformly distributed solutions on the entire Pareto front, and outperform those compared algorithms.3. Premature convergence and convergence performance difference is the major defect of the current evolutionary algorithm. In order to further improve the global searching ability of evolutionary algorithm and avoid the algorithm into a local optimal solution, this dissertation proposes a new adaptive co-evolutionary algorithm based on genotypic diversity measurement, and proves the global convergence of the algorithm. This algorithm takes genotypic diversity measurement as the link and realizes the cooperative search between operators. By introducing the new adaptive selection, mutation and substitution operators, the proposed algorithm achieves cooperative search among operators and dynamically pairing among sub-populations. The proposed algorithm successfully avoids negative effects brought by a single operator, and takes full advantage of mutual information in sub-populations. Finally, validity of the algorithm is verified through optimization experiment of 7 functions.4. In terms of the practical application problem of the divisible task scheduling under the parallel and distributed systems and taking the heterogeneity of processor(processor has arbitrary communication rate, calculation rate, calculation startup cost and communication startup cost), this dissertation has established a new optimization model with the objective of completion in the shortest time. This model can solve the following three problems:determine the optimum processor number involved in calculation, the optimum processor scheduling sequence, as well as the optimum task allocation plan. In order to effectively solve the model, the dissertation designs a new genetic algorithm and proves that the global optimal solution can be convened with 1 possibility of the algorithm. Local search strategy is also introduced in the algorithm, so as to accelerate the algorithm convergence. Finally, validity of the model and algorithm is verified by simulation experiment.
Keywords/Search Tags:Co-Evolutionary, Uniform crowding distance, Multi-objective optimization, Uniform Design, Diversity measure, Divisible-load scheduling
PDF Full Text Request
Related items