Research On Solving Covering Problem And Knapsack Problem Based On Evolutionary Algorithms

The coverage problem and the knapsack problem are two important combinatorial optimization problems,which are widely used in many fields such as investment decision-making,facility location selection,and flexible manufacturing.With the rapid development of today's society,economy and technology,more and more novel and complex coverage problems and backpack problems have emerged.Due to the large scale and high complexity of new coverage problems and knapsack problems,traditional algorithms have the disadvantages of high time complexity and slow convergence when solving these problems,which can no longer meet people's needs.Compared with traditional algorithms,evolutionary algorithms have inherent implicit parallelism and strong global optimization capabilities,and are not restricted by the nature of the problem when solving optimization problems.It provides a new idea for solving complex optimization problems and has become a new effective approach for solving the covering problem and the knapsack problem.This paper mainly studies the use of evolutionary algorithms to solve the covering problem and the knapsack problem.First of all,an effective approach is proposed to solve the budgeted maximum coverage problem by combining the group theory-based optimization algorithm(GTOA)with the repair and optimization method of greedy strategy.Then,a binary particle swarm optimization algorithm based on a new S-shape transfer function is proposed to solve the knapsack problem with single continuous variable(KPC).Finally,the evolution equation of the algorithm GTOA is improved,an improved group theory-based optimization algorithm(IGTOA)is proposed and a new and efficient approach for the KPC and the set union knapsack problem(SUKP)is given by using it.The main research contents are as follows:1.In this paper,a repair and optimization algorithm based on greedy strategy is proposed to deal with the infeasible solution of the budgeted maximum coverage problem,and a new approach to solving the budgeted maximum coverage problem based on the optimization algorithm based on group theory is given.The effectiveness of the new method is verified by comparing with existing algorithms for solving the budget maximumcoverage problem.2.On the basis of the existing transfer function,a new S-shape function is proposed as the transfer function,and a new binary particle swarm optimization algorithm(NBPSO)for solving binary optimization problems is given.The efficiency of the algorithm is verified by solving four kinds of KPC instances,and the advantages and disadvantages of the algorithm are compared with other algorithms.3.In-depth study of the evolution equation of the group theory-based optimization algorithm.Based on the new combination method and simplification strategy,a new evolution equation with simpler realization is proposed.Based on the new evolution equation,an improved group theory-based optimization algorithm(IGTOA)is given.Using the general test cases of the knapsack problem with a single continuous variable and the set union knapsack problem respectively verify the effectiveness of IGTOA.