二维矩形Strip Packing问题的算法研究与改进

二维矩形Strip Packing问题的约束条件及目标函数与基本型二维矩形Packing问题类似,都是在有限的矩形容器中,有效地摆放各个矩形块,以最大化容器利用率为目标。为了解决这一NP-hard问题,该文在邓见凯、王磊提出的拟人型全局优化算法的基础上进行了深入的算法研究与改进。针对Strip Packing问题特点,提出了QHG(Quasi-Human Group)算法,其核心改进涵盖了多个方面,包括扩充初始点集合、删除和替换评价标准以及扩大邻域空间搜索范围。和单个局部极小值点的迭代相比,对局部极小值点集合进行迭代所生成布局优度更高,跳坑策略用于跳出局部极小值点,将搜索引向有希望的区域,优美度枚举有望进一步提高布局优度。通过这些措施,QHG算法更好地模拟人类决策过程,提高了全局搜索的效率。为评估QHG算法性能,对8组标准问题实例(C组、N组、NT组、CX组、NP组、ZDF组、2sp组、bwmv组)进行了大量实验。实验结果表明,QHG算法生成的布局优度优于当前国际文献中的几种较先进算法,展现了其在Strip Packing问题上的卓越性能。

求解单位等边三角形Packing问题的近似算法

多边形Packing问题不仅具有重要的理论意义 ,而且也有广阔的应用前景 .由于该问题具有NP难度 ,且具有连续的性质 ,一般要事先对多边形的放置方位进行限制 ,例如不允许多边形旋转 ,然后再进行优化求得近似解 .该文采用一种新的思路对多边形Packing问题的一个特例———单位等边三角形Packing问题进行了研究 ,提出了零自由度动作和零自由度放置策略的概念 ,并设计了一个近似求解算法———最小损伤法 .复杂性分析和计算结果表明该算法是高效的 .以此为基础 ,可能为多边形Packing问题找到类似的求解算法 .

求解矩形Packing问题的砌墙式启发式算法

为求解正交矩形Packing问题提出了一个新颖而有效的砌墙式启发式算法.该算法主要基于砌墙式启发式策略,其思想主要来源于砖匠在砌墙过程中所积累的经验:基于基准砖的砌墙规则.对国际上公认的大量的Bench-mark问题例的计算结果表明,该算法的计算速度不仅比著名的现代启发式算法快,而且获得更优的高度.

求解平衡约束圆形Packing问题的快速启发式并行蚁群算法

带平衡约束圆形Packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1～3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.

基于粗精调技术的求解带平衡约束圆形Packing问题的拟物算法

带平衡约束的圆形Packing问题是以卫星舱布局为背景的具有NP难度的布局优化问题.文中建立了此问题相应的数学模型,同时提出了两个新的物理模型,并受工艺加工过程中"粗精加工"现象的启发,提出了基于粗精调技术的拟物算法QPCFA.该算法既兼顾了搜索空间的多样性以利于全局搜索,又能对有前途的局部区域进行精细搜索以找到相应的局部最优解.同时,在计算过程中引入禁忌技术和跳坑策略,以提高算法的求解质量.对国际上11个代表性的算例进行了计算,QPCFA更新了其中7个算例的最好记录,其余4个与目前的最好记录基本持平,且与目前的最好结果相比在计算精度上均有较大的提高.

求解方格packing问题的启发式算法

沿着拟物与拟人的途径,本文为一类具有NP难度的方格packing问题得到了实用的近似求解算法,以此算法为基础可以发展出一种为大规模集成电路芯片裁切工作做计算机辅助设计的高效的软件系统。

基于欧氏距离的矩形Packing问题的确定性启发式求解算法

使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形Packing问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC和GSRC得到了验证.

正三角形容器内等圆Packing问题的启发式算法

等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.

基于禁忌搜索的启发式算法求解圆形packing问题

求解具有NP难度的圆形 packing问题具有很高的理论与实用价值 现提出一个有效的启发式方法 ,求解了货运中常遇到的矩形区域内的不等圆 packing问题 此算法首先将圆按给定的优先级分组 ,然后逐组地用拟物拟人法放置圆 ,并且在整个过程中利用了禁忌搜索法的思想 ,通过禁止重复前面已做的工作 ,使搜索能有效地逃离局部极小值的陷阱 ,提高了搜索效率 实验结果表明 。

求解圆形Packing问题的一个启发式算法

