Application Of Ordinal Prediction Methods In Evolutionary Algorithms

The surrogate-assisted evolutionary algorithm is the mainstream method for solving expensive optimization problems.It establishes a surrogate model for the fitness function of the candidate solutions,and replaces the expensive evaluation of the fitness function with the output of the surrogate model,thereby reducing the computational cost of fitness evaluation.However,the prediction quality of the existing surrogate model methods depends on the type and modeling precision of the selected model,and the generalization performance of the built model is poor when the prior knowledge of the optimization problem is lacking.In order to reduce the dependence of modeling on prior knowledge and the precision requirements of surrogate models,this thesis studies the ordinal prediction method for evaluating the relationship between candidate solutions and its application in evolutionary algorithms.(1)An order evaluation method is proposed to represent the relationship between the pros and cons of candidate solutions,and studies different implementation techniques of ordinal prediction.The comparative prediction experiments on the pros and cons of candidate solutions show that for high-dimensional,multimodal optimization problems,ordinal prediction has better generalization than traditional surrogate model methods.(2)Given l original samples,an ordered sample set of the order of O(l~2)can be constructed.Compared to training a traditional surrogate model on the original sample set,the learning cost of training an ordinal predictor on an ordinal sample set increases significantly.In view of the reflexive and transitive properties of ordinal samples,an ordinal sample set reduction algorithm that can significantly reduce redundancy is proposed to improve the training efficiency of the ordinal predictor.(3)Aiming at the problem of function optimization,the integration technology of ordinal prediction method and genetic algorithm is studied,using the predicted order to guide the selection operation of genetic algorithm.Simulation optimization experiments show that the order prediction-assisted genetic algorithm can effectively reduce the number of real evaluations of individual fitness.(4)Using ordinal prediction methods for optimization of multi-objective 0/1 knapsack problems.An ensemble evolutionary algorithm assisted by ordinal prediction based on NSGA-Ⅱframework is implemented.The optimization experiment shows that compared with the representative random forest assisted evolution algorithm,the order prediction-assisted evolution algorithm has stronger search ability,less real evaluation times and shorter search time.(5)Aiming at the problem of expensive multi-objective interval optimization,the order prediction method of the relationship between the advantages and disadvantages of interval numbers is studied,the interval optimization algorithm integrating order prediction and NSGA-Ⅱis realized,and the strategy of screening the same order solution by using the possibility degree of prediction interval is designed.The optimization experiments show that the order prediction-assisted interval optimization algorithms has stronger search ability for the Pareto optimal solutions.