Solving 0-1 Knapsack Problem Based On Improved Glowworm Swarm Optimization Algorithm

In combinatorial optimization, 0-1 knapsack problem is one of the classic and difficult NP problem. It is a subset of the selection problem. Scholars have used backtracking algorithms, dynamic programming algorithm, and a variety of swarm intelligence optimization algorithm to solve it. However, there occurred some issues,such as too slow convergence, high complexity of time and space.Glowworm Swarm Optimization(GSO) is a new swarm intelligence and stochastic optimization, which proposed by Krishnanand. It maintains a strong versatility. This article will applied Glowworm Swarm Optimization to solve 0-1knapsack problem. In addition, it will compare with the dynamic normalization method. The theoretical basis, the principle and implementation methods of Glowworm Swarm Optimization for have been described in details. Additionally, it analyze the advantages and disadvantages of its existence, As a result, artificial Glowworm Swarm Optimization has advantage that to capture in efficiency, on the other hand, easy to fall into local optimum, and low accurate solution are drawbacks.On this basis, the Glowworm Swarm Optimization is improved in two algorithms to increase capabilities of optimization. The first is the normalization process for the too small attract of the beginning Glowworm Swarm Optimization: in the traditional Glowworm Swarm Optimization, as the distance is too large of the beginning Glowworm Swarm Optimization, that the attractiveness tends to zero. The introduction of the normalization process, uniform provisions of the fireflies distance.Followed is the improvement of the later iterations for Glowworm Swarm Optimization. As the position of the fireflies becomes smaller, that unable to locate the best position. The introduction of linear decreasing inertia weight, improving the ability of optimize for Glowworm Swarm Optimization.As mentioned, there are some shortcomings, this paper have been improved on basic Glowworm Swarm Optimization in pre attractiveness and later iteration. Then,it applied to 0-1 knapsack problem and some continuous function. Simulation results show that the improved algorithm firefly guarantee fast convergence rate, and balance the global search algorithm and local search capabilities. It demonstrates that fireflyalgorithm in continuous space and discrete space optimization of the feasibility and effectiveness. Therefore, it has a good prospect.