三维布局计算方法的研究.pdf

《三维布局计算方法的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、维普资讯http://www.cqvip.com工程技术武汉船舶职业技术学院学报2008年第2期三维布局计算方法的研究高虹静(武汉船舶职业技术学院机械工程系，湖北武汉430050)摘要布局问题是一个组合最优化问题，众多学者对此进行了深入的研究，并提出了许多算法，算法的选择直接影响布局问题的计算速度和求解精度。本文具体分析了基于规则的启发式算法；传统最优化算法；遗传算法；模拟退火算法；改进模式搜索算法；混合算法的使用场合。关键词布局问题；最优低级方法；遗传算法；模拟退火算法；改进模式搜索法中图分类号TB115文

2、献标识码A文章编号1671—8100(2008)02—0032—04布局问题就是将一些物体，按一定要求合理提出了众多的算法。地放置在一个空间内；或者说，将一个空间划分成1基于规则的启发式算法许多小空间的组合，然后用这些小空间来放置一些物体。布局问题涉及现实生活中的许多行业，基于规则的启发式算法主要应用在运筹学领如航空航天工业，航空器上各种食品的合理摆放域求解布局问题。Dowsland对各种布局问题进问题；纺织、玻璃加工工业中，各种板材的合理下行了综述和分类。启发式算法的优点是简单，它料问题；交通运输业中，运输

3、工具内不同形状、不具有很强的领域性，能有效地解决特定领域的问同大小的货物配载问题等。在船舶行业中存在大题，但应用于一般布局问题存在困难。该算法的量的布局问题，如钢材下料的二维布局问题；船舶基础是来源于常识和经验的启发式规则，但它不各种舱室的三维布置设计问题；热力、通风、管道可能考虑到所有的布局规则。因为解空间大，为(HAVC)的线路布置问题(routing)。布局结果了减少计算时间，搜索算法没有遍历解空间。的好坏对船舶设计、制造以及船舶的性能有着重戴佐等人(1995)提出了三维非立方体布局的要的影响。布局设计

4、在电路板和集成芯片设计中一种启发式计算法。他们采用八又树近似表达实得到成功应用，并且出现了许多商业的CAD系体的几何形状，其基本思想是基于八叉树结点的统。与超大规模集成电路(VLSI)二维布局相比，自动匹配。布局物体的角度限制在9O度。此方船舶布置设计中，设备的组合以及设备和布局容法对于“供需平衡”(布局物体体积总和与容器容器的三维几何外形显得更加复杂，因而船舶三维积较接近)的布局问题具有很好的效率和求解布置设计更加困难，主要表现在：1)目标函数和质量。约束的建模；2)目标函数和约束的高效计算；3)2传统最优

5、化方法最优化搜索策略的选择。虽然布局问题有不同的解析表达形式，但是传统最优化方法，如分支定界算法、线性规划通常可以抽象为一个复杂的组合最优化问题。因性、梯度法(gradient—basedalgorithm)，也用于为在布局求解过程中要进行大量的目标函数和约求解一类布局问题，但是使用范围比较狭窄。束的计算，存在计算速度和求解精度的矛盾，因此Scheithauer和Terno提出分支定界算法对布局搜索算法的好坏直接影响布局问题求解的速一维的下料问题进行最优求解。在该问题中，目度和质量，许多研究人员对此进行了深入

6、研究，并标函数和约束是设计变量的线性函数。Beasley收稿日期：2007—12—20作者简介：高虹静，男，讲师，主要从事机械设计与制造方面的教学和科研工作。32维普资讯http://www.cqvip.com三维布局计算方法的研究高虹提出0—1线性最优化方法，采用拉各朗日松驰法干涉计算的三角形数量，在干涉检测过程中，首先和次梯度循环计算上边界，对二维的矩形非直线采用包容盒检测。下料问题进行求解。在上述方法中，布局物体只布局的搜索空间是高度非连续和多模式的。能进行平移，因为布局物体的旋转会使问题变为遗传算法性

7、能的好坏以及较好解与差解之间存在非线性。随着布局规模的变大，算法的性能会下多大的差异都很难评价。评价函数权因子和染色降。体的很小变化都会带来解的很大差异。要使遗传梯度法是通过计算目标函数的梯度，在负梯算法很好地收敛，选择适当的变异率和交叉率以度方向搜索，多次反复计算、搜索，最后寻求最优也是一件不易的事。基于三角形表面的干涉计算解。梯度提供了可行搜索方向的信息。目标函数虽然精确，但随着实体的复杂，三角形面增多，计不可微或难以计算时，可采用有限差分法近似算速度会非常慢。另外，如果考虑实体的任意旋计算。转角度，计算

8、过程变得更加复杂。Landon和Balling采用梯度法。根据空间和遗传算法是一种随机算法，能有效地处理非质量属性标准对三维实体进行了布局设计。梯度光滑、非连续函数，突出优点是它的鲁棒性。遗传是通过计算质量属性对设计变量的微分求得。布算法需要反复计算适应度函数。因此，该算法适局实体模型采用边界表示法。两个实体间最近两合计算耗时少的问题。当布局物体数量很大时，点作为相应实体最小间隔距离。当一个实体沿指