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

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

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

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

求解不等圆Packing问题的带全局变换禁忌搜索算法

圆形Packing问题考察如何将N个半径任意给定的圆形物体互不嵌入地置入一个半径尽可能小的圆形容器内.圆形Packing问题是个经典的NP难度问题,具有重要的理论价值和广泛的应用背景.本文将拟物算法与禁忌搜索相结合,辅以跳离局部陷阱的全局变换策略,得到求解二维不等圆Packing问题的带全局变换禁忌搜索算法GP-TS.拟物算法用于连续优化,可从任一初始格局收敛至局部最优格局;禁忌搜索在禁忌规则和特赦准则的约束下不断地将当前格局替换为其邻域中的最优格局;若禁忌搜索所得格局不满足约束条件,则执行全局变换策略,在不完全破坏当前格局结构的前提下跳离局部陷阱,然后进行新一轮的禁忌搜索,直至满足终止条件为止.数字实验结果表明,GP-TS能在可接受的计算时间内改进多个国际公开算例的已知最优解.     

求解等圆Packing问题的拟人算法

沿着拟人的途径,本文为一类具有NP难度的等国Packing问题得到了若干求解策略,以此为基础发展出两种高效率的快速近似求解算法。     

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

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

动作空间带平衡约束圆形Packing问题的拟物求解算法

对于一个以卫星舱内设备布局为背景的具有NP难度的全局优化问题——带平衡约束的圆形Packing问题,提出了基于动作空间的拟物求解算法.在拟物下降遇到局部极小点的陷阱时,如何找到当前格局下的最空闲空间以使搜索过程跳到更有前景的区域去是设计跳坑策略的一个关键难点.借鉴求解矩形Packing问题中动作空间的概念,通过化“圆”为“方”,将不规则的空闲空间近似为一系列规则的矩形空间,从而有效地解决了此难点.另外,将拟物法与提前中止、粗精调和自适应步长这3个拟人辅助策略相结合,以提高势能下降的效率.对3组共13个代表性算例的计算结果及与国内外代表性算法的比较表明,所提格局的外包络圆半径多为最小或次小,且在部分算例上找到了有更小外包络圆半径的格局,总体计算结果较好,且静不平衡量的精度较高.     

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

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

矩形的三角形划分问题研究

给出了矩形的三角形划分问题的定义,该问题是三角形Packing问题的一个特例,证明了该问题是NP完全的,并给出了该问题有解的一个必要条件。     

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

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

Packing问题的计算复杂性

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

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

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

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

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

A heuristic quasi-physical strategy for solving disks packing problem

By elaborately simulating the movement of the smooth elastic disks in the container in the physical world, we can find the solution for the disks packing problem. This problem is a classical one that arises in many scientific and engineering fields, and it is also one of the NP hard problems. Based on the simulated annealing, i.e., imitating the displacements of the objects under different temperature, the calculation speed is improved. The performance of the algorithm is demonstrated by actual calculations.     

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

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

雷达装备维修器材集装技术研究

多约束条件下的雷达装备维修器材装箱问题是一个复杂的组合优化问题,属于NP完全问题,其求解相当困难.为了解决雷达装备维修器材集装效率低的问题,该文在考虑实际应用的约束条件下,分析并建立了雷达装备维修器材优化装箱问题的模型,采用中间包装,空间分割,空间合并,抽屉分装等策略,提出了一种基于启发式算法的雷达装备维修器材装箱问题的解决方案.仿真实例及实际工作验证了算法的有效性和实用性,较好地解决了雷达装备维修器材的优化装载问题.     

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

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

模拟退火法在钟手表机芯布局中的应用

布局问题,特别是三维物体的布局问题在工业界有着广泛的用途,由于该问题在理论上已属于ＮＰ完全问题,很难用传统优化算法求解,钟手表机芯设计中的传动件布局是具有强约束的三维物体布局问题,根据退火法是一种用于解决连续,有序离散和多模态优化问题的随机优化技术,本文利用根据退火法成功地解决了钟手表机芯设计中的难题,该文还提供了解决一般物体布局问题的框架。