Research On Knapsack Problem Based On MOA Algorithm

Knapsack problem, there is a widely application in our life, such as resource allocation, budget control, project selection, the shipment of goods, investment decisions.Deformation of the knapsack problem is often used in commercial, combinatorial mathematics, computing complexity theory, cryptography and applied mathematics and other fields. As for the complicated problem which is combined by some simple problems, there is an important effect to solve the complicated problem by deep exploring the easy problem. For these years, there are some new mixed algorithms, which are combined by several algorithms, and they have a good effect. Because the dimension of knapsack problem algorithm is higher and higher, we’ll face a great challenge of the algorithm of these mixed algorithms. The MOA algorithm is designed to make full use of modern computer memory to store the information in the search process, to share information and improve the efficiency of the search algorithm. The MOA algorithm is combined with modern computer,which provides a new method for the optimization problem, because the MOA algorithm is simple, low computational complexity and it can be widely used in the practical engineering problems, so there is an important significance of this study.Firstly, the main work of this paper is in-depth study of the principle of MOA algorithm thought, analyzes the core elements of the composition structure of MOA algorithm, and the structure of commonly used.operating table data structure, then gives the basic process of MOA algorithm. Secondly, in order to prove the availability of MOA algorithm in the knapsack problem, and prove there will be a difference when solve knapsack problem with the different dimensions by using MOA algorithm and other intelligent algorithms. This paper applies the MOA algorithm in the0/1knapsack problem, there are five sets of different dimension, which compared with the particle swarm algorithm and genetic algorithm in the optimization results of0/1knapsack problem. Thirdly, designing and realizing the experimental platform for algorithm evaluation and performance of different optimization problems from software introduction, use introduction and supplication to introduce the platform in detail. Fourth, in the test platform, MOA algorithm is applied to the multiple knapsack problem, compared seven kinds of intelligent algorithm to set different radius of the MOA algorithm and the particle swarm optimization algorithm, genetic algorithm etc.The main structure of this essay is as follow: the first chapter is Introduction, which describes the background and significance of this essay, research situation, the present situation of MOA algorithm, and the main work and structure.The second chapter is basic theory. This essay gives a brief concept of knapsack problem, some methods of solving knapsack problem, and the advantages and disadvantages of these methods. Then, it introduces the principle of MOA algorithm at full lengths, the construction and operation of the table structure in the MOA algorithm, and briefly discusses some characteristic of the algorithm.The third chapter is the realization of0/1knapsack problem in the MOA algorithm. This chapter, firstly, introduces the coding method when solving the knapsack problem, and select the radius in MOA algorithm, then, introduces MOA algorithm in the realization of the process of solving knapsack problem, finally, compares and analyzes the best method which comes from the optimal MOA algorithm and particle swarm algorithm and genetic algorithm in the five groups of experimental data.The fourth chapter introduces the experimental platform for optimal performance evaluation from Software introduction, introduction and application case to explain. The fifth chapter introduces the realization of MOA algorithm in the multiple knapsack problems. This chapter introduces the concept of gray code, code method, and method of selecting of the radius, then describes the process of the MOA algorithm to realize the multiple knapsack problem on the experimental platform for optimal performance evaluation. The sixth chapter is a summary for the whole essay, and states the author’s further program for MOA algorithm to realize knapsack problem.The conclusion of this easy is as below: the experiment result of solving0/1knapsack problem firstly prove the effectiveness when we use MOA algorithm to solve knapsack problem; the compared experiment prove that optimal performance of MOA algorithm is better than PSO and GA. the result of solving multiple knapsack problem shows that it’s not the best optimization ability of MOA algorithm, but it can verify the feasibility of the MOA algorithm in the multiple knapsack problem, and verify the1/10MOA algorithm for the total number of items in the radius is the best, but with the increase of the radius or the decrease of the MOA algorithm, the optimization performance will gradually weaken...