Research On Layout Of Rectangular Parts Based On Genetic Algorithm And Ant Algorithm

The optimal layout of rectangular means arraying as many parts as possible on the given plate, in order to improve the utilization ratio of the plate. A good solution can decrease the cost of production obviously, improve the competition, so many manufactures pay more and more attention to the optimal layout. The layout of rectangular is the basement of two-dimensionality layout, so the research in layout of rectangular is significant on the theory research and valuable on application.Packing problem can solve the problem about both efficiency and quality from the source, it is concerned with geometry, computer graphics, operational, and logical reasoning. It belongs to Nondeterministic Polynomial Complete (NPC) problem with the highest complexity. So far, there are many scholars have proposed various methods, such as genetic algorithm, ant algorithm, simulated annealing and so on. By comparing the advantages and disadvantages about the genetic algorithm and ant algorithm, this article proposes genetic-ant algorithm.Taking into account the large scale rectangular often encounters in the problem of generating chromosomes and race randomly, made improvement on genetic encoding and initial race, given treatment before the program, and received good results.For crossover operator, propose a new crossover operator, diversifying the crossover operator, guaranteeing the diversification of the race, preventing the precocious phenomenon effectively.On dealing with practical problem, parameter setting, always ant algorithm only took the area facet into account, but this article combined the two facets, dynamically generate expected heuristic factor, and give a relatively reasonable weight, optimizing the algorithm.Finally, give two examples to prove the effectiveness and practicality of this algorithm.