Research On Rectangular Packing Problem Using Genetic Simulated Annealing Algorithm

The packing optimization problem exists extensively in modern industrial production and processing industries,such as steel cutting,fabric clipping,printing and typesetting,and mechanical manufacturing.It is a key link in the process of manufacturing automation from design to cutting.The research of layout optimization problem aims to save the consumption of raw materials,reduce the production cost and improve the economic efficiency of enter-prises by finding a reasonable and effective algorithm.The rectangular packing problem is studied in this paper:On a plate with a fixed width and an unlimited length,a certain number of rectangular pieces are discharged according to a certain strategy in order to make full use of the raw materials.This kind of problem is NP-complete in mathematics and cannot guar-antee optimal solution within a limited computing time.Therefore,how to design an efficient algorithm for rectangular packing problem with high significance and value.This paper proposed an adaptive genetic simulated annealing algorithm.It combined the genetic algorithm and simulated annealing algorithm to determine the discharge order of rec-tangular pieces.And it improved a positioning solution algorithm to determine the placement of rectangular pieces in the plate.The main work of this article is as follows:1.Proposed a lowest horizontal line heuristic search algorithm based on matching degree.The rotation and heuristic judgment are introduced in the process of packing.The rectangular which cannot be discharged into the lowest horizontal line should be rotated and rearranged.If cannot be discharged with the above operations,the main influence factor and the second-ary influence factor in the matching degree function are used to guide the selection of rectan-gular parts from the global optimization in the subsequent sequence of the rectangles which should be arranged.It searched for a rectangle which has the highest matching degree with the lowest horizontal line and discharged it.The improved algorithm can effectively use idle areas and reduce the waste of plates.2.Introduced a dynamic adjustment strategy in the genetic simulated annealing algo-rithm to automatically adjust the crossover and mutation probability according to the current individual fitness value,and dynamically coordinate the speed of convergence and the search ability.At the same time,it used a circular crossover operator.The crossover process sur-rounds the ends of the chromosome,which can ensure the genes selected with equal probabil-ity.All individuals of genetic manipulation are renewed according to the state generating function and calculate the fitness value.If satisfied the acceptance probability,it replaces an old individual with the new one.Otherwise,the cooling operation is performed and the opti-mal individual is updated until the maximum number of iterations is reached,and completed the simulated annealing process.The comparison results of multiple sets of examples show that the adaptive genetic sim-ulated annealing algorithm presented in this paper has a faster solution speed while ensuring the performance.And it can effectively improve the utilization rate of the plate.