求解ＮＰ难度问题一直是计算机科学技术中的一个瓶颈任务．自２０世纪７０年代以来的研究表明，求解ＮＰ难度问题不存在既完整严格又不太慢的求解算法．因此，近年来，启发式方法成为研究热点．圆形Ｐａｃｋｉｎｇ问题是ＮＰ难的，具有很高的理论和实践价值．它的求解目标是寻求多个圆在一个大圆内的一个优良布局，使得这些圆互不重叠地放置．基于拟物法以及适者生存的启发式思想，为圆形Ｐａｃｋｉｎｇ问题的快速求解提出了一个高效的启发式算法．算法的高效性通过计算实例得到了验证．

基于禁忌搜索的启发式算法求解球体Packing问题

为求解具有NP难度的球体Packing问题,通过将禁忌搜索方法与基于自适应步长的梯度下降法和二分法相结合,提出了一个启发式算法。对50个等球算例进行了实例测试,算法改进了其中44个算例的目前最优结果。大量的实例计算结果表明,该启发式算法是求解球体Packing问题的一个有效算法。

基于改进粒子群优化算法的矩形Packing问题

针对具有NP难度的矩形Packing问题,提出一种带变异算子的双种群粒子群算法,该算法将粒子群分为2个不同的子群,使种群在全局和局部都有较好的搜索能力。通过子群重组实现种群间的信息交换。同时在算法中引入变异算子,对产生的局部最优解的邻域进行搜索。实验结果表明,该算法是一种求解矩形Packing问题的高效实用的算法。

一种求解圆形Packing问题的模拟退火算法

为求解矩形区域内的圆形Packing问题,提出一种启发式模拟退火算法。寻求多个圆在一个矩形区域内的优良布局,使这些圆两两互不嵌入地放置。算法从任一初始构形出发,采用模拟退火(SA)算法进行全局寻优,在SA执行过程中,应用基于自适应步长的梯度法进行局部搜索,同时介绍一些启发式策略。对2组共20个算例进行实算测试,计算结果证明了该算法的有效性。

求解不等圆Packing问题的一个启发式算法

求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性.

三角形Packing问题中无损放置动作的研究

提出了三角形Packing问题中的两类放置动作———完全嵌入动作和孤立动作 ,证明了这两类放置动作是当前格局下的无损放置动作 ,并从可计算性角度提出了零自由度孤立动作的概念 。

Packing问题的计算复杂性

本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及 NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形 Packing问题进行了有益的探讨。这对设计Packing问题的求解算法具有借鉴意义。

求解长方体Packing问题的高效算法

对典型的NP难度问题——著名的长方体Packing问题,通过观察体会人类几千年来在砌石头下围棋等活动中形成的经验和智慧,受到谚语"金角银边草肚皮"的启发,并将它发展提高到"价值最高钻石穴",提出了一种最大穴度的占角动作优先处理的拟人算法.计算了Loh和Nee提出的15个代表性的算例,算法在合理的时间内得出了高空间利用率的布局,其精度达到了国际先进的纪录.

求解圆形packing问题的一个快速拟物算法

求解NP难问题一直是计算机科学技术中的一个瓶颈任务。自20世纪70年代以来的研究表明,不存在求解此类问题的完整严格的有效算法。因此用启发式方法求解成为当今研究的一个热点。圆形packing问题是一个有着很高理论和实用价值的NP难问题。该文提出了一些有效的搜索策略,得到了一个求解它的快速有效启发式算法。最后用计算实例验证了此算法的有效性,计算结果表明此算法明显优于已有快速算法。

一种求解不等圆Packing问题的改进遗传模拟退火算法

不等圆Packing问题是求解半径不等的小圆在一个圆形容器内的优良布局,使得圆形容器的半径值最小。该问题属于NP hard的组合优化问题,使用传统的数学方法很难求解,提出了一种解决该问题的改进遗传模拟退火算法,该算法通过计算生成一个合适大小的初始圆形容器来指导初始种群的生成,以减少搜索范围,采用最优保存策略来保证历代的最优解不被破坏,结合了遗传算法全局搜索能力强的优势和模拟退火算法局部搜索能力强的优势,改进了算法的搜索能力。最后通过算例验证,该算法有效地提高了圆形容器的面积利用率,证明了改进遗传模拟退火算法的有效性。

求解三角形Packing问题的占角算法

三角形Packing问题是NP难的,其完整算法的时间复杂度是指数型的.建立了求解三角形Pack ing问题的数学模型;沿着拟人的途径,通过把待解决的问题与人类的社会经验作对比,得到了求解三角形Packing问题的若干拟人策略,并以此策略为基础发展出一种高效的近似求解算法.实验结果表明,沿此途径得出的求解三角形Packing问题的算法,针对三角形数目较多的情况,具有较好的完整性和较低的时间复杂度.