布局问题的建模和求解方法详解

针对布局问题的三重复杂性，首先从其建模方法和求解方法两方面进行综述。

1.布局问题建模

布局问题建模是布局问题求解的基础。模型的建立不仅关系到求解算法或方法的选取，而且其质量的好坏亦影响到布局问题的最终求解质量。布局问题建模主要包括布局对象的建模和布局求解过程的建模。本书从上述两个方面分别进行介绍。

（1）布局对象的建模。在空间布局问题中，布局对象包括待布物和布局空间。布局对象建模即待布物和布局空间的几何特征和非几何特征（如质量特性、装配特性等）的描述。布局对象从几何特征来分，主要有规则形体和不规则形体，由于在优化求解过程中计算复杂性的影响，目前多数布局设计方法处理布局对象方法是将实际布局问题中的不规则布局对象简化为规则形体进行处理，以提高计算求解效率，缓解计算复杂性困难。

1993年，滕弘飞等研究了三维航天器旋转体舱中圆柱体和长方体群布局优化设计问题，将待布物简化为三维规则形体进行干涉计算。1997年，Szykman和Cagan将大规模集成电路二维布局设计的技术扩展到三维。

随着实际应用中对不规则物体布局问题有效求解理论和方法需求的不断增加，近年来，国内外学者对三维不规则待布物描述及建模进行了研究，1995年，戴佐和查建中等将八叉树数据结构引入到三维实体的计算机仿真布局及智能布局领域，用以表示任意形状的三维实体及三维布局空间，进而给出了三维实体的实体造型和干涉检验的八叉树方法。基于八叉树方法较好地解决了复杂物体之间距离的计算问题。1998年，Cagan和Degentesh等提出了表达实体的一种改进的八叉树方法及相应的干涉检验算法。可以看出，不规则物体的描述和建模的研究已有相当的进展，但能否应用到具有一定规模的工程实际布局问题中，还有待深入的研究。

（2）布局求解过程的建模。布局求解过程的建模与布局求解方法紧密相关，其求解模型建立的方式应考虑与布局求解方法相结合，最终建立高效的布局求解模型。目前，布局问题求解模型建立方法主要包括数学模型和布局拓扑模型、广义知识求解模型等。(www.xing528.com)

目前，人们多采用数学模型对计算机科学和实际工程领域的布局问题进行抽象描述和建模。Beasley将布局问题抽象为0-1整数规划模型，其基本思想是用一个二值变量表示某类型特定物体的可行位置。Faggioli和Bentivoglio建立了切割排序问题的数学模型，并分别用贪婪算法和禁忌搜索对其求解。Udy等利用序列二次规划和广义简约梯度法来解决小型三维布局问题，但其解的质量过分依赖于初始位置的选择。黄文奇和陈亮将布局干涉约束用解析形式表达出来，提出一种求解布局问题的拟物方法。滕弘飞等以人造卫星舱的布局为背景，建立三维规则物体（长方体和圆柱体）的布局优化模型，并利用惩罚因子将布局约束转化为目标函数惩罚项，提出了求解一类航天器舱布局优化问题的方法。1998年，Stoyan等对一类圆形和矩形待布物的二维packing问题建立了非线性数学规划模型。1998年，Cagan等对发动机舱和热力泵的三维空间布局设计问题采用线性加权法和惩罚函数法建立了无约束单目标数学优化模型，并采用模拟退火算法进行了求解计算。可以看出，数学模型已经在一些领域的布局问题描述和建模中得到了一定程度的深入研究。

为了缓解布局设计中的组合爆炸问题并加强对布局问题本质的认识，国内外学者利用图论和拓扑学方法对布局问题中待布物之间的拓扑位置关系进行了深入研究，Dowland等首先建立布局的图论模型，将布局问题转换为一个在已知的连接图中寻找最大独立集或最大权平面子图的问题。由于该方法设计图的平面化问题，难以将其扩充到三维布局。吴惠中提出了一个长方体布局问题的立体正交结构图模型，但通过进一步研究发现，该模型仍不能充分表达布局知识和约束。基于此，王英林发展建立了约束图模型来表示二维或三维复杂形体。同时，李广强等研究了布局拓扑模式的不同定义及相应布局算法。上述研究在一定程度加深了对布局问题本质的认识，但纯粹采用图论等方法还不能有效地建立充分表达布局知识及约束的计算机模型，因此在解决工程实际问题中还未得到广泛的应用。

但是在布局实践中，许多工程问题难以甚至无法用单一的数学模型来描述和表达，或即使能够表达也与实际问题相距甚远，所求结果无法满足工程实际需求。为此，2003年，唐晓君等提出了建立复合知识模型的思想；2000年，孙守迁等提出了一种面向人机工程建模的方法，并将其用于摩托车协同布局设计系统；2000年，刘占伟等提出一种航天器舱布局设计问题的广义建模方法，将问题描述的自然语言、图形符号、数值符号等信息量转化为统一形式的数值编码串，作为演化算法的个体，进而通过算法的演化操作实现上述信息的融合，共同致力于问题的求解。

总之，布局求解过程的建模至关重要，建立数学、符号、仿真，以及人机一体化广义模型是今后的一个发展方向，当然对此类模型求解方法的探索也需进一步研究。因此，本书给出的人机结合布局设计方法仍以数学求解模型为主。

2.布局问题求解算法和方法

由上述描述所知，本书研究的航天器舱布局设计问题属于带性能约束的复杂布局问题，很难用传统的纯数学方法解决，目前针对此类问题常用算法有：启发式算法、数学规划法、图论法、人工智能（如人工神经网络、专家系统、多Agent系统等）、演化计算（如遗传算法、模拟退火算法、蚁群算法、免疫算法、粒子群算法、差异演化算法等）、协同进化算法、虚拟设计，以及人机结合等。下述第1.3节和第1.4节详细讨论与本书相关的求解方法。