求解VLSI布局问题的启发式算法

在人们现实布局实践经验的启发下。对 VLSI 布局问题提出了一个启发式算法。该算法由定序规则和定位规则组成,定序规则用来确定布局物体放入布局空间的先后顺序,定位规则规定每一布局物体都被当前最优的占角动作放入布局空间。对5个 MCNC 算例的测试结果表明,本文算法与基于 O-tree 表示的算法相比,速度提高15～56倍;对于其中4个算例,面积利用率提高0.95%～5.31%。     

一种基于二叉树结构表达的二维实体布局算法

利用二叉树表达二维实体布局问题,得到一个完全自动的二维实体布局算法,算法的复杂性为Ｏ（ｎ）,其中ｎ是区域树的结点数,提出了区域树面积因子等新概念,给出一个精美的旋转区域树的方法,证明了若干基本定理。     

一种基于八叉树结构表达的三维实体布局启发式算法

本文在利用八叉树结构表达三维实体布局块及布局空间的基础上,根据八叉树同构节点匹配的思想设计了一个三维实体布局的启发式算法,并提出了三环图方法,解决了八叉树节点的同构识别问题．理论分析及计算的结果表明了该算法对于具有任意形状和大小的布局对象的三维布局问题来说效果理想．     

一种基于二叉树结构的玻璃切割排样方法

在玻璃切割工艺中,整块玻璃原料切割前必须事先规划好样片的排布方法和切割路径。对于理论上属于NPC二维矩形排布问题,提出了一种基于二叉树结构的排样算法。二叉树的生长方向决定于材料利用率、空白区域尺度等各个关键因素的加权。通过调整各个关键因素的权值,来调节二叉树的生长方向,从而达到不断优化玻璃原料利用率的目的。这种近似算法速度快、效率高。经实践证明玻璃原料的平均利用率达到90％以上,能很好地满足实际生产的需求。     

三维矩形布局吸引子性质的研究

吸引子法作为一种量化的定位规则,在解决三维布局问题时取得了较好的效果。对解决三维矩形布局问题的吸引子法进行了研究,获得了吸引子法的一些基本性质,如最佳布入点、吸引子法的趋角性、隐性吸引子的“唯一”性以及位置的“动态性”等,有利于吸引子法在三维矩形布局求解中得到更好地运用。     

基于蚁群算法的带平衡约束矩形布局问题的启发式求解

以卫星舱布局问题作为研究背景,求解了带平衡约束的矩形布局问题。采用启发式策略设计了分区域分步布局法,该策略将圆形卫星舱承重板分成4个区域,分区域同步进行布局。当所布矩形和区域都确定时,采用最左最底填充策略进行布局。该方法通过不干涉约束,使布局紧凑,通过控制系统质心的位置,使系统保持平衡。在启发式策略的基础上,设计了蚁群算法搜索优化定位次序,从而得到优化的布局。数值仿真结果表明,该布局方法具有优良的计算性能。     

矩形物体布局的模拟进化算法

介绍了一种称为序列对的表示 Non- Slicing结构平面上矩形块布局的模型 ,并基于该模型提出了一个优化矩形块布局的模拟进化算法     

一种解决矩形布局问题的启发式快速算法

针对二维矩形Packing问题,提出了一种沿阶梯线轮廓进行布局矩形的启发式算法.该算法基于\"阶梯式堆码\"的启发式规则,能够快速地对矩形块进行紧靠布局.为避免算法陷入局部最优,算法采用随机回溯策略在选择矩形和阶位上扩大搜索范围.结果表明,算法对于浪费面积为零的矩形全Packing问题,能够在极短的时间内找到最优解,同时它也可以很好地求解非零浪费问题.采用国际公认的两个算例进行测试,证明文中算法是非常高效的.     

一种改进的线索二叉树结构

本文给出了一种改进的线索二叉树结构,这种改进的线索二叉树的优点在于：在其它性能不变的前提下,遍历二叉树的效率比经典的先序和后序线索二叉树优越。     

基于空间分解的集装箱布局启发式算法及布局空间利用率规律

针对集装箱布局提出了一种利用三叉树结构表达三维矩形物体布局状态空间的方法。通过将布避空间依据分割,每次放入相对于当前布局空间来说是满足特定折最优布局块,将该布局块定位于当前布局空间后部的左下角,来完成不同大小的三维矩形全的布局方案的确定,并给出试验结果。     

使用基于值规则的协作图实现多agent的动作选择

