论文部分内容阅读
以VLSI布局设计等为背景的加权布局问题属于多目标优化问题,以航天器舱布局设计为背景的圆柱体和长方体布局设计问题属于带性能约束的多目标优化问题。归因于相互冲突的多目标和高维实数解空间,它们的求解都非常困难。在设计它们的装填方案时,要求装填物体之间不能重叠,装填方案有尽可能高的空间利用率外,且满足给定的性能约束,使其达到最优。本文工作是在国家自然科学基金资助下研究加权圆集布局问题,资助项目是复杂性能驱动的两类布局问题分治与阶梯式优化理论与方法研究,编号为61272294。到目前为止,国内外专家提出了许多有效方法,如启发式方法、演化方法,人机交互方法和它们的结合方法等,但其求解精度的提高仍然需要进一步探索。为此,本文基于物理学中弹性势能原理,将自适应梯度法与王鲁达采样机制及非同构布局模式的构造结合起来,提出一种两阶段求解的优化机理和方法。其主要创新如下:1.针对矩形容器的加权圆集布局问题,构造出了系统的弹性势能函数。其思想是通过预估矩形容器的尺寸,定义矩形容器与待布圆之间、待布圆与待布圆之间的嵌入度,进而基于嵌入度构造出系统的弹性势能函数。2.针对矩形容器的加权圆集布局问题,提出了一种两阶段的自适应拟物梯度优化方法。在第一阶段,其能量函数是弹性势能与权距和的线性函数,并将步长变为自适应。提出的方法提高了收敛速度。权距和被作为弹性势能的一部分,圆形物被抽象为一个个带“磁性”的小球,其相互之间吸引力大小取决于权矩阵系数,这些使梯度迭代朝着期望的目标优化。通过第二阶段的微调使准可行解变为满足不干涉条件的可行解。实验证明此法能明显减小加权距离之和,并使布局更为紧凑。3.针对矩形容器的加权圆集布局问题,提出一种基于Wang_Landau采样的两阶段全局优化方法。此方法改进了第一阶段中系统的能量函数,并通过构造非同构的布局模式和WL采样的随机行走使系统的态密度接近其真实数值,由此提高了算法的准可行解全局搜索能力与稳定性。数值实验表明了提出的方法的可行性、有效性和稳定性。本文以VLSI布局设计为背景,充分利用给定数学模型的已知信息提出了一种两阶段的优化算法,并通过WL采样以提高全局搜索能力,使加权距离之和与包络面积得到协同优化。其结果表明这两个优化目标的求解精度都优于已有文献中的方法。希望本文方法能为设计者提供参考。