矩形件二维正交排样的一种混合遗传算法  

A hybrid genetic algorithm on two-dimensional orthogonal layout for rectangular parts

作　　者：唐伟萍[1] 王坤[2] 黄欣 Tang Weiping;Wang Kun;Huang Xin(Department of Automotive and Traffic Engineering,Guangxi Electric Polytechnic Institute,Nanning 530007,China;Department of Information Engineering,Sichuan Institute of Information Technology,Guangyuan 628017,China;Department of Information and Electromechanical Engineering,Guangxi Agriculture Vocational and Technical University,Nanning 530007,China)

机构地区：[1]广西电力职业技术学院汽车与交通工程学院,广西南宁530007 [2]四川信息职业技术学院信息工程系,四川广元628017 [3]广西农业职业技术大学信息与机电工程系,广西南宁530007

出　　处：《锻压技术》2021年第10期106-111,共6页Forging & Stamping Technology

基　　金：广西2020年度中青年教师基础能力提升项目(2020KY41016);广西农业职业技术大学2021年科学研究与技术开发计划课题(YKJ2124)。

摘　　要：讨论矩形件二维正交排样问题,即将一组已知尺寸的小矩形件正交地排放到一张大矩形板材中,寻找一个排样方式使得板材的利用率最高。将基于随机键值的遗传算法与布局策略相结合,提出一种混合遗传算法。用混合遗传算法确定矩形件的排样序列。按照排样序列,将矩形件按顺序逐个排放至板材中,每次排放矩形件时,在空闲矩形空间集合中选择一个最佳空闲矩形空间来排放当前待排矩形件,沿着该矩形件的上边和右边分别将多余空闲空间划分为两个子空闲空间,将子空闲空间添加至空闲矩形空间集合,按照上述规则继续下一个待排矩形件的布局操作,直至板材无法再排入矩形件为止。采用文献中的基准例题来测试本文算法,并与文献算法进行比较。实验结果表明,本文算法优于两种典型的文献算法。The two-dimensional orthogonal layout problem of rectangular parts was discussed,namely,a group of small rectangular parts with known sizes were orthogonally arranged into a large rectangular plate,and a layout method was found to maximize the utilization rate of plate.A hybrid genetic algorithm was proposed by combining the genetic algorithm based on random key values with the layout strategy.Then,the layout sequence of rectangular parts was determined by hybrid genetic algorithm.According to the layout sequence,the rectangular parts were arranged into the plate one by one.When each time the rectangular parts were arranged,a best free rectangular space was selected from the set of free rectangular space to layout the current rectangular parts to be arranged,and the extra free space was divided into two sub-free spaces along the upper and right sides of the rectangular part.Furthermore,the sub-free space was added to the set of free rectangular space,and the layout operation of the next rectangular part to be arranged was continued according to the above rules until the plate could no longer be arranged into the rectangular part.Finally,the algorithm was tested by benchmark examples in the literature and compared with the literature algorithm.Experimental results show that this algorithm is better than two typical literature algorithms.

关 键 词：正交排样问题 布局策略 遗传算法 板材 矩形件 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]