Layout optimization of satellite module using soft computing techniques

This paper presents a hybrid method using soft computing techniques to deal with layout design problem of a satellite module. This problem is a three-dimensional layout optimization problem with behavioral constraints, and is difficult to solve in polynomial time. In this study, we firstly used a Hopfield neural network (HNN) to allocate the given apparatuses and equipment to the bearing plate surfaces in the satellite module. Then, we integrated genetic algorithm/particle swarm optimization (GA/PSO) and quasi-principal component analysis (QPCA) to deal with the further detailed layout optimization. The numerical experimental results showed the feasibility and efficiency of our method for layout optimization of a satellite module.     

求解卫星舱布局问题的蚁群劳动分工优化算法

卫星舱布局是卫星总体设计的重要组成部分,其研究的是仪器设备在卫星舱内的最佳摆放方式.从空间的角度出发,卫星舱布局的一个设计方案就是不同的仪器设备在容器内占据着不同的空间,当仪器设备所占空间发生变化时,就会形成新的设计方案.因此,卫星舱布局可以看成是将容器空间合理地分配给仪器设备(分配特性),并达到某种最优指标(优化特性).在借鉴蚁群劳动分工任务分配实现卫星舱布局空间分配的基础上,进一步融合卫星舱布局的优化特性,提出一种蚁群劳动分工优化算法.在具体的实现过程中,为基本蚁群劳动分工算法设计启发式占位动作、自适应环境刺激和个性化响应阈值,同时引入禁忌搜索、跳坑策略和接收准则等优化技术,对16个代表性算例的计算结果表明,所提出算法是求解卫星舱布局的有效算法.     

Multi-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search

The layout design of satellite modules is considered to be NP-hard. It is not only a complex coupled system design problem but also a special multi-objective optimization problem. The greatest challenge in solving this problem is that the function to be optimized is characterized by a multitude of local minima separated by high-energy barriers. The Wang-Landau (WL) sampling method, which is an improved Monte Carlo method, has been successfully applied to solve many optimization problems. In this paper we use the WL sampling method to optimize the layout of a satellite module. To accelerate the search for a global optimal layout, local search (LS) based on the gradient method is executed once the Monte-Carlo sweep produces a new layout. By combining the WL sampling algorithm, the LS method, and heuristic layout update strategies, a hybrid method called WL-LS is proposed to obtain a final layout scheme. Furthermore, to improve significantly the efficiency of the algorithm, we propose an accurate and fast computational method for the overlapping depth between two objects (such as two rectangular objects, two circular objects, or a rectangular object and a circular object) embedding each other. The rectangular objects are placed orthogonally. We test two instances using first 51 and then 53 objects. For both instances, the proposed WL-LS algorithm outperforms methods in the literature. Numerical results show that the WL-LS algorithm is an effective method for layout optimization of satellite modules.     

Simultaneous design of components layout and supporting structures using coupled shape and topology optimization technique

The purpose of this paper was to study the layout design of the components and their supporting structures in a finite packing space. A coupled shape and topology optimization (CSTO) technique is proposed. On one hand, by defining the location and orientation of each component as geometric design variables, shape optimization is carried out to find the optimal layout of these components and a finite-circle method (FCM) is used to avoid the overlap between the components. On the other hand, the material configuration of the supporting structures that interconnect components is optimized simultaneously based on topology optimization method. As the FE mesh discretizing the packing space, i.e., design domain, has to be updated itertively to accommodate the layout variation of involved components, topology design variables, i.e., density variables assigned to density points that are distributed regularly in the entire design domain will be introduced in this paper instead of using traditional pseudo-density variables associated with finite elements as in standard topology optimization procedures. These points will thus dominate the pseudo-densities of the surrounding elements. Besides, in the CSTO, the technique of embedded mesh is used to save the computing time of the remeshing procedure, and design sensitivities are calculated w.r.t both geometric variables and density variables. In this paper, several design problems maximizing structural stiffness are considered subject to the material volume constraint. Reasonable designs of components layout and supporting structures are obtained numerically.     

带平衡约束矩形布局优化问题的深度强化学习算法

