基于改进遗传算法的任意图形最大内接矩形求解  

Solution of Graphics Maximum Enclosed Rectangle Based on Improved Genetic Algorithm

作　　者：袁哲[1] 王永振[1] 石怀涛[1] 肖健宇[2] 王琳岩 

机构地区：[1]沈阳建筑大学国家联合地方实验室,沈阳110168 [2]中南大学信息科学与工程学院,长沙410083 [3]东北大学流程工业综合自动化国家重点实验室,沈阳110168

出　　处：《控制工程》2016年第3期400-404,共5页Control Engineering of China

基　　金：国家自然科学基金(51105258);住房和城乡建设部研究开发项目(2012-K3-41);辽宁省教育厅一般项目(L2013236)

摘　　要：为了求解任意不规则图形最大内接矩形问题(MER问题),在建立MER优化数学模型的基础上,针对遗传算法收敛速度慢、无法处理模糊约束条件、容易陷入局部最优解等问题,引入惩罚函数法处理约束和评价个体适应度,提出了基于改进遗传算法的不规则图形MER模型求解方法,研究表明该方法能快速准确地确定不规则图形的最大内接矩形,可广泛地应用在目标特征提取、板材优化排样和皮革裁切中。The MER mathematical optimization model is established in order to solve the maximum enclosed rectangle of arbitrary irregular graphs problem(MER problem). The penalty function method is introduced to deal with the constraints and evaluation of individual fitness. A solution of MER problem is proposed in the paper based on the improved genetic algorithm, according to the default of slow convergence speed, cannot deal with fuzzy constraint condition, easy to fall into the local optimal solution. Experiment results prove that the proposed method can rapidly and accurately detect the maximum enclosed rectangle of arbitrary irregular graphics. It can be widely applied to the extraction of a target feature, the layout of optimizing plank and leather cutting.

关 键 词：精英保存策略 改进遗传算法 任意不规则图形 最大内接矩形 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]