The Research For Rectangular Packing Problem Of Combination Of Ant Colony Algorithm And Genetic Algorithm

Rectangluar packing means to arrange rectangluar parts of different size or same size at a given rectangular plate with the optimal way.Rectangluar packing problem is commonly faced in engineering field,such as sheet metal cutting,machining of glass, shipbuilding,manufacturing of automobiles,clothing,furniture manufacturing and so on. With a better packing pattern,the material can be saved obviously,and the production cost can be reduced,and economic benefits can be increased.Rectangluar packing problem is a combinatorial optimization problem and belongs to the NP comlete problems with the most complexity in theory. The optimal solution is hard to obtain precisely by the current calculation theory and method,and only can obtain the approximation in certain time limit. Heuristic intelligent optimization methods is a very active research fields in recent years,such as genetic algorithm, simulated annealing algorithm, ant colony algorithm, neural networks, particle swarm algorithm,etc,which can effectively solve the combinatorial optimization problem and the NP problem.To solve the rectangular packing problem, a hybrid algorithm which is based on the combination of ant colony algorithm and genetic algorithm is proposed in this paper. Considering the advantages and drawbacks of ant colony algorithm and genetic algorithm, firstly we obtain the distribution of pheromone by making full use of the advantages of rapid randomness and global convergence of genetic algorithm, and then obtain the optimal packing sequence by employing the advantages of positive feedback mechanism and efficient convergence of ant colony algorithm.Besides,the mathematical model of rectangular packing problem is established in this paper. On the basis of analysing mainly algorithms for rectangular packing problem,an improved algorithm is proposed.Considering the effect of length and width of rectangulars to the solution, the improved algorithm adds rotating strategy and improves the searching solution.We solve the rectangular packing problem by combining the improved algorithm with genetic algorithm and hybrid algorithm. The results of examples show that the improved algorithm is much more effective,and the better packing pattern can be produced by the hybrid algorithm.