带平衡约束的矩形布局问题源于卫星舱设备布局设计,属于组合优化问题。深度强化学习利用奖赏机制,通过数据训练实现高性能决策优化。针对布局优化问题,提出一种基于深度强化学习的新算法DAR及其扩展算法IDAR。DAR用指针网络输出定位顺序,再利用定位机制给出布局结果,算法的时间复杂度是O（n³）;IDAR算法在DAR的基础上引入迭代机制,算法时间复杂度是O（n⁴）,但能给出更好的结果。测试表明DAR算法具有较好的学习能力,用小型布局问题进行求解训练所获得的模型,能有效应用在大型问题上。在两个大规模典型算例的对照实验中,提出算法分别超出和接近目前最优解,具有时间和质量上的优势。     

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

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

微粒群算法在产品组件布局设计中的应用

提出了一种基于微粒群算法的自适应优化布局求解算法,该算法以组件特征模型为基础,在微粒群算法中引入人机交互技术,从整体上自动优化布局方案,以满足约束条件为目标。并以手机组件的布局求解为例,对该算法进行了验证。理论和实例分析表明,该算法能有效地生成多个手机组件布局方案。     

基于遗传算法的重力式立体仓库优化调度

为提高重力式立体仓库出入库操作的效率,分析了某企业重力式立体仓库货架布局,提出了货物在出入库操作中的七种规则集,以平均作业时间、堆垛机利用率、其它设备利用率为优化控制目标,用遗传算法求出出入库路径优化的最优解。通过C语言仿真实验验证了提出的方法的有效性。     

Component allocation and supporting frame topology optimization using global search algorithm and morphing mesh

This paper proposes a stepwise structural design methodology where the component layout and the supporting frame structure is sequentially found using global search algorithm and topology optimization. In the component layout design step, the genetic algorithm is used to handle system level multiobjective problem where the optimal locations of multiple components are searched. Based on the layout design searched, a new Topology Optimization method based on Morphing Mesh technique (TOMM) is applied to obtain the frame structure topology while adjusting the component locations simultaneously. TOMM is based on the SIMP method with morphable FE mesh, and component relocation and frame design is simultaneously done using two kinds of design variables: topology design variables and morphing design variables. Two examples are studied in this paper. First, TOMM method is applied to a simple cantilever beam problem to validate the proposed design methodology and justify inclusion of morphing design variables. Then the stepwise design methodology is applied to the commercial Boeing 757 aircraft wing design problem for the optimal placement of multiple components (subsystems) and the optimal supporting frame structure around them. Additional constraint on the weight balance is included and the corresponding design sensitivity is formulated. The benefit of using the global search algorithm (genetic algorithm) is discussed in terms of finding the global optimum and independency of initial design guess. It has been proved that the proposed stepwise method can provide innovative design insight for complex modern engineering systems with multi-component structures.     

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.     

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

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

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

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

粒子群算法及其在布局优化中的应用

复杂工程布局(如卫星舱布局)方案设计问题,在理论上属带性能约束的布局优化问题(NPC问题),很难求解。论文以卫星舱布局为例,将粒子群算法(PSO)应用于布局问题,构造此类问题的粒子表达方法,建立了此类问题的粒子群算法。文中通过3个算例(其中一个为已知最优解的算例)的数值计算,验证了该算法的可行性和有效性。     

Integrated layout design of supports and structures

Based on the previously proposed techniques for the integrated layout optimization of multi-component system, this paper is to demonstrate further developments and applications of the related techniques in the integrated layout design of supports and structures. The design procedure mainly consists of two parts. Firstly, the layout of the supports is described with the positions of movable support components on the specified boundary of the design domain. These components are partially embedded into the design domain and subjected to the applied boundary conditions. Secondly, the layout optimization of the support components and the structure is carried out. Locations of the support components and the pseudo-densities defined on the density points are assumed as geometrical and topological design variables, respectively. Geometrical constraints are imposed to avoid the overlap of multiple components. The technique of embedded meshing is employed to adapt the topology optimization to the variation of the finite element mesh caused by the component movement. Varieties of numerical examples are finally tested to validate the proposed method. Both surface load and self-weight load are taken into account. More complexities of partially supported components are introduced in the presented examples.     

