Research On Surrogate-assisted Evolutionary Algorithms For Expensive Combinatorial Optimization

Expensive combinatorial optimization problems(ECOPs)are commonly found in practical applications,featuring two main characteristics: discrete decision variables and expensive objective evaluations.With the growing need for optimization,real-world ECOPs are becoming more and more intricate.The complexity is mainly due to two significant factors: the high-dimensional decision space and noisy objective evaluation.Surrogate-assisted evolutionary algorithms(SAEAs)have been extensively utilized to solve ECOPs.However,when SAEAs are used to handle high-dimensional and noisy ECOPs,there are some significant challenges.This dissertation focuses on complex ECOPs,aiming to investigate how to use SAEAs to solve the above two types of issues with limited expensive objective evaluations.The main contributions of this dissertation are shown as follows:(1)This dissertation proposes an SAEA with parallel random grouping(SAEA-PRG)to solve a special class of high-dimensional ECOPs-feature selection problems.To overcome the challenges of constructing accurate surrogate models in high-dimensional spaces,SAEAPRG divides the high-dimensional decision variables into several equally sized and mutually exclusive groups.Each group represents an independent subproblem.After that,SAEAPRG constructs a surrogate model on each low-dimensional subproblem and uses SAEAs to solve subproblems in parallel.At last,the optimal solutions of subproblems are merged into the optimal or near-optimal solution of the original problem.In some problems,there may be a correlation between some decision variables.These correlated decision variables should be divided into a group.However,random grouping ignores the correlation.To compensate for this shortcoming,the process of random grouping performs several times in SAEA-PRG.In addition,three choosing methods,random,distance-,and voting-based methods,are proposed to increase the robustness of the final solution.Experimental results show that SAEA-PRG generally outperforms traditional,ensemble,and evolutionary feature selection methods on 14 datasets with up to 10000 features,especially when the number of real fitness evaluations is limited.(2)For high-dimensional ECOP sequences,this dissertation proposes an input reductionbased surrogate-assisted optimization algorithm to solve hypervolume-based environmental selection(HVEA)problems.Compared with feature selection problems,HVEA is a series of on-going high-dimensional ECOPs.Therefore,solving this kind of problem demands high efficiency.The proposed algorithm includes two strategies to improve efficiency: rough filter-based preselection and input reduction-based model construction.A filter is firstly designed according to the rough correspondence relation between hypervolume contribution(HVC)and distance.The filter is employed as a preselection operator to pick up a part of candidate solutions.All subsequent operations of the algorithm are based on these pre-selected solutions,so the filter can improve the search efficiency and avoid unnecessary HVC calculations,making the proposed algorithm more efficient.Then,the proposed algorithm directly take a solution’s objective values and its HVC as the input and output to train a surrogate model.Compared with using the binary-encoded selection strategies or the objective values of all selected solutions as the input,this method is in a low dimension,which is more conducive to rapidly solving HVES tasks.The proposed algorithm is tested on two types of datasets and compared with six state-of-the-art algorithms.Experimental results show that the proposed algorithm performs excellently on most datasets.(3)For noisy single-objective ECOPs,this dissertation discusses which of the two noisetolerant techniques,explicit and implicit averaging,is more suitable for embedding into SAEAs and proposes an averaging-based multi-fidelity denoising method.The quality and quantity of training data are two crucial factors affecting surrogate models’ accuracy,especially in noisy environments.When the fitness evaluation is noisy,and the number of available evaluations is limited,implicit averaging tends to generate training data with a large quantity and poor quality,while explicit averaging is the opposite.This dissertation chooses the multiple knapsack problem as the test benchmark to discuss the impact of implicit and explicit averaging on SAEAs.Two noise types are considered: additive and multiplicative noise.Experimental results show that SAEAs with explicit averaging achieve the best performance on most problems and not a fixed number of repeated evaluations enables an SAEA with explicit averaging to perform best on all problems.Based on this,this dissertation also proposes an averaging-based multi-fidelity denoising method,which gradually increases the number of repeated evaluations during the optimization process.Experimental results show that the multi-fidelity method is superior to these average methods with a fixed number of evaluations.(4)For noisy multi-objective ECOPs,this dissertation proposes an SAEA with hypervolume triggered fidelity adjustment(EA-HVFA).As the number of independent evaluations increases,the impact of noise decreases.However,it takes a longer time to collect training data.To figure out the conflict between the number of independent evaluations and the time cost of collecting training data,multiple surrogate models with different fidelity levels are constructed instead of a surrogate model with the lowest or highest fidelity level.The fidelity level represents the number of independent evaluations for each training data.In addition,the hypervolume indicator is applied as a trigger to adaptively determine when the fidelity level of surrogate models should be increased.Compared with single-fidelity SAEAs,experimental results show that EA-HVFA achieves competitive performance on most test problems.(5)For noisy bi-level ECOPs,this dissertation proposes an action inheritance-based evolutionary algorithm(AIEA)to solve soft robot design problems.The soft robot design problem is a typical bi-level optimization problem in which the outer loop optimizes morphological structures while the inner loop optimizes the control for a given structure.The outer objective is not only related to a structure but also to the optimization results of the inner loop.With the extensive application of deep reinforcement learning,the significant computational burden imposed by optimizing control has become a major factor affecting the rapid development of robot design.Moreover,the evaluation done by reinforcement learning is always noisy.As soft robot design problems have the characteristics of bi-level optimization and complex control,it is challenging to build accurate data-driven surrogate models.For a real-evaluated robot,its well-trained controller can be abstractly described as the knowledge of how to control the robot to complete a particular task.AIEA uses this knowledge to construct surrogate models.To reuse the knowledge,an action inheritance-based rapid evaluation method is proposed.The process of utilizing a well-trained controller for evaluating candidate designs is referred to action inheritance.In addition,a random perturbation operation is also proposed to estimate the error introduced by action inheritance.Experimental results show that AIEA is better than the other three state-of-the-art algorithms on most tasks when only a limited computational budget is available.Compared with the algorithm without surrogate models,AIEA saves about half the computing cost.