發(fā)布時間：2020-07-22 13:42

【摘要】：各種經(jīng)典、元啟發(fā)式約束求解算法在求解NP難題(NP-hard)時的性能通常取決于其參數(shù)配置。事實上,為一個算法配置一個合適的參數(shù)一直以來都被認(rèn)為是一個重要的任務(wù),這就給每個算法設(shè)計者和用戶留下了一個問題:如何正確配置算法參數(shù)?在過去,人們一直使用手動方式進(jìn)行參數(shù)配置,通過對各種算法的研究發(fā)現(xiàn),手動處理參數(shù)事實上是個很復(fù)雜的問題,需要不斷在運(yùn)行過程中改變參數(shù),開銷大量的時間去測試程序以使之達(dá)到理想效果。這無疑是件很麻煩的事情,既浪費(fèi)人力、物力、財力,也給程序員的編程帶來了困擾。而且通過經(jīng)驗法或者試錯法來進(jìn)行優(yōu)化,不僅耗時耗力還很容易出錯,有時,它通常還會導(dǎo)致不同算法的不均勻優(yōu)化。此外,通過試錯法優(yōu)化過度依賴直覺和算法開發(fā)者的經(jīng)驗,而該方法難以和嚴(yán)格的數(shù)學(xué)證明對應(yīng)起來,因此手動參數(shù)配置不具有推廣性。近些年,參數(shù)優(yōu)化算法逐漸成為算法發(fā)展過程的重要組成部分。許多高性能算法都具有眾多參數(shù),參數(shù)配置對控制算法行為有重要影響,特別對于難解優(yōu)化問題的求解算法尤是如此。尋找啟發(fā)式算法性能優(yōu)化的參數(shù)配置通常需要耗費(fèi)相當(dāng)大的開銷。在多數(shù)情況下,參數(shù)配置都是以繁瑣復(fù)雜的手工操作進(jìn)行,對于配置人員的素質(zhì)要求極高,因此自動化參數(shù)配置研究具有重要的實用意義。不僅如此,算法自動配置還有如下優(yōu)點(diǎn),它能夠減少開發(fā)時間和人為的主動干預(yù);能夠為算法設(shè)計提供更加有力的技術(shù)支持;能夠利用計算能力探索算法設(shè)計空間;能夠為更高層次的任務(wù)釋放人類的創(chuàng)造力;能夠為算法設(shè)計者在設(shè)計程序時提供幫助。配置復(fù)雜算法參數(shù)是一個高度勞動密集型的工作,消耗整體開發(fā)時間的很大一部分。使用算法自動配置方法可以顯著節(jié)省時間,甚至得到潛在的更好結(jié)果。在比較啟發(fā)式算法性能時的核心問題是:如何使算法在本質(zhì)上更勝一籌,該算法的成功原因是開發(fā)人員更成功地優(yōu)化了其參數(shù)。算法的自動配置方法可以減輕不公平比較這個問題,從而促進(jìn)更有意義的比較研究。復(fù)雜啟發(fā)式算法求解困難實例的能力往往取決于參數(shù)的合適配置。而用戶往往很少了解有關(guān)于算法參數(shù)配置對其性能的影響,因此簡單地使用默認(rèn)配置。即使算法已經(jīng)經(jīng)過標(biāo)準(zhǔn)的基準(zhǔn)組精心優(yōu)化,默認(rèn)配置可能不是遇到的特定問題的實例的最佳配置,算法也就不能呈現(xiàn)最佳性能。算法的自動配置方法可以以一種根本性的便捷的方式改善算法性能。本文首先介紹了算法配置,算法配置問題的定義和相關(guān)概念,接下來又介紹了解決算法配置問題的一些方法,主要進(jìn)行了兩個方面的研究:(1)深入研究了目前流行的并有重要影響的算法自動配置參數(shù)的軟件irace。使用irace軟件為acotsp程序自動的配置參數(shù),通過對參數(shù)在不同的配置下得到的結(jié)果進(jìn)行細(xì)致的分析,相互比較,使得我們對算法自動配置有了更深一步的理解。(2)基于流行的ParamlLS算法配置框架,進(jìn)行了約束求解器級別的算法自動配置的嘗試,實驗結(jié)果表明,約束求解器級別的算法自動配置對于約束求解效率提升明顯。當(dāng)然,約束求解算法以及約束求解器的自動配置還處于一個比較初級的水平,未來希望能對于約束求解算法進(jìn)行更為深入的研究,從算法自動配置的角度為研究高效約束求解算法提供一種可能。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：TP301.6
【圖文】：