多agent系统的一个关键性的问题就是多agent之间的协作,即一组agent需要选择出一个联合动作,使得整体效用最大化。该文提出了基于值规则的协作图,并改进了变量消减算法,使用它们可以实现多agent在通信条件受到限制的离散状态空间里进行动作选择。     

解决数据三维平衡的数组变换遍历算法

该文以文犤1犦、犤2犦的结果作为基础,提出了解决数据三维平衡的一个新的算法--三维数组变换遍历算法,给出了该算法的数学基础、方法步骤、算法描述及算法分析。由于该算法基础牢、误差小且稳定性好,因而具有很大的实用价值。     

关联规则在医疗数据分析中的应用

介绍了从医疗数据中发现关联规则的方法,分析了医疗数据的特点,并以心脏疾病诊断的数据集为例,阐述了把医疗数据转换成事务数据格式的方法,描述了关联规则挖掘在医疗数据分析中应用所遇到的难题,针对这些难题给出了一种改进的Apriori算法,并用数据进行测试。结果表明,此算法优于Apriori算法,它可以减少产生的规则的数量,从而能快速发现有趣的医疗关联规则。     

一种移动机器人全局路径规划新型算法

针对模拟退火算法收敛速度慢这一缺陷,提出了一种基于共轭方向法和模拟退火算法相结合的新型混合优化算法,并成功应用于机器人神经网络路径规划中．该算法可以使优化解不陷入局部极值解而得到全局最优解．仿真实验研究表明：本文提出的这种新型混合优化算法,计算简单,收敛速度快,显著提高了求解移动机器人全局最优化问题的计算效率．     

基于遗传算法求解带公差的“一刀切”问题

矩形件排样是典型的组合优化问题,在很大程度上影响着企业生产效率。将遗传算法与启发式规则相结合,同时在排样过程中考虑待排样式的公差,求解"一刀切"矩形件排样问题。首先,采用实数基因编码方式,由实数基因值与启发式信息结合确定待排样式的优先权。其次,基于待排样式的最小极限尺寸,采用两步解码方法。第一步为初始填充,将待排样式组合成满足"一刀切"的可行条料,并求解板材利用率最高的条料填充方式;第二步为对第一步剩余空白区的填充,求解不同启发式信息下,空白区利用率最高的待排样式填充方式。再者,基于待排样式的最大极限尺寸和板材尺寸,对最优排样方案进行调整。最后,以VB6.0为开发工具将算法实现,并通过实例对比分析证明了算法的有效性。     

An efficient placement heuristic for three-dimensional rectangular packing

By embodying the spirit of “gold corner, silver side and strawy void” directly on the candidate packing place such that the searching space is reduced considerably, and by utilizing the characteristic of weakly heterogeneous problems that many items are in the same size, a fit degree algorithm (FDA) is proposed for solving a classical 3D rectangular packing problem, container loading problem. Experiments show that FDA works well on the complete set of 1500 instances proposed by Bischoff, Ratcliff and Davies. Especially for the 800 difficult strongly heterogeneous instances among them, FDA outperforms other algorithms with an average volume utilization of 91.91%, which to our knowledge is 0.45% higher than current best result just reported in 2010.     

金属板材三维装箱的启发式算法

针对直方体金属板材装箱问题,提出一种模仿人装箱过程的启发式算法,该算法对木箱进行分层装箱,从最底层开始一层层往上装载,对每层出现的不平整的层进行智能填充,从而提高木箱的空间利用率,采用人工智能方法处理待装金属板材得出装箱结果,实验结果表明,该算法是行之有效的,并具有一定的通用性.     

二维优化排样方法及实现技术

在工业应用领域中存在大量的二维下料问题,其中应用最多的是矩形件下料问题.矩形件下料问题的关键是寻找二维平面的优化布局.针对工业生产中实际存在的问题与约束条件,给出了新的规则设计理论和数据模型,利用覆盖率和有效覆盖率的概念来控制余料合并操作的执行,运用布局规则、组合规则和切割规则给出了一种新的启发式算法.实验分析和工业应用证明,该启发式算法可以有效地提高板材的整体利用率,极大地减少了板材损耗.     

旋转锥体空间中圆柱体群的布局优化

旋转圆锥体空间中不等圆柱体群的布局为人造卫星再入舱布局的简化模型，属带动力性能约束的Packing优化问题，具有NP难度．本文提出了模式迭换法，用以构造布局拓扑模式，形成初始布局方案；推荐了在此初始布局方案下进行布局寻优的算法；给出了缓解“组合爆炸”的技巧和算例验证．此类问题具有广阔的工程应用前景．