Researsch On Efficient Metaheuristic Algorithm For Large-scale Optimization Problems

There are numerous optimization problems in the real world.With the development of the times,the scale of these problems is constantly increasing.Generally,large-scale optimization problems share certain characteristics,such as multi-modal and high-dimensional.These characteristics make the traditional algorithms fall into the local optimum easily.Metaheuristic algorithm is an important research direction in software engineering based on search.It is proposed as an improved heuristic algorithm to solve such challenges.In this thesis,metaheuristic algorithm and a special metaheuristic algorithm,hyper-heuristic algorithm is summarized,and the advantages and disadvantages of various metaheuristic strategies in large-scale optimization problems are discussed,and then metaheuristic algorithms are designed respectively.The specific works are described as follows:(1)Taking the large-scale layout problem characterized by nonlinear and continuous with variable parameters as a case study,the strategy based on hyper-heuristics is designed and implemented.Two different algorithms are selected as the low-level operators,and at the high level,the hyper-heuristics algorithm is used to call the low-level operators to solve the wind farm layout problem under twenty different complicated scenes.By contrast,the experiment data imply that the new strategy is more efficient and flexible.(2)In order to solve the large-scale problems from different domains,a novel Decomposition and Mathematical Programming based Hyper-heuristic(DEMPH)is proposed.The low-level heuristic operator combines sub-problems generation operator with the mathematical programming solver operator,and then scheduled by the high-level heuristic strategy.An adaptive high level strategy is employed to schedule the sub-problem selection strategies.The generalized assignment problem and the three-index assignment problem are taken as examples,experiments based on three data sets commonly used in this field indicate that DEMPH is able to tackle large-scale problems from different domains efficiently,and generalize well on different types of instances.(3)Aiming at large-sacle space reduction problem,in this thesis,a Multi-level Random Walk Algorithm(MultiWalk)is proposed to simplify the original problem instances.In each level,local optimal solutions are searched with WalkTest in potential subsets.The problem scale is reduced by locking the intersection of local optima(called backbone)and by discarding fats with no contribution.Finally,the reduced small-scale problem is combined with the backbone to obtain the solution to the original large-scale optimization problem.Taking the test suite reduction problem as a case study,which is an NP-hard problem in software engineering field as an example,experiments are conducted on the data sets of ten large-scale open source Java projects.The algorithm proposed in this thesis is compared with the traditional dominant algorithm.Experiments show that MultiWalk can more efficiently find optima on five out of six projects,over which Integer Linear Programming(ILP)can find optima;for the other four projects that ILP fails to solve,Multi Walk provides the best solutions among heuristics in comparison.(4)Aiming at a large-scale multi-objective schedule optimization problem,algorithm based on genetic algorithm is designed based on the idea of co-evolution.Through the extraction and analysis of the actual problems with a variety of targets and constraints,on the basis of genetic algorithm,the algorithm adopts a specific strategy to ensure the satisfaction of various constraints.Based on the real data and the large-scale virtual data,the algorithm can solve such large-scale multi-objective optimization problems,and the effect of the algorithm is significantly better than that of manual programming.In summary,for large-scale optimization problems with different characters from different domains,efficient and robust heuristic algorithms are designed.On the one hand,the scale of the problem is degraded by various methods,and on the other hand,a strong scalability metaheuristic algorithm is designed,both contribute to solve large-scale optimization problems in different fields and scenarios.