Research And Application Of Self-Adaptive Dynamic Multi-Objective Evolutionary Algorithms

Dynamic multi-objective optimization involves the simultaneous optimization of multiple conflicting objectives,and the objectives,constraints or the parameters may change over time,so the optimal solution of dynamic multi-objective optimization problem(DMOP)is uncertain.The characteristic of DMOP changing over time brings great challenges to the design of effective algorithms.How to effectively respond to environmental changes and effectively track the optimal solution in different environments has become a research hotspot in the field of dynamic multi-objective optimization.Although scholars have designed many different types of change response strategies,most of the existing methods are to design a response strategy to deal with different problems,without taking into account the selection of the most appropriate response strategy for different problems to respond to changes in the environment.Therefore,this paper proposes the idea of self-adaptive response strategy,and designs a series of self-adaptive dynamic multi-objective optimization algorithms to deal with DMOPs.At the same time,most researches on dynamic algorithms only involve solving the benchmark problems,so this paper integrates the idea of selfadaptive response strategy into the research of dynamic vehicle route planning,realizing to solve the actual dynamic optimization problem.The main works of this paper are shown as follows:(1)The first is to propose a self-adaptive dynamic multi-objective optimization algorithm based on contribution degree.Firstly,this algorithm designs a self-adaptive response strategy,which integrates several different types of response strategies.It could track the contribution of different response strategies in the historical environments,by adding different labels to the individuals generated by different response strategies.Once a new environmental change occurs,the probability of each response strategy being selected to generate the initial population of the new environment can be determined according to the contribution of each response strategy in the previous environments.The probability of selecting various response strategies in the future can be continuously determined through the early feedback,to realize the self-adaptive selection of different response strategies for different DMOPs.At the same time,the algorithm designs a multi-objective evolutionary algorithm based on objective space decomposition,whose main idea is to evenly divide the objective space into several subspaces,and then find the optimal solution of each subspace to form the optimal solution set of the whole problem.Experiments show that the algorithm could select the most appropriate response strategy for different DMOPs,and can be used to deal with the parameter tuning problem of PID controller in dynamic systems.(2)The second is to propose a self-adaptive dynamic multi-objective optimization algorithm based on change type.The purpose of a DMOA is to find the Pareto optimal set(PS)of each environment.Most of the existing DMOAs do not consider the impact of the type of environmental change on the performance of the algorithm.Hence,we integrate the type of environmental change into the design of response strategy,and propose a self-adaptive dynamic multi-objective optimization algorithm based on change type.Based on the current classification of DMOPs,the change types mainly consist of two categories: the environmental change that causes the PS changes over time or the environmental change that leads to the PS remains unchanged.This algorithm could evaluate whether there is a significant difference between the two PSs of two adjacent environments through Wilcoxon signed rank test,then judge the type of environmental change,and then adaptively select the appropriate response strategy to respond to different types of environmental changes.If PS changes,the algorithm adopts a linear prediction strategy to respond to environmental changes.At the same time,for the type of PS remains unchanged,a dynamic mutation diversity introduction strategy is designed to respond to environmental changes.The experimental results show that the algorithm is of better performance and could solve the parameter-tuning problem of PID controller in dynamic systems.(3)The third is to propose a self-adaptive dynamic multi-objective optimization algorithm based on classification prediction and dynamic mutation.Most of the existing DMOPs only involve a single change type,and the type of environmental change is always consistent in the whole optimization process.Therefore,we design a set of dynamic multi-objective optimization problems with variable and mixed change types.In addition,we propose a selfadaptive dynamic multi-objective optimization algorithm based on classification prediction and dynamic mutation to solve dynamic multi-objective optimization problems with variable change types.Here still regards the change types mainly consist of two classes: the environmental change that causes the PS changes over time or the environmental change that leads to the PS remains unchanged.Firstly,the algorithm judges whether PS changes by judging whether the non-dominated individuals of the current environment are still nondominated in the new environment,and then determines the type of environmental change.Then,the algorithm can adaptively select an appropriate response strategy to respond to environmental changes of different types,according to the type of environmental change.If PS changes,here designs a classification prediction strategy based on the viewpoint of “The rich first pushing those being rich later,eventually together”.The strategy divides the population into non-dominated individuals and dominated individuals,and predicts their position in the new environment respectively,realizing the non-dominated individuals guide the dominated individuals to predict the position of the dominated individuals in the new environment.If PS remains unchanged,the algorithm adopts the dynamic mutation strategy to respond to environmental changes.Experiments show that the algorithm could solve the DMOPs with variable change types and the traditional DMOPs with single change type,and could be utilized to solve the parameter-tuning problem of PID controller in dynamic systems.(4)The fourth is to propose a dynamic multi-objective optimization algorithm based on the classification response of decision variables.Most existing DMOAs do not consider that different decision variables may have different change types or change rates,so they deal with all decision variables in the same way.We propose a dynamic multi-objective optimization algorithm based on the classification response of decision variables,to achieve adopting different response strategies to response to different decision variables,realizing adaptive classification response.Firstly,the algorithm divides the decision variables into diversity variables and convergence variables.The diversity variable response strategy uses Latin hypercube sampling to generate the diversity variables of the new environment.For each-dimensional convergence variable,the convergence variable response strategy first determines whether the central prediction strategy brings positive feedback or negative feedback,and then determines whether this-dimensional convergence variable is predictable.Then,the algorithm adaptively selects suitable strategy to generate this-dimensional convergence variable in the new environment based on the judgment of whether the convergence variable is predictable.The experimental results indicate that the algorithm is of better performance,and is promising to solve the parameter-tuning problem of PID controller in dynamic systems.(5)The fifth is to propose a dynamic adaptive genetic algorithm to solve the dynamic vehicle routing problem.Inspired by the idea of self-adaptive response strategy,we design a dynamic self-adaptive genetic algorithm to solve the capacitated vehicle routing problems.Firstly,here models the static vehicle routing planning problem as a preference bi-objective optimization problem,and designs an adaptive genetic algorithm to solve this problem.It designs an adaptive genetic operator to realize the adaptive adjustment of parameters of genetic operator.At the same time,an adaptive local search operator is designed to automatically adjust the local search model of each individual according to the fitness value of different individuals.Then,combined with the actual background,here considers three different changes that may occur in distribution information of the vehicle routing problem.Meanwhile,inspired by the self-adaptive response strategy,we design a distributioninformation change type-based self-adaptive response strategy,which could judge the change type of distribution information and design different strategies to deal with different types of changes adaptively.The adaptive genetic algorithm combines the distributioninformation change type-based self-adaptive response strategy to generate the dynamic adaptive genetic algorithm,which could realize quickly planning a new route when the distribution information changes.Experiments show that the algorithm could rapidly plan reasonable routes after a single change or a mixed change occurred in the distribution information.(6)The last is to propose a dynamic adaptive genetic algorithm to solve the dynamic vehicle routing problem with time window.Based on the above(5),we design a dynamic adaptive genetic algorithm to handle the dynamic vehicle routing problems with time window.Firstly,here models the static vehicle routing planning with time window as a preference threeobjective optimization problem,and designs an improved adaptive genetic algorithm to solve this problem.It designs a new population initialization method considering time window,which can ensure the feasibility of the initial solution as much as possible.Then,we design an adaptive local search operator considering time window,which can realize the adaptive local adjustment of different individuals.Based on the time window,here considers a new change that may occur in the distribution information,that is,the service time window changes.Combined with the three changes in work(5),here mainly involves four different changes in the distribution information.The distribution-information change type-based self-adaptive response strategy could detect the change type of distribution information,and adaptively adopt different strategies to deal with different types of changes.The improved adaptive genetic algorithm combines the distribution-information change type-based selfadaptive response strategy to generate the dynamic adaptive genetic algorithm,which could realize quickly planning the new route after the distribution information changes.Experiments show that the dynamic adaptive genetic algorithm composed of the improved adaptive genetic algorithm and the distribution-information change type-based self-adaptive response strategy is able to quickly plan the appropriate routes,when a single change or a mixed change occurred in the distribution information of the vehicle routing problem with time window.