第15卷第5期2003年5月
计算机辅助设计与图形学学报
JOURNALOFCOMPUTER-AIDEDDESIGN&COMPUTERGRAPHICS
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
VoI.15,No.5
May,2003
基于遗传模拟退火算法的不规则多边形排样
陈勇唐敏童若锋董金祥
(浙江大学人工智能研究所
杭州
310027)
杭州
310027)
(浙江大学CAD&CG国家重点实验室
摘要将遗传模拟退火算法应用于计算机辅助排样领域,设计了一种基于遗传模拟退火技术的启发式排样算法.
该算法能够处理不规则多边形的排样问题;同时,给出一种对象的几何表达方式,可以忽略高度不规则形状带来的复杂性影响.该算法通过基于遗传模拟退火算法的全局优化概率搜索,寻找排样件在排样时的最优次序及各自的旋转角度,然后采用基于左下角(BL)策略的启发式排样算法实现自动排样.关键词
排样;启发式算法;遗传模拟退火算法
TP391.72
中图法分类号
PackingofPolygonsUsingGeneticSimulatedAnnealingAlgorithm
ChenYong
TangMin
TongRuofeng
DongJinxiang
310027)310027)
(InstituteofArtificialIntelligence,ZhejiangUniuersity,Hangzhou
(StateKeyLaboratoryofCAD&CG,ZhejiangUniuersity,Hangzhou
AbstractAheuristicapproachtopackingmuItipIeshapedpartsinanirreguIarsheetwithoutorienta-
tionIimitationispresented.TheaIgorithmaIsoprovidesanewwaytorepresentthesheetandpartge-ometry,thattheirreguIarityofshapedoesnotaffectthecomputationaIcompIexityofprobIem.ThesoptimumproposedapproachautomaticaIIyIooksforthebestseguenceoftheshapedpartsandeachpart’
rotationbythegeneticsimuIatedanneaIingaIgorithm,andcompIetespackingbytheheuristicaIgorithmwiththebottom-Ieft-condition.TheaIgorithmisdiscussedindetaiI.Keywords
nesting;heuristicaIgorithm;geneticsimuIatedanneaIingaIgorithm
能力.但应用实践表明,在遗传算法的应用中也有
1引言
一些不尽人意的问题,其中最主要的问题是容易产生早熟现象、局部寻优能力较差等.模拟退火算法具有很强的局部搜索能力,遗传模拟退火算法的基本思想就是将遗传算法与模拟退火算法相结合,取长补短.
人工智能方法在计算机辅助排样领域中的应用已经成为当前科研的一个新趋势.排样问题是寻求
目前,遗传算法已经成为人工智能领域的热点,在机器学习、工程优化、任务调度、图像处理等领域得到了成功的应用.遗传算法通过对生物遗传和进化过程中选择、交叉、变异机理的模仿,来完成对问题最优解的自适应搜索过程,具有良好的全局搜索
原稿收到日期:修改稿收到日期:(2000033554)和浙江省自然科学基金2002-06-21;2002-08-12.本课题得到国家教育部博士点基金资助.陈(601107)
勇,男,硕士研究生,主要研究方向为CAD、计算机辅助排样等.唐1978年生,
敏,男,博士,副教授,主要研究1974年生,
方向为CAD、几何造型等.童若锋,男,博士,副教授,主要研究方向为计算机图形学、计算机动画、几何造型等.董金祥,男,1969年生,1945年用户界面、计算机图形学等.生,教授,博士生导师,主要研究方向为CIMS、
基于遗传模拟退火算法的二维不规则多边形排样问题 基于遗传模拟退火算法的二维不规则多边形排样问题基于遗传模拟退火算法的二维不规则多边形排样问题隐藏>> 学校代码 ...
对于二维不规则图形零件在排样区域上的最优排列,将排样和制造工艺联系起来,将多边形 摘要: 各边向外扩充,为零件预留加工余量;然后采用遗传模拟退火算法与小生境技术...
对于二维不规则图形零件在排样区域上的最优排列,也就是对二维不规则图形的计算机自动排样算法进行优化问题。采用矩形包络算法、遗传模拟退火算法及小生境技术相结合,...
一种二维不规则零件优化... 8页 1下载券 基于遗传模拟退火算法的... 62页...一种基于重心 N FP 的二维不规则多边形排样算法 ,算法主要包括临界多边形计算和...
一种二维不规则零件优化... 8页 1下载券 基于遗传模拟退火算法的... 62页...一种基于重心 N FP 的二维不规则多边形排样算法 ,算法主要包括临界多边形计算和...
遗传模拟退火混合算法在钣金自动排样中的研究_专业资料。在钣金制造中,如何进行... 基于混合遗传模拟退火算... 1人阅读 3页 3.00 不规则件优化排样的...
求解矩形件优化排样的自适应模拟退火遗传算法_专业资料。矩形件优化排样是一个...第2 卷O 第1 1期 计 算机 辅 助设计 与 图形 学学 报 JOURNAI OFCOMP ...
不规则件优化排样的小生... 4人阅读 6页 2.00 基于模拟退火遗传算法...(070020 10—2520)3—06—4 基于遗传 模拟 退火 算法 的铣 削 用量 优化 ...
基于遗传模拟退火算法的移动机器人静态路径规划_专业资料。采用多边形法描述了机器人的工作环境模型,应用简化编码长度的技术简化了工作路径编码方式.对于基于遗传算法...
一个基于遗传算法和模拟退火 算法的求解布局问题( 矩形件排样优化) 算法, 并...( 对于非矩形的不规则形状零件的排样 问题, 可通过计算机的图形处理技术将一个...
热门文档