Research On Solving Method Of Multidimensional Knapsack Problem Based On Random Sampling Preprocessing

The research content of this paper is the multidimensional knapsack problem.The goal of the multidimensional knapsack problem is to find the combination with the largest total value of the selected items while satisfying the constraints of all dimensions.It is an NP-hard combination optimization problem,which is computationally challenging.Widely used in daily life,the problem of multidimensional knapsack is widely present in cargo loading,inventory reduction,project selection,capital budgeting,and solving the allocation problems of processors and databases on distributed computer systems.Therefore,solving the multidimensional knapsack problem has important theoretical guiding significance and practical application value.This paper proposes random sampling preprocessing method to solve the multidimensional knapsack problem.This paper improves the current best quantum particle swarm optimization algorithm for multidimensional knapsack problems.According to the process of random sampling preprocessing,it is estimated whether each item in the multidimensional knapsack problem should be put into the backpack.The disturbance factor obtained by random sampling will be disturbed during the item sorting process and the quantum particle swarm solution updating process.The item sorting process and the quantum particle swarm solution updating process will be processed.The two parts are processed separately and the disturbance factors of the random sampling preprocessing method are different for different parts.The disturbance factors of the random sampling preprocessing are set separately in these two parts.The first part is to disturb the item sorting process.In the item sorting process,this paper no longer chooses the popular item sorting formula and process,but chooses the new disturbance factor proposed in this paper by the random sampling preprocessing process to preprocess the item sorting process.The second part is to perturb the updating process of the quantum particle swarm.The updating process of the quantum particle swarm is to combine the operators obtained by the random sampling preprocessing with the original quantum particle swarm optimization algorithm to form a new perturbation factor.The updating process is to perturb the renewal process of the quantum particle swarm.The improvements of these two parts are important for solving the multidimensional knapsack problem.The experimental benchmark instances are benchmark instances of the multidimensional knapsack problem in OR-Library.The experiment will be tested on this data set.Through the setup and implementation of the experiment and the comparison with the best quantum particle swarm optimization algorithm at present,the results show that the method proposed in this paper can find a better solution faster than the current best quantum particle swarm optimization algorithm in a certain period of time.It has implications for the solution of the multidimensional knapsack problem and the practical application of the multidimensional knapsack problem.It's very important for achieving the purpose of algorithm optimization.