模式识别与人工智能
2025年4月2日 星期三   首 页     期刊简介     编委会     投稿指南     伦理声明     联系我们                                                                English
模式识别与人工智能  2010, Vol. 23 Issue (6): 794-801    DOI:
论文与报告 最新目录| 下期目录| 过刊浏览| 高级检索 |
带平衡约束矩形布局优化问题的遗传算法
徐义春1,董方敏1,刘勇1,肖人彬
1.三峡大学 智能视觉与图像信息研究所 宜昌 443002
2.华中科技大学 控制科学与工程系 武汉 430074
Genetic Algorithm for Rectangle Layout Optimization with Equilibrium Constraints
XU Yi-Chun1 ,DONG Fang-Min1,LIU Yong1,XIAO Ren-Bin2
1.Institute of Intelligent Vision and Image Information,China Three Gorges University,Yichang 443002
2.Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074

全文: PDF (497 KB)   HTML (1 KB) 
输出: BibTeX | EndNote (RIS)      
摘要 研究二维矩形布局优化问题,将多个不同重量和尺寸的矩形目标填充到一个圆形容器中,要求给出最小的容器半径,并且系统保持平衡。目前的文献多采用局部搜索方法,但布局质量有待提高。文中设计一种构造式方法——定位法。其基本思想是将一个矩形围绕另外一个已经确定位置的矩形作为参照进行部署。由于围绕着参照矩形部署时只考虑有限个可布局位置,故定位法具有多项式时间复杂性。定位法可能得到较好的布局,但其质量受到布局顺序的影响较大,因此文中提出一种基于遗传算法的布局顺序寻优算法,其中遗传算法的交叉算子和变异算子经过特别的设计,使得遗传的下一代能继续作为布局顺序。在具有大规模测试用例的测试集上的计算结果表明,该布局方法比局部搜索方法有更优良的计算性能。
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
徐义春1
董方敏1
刘勇1
肖人彬
关键词 布局优化问题启发式方法遗传算法    
Abstract:The 2-dimensional layout optimization problem is studied, where the unequal weighted rectangles are required to be placed in a circular container without overlap. There are two objectives, minimum of the radius of the circle and equilibrium of the system. In most of the literatures, the local search heuristics is applied to the problem. However, the performance of the local search heuristics is not satisfactory. A constructive heuristics is proposed, named orderly positioning technique (OPT). A rectangle is placed close to an already deployed rectangle. Around the deployed rectangle, only finite configurations are considered. Then the time complexity of OPT is polynomial. The output layout of OPT is often with good performance, nevertheless the positioning order of OPT affects the quality of the layout a lot. Thus, a genetic algorithm (GA) to search for the optimal positioning order is designed. In the GA, the crossover operator and mutation operator are specially designed to keep the offspring having a valid placing order. The proposed algorithm is tested on the benchmarks with large-scale instances. The numerical results show that the proposed algorithm has better performance than the local search heuristics from literatures.
Key wordsLayout Optimization Problem    Heuristics    Genetic Algorithm   
收稿日期: 2009-08-17     
ZTFLH: TP391  
基金资助:教育部博士点基金项目(No.200804870070)、湖北省教育厅重大项目(No.Z20081301)资助
作者简介: 徐义春,男,1970年生,副教授,主要研究方向为智能计算.E-mail:yichunx@gmail.com.董方敏,男,1965年生,教授,主要研究方向为图形图像处理.刘勇,男,1975年生,副教授,主要研究方向为智能计算与模式识别.肖人彬,男,1965年生,教授,主要研究方向为系统工程与信息管理。
引用本文:   
徐义春,董方敏,刘勇,肖人彬. 带平衡约束矩形布局优化问题的遗传算法[J]. 模式识别与人工智能, 2010, 23(6): 794-801. XU Yi-Chun ,DONG Fang-Min,LIU Yong,XIAO Ren-Bin. Genetic Algorithm for Rectangle Layout Optimization with Equilibrium Constraints. , 2010, 23(6): 794-801.
链接本文:  
http://manu46.magtech.com.cn/Jweb_prai/CN/      或     http://manu46.magtech.com.cn/Jweb_prai/CN/Y2010/V23/I6/794
版权所有 © 《模式识别与人工智能》编辑部
地址:安微省合肥市蜀山湖路350号 电话:0551-65591176 传真:0551-65591176 Email:bjb@iim.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn