改进的模拟退火算法及其在装填问题中的应用

NP难度问题一直是计算机科学研究的一个重要问题,具有很高的理论和实用价值。这篇文章主要研究利用模拟退火算法解决具有NP难度的装填问题,它的求解目标是寻求多个圆在一个矩形内的优良布局,使得这些圆两两互不嵌入地放置。通过将模拟退火算法与梯度法相结合,并且融入一些启发式的格局更新策略,提出了改进的模拟退火算法。计算结果显示,该算法对于解决圆形装填问题具有很高的效率。

基于蚁群劳动分工的空间分配方法求解带平衡约束的圆形装填问题

针对以卫星舱布局为背景的具有NP难度的全局优化问题——带平衡约束的圆形装填问题,提出基于蚁群劳动分工的空间分配方法。该方法将圆形装填问题看作空间分配问题,并借鉴蚁群劳动分工的任务分配来实现圆形装填问题的空间分配。通过中心平移策略和允许干涉策略,将带平衡约束的圆形装填问题由多目标带约束优化转化为单目标无约束优化。从空间的角度出发,建立了蚁群劳动分工与圆形装填问题之间的映射关系。引入蚁群劳动分工中的刺激—响应原理,提出了空间分配方法。该方法为圆形待布物定义了4个占位动作,并设计了相应的刺激和阈值,进而通过刺激—响应方式完成问题求解。通过3组共13个代表性算例的计算结果及与其他算法的比较表明,所提方法找到的圆形容器半径多为最优或者次优,且静不平衡量的精度最高。

裁剪与装填问题

裁剪与装填问题广泛存在于各行业的材料剪裁、平面布局设计及三维布局设计等方面。这些实际应用需要给出问题的最优解。然而，裁剪与装填问题是ＮＰ－完全问题，很难在有限的合理时间内取得最优解。这种广泛的实用性和解的复杂性使得这类问题成为国际上近年来的一个研究焦点、现简要介绍裁剪与装填问题的基本知识、基本分类以及裁剪问题与装填问题之间的内在联系，并重点介绍了此类问题的优化算法。

一个未解决的装填问题的解答

在尺寸为2×1000的长方形L内,装填直径为1的单位圆,装填时任何两圆都不许有重叠的部分,也没有任何一圆的任何部分超出长方形外,问长方形L内最多能装填几个圆?

求解带平衡性能约束的圆形装填问题的吸引盘填充算法

以卫星舱布局为背景的带平衡性能约束的圆形装填(Packing)问题是NP难度的布局优化问题.缺乏高效的全局优化方法是阻碍这一问题有效解决的关键障碍.势能曲面变平(ELP)法是一种基于Monte-Carlo抽样的随机优化方法.采用拟物策略和罚函数法将带平衡性能约束的圆形装填问题转化为无约束的优化问题.通过对ELP法进行改进,并将改进的ELP法与局部搜索的梯度法和一些启发式的格局更新机制相结合,得到一种新的全局搜索算法—吸引盘填充算法.数值实验结果表明,该方法是求解带平衡性能约束的圆形装填问题的有效算法,并可推广应用于其他布局优化问题的求解.

基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题

带平衡约束的圆形装填(Packing)问题是一类简化的卫星舱布局优化问题.现提出一个基于禁忌搜索的启发式(TSH)算法对该问题进行求解.算法从任一初始格局出发,应用基于自适应步长的梯度法进行能量极小化.为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索,算法采用了禁忌搜索的策略.在禁忌搜索的过程中,我们对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进.对两组共11个有代表性的算例进行了实算.计算结果表明,TSH算法刷新了其中7个算例的当今国际上的最好纪录,对于其余4个算例,该算法均达到问题的最优解.

装填布局问题的三元组编码方法求解

装填布局问题的求解已经被证明是NPC问题,最终求解的结果是符合约束条件的最优解。布局设计问题在求解中一般会采用启发式算法和智能算法对布局问题进行建模求解。针对机械产品布局问题,描述了该问题的求解思路和三元组模拟退火编码方法,并通过实例对三元组分解编码方法在机械产品布局问题上的有效性进行验证。

球形容器内等球装填问题的启发式算法

为了在球形容器内紧密装填n个等球,设计了序列对称换位策略,将其与拟物算法结合得到一个有效的启发式算法.序列对称换位策略每次从一个局部最优布局出发,通过对称换位此局部最优布局的不同真子集得到n(n-1)/2个不同的新布局,并用拟物算法检查这些新布局.此启发式算法只须检查O(n2)个布局,即可找到一个紧凑的可行布局.所找到的最好结果显著改进了目前best known记录,并证否了半径为5的球形容器至多只能装填67个半径为1的等球的猜想.

求解装填布局问题的膨胀方法

介绍了膨胀装填布局的思想原理与算法实现 .膨胀装填布局通过对缩小了的装填物体系统地施加膨胀 -排斥操作而实现被装填物体布局位置的自动产生 ,具有直观性强、聚集性好、几何形状适应性广、便于工程推广等优点 .作为算例 ,使用膨胀装填算法对几种与平面圆相关的装填布局问题给出了计算结果 .

一类装填布局问题的半自动求解方案

装填布局问题在航空、航天、机械、船舶等工程中广泛存在，是相关部门进行产品总体方案设计的关键技术。最典型的装填布局问题是在一个旋转舱内，将Ⅳ个待布组件放置到各安装板上，要求各组件之间、组件与旋转舱之间互不干涉，且整个系统的质心尽量靠近旋转舱的小端、质心横偏菇尽量小，系统绕z轴的转动惯量尽量小。

