锻压技术

二维矩形件排样问题的自适应多岛遗传算法优化

英文标题：Adaptive multi-island genetic algorithm optimization on layout problem for 2D rectangular parts

作者：曾晓亮吴琼袁旭华

分类号：TP391

出版年,卷(期):页码：2020,45(12):53-58

摘要：

为了提高二维矩形件排样问题的板材利用率、降低生产成本，提出了基于自适应多岛遗传算法的排样优化方法。使用六元数组对矩形件进行表征，以板材利用率最大为优化目标，建立了排样问题的带约束优化模型。以多岛遗传算法为基础，引入了交叉概率和变异概率的自适应调整方法，从而提出了自适应多岛遗传算法；针对排样问题的特殊性，对遗传算子进行适应性设计，提出了环形交叉方法和交换变异策略，保证了执行遗传算子前、后的矩形规模不变；提出了最低水平线启发式算法的基因解码方法。使用规模为30和59的两组矩形件排样实验进行验证，结果表明：与分布估计排样方法相比，自适应多岛遗传算法的排样结果的板材利用率更高，且排样方法的稳定性也优于分布估计排样方法。

The optimization method of layout based on adaptive multi-island genetic algorithm was proposed in order to increase the utilization rate of plate and reduce production cost for the layout problem of 2D rectangular parts. Then, the rectangular part was characterized by six-element array, taking the maximum utilization rate of plate as the optimizing goal, the optimization model with constraint of layout problem was built. Based on multi-island genetic algorithm, the adaptively adjusting method of crossover probability and mutation probability was introduced, and the adaptive multi-island genetic algorithm was put forward. Furthermore, for the particularity of layout problem, the genetic operators were designed adaptively, and the circular crossover method and changing mutation strategy were given to ensure that the rectangle scale remained unchanged before and after the execution of genetic operator. Finally, the gene decoding method was set by the lowest horizontal line heuristic algorithm, and two sets of layout experiments for rectangular part with the scales of 30 and 59 for verification were conducted. The result shows that compared with the distribution estimation layout method, the utilization rate of plate and the stability of layout method for the layout results of adaptive multi-island genetic algorithm are higher.

基金项目：

江西省高等学校教学改革研究重点课题（JXJG-16-52-2）

曾晓亮（1984-），男，学士，副教授 E-mail：ixeio9@163com

参考文献：

［1］扈少华，潘立武. 针矩形件五级剪切排样方式的一种生成算法
［J］. 锻压技术，2018，43(10):190-194.

Hu S H, Pan L W. A generating algorithm for fivelevel cutting layout pattern of rectangular part
［J］. Forging & Stamping Technology, 2018，43(10):190-194.

［2］王晓庆，李尚芳，崔耀东. 矩形毛坯最优层排样方式的动态规划算法
［
［J］.计算机应用研究，2010, 27(6): 2040-2042.

Wang X Q, Li S F, Cui Y D. Dynamic programming algorithm for generating optimal layer patterns of rectangular blanks
［J］. Application Research of Computers, 2010, 27(6): 2040-2042.

［3］Liao X, Xiao H, Zhou X, et al. A new linear programming approach for TDGCS layout problem
［J］. Engineering and Technology Research， 2016，978：354-360.

［4］王磊，刘强，陈新. 单规格一刀切矩形排样问题的启发式搜索算法
［J］. 软件学报, 2017, 28(7): 1640-1654.

Wang L, Liu Q, Chen X. Heuristic search algorithm for the rectangular fixedsize guillotine bin packing problem
［J］. Journal of Software, 2017, 28(7):1640-1654.

［5］郭蕴华，许昆仑，常万里，等. 基于改进蚁群算法和剩余矩形法的二维矩形件优化排样
［J］. 武汉理工大学学报, 2018，40(2):95-100.

Guo Y H, Xu K L, Chang W L, et al. Packing optimization of rectangles based on improved ant colony algorithm and surplus rectangle method
［J］. Journal of Wuhan University of Technology, 2018，40(2):95-100.

［6］罗强, 饶运清, 刘泉辉, 等. 求解矩形件排样问题的十进制狼群算法
［J］. 计算机集成制造系统, 2019, 25(5):1169-1179.

Luo Q, Rao Y Q, Liu Q H, et al. Decimal wolf pack algorithm for rectangular packing problem
［J］. Computer Integrated Manufacturing Systems, 2019, 25(5):1169-1179.

［7］孙永厚，杨帅，刘夫云，等. 基于多岛遗传算法汽车动力总成悬置解藕优化
［J］. 机械设计与制造, 2019，(12):155-159.

Sun Y H, Yang S, Liu F Y, et al. Decoupling optimization of an automotive powertrain suspension based on multiisland genetic algorithm
［J］. Machinery Design & Manufacture, 2019，(12):155-159.

［8］黄致谦, 丁勤卫, 李春, 等. 基于多岛遗传算法的漂浮式风力机稳定性多重调谐质量阻尼器优化控制
［J］. 中国机械工程, 2018, 29(11):1349-1356.

Huang Z Q, Ding Q W, Li C, et al. Optimal control of MTMD in floating wind turbine stability based on MIGA
［J］. China Mechanical Engineering, 2018, 29(11):1349-1356.

［9］熊昕, 赖国明. 改进的三级遗传算法定制特定应用片上网络拓扑
［J］. 计算机应用与软件, 2018，35（3）：241-246.

Xiong X, Lai G M. An improved threelevel genetic algorithm to customize applicationspecific networkonchip topology
［J］. Computer Applications and Software, 2018，35（3）：241-246.

［10］胡士娟. 基于改进遗传算法的多旅行商问题的研究
［D］. 无锡：江南大学，2019.

Hu S J. Research on Multiple Traveling Salesman Problem Based on Improved Genetic Algorithm
［D］. Wuxi: Jiangnan University, 2019.

［11］杨华丽. 基于遗传算法的复杂间歇生产绿色调度优化研究
［D］. 湘潭：湘潭大学，2019.

Yang H L. Research on Green Scheduling Optimization of Complex Batch Production Based on Genetic Algorithm
［D］. Xiangtan: Xiangtan University, 2019.

［12］马康，高尚. 分布估计算法求解矩形件排样优化问题
［J］. 电子设计工程，2017,25(2): 49-54.

Ma K, Gao S. Solution to optimize cutting pattern in rectangular packing problem based on estimation of distribution algorithm
［J］. Electronic Design Engineering, 2017,25(2): 49-54.

服务与反馈：

【文章下载】【加入收藏】