在實(shí)際生產(chǎn)生活和現(xiàn)代科學(xué)研究中存在著大量具有NP難性質(zhì)的優(yōu)化問(wèn)題,如無(wú)線通訊信號(hào)覆蓋、復(fù)雜電路設(shè)計(jì)布線、網(wǎng)絡(luò)流量控制與疏導(dǎo)、航班任務(wù)調(diào)度等問(wèn)題。這些具有NP難性質(zhì)的眾多復(fù)雜實(shí)際應(yīng)用問(wèn)題都是屬于各自領(lǐng)域中的核心和關(guān)鍵性問(wèn)題。基于計(jì)算復(fù)雜性理論的研究經(jīng)驗(yàn),計(jì)算機(jī)科學(xué)界普遍認(rèn)為對(duì)這些具有NP難性質(zhì)的復(fù)雜優(yōu)化問(wèn)題不存在多項(xiàng)式時(shí)間復(fù)雜度的完備且高效的精確求解算法。而在最近幾十年的研究中,基于非完備的啟發(fā)式優(yōu)化算法在求解許多具有NP難性質(zhì)的組合優(yōu)化問(wèn)題上表現(xiàn)出了良好的效果。也就是說(shuō),在一個(gè)相對(duì)合理的時(shí)間開銷內(nèi),一個(gè)比較優(yōu)秀的啟發(fā)式優(yōu)化算法通常能夠獲得所求問(wèn)題的優(yōu)度非常高的解。這為實(shí)際應(yīng)用領(lǐng)域出現(xiàn)的大量NP難度的復(fù)雜優(yōu)化問(wèn)題提供了現(xiàn)實(shí)解決的途徑。研究表明,上述實(shí)際案例中出現(xiàn)的大量NP難度的復(fù)雜優(yōu)化問(wèn)題均可在基于頂點(diǎn)覆蓋和線性排序問(wèn)題模型的基礎(chǔ)上建模來(lái)求解。本文首先從算法研究的理論背景、經(jīng)典求解算法框架方面系統(tǒng)梳理了啟發(fā)式優(yōu)化方法的特點(diǎn)、作用機(jī)理及其評(píng)價(jià)準(zhǔn)則。然后選取兩類經(jīng)典的且具有重要實(shí)際價(jià)值的組合優(yōu)化問(wèn)題最小權(quán)頂點(diǎn)覆蓋問(wèn)題和線性排序問(wèn)題(包括帶累積成本的線性排序問(wèn)題)作為參考研究對(duì)象,分別基于其各自問(wèn)題的本質(zhì)為它們?cè)O(shè)計(jì)了四種高效的啟發(fā)式優(yōu)化求解算法,并借助在公開基準(zhǔn)算例上的計(jì)算實(shí)驗(yàn)對(duì)提出的算法進(jìn)行了分析和評(píng)價(jià)。本文的主要貢獻(xiàn)包括:(1)針對(duì)最小權(quán)頂點(diǎn)覆蓋問(wèn)題提出了一種高效的多啟動(dòng)迭代禁忌搜索算法(MS-ITS算法)。MS-ITS算法包括三個(gè)主要子算法和一個(gè)調(diào)節(jié)機(jī)制:初始解構(gòu)造算法、禁忌搜索算法、擾動(dòng)算法及多啟動(dòng)迭代機(jī)制。初始解構(gòu)造算法通過(guò)引入隨機(jī)和貪心兩種策略來(lái)選擇若干關(guān)鍵頂點(diǎn)構(gòu)成合法初始解。禁忌搜索算法通過(guò)引入兩種特性即基于同時(shí)多點(diǎn)移動(dòng)的鄰域結(jié)構(gòu)并與之相適應(yīng)的基于增量計(jì)算的快速鄰域評(píng)估機(jī)制和雙表禁忌策略,算法在每個(gè)當(dāng)前解作鄰域變換中既能探索更大的鄰域空間又能快速的產(chǎn)生局部最優(yōu)解。擾動(dòng)算法引入一個(gè)基于頂點(diǎn)權(quán)值和關(guān)聯(lián)度信息的擾動(dòng)策略對(duì)局部最優(yōu)解實(shí)施變換。使得算法搜索能從一個(gè)局部最優(yōu)解慢慢找到優(yōu)度更好的局部最優(yōu)解。另外引入了多啟動(dòng)迭代機(jī)制擴(kuò)展了算法的全局搜索能力。使用了最小權(quán)頂點(diǎn)覆蓋問(wèn)題的公開算例集(SPI、MPI和LPI)上的共126個(gè)基準(zhǔn)算例進(jìn)行了測(cè)試,多啟動(dòng)迭代禁忌搜索算法能夠匹配約92%算例的歷史最好結(jié)果并改進(jìn)了44個(gè)算例的當(dāng)前最好上界。(2)針對(duì)最小權(quán)頂點(diǎn)覆蓋問(wèn)題提出了一種更為高效的混合進(jìn)化算法(HGA算法)。HGA算法混合了基于多啟動(dòng)迭代禁忌搜索算法MS-ITS和基于群體解操作的遺傳算法GA。首先,通過(guò)引入一個(gè)基于GRASP思想的初始解生成策略來(lái)構(gòu)造具有一定質(zhì)量和分散性保證的初始種群,然后算法開始周期性迭代求解。在每次迭代周期中,通過(guò)引入基于公共基因繼承機(jī)制的交叉算子對(duì)選擇的兩個(gè)隨機(jī)父本解進(jìn)化產(chǎn)生優(yōu)質(zhì)的新子代個(gè)體。再通過(guò)多啟動(dòng)迭代禁忌搜索算法使得當(dāng)前優(yōu)質(zhì)的新子代個(gè)體從現(xiàn)有格局逐步變換到一個(gè)更優(yōu)的局部最優(yōu)解上,最后通過(guò)引入一個(gè)精英值打分機(jī)制來(lái)進(jìn)行種群更新以使得種群中個(gè)體保持多樣性的同時(shí)種群中的局部最優(yōu)解的質(zhì)量更好。其中多啟動(dòng)迭代禁忌搜索算法作為HGA算法的局部搜索算法強(qiáng)調(diào)算法的集中性搜索能力以找到質(zhì)量更優(yōu)的局部最優(yōu)解,基于群體解的遺傳進(jìn)化算法來(lái)加強(qiáng)整個(gè)算法的疏散性搜索能力達(dá)到全局尋優(yōu)。使用了最小權(quán)頂點(diǎn)覆蓋問(wèn)題的公開算例集(SPI、MPI、LPI)和另外的隨機(jī)生成的大規(guī)模算例集RLPI上的共176個(gè)基準(zhǔn)算例進(jìn)行了測(cè)試,在同時(shí)比較MS-ITS算法的結(jié)果并引入公開的ILP求解器Gurobi的結(jié)果對(duì)比實(shí)驗(yàn)中,基于全部176個(gè)MWVCP測(cè)試算例上,HGA算法能夠找到其中27個(gè)算例的最好上界并達(dá)到剩余所有算例的當(dāng)前最好解或最優(yōu)解。(3)針對(duì)帶累積成本的線性排序問(wèn)題提出了一個(gè)有效的混合進(jìn)化算法(FBLSE算法)帶累積成本的線性排序問(wèn)題是線性排序問(wèn)題的一種特殊演變形式。其解序列上的每個(gè)子項(xiàng)又包含了一個(gè)非線性的累積代價(jià),該問(wèn)題表現(xiàn)出了更高的計(jì)算復(fù)雜性。FBLS-E算法融合了一個(gè)Memetic框架和一個(gè)基于問(wèn)題結(jié)構(gòu)新提出的局部搜索算法。首先針對(duì)帶累積成本的線性排序問(wèn)題的內(nèi)在結(jié)構(gòu)提出了一個(gè)forward-backward鄰域結(jié)構(gòu),該鄰域結(jié)構(gòu)擴(kuò)展了當(dāng)前解的鄰域搜索空間,為每次鄰域動(dòng)作能夠從一個(gè)當(dāng)前解變換到更好的鄰居解提供了更多的機(jī)會(huì)。由此,同時(shí)引入了一個(gè)基于多次SWAP動(dòng)作的快速鄰域評(píng)估方法以提高在較大鄰域空間搜索上對(duì)解的評(píng)估效率。以此為基礎(chǔ),為帶累積成本的線性排序問(wèn)題設(shè)計(jì)了一個(gè)基于forward-backward鄰域結(jié)構(gòu)的高效局部搜索算法FBLS。在算法的每次迭代中,首先初始解構(gòu)造算法融合隨機(jī)初始解方法和局部搜索算法FBLS來(lái)產(chǎn)生高質(zhì)量的初始種群。然后引入一個(gè)基于序列再融合的操作算子對(duì)兩個(gè)隨機(jī)選擇的父本進(jìn)化以產(chǎn)生優(yōu)度較好的新子代解。接著通過(guò)局部搜索算法FBLS對(duì)新子代優(yōu)化以產(chǎn)生更好的局部最優(yōu)解。通過(guò)引入基于解的質(zhì)量替換標(biāo)準(zhǔn)的種群更新策略來(lái)維護(hù)算法迭代中種群的多樣性。使用了帶累積成本的線性排序問(wèn)題的118個(gè)公開基準(zhǔn)算例進(jìn)行了測(cè)試,FBLS-E算法在很短的時(shí)間內(nèi)能匹配絕大部分算例的最優(yōu)解,并找到了另外46個(gè)算例的最新上界。(4)針對(duì)經(jīng)典線性排序問(wèn)題提出了一個(gè)基于多父本再融合操作的改進(jìn)的混合進(jìn)化算法(MPM算法)MPM算法融合了一個(gè)Memetic進(jìn)化框架和一個(gè)有效的局部搜索算法。首先,通過(guò)隨機(jī)初始解生成策略和局部?jī)?yōu)化操作相融合的種群初始化構(gòu)造算法來(lái)產(chǎn)生由局部最優(yōu)解組成的初始種群。然后算法開始周期性迭代求解。在每次迭代周期中,先通過(guò)引入一個(gè)基于解距離特征的父本選擇策略在考慮種群多樣性的條件下進(jìn)行多父本選擇。在此基礎(chǔ)上提出了一個(gè)基于多父本操作的再融合交叉算子對(duì)多個(gè)父本進(jìn)化操作以產(chǎn)生盡可能繼承更多父本優(yōu)秀特征的新子代解,以此保證新產(chǎn)生的解的優(yōu)異性。接著使用局部搜索算法對(duì)新子代進(jìn)一步優(yōu)化產(chǎn)生更好的局部最優(yōu)解。最后通過(guò)引入一個(gè)基于種群解的質(zhì)量和健康度的打分策略來(lái)更新種群,以維護(hù)進(jìn)化過(guò)程中種群的多樣性,以此進(jìn)一步增強(qiáng)算法的全局尋優(yōu)能力。使用了經(jīng)典線性排序問(wèn)題的8組共484個(gè)公開算例進(jìn)行了測(cè)試,MPM算法能成功匹配所有最優(yōu)解已知算例的最好結(jié)果,并在另外255個(gè)最優(yōu)解未知的困難算例上,能成功匹配其中的163個(gè)當(dāng)前最好解,并找到了其余66個(gè)算例的最新下界。以上研究成果表明,本文提出的多啟動(dòng)迭代禁忌搜索算法、混合進(jìn)化算法及改進(jìn)的混合進(jìn)化算法都是求解對(duì)應(yīng)頂點(diǎn)覆蓋和線性排序類NP難優(yōu)化問(wèn)題的有效的啟發(fā)式算法。通過(guò)本課題的研究,加深了對(duì)啟發(fā)式優(yōu)化算法求解NP難度的組合優(yōu)化問(wèn)題的理解。
【學(xué)位單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2019
【中圖分類】：TP18;O224
【文章目錄】：摘要
Abstract
1 緒言
1.1 選題來(lái)源與研究目的
1.2 本文研究背景與意義
1.3 主要研究?jī)?nèi)容及組織
2 組合優(yōu)化及啟發(fā)式優(yōu)化方法簡(jiǎn)析
2.1 關(guān)于組合優(yōu)化問(wèn)題
2.2 組合優(yōu)化問(wèn)題的計(jì)算復(fù)雜性
2.3 啟發(fā)式優(yōu)化經(jīng)典算法簡(jiǎn)析
2.4 啟發(fā)式算法的評(píng)價(jià)準(zhǔn)則
2.5 本章小結(jié)
3 求解最小權(quán)頂點(diǎn)覆蓋問(wèn)題的多啟動(dòng)迭代禁忌搜索算法
3.1 最小權(quán)頂點(diǎn)覆蓋問(wèn)題概述
3.2 MWVCP問(wèn)題的多啟動(dòng)迭代禁忌搜索優(yōu)化算法
3.3 計(jì)算結(jié)果及與其他參考算法的比較
3.4 實(shí)驗(yàn)分析與討論
3.5 本章小結(jié)
4 求解最小權(quán)頂點(diǎn)覆蓋問(wèn)題的混合進(jìn)化算法
4.1 混合進(jìn)化算法的基本原理
4.2 MWVCP問(wèn)題的混合進(jìn)化優(yōu)化算法
4.3 計(jì)算結(jié)果及與其他參考算法的比較
4.4 實(shí)驗(yàn)分析與討論
4.5 本章小結(jié)
5 求解帶累積成本的線性排序問(wèn)題的混合進(jìn)化算法
5.1 帶累積成本的線性排序問(wèn)題概述
5.2 帶累積成本的線性排序問(wèn)題的研究現(xiàn)狀
5.3 帶累積成本的線性排序問(wèn)題模型
5.4 LOPCC問(wèn)題的混合進(jìn)化優(yōu)化算法
5.5 計(jì)算結(jié)果及與其他參考算法的比較
5.6 本章小結(jié)
6 求解經(jīng)典線性排序問(wèn)題的改進(jìn)的混合進(jìn)化算法
6.1 線性排序問(wèn)題的研究現(xiàn)狀
6.2 經(jīng)典線性排序問(wèn)題模型
6.3 LOP問(wèn)題的改進(jìn)的混合進(jìn)化優(yōu)化算法
6.4 計(jì)算結(jié)果及與其他參考算法的比較
6.5 分析和討論
6.6 本章小結(jié)
7 總結(jié)及展望
7.1 本文總結(jié)及研究成果
7.2 主要?jiǎng)?chuàng)新點(diǎn)
7.3 未來(lái)探索的著力點(diǎn)
參考文獻(xiàn)
致謝
附錄1 攻讀學(xué)位期間發(fā)表論文目錄
附錄2 攻讀博士學(xué)位期間參與的科研項(xiàng)目
【相似文獻(xiàn)】
相關(guān)期刊論文 前10條
1 李剛剛;魯習(xí)文;;目標(biāo)為最小化工件運(yùn)輸時(shí)間和的單臺(tái)機(jī)器帶一個(gè)維修時(shí)間段的排序問(wèn)題的一個(gè)改進(jìn)算法[J];運(yùn)籌學(xué)學(xué)報(bào);2019年04期
2 茍燕;戴秦;張新功;;具有時(shí)間與位置相關(guān)的兩類平行機(jī)排序問(wèn)題[J];運(yùn)籌學(xué)學(xué)報(bào);2019年04期
3 冉金玉;張新功;;總加權(quán)誤工損失的兩個(gè)代理單機(jī)排序問(wèn)題[J];湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2019年01期
4 韓飛;;高中數(shù)學(xué)一道數(shù)列典型題解法的探究[J];數(shù)學(xué)學(xué)習(xí)與研究;2016年23期
5 豆俊梅;孫彩賢;;單機(jī)排序問(wèn)題的研究[J];數(shù)學(xué)學(xué)習(xí)與研究;2017年24期
6 胡覺亮;楊佳雯;蘇曉彤;董建明;;機(jī)器帶周期性維護(hù)時(shí)段的加工與運(yùn)輸協(xié)同排序問(wèn)題[J];浙江理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年06期
7 仲維亞;馬曉茹;;帶有運(yùn)輸且加工具有靈活性的無(wú)等待流水作業(yè)排序問(wèn)題[J];運(yùn)籌學(xué)學(xué)報(bào);2016年04期
8 隋楠;羅成新;;具有維護(hù)活動(dòng)及公共工期的加工時(shí)間依賴資源的單機(jī)排序問(wèn)題[J];沈陽(yáng)航空航天大學(xué)學(xué)報(bào);2016年06期
9 林浩;何程;;關(guān)于工期分配與加權(quán)誤工數(shù)的雙指標(biāo)排序問(wèn)題（英文）[J];工程數(shù)學(xué)學(xué)報(bào);2017年01期
10 趙傳立;張蕾;;帶有交貨期窗口和加工時(shí)間可控的排序問(wèn)題[J];沈陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年04期
相關(guān)博士學(xué)位論文 前10條
1 周淘晴;最小權(quán)頂點(diǎn)覆蓋和線性排序問(wèn)題的求解算法研究[D];華中科技大學(xué);2019年
2 李融奇;在線排序和批排序問(wèn)題研究[D];浙江大學(xué);2018年
3 沈佳煜;不確定情形下若干排序問(wèn)題的研究[D];南京理工大學(xué);2017年
4 高園;新型排序問(wèn)題的計(jì)算復(fù)雜性研究[D];鄭州大學(xué);2018年
5 殷娜;依賴于資源分配的排序問(wèn)題研究[D];上海大學(xué);2015年
6 李好好;若干排序問(wèn)題研究[D];浙江大學(xué);2014年
7 王吉波;工件加工時(shí)間可變的現(xiàn)代排序問(wèn)題[D];大連理工大學(xué);2005年
8 羅潤(rùn)梓;平行機(jī)半在線排序問(wèn)題[D];上海大學(xué);2005年
9 季敏;當(dāng)代工業(yè)中的若干排序問(wèn)題研究[D];浙江大學(xué);2006年
10 葉德仕;通訊網(wǎng)絡(luò)中排序問(wèn)題的若干在線和高性能算法[D];浙江大學(xué);2005年
相關(guān)碩士學(xué)位論文 前10條
1 李紅;多AGV的多任務(wù)分配與路徑規(guī)劃研究[D];南京郵電大學(xué);2019年
2 陳秋宏;與誤工相關(guān)的雙代理單機(jī)排序問(wèn)題研究[D];重慶師范大學(xué);2019年
3 馬亞杰;工件具有相似加工時(shí)長(zhǎng)的排序問(wèn)題[D];湖南師范大學(xué);2019年
4 叢穩(wěn);工件可拒絕的單機(jī)重新排序問(wèn)題[D];鄭州大學(xué);2019年
5 曹移林;平行多階段作業(yè)排序問(wèn)題的研究[D];華東理工大學(xué);2019年
6 康宇紅;具有錯(cuò)位限制的重新排序問(wèn)題研究[D];重慶師范大學(xué);2019年
7 姜曉燕;MapReduce排序問(wèn)題的若干算法研究[D];北京郵電大學(xué);2019年
8 王亞男;具有退化維護(hù)和資源分配的單機(jī)排序問(wèn)題[D];沈陽(yáng)師范大學(xué);2019年
9 李石;與資源相關(guān)加工時(shí)間可變的單機(jī)排序問(wèn)題[D];沈陽(yáng)師范大學(xué);2019年
10 高焰紅;平行批處理機(jī)上不相容族工件的在線排序問(wèn)題[D];鄭州大學(xué);2019年
本文編號(hào)：
2842772
