带性能约束的复杂布局问题的模型及搜索算法研究

The complex packing problem with behavioral constraints is crucial for the satellite module layout design and other related fields, and becomes the urgent problem to be solved. However,the key obstacles of solving this problem are to lack an unanimous modeling method and high-performance search algorithms. This project will carry out research for modeling of the complex layout problem and finding the conformation search algorithms. First, we will build the geometric representation of arbitrary shaped objects and layout space, and give the mathematical model of the problem by the finite-envoloping-spheres approximation method. Thereafter, based on quasi-physical strategy and penalty function method, we will convert the complex packing problem with behavioral constraints into the unconstrained optimization problem. For this unconstrained optimization problem, we will modify the energy or the state density of the new updated conformation by using the histogram function, and put forward a new stochastic optimization method based on histogram function. Furthermore, we will give an effective framework constructing high-performance layout search algorithms by combining reasonably the proposed stochastic optimization method, the energy minimization method with local search and some heuristic strategies, and thereafter put forward some concrete high-performance layout search algorithms. At last, through the numerical experiments of the simplfied recoverable satellite module and international communication satellite module, et al, it is verified to the feasibility and validity of the proposed layout search algorithms.

带性能约束的复杂布局问题对卫星舱布局设计等领域具有重要的意义,是亟待解决的重大课题。然而，目前国内外缺乏一种对该问题进行有效建模的通用方法和高效求解的布局搜索算法。为此，本项目针对复杂布局问题的布局模型和构形搜索算法开展研究，首先采用有限包络球组填充的近似方法建立任意形状待布物和布局区域的通用几何表示及数学模型；在此基础上，通过拟物方法和罚函数法将带性能约束的复杂布局问题转化为无约束条件的布局优化问题；对此无约束优化问题，提出采用频率直方图函数修改新访问到的构形的势能或状态密度，对构形搜索提出一种基于直方图函数的随机优化方法；然后将具有全局搜索的随机优化方法与局部搜索的能量极小化方法以及一些启发式策略相结合，提出构建布局搜索算法的一种新的框架，并由此提出若干具体布局搜索算法；最后，拟把所提出的布局搜索算法应用于简化返回式卫星舱和简化国际商业通信卫星舱等布局设计的复杂布局问题进行仿真验证。

卫星舱布局问题不仅是一个复杂的耦合系统设计问题，也是一个带有多个目标和多个约束的复杂优化问题，具有NP 难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。主要研究复杂布局问题的数学模型、约束处理方法、随机抽样机制及布局算法设计及其应用等。. 针对该类复杂布局问题，本项目取得以下重要研究成果：. 1） 给出了以卫星舱布局为背景的若干数学模型。这些模型以优化转动惯量、容器半径为目标，以待布物不干涉、质心偏差以及静不平衡量或动不平衡量为约束。给出了一种基于有限包络球（或圆）的待布物或布局区域的通用几何表示。提出了各类待布物（包括规则待布物，如矩形待布物，圆形待布物，圆柱体待布物和长方体待布物，和任意形状待布物）之间，以及待布物与布局区域之间的一些新的干涉性判断和干涉量计算方法。. 2）提出了基于拟物策略和罚函数法相结合的约束问题转变为无约束优化问题的约束处理方法。. 3）提出了基于频数和状态密度抽样的若干新的抽样方法。. 4）对于复杂布局问题中的单目标优化问题，提出了一种新的算法框架：将全局搜索的随机算法与局部极小化方法以及一些启发式策略相结合，创造性地构造了若干高效的单点局部搜索算法（不同于Memetic算法），如改进的吸引盘填充算法，启发式禁忌搜索算法，启发式模拟退火算法，以及基于状态密度函数的抽样算法等。. 5）对于复杂布局问题中的多目标优化问题，提出了一类基于构象空间的多目标演化算法，多目标蚁群算法和多目标粒子群算法。通过将传统的演化算法、蚁群算法、粒子群算法与新提出的个体选择方法（最近最远候选解法）、外部文档、小生境技术以及目标空间分割法相结合，提高了算法的搜索性能和效率。. 本项目为卫星舱等复杂布局问题提出了若干有效的解决方法。项目研究中所提出的布局算法极大地丰富了计算机理论科学，特别是为智能计算提供了一些新的方法和理论。另外，本项目所提出的这些算法具有广泛的适应性和推广性，可以广泛应用于一些复杂系统（单目标或多目标、带约束或不带约束）的优化计算，如航天舱物件布局、制造业设施布置和蛋白质结构从头预测等NP难度问题的求解。