Research On Key Techniques Of Knapsack Problem On Heterogeneous Platform

Many aspects of human's life are seriously influenced by decision results,therefore,research on methods which affect decision process is critical.Normally,numerical values are designed to denote any decision,thus it would be easier to compare solutions quantitatively.Decision results can be represented as cost,profits,loss,etc.The comparision of these results decides which solution is better.Simplest formulation of decision questions is to choose a feasible soluteon from a binary variable,which can be formulated as a quantateive model where a binary value x is included.If x=1 then the first solution is selected otherwise the second one.There are many instances can be represented as a quantative model,such as resource scheduling in cloud computing,cargo loading,Merkle-Hellman knapsack encryption algorithm,and so forth.All these problems can be abstracted as knapsack problem,thus it's crucial to efficiently solve knapsack problems as binary decision problem.For the knapsack problem,this paper mainly studies the intelligence algorithms on heterogeneous platforms,and the main work is elaborated as follows:First of all,this study proposed greedy frog leaping algorithm for knapsack problem.Compared to traditional shuffled frog leaping algorithm,greedy frog leaping algorithm outperforms based on two aspects.The first optimization is the population's global search process.The original shuffled frog leaping algorithm update the global best solution after all memplex evolution,while greedy frog leaping algorithm in this paper updates the global best solution in time after each memtic group's evolution;and the second optimization is the repair operation to prevent knapsack's overflow.Optimized algorithm further expands solutions' search space and accelerates algorithm's convergence.Experiments show that frog leaping algorithm outperforms traditional swarm intelligent algorithms and on different datasets profits improved 5.81%,2.42%,6.35% respectively.Secondly,this paper designs a hybrid algorithm named NNS(Neural Network Swarm)which combines neural network algorithm and the core idea of swarm intelligence algorithm.NNS firstly generates feasible solutions for knapsack problem by employing neural network algorithm,and then initial solution of swarm population is generated from the feasible solutions by NNS.Next global search process continues.After specified iterations,the best solutions are output.Compared with the original neural network algorithm,NNS improved 6.89%,27.73%,16.14%,13.25%,3.57%,14.18%.Finally,based on heterogeneous platform,optimized neural network swarm algorithm is accelerated.Considering that neural network swarm algorithm owns more computation operation and GPU has many cores to support parallel computing.Compared with NNS which only uses CPU as computing resource,heterogeneous neural network swarm algorithm always spent the least time,with performance inproved 47.62%,73.81%,210.87%,212.28%,472.58%,except for the instance with 10 items.Experimental results show that,greedy frog leaping algorithm outperforms the traditional swarm intelligence algorithms and can obtain the equivalent results as exact algorithms.In addition,neural network algorithm also obtains better results.Furthermore,accelerated neural network algorithm on heterogeneous platform owns faster computing speed,which indicates that optimized algorithms in this paper are efficient and feasible for knapsack problem.