带静不平衡约束的正交矩形布局问题的启发式模拟退火算法*

以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法.     

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

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

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

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

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

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

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

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

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

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

文化基因算法在多约束背包问题中的应用

文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题.文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题.通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能.     

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

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

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

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

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

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

求解圆形packing问题的拟人退火算法

Circles packing problem is an NP-hard problem and is difficult to solve. In this paper, a hybrid search strategy for circles packing problem is discussed. A way of generating new configuration is presented by simulating the moving of elastic objects, which can avoid the blindness of simulated annealing search and make iteration process converge fast. Inspired by the life experiences of people, an effective personified strategy to jump out of local minima is given. Based on the simulated annealing idea and personification strategy, an effective personified annealing algorithm for circles packing problem is developed. Numerical experiments on benchmark problem instances show that the proposed algorithm outperforms the best algorithm in the literature.     

An action-space-based global optimization algorithm for packing circles into a square container

This paper proposes an action-space-based global optimization (ASGO) approach for the problem of packing unequal circles into a square container such that the size of the square is minimized. Starting from several random configurations, ASGO runs the following potential descent method and basin-hopping strategy iteratively. It finds configurations with the local minimum potential energy by the limited-memory BFGS (LBFGS) algorithm, then selects the circular items having the most deformations and moves them to some large vacant space or randomly chosen vacant space. By adapting the action space defined for the rectangular packing problem, we approximate each circular item as a rectangular item, thus making it much easier to find comparatively larger vacant spaces for any given configuration. The tabu strategy is used to prevent cycling and enhance the diversification during the search procedure. Several other strategies, such as swapping two similar circles or swapping two circles in different quadrants in the container, are combined to increase the diversity of the configurations. We compare the performance of ASGO on 68 benchmark instances at the Packomania website with the state-of-the-art results. ASGO obtains configurations with smaller square containers on 63 instances; at the same time it matches or approaches the current best results on the other five instances.     

Packing unequal circles using formulation space search

In this paper we present a heuristic algorithm for the problem of packing unequal circles in a fixed size container such as the unit circle, the unit square or a rectangle. We view the problem as being one of scaling the radii of the unequal circles so that they can all be packed into the container. Our algorithm is composed of an optimisation phase and an improvement phase. The optimisation phase is based on the formulation space search method whilst the improvement phase creates a perturbation of the current solution by swapping two circles. The instances considered in this work can be categorised into two: instances with large variations in radii and instances with small variations in radii. We consider six different containers: circle, square, rectangle, right-angled isosceles triangle, semicircle and circular quadrant. Computational results show improvements over previous work in the literature.     

A new heuristic algorithm for the circular packing problem with equilibrium constraints

The circular packing problem with equilibrium constraints is an optimization problem about simplified satellite module layout design.A heuristic algorithm based on tabu search is put forward for solving this problem.The algorithm begins from a random initial configuration and applies the gradient method with an adaptive step length to search for the minimum energy configuration.To jump out of the local minima and avoid the search doing repeated work,the algorithm adopts the strategy of tabu search.In the pr...     

带静不平衡约束的矩形装填问题的启发式算法

卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。Wang-Landau（WL）抽样算法是一种改进的蒙特卡罗方法,已经被成功地运用蛋白质结构预测等优化问题。本文以卫星舱布局优化问题为背景,首次将WL抽样算法引入矩形装填问题的求解。针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走。为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,便执行梯度法进行局部搜索。通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法。在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求。另外,为了改进算法的搜索效率,提出了改进的有限圆族法用于装填物之间的干涉性判断和干涉量计算。通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法。     

An effective hybrid algorithm for the problem of packing circles into a larger containing circle

Simulated annealing is a powerful stochastic search method, but it still has the disadvantage of blind search. Tabu search (TS) which can prevent cycling and enhance diversification, is an adaptive strategy based on tabu list. By reasonably combining simulated annealing with TS, an effective hybrid algorithm for the problem of packing circles into a larger containing circle is presented. Based on a special neighborhood and tabu strategy, some benchmark problem instances can be well solved by the presented hybrid algorithm, and the computational results can compete with the best literature results.     

Two-dimensional equilibrium constraint layout using simulated annealing

This paper studies the layout optimization problem with equilibrium constraint. It is a two-dimensional packing problem with the industrial background of simplified satellite module layout design, and is known as NP-hard problem. By incorporating the heuristic neighborhood search mechanism and the adaptive gradient method into the simulated annealing procedure, a heuristic simulated annealing algorithm is put forward for this problem. The special neighborhood search mechanism can avoid the disadvantage of blind search in the simulated annealing algorithm, and the adaptive gradient method is used to execute local search and speed up finding the global optimal solution. Numerical examples are illustrated to verify the effectiveness of the proposed algorithm.