Relational Model Based Expensive Evolutionary Optimization Algorithms

Expensive optimization problems(EOPs)are a typical class of optimization problems that widely exist in academic research and industrial applications.These problems have two distinctive features.One is that there is no closed-form representation of the objective function,and the other is that each function(fitness)evaluation is expensive.Therefore,neither gradient-based optimization nor gradient-free heuristic search can solve the above problems.Surrogate-assisted evolutionary algorithms(SAEAs)combine the weak assumptions of problems in evolutionary algorithms and the cheap evaluation consumption of using surrogate models.It has become one of the mainstream methods for solving expensive optimization problems.The key to SAEAs lies in constructing a reliable surrogate model.Traditional surrogate models are trained based on the single solution feature.In order to further improve the quality of the surrogate model,this thesis focuses on the ’comparison’ relationship,which is natural in evolutionary algorithms.We propose an idea for constructing surrogate models based on data relationships.Systematic studies are carried out on two typical scientific problems,single-and multi-objective expensive optimization problems,centering on data preparation,model training,and model usage.Moreover,a series of relation model-assisted evolutionary algorithms are proposed to solve EOPs.The main work of this thesis includes:1.Relation Model Based Pre-selection Strategy for EAs.This thesis proposed a kind of surrogate model construction method of comparison relationship in EAs,named the relation model,and applied this idea in EAs for solving single-and multi-optimization problems.Pre-selection strategies,simple and general evolutionary frameworks,are used for studying the performance of relation models.The relation model construction is divided into training data,surrogate model,and model usage.Each pair of solutions in the population forms a relation pair,and its label is determined by the objective values of the two solutions;A series of machine learning methods are used to learn the relationship of the pairs;in the model usage stage,the relationship between a pair of candidate solutions is estimated by the surrogate model.Tournaments selection and approximate dominance selection strategies are used to preselect single-and multi-objective problems.The experimental results suggest that RCPS outperforms other regression and classification based pre-selection methods.2.Relation Model Assisted Evolution Algorithms for Expensive Optimization Problems.Good performance of RCPS in Pre-selection strategies demonstrates that reliable surrogate models can be constructed using the relationship between solutions.However,the number of fitness evaluations in each generation is not significantly reduced due to the limitations of the pre-selection strategy,thus hindering the use of the relation model in EOPs with limited computation budget.In order to effectively solve EOPs,more efficient relational models and search algorithm will be designed from data preparation and model usage.Specifically,two data construction methods are proposed in the data preparation stage with consideration of data characteristics.In the model usage stage,’voting-scoring’strategies are proposed,which combine multiple prediction results to overcome the model errors.In addition,an adaptive data partitioning strategy is designed for multi-objective optimization problems,considering convergence and diversity during the search process.Based on the above work,the relation model assisted evolution algorithms,called RESO and REMO,are proposed for EOPs.These algorithms show promising results in both benchmark problems and real-world applications.3.Convolutional Relation Model-Assisted Multi-objective Evolutionary Algorithm for Continuous and Combinatorial Problems.Currently,the research on EOPs mainly focuses on continuous problems.On the contrary,combinatorial problems exist more widely in real-world applications.However,there are very few SAEAs suitable for such problems.Therefore,it is crucial to generalize relational models to expensive combinatorial optimization problems.We propose a convolution model assisted version of REMO named CREMO.A sample representation method of relation matrix is proposed in the data preparation.The convolution kernel is used in the model training to extract the features.Experimental results show that the relational model can solve continuous and combinatorial optimization problems.This method enriches the research content and improves the solving ability of SAEAs on combinatorial expensive optimization problems.