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

實(shí)驗(yàn)結(jié)果

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 武衛(wèi);通過算法來思考世界[N];財(cái)會(huì)信報(bào);2018年

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

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

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

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

8 胡捷遞　記者 姜雪松;“計(jì)算機(jī)奧運(yùn)會(huì)”將在哈舉行[N];哈爾濱日?qǐng)?bào);2010年

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

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

2 陳培;探測(cè)復(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è)計(jì)及其應(yīng)用[D];華中科技大學(xué);2006年

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

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

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

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

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

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

3 初星漢;基于蟻群算法的專家抽取系統(tǒng)設(shè)計(jì)與實(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)檢測(cè)與跟蹤算法研究[D];中國科學(xué)技術(shù)大學(xué);2019年

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

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

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

本文編號(hào)：2765890