基于Wang_Landau采样求解加权圆集布局问题的拟物方法研究

发布时间：2018-05-01 21:32

本文选题：加权圆集布局 + Wang_Landau采样　；参考：《湘潭大学》2017年硕士论文

【摘要】：以VLSI布局设计等为背景的加权布局问题属于多目标优化问题,以航天器舱布局设计为背景的圆柱体和长方体布局设计问题属于带性能约束的多目标优化问题。归因于相互冲突的多目标和高维实数解空间,它们的求解都非常困难。在设计它们的装填方案时,要求装填物体之间不能重叠,装填方案有尽可能高的空间利用率外,且满足给定的性能约束,使其达到最优。本文工作是在国家自然科学基金资助下研究加权圆集布局问题,资助项目是复杂性能驱动的两类布局问题分治与阶梯式优化理论与方法研究,编号为61272294。到目前为止,国内外专家提出了许多有效方法,如启发式方法、演化方法,人机交互方法和它们的结合方法等,但其求解精度的提高仍然需要进一步探索。为此,本文基于物理学中弹性势能原理,将自适应梯度法与王鲁达采样机制及非同构布局模式的构造结合起来,提出一种两阶段求解的优化机理和方法。其主要创新如下:1.针对矩形容器的加权圆集布局问题,构造出了系统的弹性势能函数。其思想是通过预估矩形容器的尺寸,定义矩形容器与待布圆之间、待布圆与待布圆之间的嵌入度,进而基于嵌入度构造出系统的弹性势能函数。2.针对矩形容器的加权圆集布局问题,提出了一种两阶段的自适应拟物梯度优化方法。在第一阶段,其能量函数是弹性势能与权距和的线性函数,并将步长变为自适应。提出的方法提高了收敛速度。权距和被作为弹性势能的一部分,圆形物被抽象为一个个带“磁性”的小球,其相互之间吸引力大小取决于权矩阵系数,这些使梯度迭代朝着期望的目标优化。通过第二阶段的微调使准可行解变为满足不干涉条件的可行解。实验证明此法能明显减小加权距离之和,并使布局更为紧凑。3.针对矩形容器的加权圆集布局问题,提出一种基于Wang_Landau采样的两阶段全局优化方法。此方法改进了第一阶段中系统的能量函数,并通过构造非同构的布局模式和WL采样的随机行走使系统的态密度接近其真实数值,由此提高了算法的准可行解全局搜索能力与稳定性。数值实验表明了提出的方法的可行性、有效性和稳定性。本文以VLSI布局设计为背景,充分利用给定数学模型的已知信息提出了一种两阶段的优化算法,并通过WL采样以提高全局搜索能力,使加权距离之和与包络面积得到协同优化。其结果表明这两个优化目标的求解精度都优于已有文献中的方法。希望本文方法能为设计者提供参考。
[Abstract]:The weighted layout problem with the background of VLSI layout design is a multi-objective optimization problem, and the cylindrical and cuboid layout design problem with the background of spacecraft cabin layout design belongs to a multi-objective optimization problem with performance constraints. Due to the conflicting multi-objective and high-dimensional real solution space, their solution is very difficult. When designing their filling schemes, it is required that there should be no overlap between the loading objects. The loading scheme has the highest space utilization ratio and satisfies the given performance constraints to make it optimal. In this paper, the weighted circular set placement problem is studied with the aid of the National Natural Science Foundation of China. The funded project is a study of the theory and method of divide-and-conquer and step optimization of two types of layout problems driven by complex performance, numbered 61272294. Up to now, experts at home and abroad have put forward many effective methods, such as heuristic method, evolution method, human-computer interaction method and their combination method, etc. Therefore, based on the principle of elastic potential energy in physics, the adaptive gradient method is combined with Wang Ruda sampling mechanism and the construction of non-isomorphic layout pattern, and an optimization mechanism and method for two-stage solution are proposed. Its main innovations are as follows: 1. The elastic potential energy function of the system is constructed for the problem of the weighted circular set layout of the rectangular container. The idea is to estimate the size of the rectangular container, define the embedding degree between the rectangular container and the circle to be distributed, and then construct the elastic potential energy function of the system based on the embedding degree. A two-stage adaptive quasi-material gradient optimization method is proposed to solve the problem of weighted circular set layout of rectangular vessels. In the first stage, the energy function is a linear function of the sum of elastic potential energy and weight, and the step size becomes adaptive. The proposed method improves the convergence rate. As a part of elastic potential energy, the weight distance and the circular object are abstracted as a "magnetic" sphere, and the mutual attraction depends on the coefficient of the weight matrix, which makes the gradient iteration optimize towards the desired goal. By fine-tuning the second stage, the quasi-feasible solution is transformed into a feasible solution satisfying the non-interference condition. Experimental results show that this method can obviously reduce the sum of weighted distance and make the layout more compact. 3. A two-stage global optimization method based on Wang_Landau sampling is proposed for the weighted circular set layout of rectangular vessels. This method improves the energy function of the system in the first stage, and makes the density of states of the system close to its true value by constructing a nonisomorphic layout pattern and random walk of WL sampling. Therefore, the global search ability and stability of the quasi-feasible solution are improved. Numerical experiments show that the proposed method is feasible, effective and stable. In this paper, based on the VLSI layout design, a two-stage optimization algorithm is proposed, which makes full use of the known information of the given mathematical model. WL sampling is used to improve the global search ability, so that the sum of the weighted distance and the envelope area can be optimized in cooperation. The results show that the accuracy of the two optimization targets is better than that of the existing methods. It is hoped that this method can be used as a reference for designers.
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN47

【参考文献】