A new energy landscape paving heuristic for satellite module layouts

This article describes a study of the satellite module layout problem (SMLP), which is a three-dimensional (3D) layout optimization problem with performance constraints that has proved to be non-deterministic polynomial-time hard (NP-hard). To deal with this problem, we convert it into an unconstrained optimization problem using a quasi-physical strategy and the penalty function method. The energy landscape paving (ELP) method is a class of Monte-Carlo-based global optimization algorithm that has been successfully applied to solve many optimization problems. ELP can search for low-energy layouts via a random walk in complex energy landscapes. However, when ELP falls into the narrow and deep valleys of an energy landscape, it is difficult to escape. By putting forward a new update mechanism of the histogram function in ELP, we obtain an improved ELP method which can overcome this drawback. By incorporating the gradient method with local search into the improved ELP method, a new global search optimization method, nELP, is proposed for SMLP. Two representative instances from the literature are tested. Computational results show that the proposed nELP algorithm is an effective method for solving SMLP with performance constraints.     

Multiobjective layout optimization of robotic cellular manufacturing systems

This paper proposes a multiobjective layout optimization method for the conceptual design of robot cellular manufacturing systems. Robot cellular manufacturing systems utilize one or more flexible robots which can carry out a large number of operations, and can conduct flexible assemble processes. The layout design stage of such manufacturing systems is especially important since fundamental performances of the manufacturing system under consideration are determined at this stage. In this paper, the design criteria for robot cellular manufacturing system layout designs are clarified, and objective functions are formulated. Next, layout design candidates are represented using a sequence-pair scheme to avoid interference between assembly system components, and the use of dummy components is proposed to represent layout areas where components are sparse. A multiobjective genetic algorithm is then used to obtain Pareto optimal solutions for the layout optimization problems. Finally, several numerical examples are provided to illustrate the effectiveness and usefulness of the proposed method.     

旋转卫星舱内长方体群的布局

该文以人造卫星舱布局为背景,研究二维带平衡及不干涉等约束的长方形集在圆容器内的布局优化问题,此问题属于NP-困难问题。文章将粒子群算法(PSO)应用于该问题,构造此类问题的粒子表达方法,建立此类问题的粒子群算法。文中通过4个算例(其中一个属于高维)的数值计算,验证了该算法的可行性和有效性。     

基于全局和分离部件融合的双L1稀疏表示人脸图像识别算法

考虑到人脸识别中全局与局部信息的互补作用,提出基于全局和分离部件相结合的双L1稀疏表示人脸图像识别算法.首先在L1稀疏表示的基础上,对入脸进行全局稀疏逼近.其次,在分离部件识别模型中,抽取并对齐稍有重叠的几个人脸部件,分别进行稀疏表示,然后使用基于稀疏表示残差的相似度投票方法,将各部件逼近结果综合.最后在决策层上将全局与部件的稀疏表示加权集成,形成双L1稀疏表示分类器.在公用人脸数据库上的实验表明,集成分类器优于各单一模块的识别性能,且由于融合了对光照、表情等变化不敏感的部件信息,系统鲁棒性得到提高.     

新型电路版图布局布线算法设计

调研了电路自动布局布线技术的国内外研究现状,在此基础上设计了一种面向中等规模电路布局布线算法,主要用于大型版图设计软件的模块测试环节,为用户提供各模块初步的布线布局结果,方便用户高效查找并修正错误点,填补了我国在相关领域的空白.建立了超图模型并转换为图模型,改进了Stoer-Wagner算法并利用该算法和Fiduccia-Mattheyses算法对图进行了基于最小割理论的划分,从而构建出一棵划分树.在这棵树的基础上设计了一种二元相对移动算法来确定各个电路元件的位置,大大降低了布局拥挤度,提高了美观度,对于数百元件的电路均能在0.5s内得出布局结果.基于A*算法在多个方面做了改进,提高了布线速度,对于线路数1000以下的元件能在0.1 s～60 s内得出结果,实现了100％ 布通率以及均匀的布局布线效果.