Researches And Designs On Evolutionary Algorithms Based On Cooperative Decomposition And Dominance For Many-objective Knapsack Problems

The multi-objective knapsack problem is an abstraction of limited resource competition problems,such as portfolio,project selection,cargo loading,etc.It has a broad engineering background and has been a difficult and hot spot in the field of scientific and engineering re-search.When the number of knapsacks is greater than or equal to 4,the multi-objective knap-sack problem is also called the many-objective knapsack problem.Existing multi-objective evolutionary algorithms have encountered a series of challenges when solving complex many-objective knapsack problems.With the increase of the number of knapsacks,the Pareto dominance-based evolutionary algorithm is prone to lose the selection pressure for generating a solution close to the Pareto front,and the hypervolume-based algorithm will increase sharply in running time and become less feasible.In contrast,the decomposition-based evolutionary algorithm is computationally efficient and its effectiveness has been verified in solving these problems.However,the decomposition-based evolutionary algorithm still has shortcomings.In the process of evolution,it is easy to keep redundant individuals,and there is a phenomenon that individuals and subproblems do not match,which eventually leads to the degradation of population diversity and convergence.Besides,almost all existing multi-objective evolution al-gorithms generate new individuals based on the recombination operation of crossover mutation,which makes the algorithm stochastic.To effectively solve the many-objective knapsack problem,this paper will propose a decomposition-dominance collaboration mechanism that is on the basis of the original MOEA/D and design a decomposition-dominance collaboration evolutionary algorithm based on the cross mutation to initially improve the algorithm's performance.Based on this,the recombina-tion operation of cross mutation was replaced by the recombination operation of neuroevolution,and a decomposition-dominance collaboration evolution algorithm based on neuroevolution was designed to further improve the performance of the algorithm.The main research work in this paper is summarized as follows:1)A decomposition-dominance collaboration mechanism is proposed,which is divided into the dominance-based archive's generation and update,the decomposition-based popula-tion's repair,and the merge of archive and population.The dominance-based archive is generated mainly by the decomposition-based population.In the stage of the archive's up-date,it aims to select elite individuals.The decomposition-based population's repair is to evolve the population relying on the elite individuals of the archive.Finally,in the stage of the merge of archive and population,the elite individuals in the population and the archive are screened to obtain the optimal population.2)Aiming at the shortcomings of the original MOEA/ D,based on the decomposition-dominance collaboration mechanism,a decomposition-dominance collaboration evolution-ary algorithm based on cross mutation is designed.The algorithm can solve the problem of redundant individuals in MOEA/D,and the problem that the individual does not match the subproblem.So,it can avoid degradation of population convergence and diversity and improve the quality of the solution set.3)On the basis of the decomposition-dominance collaboration evolutionary algorithm based on cross mutation,a decomposition-dominance collaboration evolutionary algorithm based on neuroevolution was designed by adding the idea of neuroevolution.In the initialization phase of the population,each individual will uniquely bind to a neural network model.During the recombination phase,the parameters of the individual's neural network model corresponding to the current subproblem are updated,and the output of the neural network is a new individual.As the neural network can learn,the learning ability is gradually enhanced in the process of evolution.Thus,it further improves the solution set quality obtained by the decomposition-dominance collaboration evolutionary algorithm.4)The effectiveness of the decomposition-dominance collaboration evolutionary algorithm designed in this paper is tested on three many-objective knapsack test cases of random type,correlation type and dependent type.First,several excellent multi-objective evolutionary algorithms are used as a comparison to verify the preliminary effects of the decomposition-dominance collaboration evolutionary algorithm based on cross mutation,and then the decomposition-dominance collaboration evolutionary algorithm designed by the idea of neuroevolution is added to further verify the algorithm's effect.The experimental results on three many-objective knapsack test cases show that the decomposition-dominance collaboration evolutionary algorithm based on cross mutation de-signed in this paper can improve the performance of the original MOEA/D.Further design of the decomposition-dominance collaboration evolutionary algorithm based on neuroevolution can achieve better experimental results and perfectly solves the problem of complex many-objective knapsack problems.