在過去十年中,得益于大規(guī)模并行計算架構(gòu)的廣泛部署,人們可利用的計算資源得到了極大提升。如今,在為復(fù)雜計算問題設(shè)計求解器時,設(shè)計并行求解機制以有效利用并行計算平臺已變得越來越重要。然而,人工設(shè)計并行求解器仍然是一項艱巨的工作。作為一種新的并行求解器設(shè)計范式,面向并行啟發(fā)式算法組的自動構(gòu)建技術(shù)（Automatic Construction of Parallel Heuristic-algorithm Portfolios,簡稱ACPP）在近年來逐漸成為研究熱點。ACPP技術(shù)基于一組訓(xùn)練問題樣例和一個算法配置空間自動構(gòu)建出包含多個成員算法的并行算法組（Parallel Algorithm Portfolios,簡稱PAP）。由于PAP構(gòu)建過程完全自動化,因而人力成本得到大幅減低。此外,PAP在實際運行時各成員算法相互獨立地并行運行,這使得PAP可以無縫部署在工作站、服務(wù)器以及云計算環(huán)境下。由于具有低人力成本、易部署等優(yōu)點,ACPP技術(shù)具有良好的發(fā)展和應(yīng)用前景。然而,目前學(xué)術(shù)界對于ACPP的研究尚處于早期階段,仍存在不少痛點、盲點亟待解決。本文旨在從理論和方法層面上對ACPP技術(shù)進行進一步探... 

【文章來源】：中國科學(xué)技術(shù)大學(xué)安徽省 211工程院校 985工程院校

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

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

【部分圖文】：

圖１．１單基礎(chǔ)算法和多基礎(chǔ)算法的法配置空間

＊？??２?５００１??ｒｒ２?２?５００１??｜－［２．０??＜?＜??孟４００．?１?＞＞４００?１．５??ｌ?３００?ｇ?ｌ＾ＯＯ?ｉ．〇??ｉ：ｉｕｉ：丨：Ｌ?Ｉ：：??〇?０?１００?２００?〇?０?１００?２００??ｕ?ｉｎｓｔａｎｃｅｓ?（ｓｏｒｔｅｄ?ｂｙ?ｈａｒｄｎｅｓｓ）?ｕ?ｉｎｓｔａｎｃｅｓ?（ｓｏｒｔｅｄ?ｂｙ?ｈａｒｄｎｅｓｓ）??（ｃ）?ＬＫＨ－ｕｎｉｆｏｒｍ－４００?（ｄ）?ＬＫＨ－ｕｎｉｆｏｒｍ－１０００??圖２．１各場景下性能矩陣的可視化表示。圖中每個點表示５次運行的平均時間取以１０為??底的對數(shù)。顏色越深，時間越短。??簡稱ＰＡＲ－１０）。對ＰＡＲ－１０而言，值越小越好。表２．１詳細總結(jié)了我們在為各場??景構(gòu)造性能矩陣時所使用的設(shè)置。圖２．１給出了各場景下性能矩陣的可視化表示，??可以看到，不同性能矩陣的數(shù)據(jù)分布差異很大，這說明我們的實驗具有較好的代??表性。??為了方便，本節(jié)剩余部分中我們將使用“ｓｐｌｉｔＰｉ｜Ｐ２”來表示我們依次從２Ｐ??中無放回地隨機選取了巧和Ａ個問題樣例分別作為訓(xùn)練樣例和測試樣例。對??于給定算法配置０，我們總是使用性能估計器在訓(xùn)練樣例上得到０的估計性能??（又叫訓(xùn)練性能），并使用０在測試樣例上的性能作為其真實性能。我們使用??ｕｎｉｆｏｒｍ＿ｅｓ＿ｅｒｒｏｒ（０）表不在０中所有算法配置上的估計誤差的最大值。最后，所??有實驗均在一個運行ＣｅｎｔＯＳ，且具有１２８ＧＢ內(nèi)存和２４個ＣＰＵ核心（２．２０ＧＨｚ，??３０ＭＢ緩存）的Ｘｅｏｎ機器上進行。??２４??

■丨?■■＿．■■■■?＇?ｉ?〇ｌ?ｉ?ｉ?ｉ?Ｉ．?ｎｌ?■?ｉ?＿?Ｊ?ｆｉ？?ｉ?ｉ?ｉ??Ｕ?ＳＵ?１Ｕ：?丨抽?ＡＵ?Ｕ?１．?Ａ?３Ｕ?＜Ｕ?＆Ｕ?ＶＪ?Ｕ?／Ｊ?？Ｊ?＆＇?Ｍ＇?Ｊｊ?Ｕ?Ｘ?Ｗ?Ｋ＇?０Ｕ?．ＵＵ?１＾．??Ｋ?Ｋ?Ｋ?Ｋ??（ｉ）?ＳＡＴｅｎｓｔｅｉｎ－ＱＣＰ?（ｊ）?ｃｌａｓｐ－ｗｅｉｇｈｔｅｄ－ｓｅｑｕｅｎｃｅ?（ｋ）?ＬＫＨ－ｕｎｉｆｏｒｍ－４００?（１）?ＬＫＨ－ｕｎｉｆｏｒｍ－１０００??圖２．４?在ＡＴ、Ｍ和Ｘ取不同值時的一致性估計誤差以及相應(yīng)的擬合結(jié)果。??Ｓ?ｕ〇?￣￣?〇？?〇，?ｆｈ?（ｕｎｃｔｉｏｎ?２：——?ｆｉｔ?ｆｕｎｃｔｉｏｎ??ｆ?ｕｔ?｜?｜?—＾?ｕａｉｃ－？ｓ．ＯＴ〇ｒ（〇ｋｉ．Ｎ）?２?■■?ｉｒａｉｎ＿？＊ａｒｒｏｒ（０Ｋ（．Ｋ）??？？?ｓ＊?ｉ．?ｔ：：Ｊ??ｆ?＼??�。浚�?ｔ?Ｉ?Ｉ?ｊ??ｊ?Ｍ?ｆ?——?ｆｉｔ?ｆｕｎｃｔｉｏｎ?｜?Ｉ?ｆｈ?ｆｕｎｃｔｉｏｎ?１．１??Ｉ?＊＊?！??ｔｎｉｎ＿ｅｉ．ｅｆＴ〇ｒ（６ｂａＢ，?ｍ）?Ｉ?Ｕ?—?ｔｒａｉｎ．？ｓ．？ｒｒｏｒｉ６ｕｔＵ），?ｍ）?ｉ?ｉ＇＇??〇｜?＾?．?－Ｊ?＾?，?Ｊ??（ａ）?ｃｌａｓｐ－ｗｅｉｇｈｔｅｄ－ｓｅｑｕｅｎｃｅ?（ｂ）?ＬＫＨ－ｕｎｉｆｏｒｍ－１０００?（ｃ）?ＬＫＨ－ｕｎｉｆｏｒｍ－４００?（ｄ）?ＳＡＴｅｎｓｔｅｉｎ－ＱＣＰ??圖２．５?在ＡＴ、Ｍ和欠取不同值時在ｆ上的估計誤差以及相應(yīng)的擬合結(jié)果。??為了驗證定理２．７是否準確地反映了一致性估計誤差


本文編號：3337723