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

Computer-aided layout design of spacecraft modules, such as satellite module andmanned spaceship module, is of great significance and egregious complexity. It is known as acombinatorial optimization and NPC problem in mathematics, a conceptual design and complex system inengineering. The main difficulties consist of representation and formulation of the problem inmathematics and the solution strategy and pragmatic approaches in engineering practice. After a briefsurvey of the state-of-the art in relevant fields, this paper summarizes the research work of the authors' group on automatic layout design of spacecraft module in last 15 years, mainly focusing on 5 keyproblems. They are modeling and problem-solving algorithms, interference calculation, theory andapplications of layout topological pattern, decision-making in layout design, and their pragmaticapproaches in engineering practice.

为解决不规则图形排样问题，讨论了基于实例（样图）的推理方法在零件排样问题中的应用，给出了基于样图的排样系统结构。此方法的一个关键问题是在已知待排的零件组和板料的前提下，如何从样图库中检索出相应样图的图形匹配方法。为此提出了基于图形ˆ组‰简化骨架的模式编码的串间Findler距离的图形（组）之间相似性检索算法，并给出了算例验证。

航天器（卫星、飞船等）舱自动化布局设计在数学上属组合最优化、Packin，NPC问题，在工程上属概念设计和方案设计问题。存在的主要困难是：布局问题描述复杂，建模和求解困难，既要解决数学上的组合爆炸问题，又要解决工程系统的复杂性问题，以达到工程上的实用。在综述国内外有关进展的基础上，介绍了该课题组近15年来的阶段性研究进展，重点讨论：（1）模型和求解算法；（2）干涉计算；（3）布局拓扑模式；（4）布局方案评价；（5）工程实用化等5个关键科学问题。

演化设计是近10年兴起的方兴未艾的重要的设计方法。综述了演化设计的现状和进展，侧重介绍其在结构优化、方案设计、人工生命设计中的应用及所用的方法。重点介绍和分析Lipson和Pollack的机器人全自动化演化设计方法-讨论其给予的启示和待研究问题。同时介绍人机结合演化设计方法及其人机交互界面，内含给出的一种人机结合演化设计方法及其在卫星舱布局方案设计中的应用。最后讨论了演化设计方法的发展趋势。

复杂工程布局（如卫星舱布局）方案设计问题在理论上属带性能约束的布局优化问题（NPC问题），很难求解，因而目前研究得尚少。为解决此类问题，该文提出了一种人机交互的遗传算法。该算法首先将人工设计的个体作为染色体群体的组成部分，然后在遗传运算中，把人工适时设计的新个体加入到染色体群体中，以代替群体中的较差个体。从而构成人机交互的遗传算法，这样可以充分发挥人和计算机各自的特长。文后通过3个算例（其中一个为作者构造的已知最优解的算例）的数值计算，验证了该算法的可行性和有效性。

The two-dimensional layout problem is known to be NP-complete, and the current research work is basically in theheuristic way. In this paper, we mainly discuss the methods for solving layout problem about the arti

Layout design of a satellite module directly concerns its structure, performance, service life, and cost of assembly andmaintenance. It is an important andNP-complete problem. Themain difficulties consist of combinatorial optimizationsinmathematics and system complexity in engineering practice, and relevant researches are far from enough. This paperproposes a basic solution strategy for the optimal layout design of a satellite module, which consists of two stages,global (or loose) layout design and detailed layout design. Corresponding algorithms are then developed while takingthe layout design of an international commercial communication satellite as an example. They are the centripetalbalancing method for global layout design and a quasi Traveling Salesman Problem (TSP) model-based Ant ColonyOptimization (ACO) algorithm for layout optimization. The proposed method demonstrates its feasibility and validityon an application instance. Existing problems and further research directions are finally discussed.

布局问题在理论上属于NPC问题，在工程实践上具有广泛的应用。为较好地求解该问题，以并行遗传算法（PGA）为基础，针对其早熟和收敛速度慢两大缺陷加以改进，提出了并行混合免疫算法（PHlA）。该算法将免疫思想加入遗传算法起到了双重作用，一是免疫选择可有效地防止早熟，二是通过基于免疫记忆的子群体信息交换策略可加速收敛。算法采用混沌初始化，并依自适应交叉和变异的概率值对子群体进行分类，与Powcll法混合可更好地改善局部搜索性能。以卫星舱和印制电路板布局设计为背景的算例验证了该算法的可行性和有效性。

This paper studies the layout optimization problem of the simpli"ed vessel of satellite which movesspirally. It is a three-dimensional packing problem with dynamical equilibrium constraints, and is known asNP-hard problem. A solution strategy for such a problem is proposed and corresponding heuristicalgorithms are presented in this paper. Numerical examples are illustrated to verify the e!ectiveness of theproposed algorithms.