作為一類經(jīng)典的NP難度問題,考慮空間緊密布局的Packing問題一直在工業(yè)界和學(xué)術(shù)界有著很高的研究價值。根據(jù)容器和裝載物體形狀差異,Packing問題可以細(xì)分為很多類。深入研究了等圓Packing問題,即在二維圓形容器中裝入給定數(shù)量的半徑相等的二維圓形物體,要求容器中物體和物體、物體和容器邊界均無重疊,目標(biāo)是最小化圓形容器的半徑。本文分別針對容器內(nèi)小圓數(shù)目不超過320的小規(guī)模等圓Packing和小圓數(shù)目超過320的大規(guī)模等圓Packing問題,提出了兩種有效的算法。對于待放圓的數(shù)量小于等于320的小規(guī)模問題,提出了一種高效的擬人擬物算法。將待放圓視為彈性小球,重疊時產(chǎn)生彈性勢能,使用經(jīng)典的擬牛頓法BFGS算法,通過局部優(yōu)化策略加快計算速度;當(dāng)整體勢能達(dá)到局部最優(yōu)的時候,設(shè)計了先縮小大圓半徑再松弛的新的高效跳坑策略,使下一輪梯度下降達(dá)到一個更好的格局;如此反復(fù)迭代,直到找到一個全局最優(yōu)解。實驗結(jié)果表明,該算法在圓形物體的數(shù)量n為1到320的這320個典型算例中找到了66個比當(dāng)前國際最優(yōu)解更優(yōu)的布局方案。對于待放圓的數(shù)量較高的大規(guī)模問題,對整個系統(tǒng)進(jìn)行梯度下降的策略很難在合理時間內(nèi)得到布圖... 

【文章來源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：56 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 研究背景及意義
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 本文主要研究內(nèi)容
    1.4 論文組織結(jié)構(gòu)
2 問題描述
    2.1 數(shù)學(xué)模型
    2.2 物理模型
3 求解小規(guī)模等圓Packing問題的擬物擬人算法
    3.1 BFGS算法
    3.2 局部BFGS算法
    3.3 跳坑策略
    3.4 容器調(diào)整策略
    3.5 高效擬物擬人算法(QPQH)
    3.6 本章小結(jié)
4 基于機(jī)器學(xué)習(xí)求解大規(guī)模等圓Packing問題
    4.1 隨機(jī)梯度下降法(Stochastic gradient descent,SGD)
    4.2 隨機(jī)局部BFGS算法
    4.3 基于分組梯度下降的跳坑策略
    4.4 本章小結(jié)
5 實驗結(jié)果與分析
    5.1 參數(shù)調(diào)整
    5.2 小規(guī)模等圓Packing實驗結(jié)果
    5.3 大規(guī)模等圓Packing實驗結(jié)果
    5.4 本章小結(jié)
6 總結(jié)與展望
    6.1 總結(jié)
    6.2 展望
致謝
參考文獻(xiàn)
附錄1:攻讀碩士學(xué)位期間參與的科研項目
附錄2:攻讀碩士學(xué)位期間發(fā)表論文目錄


【參考文獻(xiàn)】：
期刊論文
[1]Packing unequal circles into a square container based on the narrow action spaces[J]. Kun HE,Mohammed DOSH,Yan JIN,Shenghao ZOU.  Science China（Information Sciences）. 2018(04)
[2]基于穴度的三維時空優(yōu)化問題的貪心調(diào)度算法[J]. 朱鵬,何琨,曹偉剛,楊歡.  計算機(jī)科學(xué)與探索. 2016(08)
[3]四維時空高效利用的裝箱調(diào)度問題及其可計算性證明[J]. 黃文奇,何琨.  計算機(jī)學(xué)報. 2013(09)
[4]三維裝箱工作的優(yōu)化調(diào)度問題[J]. 黃文奇,何琨.  華中科技大學(xué)學(xué)報(自然科學(xué)版). 2010(12)
[5]人機(jī)交互的遺傳算法及其在約束布局優(yōu)化中的應(yīng)用[J]. 錢志勤,滕弘飛,孫治國.  計算機(jī)學(xué)報. 2001(05)



本文編號：3187680