首页 | 本学科首页   官方微博 | 高级检索  
     

一种用于矩形排样优化的改进遗传算法
引用本文:蒋兴波,吕肖庆,刘成城.一种用于矩形排样优化的改进遗传算法[J].计算机工程与应用,2008,44(22):244-248.
作者姓名:蒋兴波  吕肖庆  刘成城
作者单位:1. 北京大学,计算机科学技术研究所,北京,100871;第二军医大学,卫生勤务学教研室,上海,200433
2. 北京大学,计算机科学技术研究所,北京,100871
摘    要:矩形排样优化属于NPC问题,在工业界有着广泛的应用,如布料切割、金属下料和新闻组版等。提出了一种基于环形交叉算子和环形变异算子的自适应遗传算法,并将改进的自适应遗传算法和IBL启发式布局算法相结合,有效地解决了矩形排样优化问题。对比实验结果表明,环形交叉算子和环形变异算子对遗传算法是有效的,所提出的改进混合自适应遗传算法能够在一个较短的时间内找到满意解。

关 键 词:自适应遗传算法  矩形排样优化  启发式布局算法  环形交叉算子  环形变异算子
收稿时间:2008-2-27
修稿时间:2008-5-5  

Improved genetic algorithm for packing problem of rectangles
JIANG Xing-bo,LV Xiao-qing,LIU Cheng-cheng.Improved genetic algorithm for packing problem of rectangles[J].Computer Engineering and Applications,2008,44(22):244-248.
Authors:JIANG Xing-bo  LV Xiao-qing  LIU Cheng-cheng
Affiliation:1.Institute of Computer Science and Technology,Peking University,Beijing 100871,China 2.Department of Health Services,Second Military Medical University,Shanghai 200433,China
Abstract:The packing of rectangles is a NP-Complete problem and possesses widespread applications in the industry,such as the cutting of clothing,metal and composition of news.In this paper,circular-based crossover operator and circular-based mutation operator are adopted in the proposed adaptive genetic algorithm.With the combination of Improved Adaptive Genetic Algorithm(IAGA) and Improved Bottom-Left heuristic(IBL) algorithm,the packing of rectangles can be effectively solved.The comparison results show that genetic algorithm is more effective by using circular-based crossover operator and circular-based mutation operator and the satisfactory solution can be obtained in a reasonably short period of time by using hybrid IAGA.
Keywords:Adaptive Genetic Algorithm(AGA)  packing of rectangles  heuristic placement algorithm  circular-based crossover operator  circular-based mutation operator
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《计算机工程与应用》浏览原始摘要信息
点击此处可从《计算机工程与应用》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号