Algorithm Portfolio For Surrogate Assisted Evolutionary Algorithms

Computationally expensive problems(CEPs),for which the fitness function is very complex and expensive to compute,are very common in practical system.Evolutionary Algorithms(EAs)require a so-called fitness function to evaluate the quality of candidate solutions when solving a problem,and a large number of fitness evaluations may be required in order to obtain a satisfying solution.Therefore,computational cost has become a crucial challenge in applying EAs to solve CEPs.To reduce the computational cost of solving CEPs,surrogate-assisted evolutionary algorithms(SAEAs)were developed.In SAEAs,surrogate models or meta-models are approximate models that can simulate the behavior of the original fitness function,but can be evaluated much faster and more cheaply.The easy-to-compute surrogates are used to evaluate a part of candidate solutions instead of evaluating them by real fitness function,so that the computational cost of the optimization procedure is reduced.Surrogate assisted evolutionary algorithms(SAEAs)have been widely used to solve CEPs in the past decades.However,most studied SAEAs focus on solving problems with a relatively large budget which is unacceptable in many very expensive real-world problems.One fitness evaluation in very expensive problems will cost several hours or even days.Therefore,the first work of this dissertation is that we employ Voronoi diagram to boost the performance of SAEAs and propose a novel framework named Voronoi-based efficient surrogate assisted evolutionary algorithm(VESAEA)for very expensive problems.In the proposed framework,the Voronoi diagram divides the whole search space into several subspace and then the local search is operated in some potentially better subspace.Additionally,in order to trade off the exploration and exploitation,the framework involves a global search stage developed by combining leave-one-out crossvalidation and radial basis function surrogate model.A performance selector is designed to switch the search dynamically and automatically between the global and local search stages.The empirical results demonstrate the proposed algorithm's potential to optimize very expensive problems.Surrogate-assisted evolutionary algorithms(SAEAs)are powerful optimisation tools for computationally expensive problems(CEPs).But a randomly selected algorithm is likely to fail in solving unknown problems due to no free lunch theorems,and it will cause more computational resource for re-running the algorithm to get a much better solution,which is more serious in CEPs.In the another work of this dissertation,we applied algorithm portfolio techniques to CEPs.It's the first time to consider the algorithm portfolio for individual-based SAEAs to reduce the optimisation risk for CEPs.We proposed two excellent portfolio frameworks for very expensive problems in which the maximal number of fitness evaluations is only 5 times of problem's dimension.One framework named Par-IBSAEA runs all algorithm candidates in parallel and another framework named UCB-IBSAEA employs the UCB policy to help select the most appropriate algorithm at each iteration.Additionally,an effective reward definition in the optimisation algorithm is proposed for UCB policy.We consider three state-of-the-art individual-based SAEAs on different problems and compare them to the portfolios built on their instances on several benchmark problems using a limited budget.Experimental study demonstrates that our proposed portfolio frameworks could significantly reduce the optimization risk when to solve CEPs compared to the single algorithm.