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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于遗传模拟退火算法的矩形件优化排样

为了探索更高效的矩形件优化排样方法,提出了一种改进的自适应遗传模拟退火算法。设计了基于矩形件的排样次序及旋转变量的两层染色体编码方法,并采用基于临界多边形的BL定位策略实现矩形件的布局;通过构造启发式算法生成排样初始种群,然后各个种群之间通过相互竞争实现优秀个体的迁移与共享,最终搜索到最优解。标准测试问题的实验结果验证了所提算法的可行性与有效性。     

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

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

一种多目标不等面积设施布局问题的启发式算法

多目标不等面积设施布局问题（UA-FLP）是将一些不等面积设施放置在车间内进行布局,要求优化多个目标并满足一定的限制条件。以物料搬运成本最小和非物流关系强度最大来建立生产车间的多目标优化模型,并提出一种启发式算法进行求解。算法采用启发式布局更新策略更新构型,通过结合基于自适应步长梯度法的局部搜索机制和启发式设施变形策略来处理设施之间的干涉性约束。为了得到问题的Pareto最优解集,提出了基于Pareto优化的局部搜索和基于小生境技术的全局优化方法。通过两个典型算例对算法性能进行测试,实验结果表明,所提出的启发式算法是求解多目标UA-FLP的有效方法。     

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...     

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.     

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.     

Applying multi-objective ant colony optimization algorithm for solving the unequal area facility layout problems

The unequal area facility layout problem (UA-FLP) which deals with the layout of departments in a facility comprises of a class of extremely difficult and widely applicable multi-objective optimization problems with constraints arising in diverse areas and meeting the requirements for real-world applications. Based on the heuristic strategy, the problem is first converted into an unconstrained optimization problem. Then, we use a modified version of the multi-objective ant colony optimization (MOACO) algorithm which is a heuristic global optimization algorithm and has shown promising performances in solving many optimization problems to solve the multi-objective UA-FLP. In the modified MOACO algorithm, the ACO with heuristic layout updating strategy which is proposed to update the layouts and add the diversity of solutions is a discrete ACO algorithm, with a difference from general ACO algorithms for discrete domains which perform an incremental construction of solutions but the ACO in this paper does not. We propose a novel pheromone update method and combine the Pareto optimization based on the local pheromone communication and the global search based on the niche technology to obtain Pareto-optimal solutions of the problem. In addition, the combination of the local search based on the adaptive gradient method and the heuristic department deformation strategy is applied to deal with the non-overlapping constraint between departments so as to obtain feasible solutions. Ten benchmark instances from the literature are tested. The experimental results show that the proposed MOACO algorithm is an effective method for solving the UA-FLP.     

基于Wang-Landau抽样的带静不平衡约束的简化卫星舱布局方法

以简化卫星舱承载板上三维布局设计问题为背景,研究一类带静不平衡约束的圆柱体和长方体混合待布物布局问题。针对该三维布局问题,将已成功应用于统计物理学和蛋白质结构预测的Wang-Landau抽样算法引入布局问题中。Wang- Landau抽样算法通过在复杂布局空间中进行有效抽样来得到一个平坦的能量直方图,从而精确估计布局系统的状态密度。通过将Wang- Landau抽样算法与带加速策略的最速下降法、质心平移策略相结合,提出了改进的Wang-Landau抽样算法。对文献中两个算例进行了实算,计算结果表明,改进的Wang-Landau抽样算法的收敛速度和解的质量相比文献中其它算法均有较大的提高。