The Research On Rectangular Packing Problem Based On Genetic Algorithm

The rectangle packing problem has high application value,it is widely exists in today's production industry,such as sheet metal processing,glass cutting,electronic equipment processing,mechanical equipment processing,furniture and wood cutting,printing industry layout,garment cloth cutting,etc.The research of the packing problem aims to provide a reasonable cutting plan,so as to save materials,reduce production costs and improve the competitiveness of enter:prises.In this paper,we research on such a rectangular packing problem:rectangular parts with a limited size and quantity are put on a limited width and unlimited length of rectangular plate.The genetic algorithm is used to solve the rectangular packing problem as the sequencing algorithm,combined with the lowest horizontal line algorithm as the positioning algorithm.The sequencing algorithm is used to optimize the order of the rectangular parts' placing sequence.The positioning algorithm is used to place rectangular parts according to their orders by specific placing rules,and obtain the results of the layout.The improved genetic algorithm is used to enhance the performance of the algorithm and obtain higher material utilization.Based on genetic algorithm for rectangular packing problem,The main work of this paper is as follows:1.To solve the problem of low utilization of material caused by premature convergence of basic genetic algorithm.A hierarchical evolutionary model is proposed to replace the roulette strategy.The individuals in the population are classified according to their adaptability and then evolved according to the hierarchy.And the genetic algorithm is redesigned to make it suitable for rectangular packing problem:(1)put forward the mode detection strategy,which is used to generate the initial population to ensure that all genes are included.(2)genetic manipulations are performed using elitist retention strategy,circular-based crossover method,exchange mutation method and rotational mutation method.The experiment is used to compare the simple genetic algorithm with the hierarchical evolutionary model genetic algorithm.(All of the algorithms use the lowest horizontal line algorithm as a rectangular positioning algorithm).The experiment's results show that the hierarchical evolutionary model genetic algorithm is superior to the simple genetic algorithm.2.To solve the problem of slow convergence speed of hierarchical evolutionary model genetic algorithm,a hierarchical evolutionary model of adaptive genetic algorithm is proposed.According to the update of the population's optimal individual,the selection operator and crossover operator are dynamically changed,and the convergence speed and search ability are coordinated.The algorithm can improve the convergence speed of the algorithm.The experimental results show that the hierarchical evolutionary model of adaptive genetic algorithm can improves the convergence speed of the algorithm.In the same iteration algebra,the hierarchical evolutionary model of adaptive genetic algorithm can obtain higher material utilization.The rectangular packing algorithm which is combined with the hierarchical evolutionary model of adaptive genetic algorithm and the lowest horizontal line positioning algorithm,can obtain higher material utilization than the reference paper.