An Orthogonal Genetic Algorithm With Multi-pointi Mult-parent Crossover For Knapsack Problem

The backpack problem not only has important theoretical research value,but also has important economic benefits in practical problems.The knapsack problem has important applications in system processing and database allocation,resource allocation,and investment decision-making in the industrial and financial fields.The research and optimization of the knapsack problem has gradually become an important factor closely related to corporate efficiency.From the perspective of practical problems,this paper proposes a combination of evolutionary strategies and genetic algorithms for the 0-1 knapsack problem,and is committed to improving the quality of solving combinatorial optimization problems and the efficiency of optimization algorithms.According to the inherent characteristics of the knapsack problem and the analysis of the operation mechanism of the genetic algorithm,this paper proposes a multi-point multi-parent crossover operation(MP2X),and uses orthogonal experimental design methods to optimize and improve the crossover operator.The purpose of implementing the orthogonal experiment design method for MP2X crossover operation is to make full use of the inherent information of several genes from multiple chromosome individuals.Based on the method of multi-parent multi-point crossover(MP2X)operation and orthogonal design,a genetic algorithm variant multi-parent multi-point orthogonal genetic algorithm(MPXOGA)is proposed.At the same time,the elite retention strategy is adopted,which not only continues the optimal performance of the parent sample,but also the optimal performance offspring evolved by the genetic mutation algorithm can be saved,and the next generation of poorly adaptable offspring individuals is eliminated.Continuing the performance of the parent sample with excellent performance can allowing it to evolve with the chromosome contract of the current generation,greatly enriching the outstanding characteristics of the offspring of the population,speeding up the population to converge,and ensuring the optimality and diversity of chromosomes in the newborn population.Elite retention strategy not only reduces the average number of iterations for which the genetic algorithm obtains the optimal solution,but also shortens the overall solution time,which is conducive to optimizing the performance of the genetic algorithm in solving the knapsack problem.Based on the analysis of the knapsack problem and the unique model characteristics of the corresponding problem,this paper optimizes and improves part of the operator process in the genetic algorithm.For the correction part of the solution,the greedy algorithm is introduced into the genetic algorithm.Use two correction strategies TX10 and TX01 to make reasonable modifications or updates to the current search path,and construct a contract combination optimization model to obtain a practical solution that meets practical constraints and has the best fitness at the same time.It can reach a better promotion and optimization.By adopting a modified strategy to optimize the algorithm's solution operation,the operation maintenance of the genetic algorithm is guaranteed,and the purpose of seeking path diversity is achieved.The simulation results on the classic backpack example show that the performance of MPXOGA is better than hybrid genetic algorithm(HGA),greedy genetic algorithm(GGA),greedy binary particle swarm optimization(GBPSOA),and greedy PSO(VGPSO).MPXOGA optimizes and finds the best solution in solving the backpack problem,which improves the efficiency and robustness of the algorithm.