本文選題：加權(quán)圓集布局 + Wang_Landau采樣��； 參考：《湘潭大學(xué)》2017年碩士論文

【摘要】：以VLSI布局設(shè)計(jì)等為背景的加權(quán)布局問題屬于多目標(biāo)優(yōu)化問題,以航天器艙布局設(shè)計(jì)為背景的圓柱體和長(zhǎng)方體布局設(shè)計(jì)問題屬于帶性能約束的多目標(biāo)優(yōu)化問題。歸因于相互沖突的多目標(biāo)和高維實(shí)數(shù)解空間,它們的求解都非常困難。在設(shè)計(jì)它們的裝填方案時(shí),要求裝填物體之間不能重疊,裝填方案有盡可能高的空間利用率外,且滿足給定的性能約束,使其達(dá)到最優(yōu)。本文工作是在國家自然科學(xué)基金資助下研究加權(quán)圓集布局問題,資助項(xiàng)目是復(fù)雜性能驅(qū)動(dòng)的兩類布局問題分治與階梯式優(yōu)化理論與方法研究,編號(hào)為61272294。到目前為止,國內(nèi)外專家提出了許多有效方法,如啟發(fā)式方法、演化方法,人機(jī)交互方法和它們的結(jié)合方法等,但其求解精度的提高仍然需要進(jìn)一步探索。為此,本文基于物理學(xué)中彈性勢(shì)能原理,將自適應(yīng)梯度法與王魯達(dá)采樣機(jī)制及非同構(gòu)布局模式的構(gòu)造結(jié)合起來,提出一種兩階段求解的優(yōu)化機(jī)理和方法。其主要?jiǎng)?chuàng)新如下:1.針對(duì)矩形容器的加權(quán)圓集布局問題,構(gòu)造出了系統(tǒng)的彈性勢(shì)能函數(shù)。其思想是通過預(yù)估矩形容器的尺寸,定義矩形容器與待布圓之間、待布圓與待布圓之間的嵌入度,進(jìn)而基于嵌入度構(gòu)造出系統(tǒng)的彈性勢(shì)能函數(shù)。2.針對(duì)矩形容器的加權(quán)圓集布局問題,提出了一種兩階段的自適應(yīng)擬物梯度優(yōu)化方法。在第一階段,其能量函數(shù)是彈性勢(shì)能與權(quán)距和的線性函數(shù),并將步長(zhǎng)變?yōu)樽赃m應(yīng)。提出的方法提高了收斂速度。權(quán)距和被作為彈性勢(shì)能的一部分,圓形物被抽象為一個(gè)個(gè)帶“磁性”的小球,其相互之間吸引力大小取決于權(quán)矩陣系數(shù),這些使梯度迭代朝著期望的目標(biāo)優(yōu)化。通過第二階段的微調(diào)使準(zhǔn)可行解變?yōu)闈M足不干涉條件的可行解。實(shí)驗(yàn)證明此法能明顯減小加權(quán)距離之和,并使布局更為緊湊。3.針對(duì)矩形容器的加權(quán)圓集布局問題,提出一種基于Wang_Landau采樣的兩階段全局優(yōu)化方法。此方法改進(jìn)了第一階段中系統(tǒng)的能量函數(shù),并通過構(gòu)造非同構(gòu)的布局模式和WL采樣的隨機(jī)行走使系統(tǒng)的態(tài)密度接近其真實(shí)數(shù)值,由此提高了算法的準(zhǔn)可行解全局搜索能力與穩(wěn)定性。數(shù)值實(shí)驗(yàn)表明了提出的方法的可行性、有效性和穩(wěn)定性。本文以VLSI布局設(shè)計(jì)為背景,充分利用給定數(shù)學(xué)模型的已知信息提出了一種兩階段的優(yōu)化算法,并通過WL采樣以提高全局搜索能力,使加權(quán)距離之和與包絡(luò)面積得到協(xié)同優(yōu)化。其結(jié)果表明這兩個(gè)優(yōu)化目標(biāo)的求解精度都優(yōu)于已有文獻(xiàn)中的方法。希望本文方法能為設(shè)計(jì)者提供參考。
[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.
【學(xué)位授予單位】：湘潭大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TN47

【參考文獻(xiàn)】

相關(guān)期刊論文 前3條

1 吳軍;李建;胡永泉;;求解TSP問題的擬人算法[J];計(jì)算機(jī)系統(tǒng)應(yīng)用;2011年04期

2 唐堅(jiān)剛;劉叢;張麗紅;;基于改進(jìn)遺傳算法的不規(guī)則圖形排樣[J];計(jì)算機(jī)工程;2010年21期

3 季美;肖人彬;;基于蟻群算法的帶平衡約束矩形布局問題的啟發(fā)式求解[J];計(jì)算機(jī)應(yīng)用;2010年11期

相關(guān)碩士學(xué)位論文 前2條

1 謝艷芳;求解加權(quán)圓集布局問題的啟發(fā)式演化算法研究[D];湘潭大學(xué);2012年

2 石巖;基于遺傳模擬退火算法的二維不規(guī)則多邊形排樣問題[D];西北工業(yè)大學(xué);2007年

，

本文編號(hào)：1831113