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

讨论矩形件二维正交排样问题,即将一组已知尺寸的小矩形件正交地排放到一张大矩形板材中,寻找一个排样方式使得板材的利用率最高。将基于随机键值的遗传算法与布局策略相结合,提出一种混合遗传算法。用混合遗传算法确定矩形件的排样序列。按照排样序列,将矩形件按顺序逐个排放至板材中,每次排放矩形件时,在空闲矩形空间集合中选择一个最佳空闲矩形空间来排放当前待排矩形件,沿着该矩形件的上边和右边分别将多余空闲空间划分为两个子空闲空间,将子空闲空间添加至空闲矩形空间集合,按照上述规则继续下一个待排矩形件的布局操作,直至板材无法再排入矩形件为止。采用文献中的基准例题来测试本文算法,并与文献算法进行比较。实验结果表明,本文算法优于两种典型的文献算法。