求解带动不平衡约束的卫星舱布局问题的启发式算法

以卫星舱中承载板上物件的三维布局为背景,研究一类带动不平衡约束的圆柱体形和长方体形待布物的混合布局问题.采用两阶段法进行求解,首先引入基面分配策略,将待布物分配到承载板上、下基面上;然后采用禁忌搜索算法对每一基面上的待布物进行布局优化:对传统禁忌搜索算法中的邻域格局提出启发式的产生策略,并对禁忌对象和格局接受原则进行有效改进,将改进的禁忌搜索算法与局部搜索的梯度下降法相结合,提出一种启发式的布局方法——基于梯度下降的禁忌搜索算法.最后通过算例验证了文中算法的高效性.

装填布局拓扑模式变换的遗传算法

在布局优化中需给出初始点以构成初始布局，用构造非同胚布局拓扑模式的方法给出若干非同胚的初始布局，是缓解组合爆炸、求得全局最优解或较好的局部最优解的关键．用遗传算法的思想来实现布局拓扑模式变换，生成非同胚布局拓扑模式的不同初始布局．介绍了该算法所依据的原理及其实现要点，并通过算例说明了本算法的有效性．该算法还便于实现并行计算．

基于格局变换策略的不等圆Packing问题求解算法

采用基于格局变换策略的算法ACP-Solver求解不等圆Packing问题。ACP-Solver由连续优化方法、格局变换算子和接收准则组成。连续优化方法可从任一初始格局收敛至对应的局部最优格局。格局变换算子将当前格局变换为新格局。接收准则决定是否接收变换所得格局。基于24个国际公开算例的计算实验表明,ACP-Solver能在可接受的计算时间内改进或持平绝大多数算例的当前最优记录。实验结果表明了ACP-Solver的高效性能。

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

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

圆形多组件装填布局的优化求解方法

针对带性能约束的圆形多组件装填布局问题,提出一种具有全局寻优能力的内点法。该算法采用线性搜索和信赖域方法相结合的内点法进行局部寻优;为使算法具有全局寻优能力,提出了自交叉操作的布局变换策略,从而跳出局部最优布局模式,实现组件装填布局的优化求解。对3个经典算例进行了计算验证,并重点与目前的主流算法进行深入分析对比。算例结果表明,该算法在小规模布局问题上的计算效率和精度与其他算法相当,对于规模较大的布局问题则有更好的计算结果,刷新了目前的最优结果。

装填布局的同构和非同构模式

装填布局问题在工程实践上具有广泛的应用 ,在理论上属于NPC问题 .布局模式是其中的一个重要问题 .该文以卫星舱布局方案设计为背景 ,研究装填布局模式问题 ,定义了同构和非同构布局模式、待布物的布局等价关系等概念 ,给出了关系矩阵和模式矩阵以及它们的变换 ,描述了布局模式控制区和非同构度 ,提出了同构和非同构布局模式的识别及构造方法 .文后讨论了布局模式的若干应用 .该工作希望能为缓解装填布局优化问题求解时存在的组合爆炸以及构造高效的求解算法提供启发和借鉴 .

制氢转化炉催化剂的布袋式装填

转化系统是制氢装置的核心,转化催化剂在制氢装置中起着非常关键的作用。本文着重介绍了制氢转化炉催化剂的布袋式装填为合理利用炼厂气资源,降低制氢成本,取得经济效益最大化。

配送中心存储布局的一种动态调度方法

货物在配送中心仓储空间内的定位可以描述为一个NP-Hard的装填问题。把仓储空间分为若干单位空间,并结合空间、时间性质,提出了货物存储空间动态调度的优化算法,在一段连续的调度计划时间段内,整个调度方法被分成三部分。第一部分通过考虑空间约束、离库时间产生对应于不同时间片的货物初步分组集合。第二部分设计了遗传算法来实现初步分组后的货物在单位空间内的优化布局。由于GA的全局搜索特性及精华策略、去负策略的应用,可以实现一个单位空间内的较优货物布局方案。为了克服零散货物占用空间的问题,第三部分是进行手工微调。最后两个仿真例子验证了所提方法的有效性。

应急救援车辆装备器材快速布局设计方法

现有救援车辆器材布局设计主要依据使用对象直观需求和设计人员布局经验定性化设计方法.将器材布局归属于布局问题中的三维空间装填问题,提出一种基于启发式算法的器材装备快速布局设计及优化方法.综合考虑器材布局的目标:空间利用率最大化、平衡布局(保证重心位置)以及人性化要求,将器材布局原则转化为综合关系矩阵,提出待布器材的提取和布置方式与待布空间相匹配的构造方法.利用空间规划的思路,提出先外层后内层的布局策略,将问题转化为带已布物群约束的布局,在此基础上设计器材装备快速布局优化算法.通过实例验证该布局思路和方法,具有较强实用性.

不等圆Packing问题的拟物型邻域搜索算法

将拟物方法与邻域搜索过程结合,得到求解不等圆Packing问题的拟物型邻域搜索算法(QP-NS).拟物方法用于连续优化,可从任一初始格局收敛至对应的局部最优格局;邻域搜索过程迭代地将当前格局替换为其邻域中的最优格局,直至无法继续改进当前格局为止.QP-NS可在不严重破坏当前格局的前提下稳定地改进当前格局,鲁棒性较强.基于14个国际公开算例的计算实验表明:QP-NS可在60s内改进10个算例的此前最优解,并与其余4个算例的此前最优解持平.