以动态吸引子为导向的布局求解理论的研究

布局问题属于复杂的组合最优化问题和NP完全问题，所以关于其研究具有重要的理论价值。布局问题涉及现代生产的许多领域，布局结果的好坏对这些领域生产的合理性、经济性、安全性及节能、环保等质量指标具有重大影响。通过分析布局问题的特性，研究布局求解中布局空间和物体的几何表达、布局要求及相互关系如功能、结构、空间限制等，将这些信息及关系转化为有效的表达、并将其分类及分层，建立布局模型，从而为布局求解奠定坚实的基础。根据布局物体及空间的几何表达形式，研究不依赖于具体问题的通用干涉计算方法，利于进行干涉、碰撞检测等过程，通过将布局因素定量化，提出量化的定序和定位函数（规则），建立以动态吸引子为导向的高效求解算法，促使各种算法有效综合。通过实验分析得出布局优化策略和相关参数。合理评价算法效率，从而为不同布局问题的解决提供依据。

布局问题属于复杂的组合最优化问题和NP完全问题，所以关于其研究具有重要的理论价值。在研究现有布局问题的基础上，对布局问题中的各种约束进行了研究和归类，并分析了它们在布局模型中所起作用。利用面向对象思想给出了布局约束的表达形式。采用自上而下的分层设计思想，提出了布局问题的复合知识模型，为今后的布局设计提供了参考。布局模型由问题模型、序列模型、骨架模型、目标模型和智能体模型组成。该模型既适合概念设计的抽象信息又适合详细设计等阶段的具体信息，还包括约束耦合关系的表达及系统设计目标的表达等。.基于八叉树的空间有序性，根据树结点的相邻特性提出了一种计算八叉树模型边界表示的算法。算法由八叉树的最小全满结点开始循环并逐步递增至最大结点，从而有效避免了子结点的分解。为了提高算法的计算效率，在算法运行时利用整数的“位”来记录结点的状态并进行判定。算法也可用于扫掠体的计算。首先将扫掠物体离散为一些特征点，然后将这些特征点沿扫掠路径进行变换，形成点集合；此后，将点集合转化为八叉树模型，最后利用本算法将八叉树模型转化为表面模型，从而求得扫掠体。算法可应用于干涉检测、布局求解以及机器人等领域。此外，通过利用布尔差，提出了长方体布局可行域的求解算法。.对吸引子法进行了研究，并获得了一些基本性质，诸如矩形布局定位函数的三维图像为一个平面，定位函数值相等的点共线，吸引子法使矩形块堆积在一个角上等。此外，通过研究吸引子放置位置对布局的影响，得出了隐性吸引子这一重要的性质。.以动态吸引子法为依据，根据智能优化算法的特点，采用遗传算法、模拟退火算法以及将二者相结合的方法，获得定位函数的合适参数，建立了以动态吸引子为导向的求解算法，从而获得较佳的布局结果。算法有效地克服了传统布局求解方法单一的局限性，具有自适应性等智能特征，从而为不同布局问题的解决提供依据。.提出布局问题的粒子群算法并对算法搜索效率进行了研究，通过对布局结果解区间长度与迭代次数的数据拟合，证明粒子群算法有较强的搜索能力。多种扰动策略的分析比较表明多样性的扰动策略有利于提高算法的搜索能力。.通过将布局因素定量化，提出量化的定序和定位函数（规则）。如提出一个考虑矩形布局三个基本要素即布局块的长度、宽度和面积的静态定序函数；提出一种基于尺寸配合的动态定序规则，其根据矩形块与剩余布局空间的尺寸配合程度选择布入矩形块。