Research On Theory And Algorithms In Multi-Objective Evolutionary Learning

In many machine learning tasks,there are usually more than one objective to be optimized,which may be conflicting.Thus,how to solve multi-objective optimization effectively is an important research direction in machine learning.Recently,multi?objective evolutionary algorithms(MOEAs)have been applied in machine learning.However,due to the weak theoretical foundation of evolutionary algorithms,the devel-opment of multi-objective evolutionary learning has been hindered greatly.This disser-tation tries to build the theoretical foundation of multi-objective evolutionary learning.Particularly,three important theoretical issues are studied,and according to the the-oretical analysis,effective methods for two typical multi-objective tasks in machine learning are proposed.The main results are summarized as follows.1.A theoretical analysis method for the constrained optimization performance of MOEAs is proposed,which is then applied on P and NP-hard problems.Previous theoretical studies mainly focused on unconstrained optimization,while optimization tasks usually come with constraints.Through disclosing that MOEAs can follow greedy algorithms,we propose a theoretical analysis method for the constrained optimization performance.Using this method,we show the superior performance of MOEAs on typical P and NP-hard problems.2.A theoretical analysis method for the effectiveness of crossover is proposed,which is then applied on P and NP-hard problems.Previous theoretical stud-ies mainly focused on mutation operators,while practical MOEAs usually em-ploy crossover operators.Through comparing the performance of MOEAs with crossover or not,we propose a theoretical analysis method for the effectiveness of crossover.Using this method,we show the superior performance of using crossover on typical P and NP-hard problems.3.A theoretical analysis method for the optimization performance of MOEAs under noise is proposed,which is then applied on EA-easy and EA-hard prob-lems.Previous theoretical studies mainly focused on clean environments,while op-timization tasks usually come with noise.Through modeling MOEAs by Markov chains,we propose a theoretical analysis method for the optimization performance under noise.Using this method,we show that MOEAs can always find an optimal solution within polynomial time on typical EA-easy and EA-hard problems.4.A new MOEA-based ensemble pruning method PEP is proposed.Ensemble pruning is to optimize the generalization performance,and meanwhile minimize the number of selected learners.According to the theoretical analysis of multi-objective evolutionary learning,we propose a MOEA-based ensemble pruning method PEP.Theoretical analysis and empirical study show the effectiveness of PEP.5.A new MOEA-based subset selection method POSS is proposed.Subset se-lection is to optimize the given objective,and meanwhile minimize the number of selected variables.According to the theoretical analysis of multi-objective evo-lutionary learning,we propose a MOEA-based ensemble pruning method POSS.Theoretical analysis and empirical study show the effectiveness of POSS.