實驗結(jié)果

第 3 章 基于 irace 的約束求解算法自動配置在第二次迭代結(jié)束后，軟件挑選出 26 個候選配置，并對候選配置各個參數(shù)進(jìn)行描述，還生成了 2 個精英候選配置。如圖 3.4

第 3 章 基于 irace 的約束求解算法自動配置在第三次迭代結(jié)束后，軟件挑選出 6 個候選配置，并對候選配置各個參數(shù)進(jìn)行描述，還生成了 4 個精英候選配置。如圖 3.5

【相似文獻(xiàn)】

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

1 李康樂;;算法“塑造世界”客觀嗎[J];中國報業(yè);2018年11期

2 ;聚焦核心素養(yǎng)案例研討專題二:體驗編程計算,初步了解算法[J];中國信息技術(shù)教育;2017年08期

3 李亞娟;劉建貞;張興剛;鄧重陽;;結(jié)合科研的計算機(jī)輔助幾何設(shè)計教學(xué)[J];數(shù)學(xué)學(xué)習(xí)與研究;2017年17期

4 何克晶;張星明;鄭運(yùn)平;;算法設(shè)計與分析課程全方位實踐教學(xué)改革探索[J];計算機(jī)教育;2017年02期

5 李勇;;基于實踐性教學(xué)的《算法設(shè)計與分析》教學(xué)研究[J];曲靖師范學(xué)院學(xué)報;2015年06期

6 張遠(yuǎn)平;邱麗娜;;在算法設(shè)計與分析課程教學(xué)中融入計算思維[J];價值工程;2016年08期

7 秦丹;;算法設(shè)計與分析教學(xué)常見問題分析[J];電腦知識與技術(shù);2014年24期

8 黃如兵;楊鶴標(biāo);;算法設(shè)計與分析課程的教學(xué)與實踐探索與研究[J];科教文匯(上旬刊);2015年03期

9 紀(jì)穎;;算法設(shè)計與分析課程教學(xué)改革探討[J];黑龍江教育學(xué)院學(xué)報;2014年08期

10 李秦;;建構(gòu)主義教學(xué)模式與算法設(shè)計與分析課程教學(xué)[J];甘肅科技;2013年24期

相關(guān)會議論文 前10條

1 王輝;劉治昌;;用一種新算法設(shè)計的安全系統(tǒng)[A];2007年中國智能自動化會議論文集[C];2007年

2 雷詠梅;;橢圓曲線密碼體制的算法設(shè)計與實現(xiàn)[A];西部大開發(fā) 科教先行與可持續(xù)發(fā)展——中國科協(xié)2000年學(xué)術(shù)年會文集[C];2000年

3 韓進(jìn)宏;張先峰;王運(yùn)凱;;表面粗糙度頻譜分析C++算法設(shè)計[A];2007'中國儀器儀表與測控技術(shù)交流大會論文集（二）[C];2007年

4 高文超;孫宇清;韓冬雪;;一種改進(jìn)的素數(shù)尋找問題的算法設(shè)計與實現(xiàn)[A];中國電子學(xué)會第十六屆信息論學(xué)術(shù)年會論文集[C];2009年

5 楊俊;關(guān)旭東;;板形控制液壓彎輥系統(tǒng)的特性分析與控制算法設(shè)計[A];1996中國控制與決策學(xué)術(shù)年會論文集[C];1996年

6 黃翔東;李海亮;王玲;;光時域反射儀的事件檢測算法設(shè)計[A];第六屆全國信號和智能信息處理與應(yīng)用學(xué)術(shù)會議論文集[C];2012年

7 徐子珊;;《算法設(shè)計與分析》課程中的工程教育[A];2005年全國理論計算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

8 李皓;羅熊;;云存儲部署優(yōu)化的進(jìn)化算法設(shè)計[A];2013年中國智能自動化學(xué)術(shù)會議論文集（第三分冊）[C];2013年

