Improved Particle Swarm Optimization Algorithm For Industrial Cutting-Stock Problem

This paper mainly introduces the development process of the particle swarm optimization algorithm and genetic algorithm as well as the research status at home and abroad, also the principles of the algorithms and some improved models; Then we discuss the background of industrial cutting-stock problem to which this paper will mainly solve. We focus on the research of the one-dimensional cutting-stock problem and the rectangle packing problem.And We solve the above two problems with the proposed improved particle swarm optimization algorithm in this paper. Finally, experimental results show the algorithm in solving the issue of industrial cutting-stock effectiveness.PSO is a successful application and development of evolutionary computing technology in the field of intelligent computing. The main idea comes from the field of bionics. The group reflects a high degree of intelligence through individual collaboration and information sharing with each other. Inspired by the behavior of birds foraging,_combination of human behavior and cognitive style, Kennedy and Eberhart proposed PSO algorithm in 1995. During the algorithm execution, each particle continuously adjusts its speed and direction of movement, searching for optimal solution by iteration in the solution space. The basis for the adjustment is based on the information the particle obtained by itself and other particles. As easy to operate, less parameters and high efficiency, PSO have been widely used not only in computing field but also in the engineering field.Genetic algorithm is also an intelligent optimization algorithm combining swarm intelligence theory and evolution technology. It is proposed by American Professor Holland.J.H in 1975. After the scholars studied and improved the algorithm for decades,_algorithm theory is more mature than before. The algorithm is a parallel global search technique which is based on the objective law of natural survival of the fittest and according evolutionary theory and the mutation theory as a guide. The main work process is to preserve excellent genes of generation to the genes of the offspring through selection, crossover and mutation of several processes. The algorithm seeks optimum solutions through the iterative evolution. Industrial cutting stock problem is the issue that split the same shape of the raw materials into several parts with different specifications, achieving maximum utilization of raw materials requirements. According to the dimension, industrial cutting-stock problem can be classified into one-dimensional cutting problem, rectangle packing problem, three-dimensional and multi-dimensional layout problems.The one-dimensional cutting stock problem and rectangle packing problem are important branches of industrial cutting stock problem. According to the theory of computing complexity, these two problems have been proved to be a NP-complete problem. It is difficult to find the exact global optimal solution for such problems because of the high complexity of computation.This paper converts the one-dimensional cutting stock problem and rectangle packing problem into combinatorial optimization problem in discrete domain by building mathematical models for them, an improved particle swarm optimization algorithm is proposed in this paper.The algorithm bases on discrete particle swarm optimization, combining the idea of mutation and crossover in genetic algorithm to update particle.This method breakthroughs the limit of the velocity model of the standard particle swarm optimization algorithm and solves the problem of difficult to describe the update particles in the standard particle swarm optimization algorithm for combinatorial optimization problem.]t can also ensure the continuity and stability of the exchange of information. An improved search strategy is proposed to accelerate convergence rate and formation of coding scheme.The experimental data show that the proposed algorithm is effective and robust in solving the problem of one-dimensional cutting and rectangular packing. The algorithm has good performance and broad industrial application foreground in solving industrial cutting-stock issue.