最小延時(shí)問題的并行混合元啟發(fā)式算法

發(fā)布時(shí)間：2020-08-07 23:38

【摘要】：最小延時(shí)問題是旅行商問題的變體,目的是求解路線中所有客戶的累計(jì)等待時(shí)間,最小延時(shí)問題相比于旅行商問題更難以解決。目前的求解方法,只能在客戶數(shù)量較小時(shí)具有較高的性能,當(dāng)客戶數(shù)量變大時(shí)算法很難兼顧運(yùn)行時(shí)間與求解質(zhì)量�；谏鲜鰡栴},對(duì)如何在較短時(shí)間內(nèi)獲得大數(shù)據(jù)量最小延時(shí)問題的優(yōu)質(zhì)解這一問題進(jìn)行以下研究。1.對(duì)于大數(shù)據(jù)量的最小延時(shí)問題,目前主要使用元啟發(fā)式算法求解,在此基礎(chǔ)上提出一種混合元啟發(fā)式算法。將遺傳算法與變鄰域搜索算法細(xì)粒度結(jié)合,在遺傳算法的框架內(nèi)實(shí)現(xiàn)變鄰域搜索。當(dāng)算法陷入局部最優(yōu)解時(shí),可以在遺傳算法的交叉過程中改變子代染色體的鄰域結(jié)構(gòu);并對(duì)遺傳算法的變異過程進(jìn)行改進(jìn),子代染色體可以在增加多樣性的同時(shí)有較大概率發(fā)生優(yōu)化。然后對(duì)算法進(jìn)行數(shù)據(jù)預(yù)處理,通過為每個(gè)染色體構(gòu)建基因節(jié)點(diǎn)索引列表,降低生成子代染色體的時(shí)間復(fù)雜度。2.為了進(jìn)一步加快算法運(yùn)行,使用GPU實(shí)現(xiàn)算法的并行化,并根據(jù)GPU運(yùn)行特點(diǎn)對(duì)并行算法做出改進(jìn)。將并行算法的交叉與變異過程以線程束為單位分開同步運(yùn)行,每個(gè)線程具有固定的染色體選取位置與生成位置。算法整體上以線程塊為單位并行運(yùn)行,以保證并行算法避免產(chǎn)生線程發(fā)散問題并且減少線程通信開銷,同時(shí)實(shí)現(xiàn)染色體的動(dòng)態(tài)選擇。此外將算法與擾動(dòng)機(jī)制相結(jié)合,增強(qiáng)并行算法全局搜索能力,并使用多重改進(jìn)方式生成最終解。通過上述方法進(jìn)一步提升算法性能。為驗(yàn)證算法的實(shí)際運(yùn)行情況,對(duì)算法進(jìn)行對(duì)比實(shí)驗(yàn),測(cè)試數(shù)據(jù)的節(jié)點(diǎn)個(gè)數(shù)從51到10150不等。實(shí)驗(yàn)結(jié)果表明,提出的算法在CPU環(huán)境中,相對(duì)于其它元啟發(fā)式算法,可以在較短的時(shí)間內(nèi)取得優(yōu)質(zhì)解;在CPU-GPU環(huán)境中,當(dāng)數(shù)據(jù)規(guī)模較大時(shí),并行算法可以取得明顯的加速效果,數(shù)據(jù)規(guī)模越大,加速效果越明顯。并且該并行算法相較于實(shí)驗(yàn)中其它的并行算法,具有更好的性能。因此,對(duì)于大數(shù)據(jù)量的最小延時(shí)問題,并行混合元啟發(fā)式算法可以在相對(duì)較短的時(shí)間內(nèi)獲得優(yōu)質(zhì)解。
【學(xué)位授予單位】：河北大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP301.6
【圖文】：

基本圖,遍歷,閉環(huán)