9 宋琦;陳璞;;有限元分析中結(jié)構(gòu)修改的算法設(shè)計[A];北京力學(xué)會第18屆學(xué)術(shù)年會論文集[C];2012年

10 楊利容;;用優(yōu)化算法設(shè)計雙工器[A];中國航海學(xué)會通信導(dǎo)航專業(yè)委員會2005年學(xué)術(shù)年會論文集[C];2005年

相關(guān)重要報紙文章 前8條

1 趙丹;大數(shù)據(jù)算法的困境[N];學(xué)習(xí)時報;2017年

2 ;算法設(shè)計的策略[N];電腦報;2003年

3 武衛(wèi);通過算法來思考世界[N];財會信報;2018年

4 陸峰;大數(shù)據(jù)健康發(fā)展需要新機(jī)制護(hù)航[N];學(xué)習(xí)時報;2019年

5 李健 周勝利;懂算法才能打“算法戰(zhàn)”[N];解放軍報;2019年

6 本報記者 霍光;從算法設(shè)計角度推進(jìn)網(wǎng)絡(luò)節(jié)能[N];中國計算機(jī)報;2012年

7 林東;迎接算法決定戰(zhàn)法的時代[N];解放軍報;2018年

8 胡捷遞　記者 姜雪松;“計算機(jī)奧運(yùn)會”將在哈舉行[N];哈爾濱日報;2010年

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

1 王子玉;網(wǎng)絡(luò)異常檢測算法研究[D];清華大學(xué);2017年

2 陳培;探測復(fù)雜疾病臨界點(diǎn)的算法[D];華南理工大學(xué);2018年

3 李瑩玉;基于分布式ADMM算法的無線網(wǎng)絡(luò)資源管理與大數(shù)據(jù)分析[D];西安電子科技大學(xué);2018年

4 蔣海青;開放式低碳選址—路徑模型及其算法研究[D];浙江工業(yè)大學(xué);2019年

5 張雪;圖像處理中的若干非凸建模，算法及應(yīng)用[D];上海交通大學(xué);2017年

6 王普;多標(biāo)記學(xué)習(xí)算法研究及在生物醫(yī)學(xué)數(shù)據(jù)挖掘中的應(yīng)用[D];中國科學(xué)院大學(xué)(中國科學(xué)院深圳先進(jìn)技術(shù)研究院);2017年

7 陳寧濤;基于二分技術(shù)的高效算法設(shè)計及其應(yīng)用[D];華中科技大學(xué);2006年

8 張磊;約束優(yōu)化算法的關(guān)鍵技術(shù)研究及應(yīng)用[D];哈爾濱工程大學(xué);2016年

9 孫賀;算法設(shè)計中的若干前沿問題[D];復(fù)旦大學(xué);2009年

10 劉院英;社會網(wǎng)絡(luò)影響最大化方法研究[D];燕山大學(xué);2017年

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

1 吳云鵬;約束求解算法自動配置研究[D];吉林大學(xué);2019年

2 夏志雄;動力電池管理單元及其SOC估算算法的研究與實現(xiàn)[D];武漢理工大學(xué);2018年

3 初星漢;基于蟻群算法的專家抽取系統(tǒng)設(shè)計與實現(xiàn)[D];大連理工大學(xué);2018年

4 劉凌云;基于Q-學(xué)習(xí)算法的序列決策模型研究[D];河北大學(xué);2019年

5 李鵬清;基于SimRank及密度的聚類算法[D];廣西師范大學(xué);2019年

6 張煜;強(qiáng)化學(xué)習(xí)中基于函數(shù)逼近的多步統(tǒng)一算法研究[D];浙江大學(xué);2019年

7 房永峰;基于深度學(xué)習(xí)的牲畜目標(biāo)檢測與跟蹤算法研究[D];中國科學(xué)技術(shù)大學(xué);2019年

8 忻曉雯;LTE系統(tǒng)資源分配的算法研究[D];上海交通大學(xué);2017年

9 楊欣;基于正交化學(xué)反應(yīng)優(yōu)化算法的社團(tuán)檢測研究與實現(xiàn)[D];河南大學(xué);2018年

10 曾鳳華;護(hù)士周排班算法研究及其系統(tǒng)實現(xiàn)[D];華南理工大學(xué);2018年

本文編號：2765890