A Study Of Large-Scale Optimization Based On Multi-Space Evolutionary Search

Decision problems in complex scenarios widely exist in many fields in real world.The optimization of relevant decisions has drawn much attentation in scientific research.In recent years,with the development of the science and technology,the scale of these optimization problems sharply increases.Generally,large-scale optimization problems have thousands of decision variables,particular examples include optimization of air traffic flow,Qo S-aware service,vehicle route optimization in large-scale transportation network,etc.In such scenario,the fast-growing number of decision variables may lead to the exponential growth of search space,which results in deteriorating rapidly on the performance of heuristic search algorithm and “curse of dimension”.Furthermore,the large-scale optimization problems typically involve the characteristics of multimodality,nonlinearity and nondifferentiability,which leads to the soaring number of local optimal solutions of multimodal function increasing exponentially.As a result,it is difficult to find the optimal solution within the limited computing resources,and the algorithm may fall into the local optimization,which has great difficulty and challenge for deterministic optimization algorithm.To address these issues,many approaches to simplify the search space are proposed,which can be categorized into two groups:decomposition-based methods and dimension-reduction-based methods.However,it is worth noting that decomposition-based approaches mostly rely on the accurate detection of the relationships between decision variables,which may fail in solving large-scale optimization problems that possess complex variable interactions,or even nondecomposable.On the other hand,dimension-reduction-methods may lose important optimization information,and it is difficult to guarantees the global optimum or high-quality solutions in reduced solution space.Keeping this in mind,in this thesis,we focus on simplifying the search space of large-scale optimization problem to develop multi-space evolutionary search paradigm.Specifically,main contributions of this thesis can be summarized as follows:(1)Existing simplifying search space methods for solving large-scale continuous optimization problem often need to consider the problem characterstics.There are assumptions and requirements on the relationships between decision variables of the given optimization problem,and it cannot guarantee the existence of global optimum or high-quality solutions in the search space.To tackle such problem,a new evolutionary search paradigm,namely the multi-space evolutionary search,for solving large-scale continuous optimization problem is proposed.Specifically,given a large-scale optimization problem,besides the original problem space,multiple simplified solution spaces are derived.Moreover,the mapping between these problem spaces is learned,which will be used for knowledge transfer across spaces during the evolutionary search process.In this way,the useful traits found in the simplified problem space can be leveraged to facilitate the search in the original space,while the high-quality solutions found in the original problem space may also guide the search direction in the simplified problem space toward promising areas.Furthermore,to explore the usefulness of diverse auxiliary tasks,the simplified problem space will be re-constructed periodically using the solutions found during the evolutionary search process.The experimental results on 15 functions of CEC2013 large-scale benchmark suite show that the proposed MSES achieved significantly better averaged objective values on 13,13 and 12 problems in contrast to DG2,RDG,RDG3.Compared with the DLLSO and Me MAO,the proposed MSES obtained significantly better averaged objective values on 9 and 13 problems.(2)For solving large-scale discrete optimization problems,the multi-space memetic search algorithm is presented by taking the classical vehicle routing problem as an example.Specifically,multiple simplified vehicle routing problems are firstly constructed and acted as the auxiliary tasks of the original vehicle routing problem.The memetic evolutionary search is thus simultaneously performed on simplified vehicle routing problems and original vehicle routing problem.In this way,the useful traits found in the simplified vehicle routing problems can be transferred to original vehicle routing problem to enhance the evolutionary search.The experimental results on 65 instances of commonly used CVRP benchmark suit demonstrate that the proposed method can obtain superior results than the baseline algorithm and random method.(3)To handle the unreasonable resource allocation problem in multi-space evolutionary search,the multi-space evolutionary search with dynamic resource allocation strategy(MSES-DRA)is proposed,which is designed based on explicit-implicit contributions of spaces according to the interaction between optimal individual and population.In particular,a detection mechanism is presented to measure the reasonableness of assignment in terms of computation resource of spaces.Meanwhile,an online resource statistics based on implicit and explicit contribution is proposed.Specifically,the explicit contributions can be defined by the fitness improvements of the best solutions found by independent evolutionary search performed on different spaces.The implicit contributions can be defined by the survivals of individuals that are transferred solutions across problem spaces.Further,an adaptive technology based on feedback is conducted to balance the assignment in terms of computational resource based on explicit contribution and implicit contribution.The experimental results on 15 problems of CEC2013 large-scale benchmark suite demonstrate that the proposed MSES-DRA method achieved significantly better averaged objective values on 10,9 and 9 problems in contrast to the MSES method using DLLSO,SHADE and Sa NSDE as the optimizers,respectively.Compared with the FCRACC and CCFR2,the proposed MSES-DRA method obtained significantly better averaged objective values on 10 and 10 problems,respectively.