發(fā)布時間：2020-10-16 04:37

　　 在實際生產生活和現(xiàn)代科學研究中存在著大量具有NP難性質的優(yōu)化問題,如無線通訊信號覆蓋、復雜電路設計布線、網絡流量控制與疏導、航班任務調度等問題。這些具有NP難性質的眾多復雜實際應用問題都是屬于各自領域中的核心和關鍵性問題。基于計算復雜性理論的研究經驗,計算機科學界普遍認為對這些具有NP難性質的復雜優(yōu)化問題不存在多項式時間復雜度的完備且高效的精確求解算法。而在最近幾十年的研究中,基于非完備的啟發(fā)式優(yōu)化算法在求解許多具有NP難性質的組合優(yōu)化問題上表現(xiàn)出了良好的效果。也就是說,在一個相對合理的時間開銷內,一個比較優(yōu)秀的啟發(fā)式優(yōu)化算法通常能夠獲得所求問題的優(yōu)度非常高的解。這為實際應用領域出現(xiàn)的大量NP難度的復雜優(yōu)化問題提供了現(xiàn)實解決的途徑。研究表明,上述實際案例中出現(xiàn)的大量NP難度的復雜優(yōu)化問題均可在基于頂點覆蓋和線性排序問題模型的基礎上建模來求解。本文首先從算法研究的理論背景、經典求解算法框架方面系統(tǒng)梳理了啟發(fā)式優(yōu)化方法的特點、作用機理及其評價準則。然后選取兩類經典的且具有重要實際價值的組合優(yōu)化問題最小權頂點覆蓋問題和線性排序問題(包括帶累積成本的線性排序問題)作為參考研究對象,分別基于其各自問題的本質為它們設計了四種高效的啟發(fā)式優(yōu)化求解算法,并借助在公開基準算例上的計算實驗對提出的算法進行了分析和評價。本文的主要貢獻包括:(1)針對最小權頂點覆蓋問題提出了一種高效的多啟動迭代禁忌搜索算法(MS-ITS算法)。MS-ITS算法包括三個主要子算法和一個調節(jié)機制:初始解構造算法、禁忌搜索算法、擾動算法及多啟動迭代機制。初始解構造算法通過引入隨機和貪心兩種策略來選擇若干關鍵頂點構成合法初始解。禁忌搜索算法通過引入兩種特性即基于同時多點移動的鄰域結構并與之相適應的基于增量計算的快速鄰域評估機制和雙表禁忌策略,算法在每個當前解作鄰域變換中既能探索更大的鄰域空間又能快速的產生局部最優(yōu)解。擾動算法引入一個基于頂點權值和關聯(lián)度信息的擾動策略對局部最優(yōu)解實施變換。使得算法搜索能從一個局部最優(yōu)解慢慢找到優(yōu)度更好的局部最優(yōu)解。另外引入了多啟動迭代機制擴展了算法的全局搜索能力。使用了最小權頂點覆蓋問題的公開算例集(SPI、MPI和LPI)上的共126個基準算例進行了測試,多啟動迭代禁忌搜索算法能夠匹配約92%算例的歷史最好結果并改進了44個算例的當前最好上界。(2)針對最小權頂點覆蓋問題提出了一種更為高效的混合進化算法(HGA算法)。HGA算法混合了基于多啟動迭代禁忌搜索算法MS-ITS和基于群體解操作的遺傳算法GA。首先,通過引入一個基于GRASP思想的初始解生成策略來構造具有一定質量和分散性保證的初始種群,然后算法開始周期性迭代求解。在每次迭代周期中,通過引入基于公共基因繼承機制的交叉算子對選擇的兩個隨機父本解進化產生優(yōu)質的新子代個體。再通過多啟動迭代禁忌搜索算法使得當前優(yōu)質的新子代個體從現(xiàn)有格局逐步變換到一個更優(yōu)的局部最優(yōu)解上,最后通過引入一個精英值打分機制來進行種群更新以使得種群中個體保持多樣性的同時種群中的局部最優(yōu)解的質量更好。其中多啟動迭代禁忌搜索算法作為HGA算法的局部搜索算法強調算法的集中性搜索能力以找到質量更優(yōu)的局部最優(yōu)解,基于群體解的遺傳進化算法來加強整個算法的疏散性搜索能力達到全局尋優(yōu)。使用了最小權頂點覆蓋問題的公開算例集(SPI、MPI、LPI)和另外的隨機生成的大規(guī)模算例集RLPI上的共176個基準算例進行了測試,在同時比較MS-ITS算法的結果并引入公開的ILP求解器Gurobi的結果對比實驗中,基于全部176個MWVCP測試算例上,HGA算法能夠找到其中27個算例的最好上界并達到剩余所有算例的當前最好解或最優(yōu)解。(3)針對帶累積成本的線性排序問題提出了一個有效的混合進化算法(FBLSE算法)帶累積成本的線性排序問題是線性排序問題的一種特殊演變形式。其解序列上的每個子項又包含了一個非線性的累積代價,該問題表現(xiàn)出了更高的計算復雜性。FBLS-E算法融合了一個Memetic框架和一個基于問題結構新提出的局部搜索算法。首先針對帶累積成本的線性排序問題的內在結構提出了一個forward-backward鄰域結構,該鄰域結構擴展了當前解的鄰域搜索空間,為每次鄰域動作能夠從一個當前解變換到更好的鄰居解提供了更多的機會。由此,同時引入了一個基于多次SWAP動作的快速鄰域評估方法以提高在較大鄰域空間搜索上對解的評估效率。以此為基礎,為帶累積成本的線性排序問題設計了一個基于forward-backward鄰域結構的高效局部搜索算法FBLS。在算法的每次迭代中,首先初始解構造算法融合隨機初始解方法和局部搜索算法FBLS來產生高質量的初始種群。然后引入一個基于序列再融合的操作算子對兩個隨機選擇的父本進化以產生優(yōu)度較好的新子代解。接著通過局部搜索算法FBLS對新子代優(yōu)化以產生更好的局部最優(yōu)解。通過引入基于解的質量替換標準的種群更新策略來維護算法迭代中種群的多樣性。使用了帶累積成本的線性排序問題的118個公開基準算例進行了測試,FBLS-E算法在很短的時間內能匹配絕大部分算例的最優(yōu)解,并找到了另外46個算例的最新上界。(4)針對經典線性排序問題提出了一個基于多父本再融合操作的改進的混合進化算法(MPM算法)MPM算法融合了一個Memetic進化框架和一個有效的局部搜索算法。首先,通過隨機初始解生成策略和局部優(yōu)化操作相融合的種群初始化構造算法來產生由局部最優(yōu)解組成的初始種群。然后算法開始周期性迭代求解。在每次迭代周期中,先通過引入一個基于解距離特征的父本選擇策略在考慮種群多樣性的條件下進行多父本選擇。在此基礎上提出了一個基于多父本操作的再融合交叉算子對多個父本進化操作以產生盡可能繼承更多父本優(yōu)秀特征的新子代解,以此保證新產生的解的優(yōu)異性。接著使用局部搜索算法對新子代進一步優(yōu)化產生更好的局部最優(yōu)解。最后通過引入一個基于種群解的質量和健康度的打分策略來更新種群,以維護進化過程中種群的多樣性,以此進一步增強算法的全局尋優(yōu)能力。使用了經典線性排序問題的8組共484個公開算例進行了測試,MPM算法能成功匹配所有最優(yōu)解已知算例的最好結果,并在另外255個最優(yōu)解未知的困難算例上,能成功匹配其中的163個當前最好解,并找到了其余66個算例的最新下界。以上研究成果表明,本文提出的多啟動迭代禁忌搜索算法、混合進化算法及改進的混合進化算法都是求解對應頂點覆蓋和線性排序類NP難優(yōu)化問題的有效的啟發(fā)式算法。通過本課題的研究,加深了對啟發(fā)式優(yōu)化算法求解NP難度的組合優(yōu)化問題的理解。
【學位單位】：華中科技大學
【學位級別】：博士
【學位年份】：2019
【中圖分類】：TP18;O224
【文章目錄】：
摘要
Abstract
1 緒言
    1.1 選題來源與研究目的
    1.2 本文研究背景與意義
    1.3 主要研究內容及組織
2 組合優(yōu)化及啟發(fā)式優(yōu)化方法簡析
    2.1 關于組合優(yōu)化問題
    2.2 組合優(yōu)化問題的計算復雜性
    2.3 啟發(fā)式優(yōu)化經典算法簡析
    2.4 啟發(fā)式算法的評價準則
    2.5 本章小結
3 求解最小權頂點覆蓋問題的多啟動迭代禁忌搜索算法
    3.1 最小權頂點覆蓋問題概述
    3.2 MWVCP問題的多啟動迭代禁忌搜索優(yōu)化算法
    3.3 計算結果及與其他參考算法的比較
    3.4 實驗分析與討論
    3.5 本章小結
4 求解最小權頂點覆蓋問題的混合進化算法
    4.1 混合進化算法的基本原理
    4.2 MWVCP問題的混合進化優(yōu)化算法
    4.3 計算結果及與其他參考算法的比較
    4.4 實驗分析與討論
    4.5 本章小結
5 求解帶累積成本的線性排序問題的混合進化算法
    5.1 帶累積成本的線性排序問題概述
    5.2 帶累積成本的線性排序問題的研究現(xiàn)狀
    5.3 帶累積成本的線性排序問題模型
    5.4 LOPCC問題的混合進化優(yōu)化算法
    5.5 計算結果及與其他參考算法的比較
    5.6 本章小結
6 求解經典線性排序問題的改進的混合進化算法
    6.1 線性排序問題的研究現(xiàn)狀
    6.2 經典線性排序問題模型
    6.3 LOP問題的改進的混合進化優(yōu)化算法
    6.4 計算結果及與其他參考算法的比較
    6.5 分析和討論
    6.6 本章小結
7 總結及展望
    7.1 本文總結及研究成果
    7.2 主要創(chuàng)新點
    7.3 未來探索的著力點
參考文獻
致謝
附錄1 攻讀學位期間發(fā)表論文目錄
附錄2 攻讀博士學位期間參與的科研項目

【相似文獻】

相關期刊論文 前10條

1 李剛剛;魯習文;;目標為最小化工件運輸時間和的單臺機器帶一個維修時間段的排序問題的一個改進算法[J];運籌學學報;2019年04期

2 茍燕;戴秦;張新功;;具有時間與位置相關的兩類平行機排序問題[J];運籌學學報;2019年04期

3 冉金玉;張新功;;總加權誤工損失的兩個代理單機排序問題[J];湖北民族學院學報(自然科學版);2019年01期

4 韓飛;;高中數(shù)學一道數(shù)列典型題解法的探究[J];數(shù)學學習與研究;2016年23期

5 豆俊梅;孫彩賢;;單機排序問題的研究[J];數(shù)學學習與研究;2017年24期

6 胡覺亮;楊佳雯;蘇曉彤;董建明;;機器帶周期性維護時段的加工與運輸協(xié)同排序問題[J];浙江理工大學學報(自然科學版);2016年06期

7 仲維亞;馬曉茹;;帶有運輸且加工具有靈活性的無等待流水作業(yè)排序問題[J];運籌學學報;2016年04期

8 隋楠;羅成新;;具有維護活動及公共工期的加工時間依賴資源的單機排序問題[J];沈陽航空航天大學學報;2016年06期

9 林浩;何程;;關于工期分配與加權誤工數(shù)的雙指標排序問題（英文）[J];工程數(shù)學學報;2017年01期

10 趙傳立;張蕾;;帶有交貨期窗口和加工時間可控的排序問題[J];沈陽師范大學學報(自然科學版);2016年04期

相關博士學位論文 前10條

1 周淘晴;最小權頂點覆蓋和線性排序問題的求解算法研究[D];華中科技大學;2019年

2 李融奇;在線排序和批排序問題研究[D];浙江大學;2018年

3 沈佳煜;不確定情形下若干排序問題的研究[D];南京理工大學;2017年

4 高園;新型排序問題的計算復雜性研究[D];鄭州大學;2018年

5 殷娜;依賴于資源分配的排序問題研究[D];上海大學;2015年

6 李好好;若干排序問題研究[D];浙江大學;2014年

7 王吉波;工件加工時間可變的現(xiàn)代排序問題[D];大連理工大學;2005年

8 羅潤梓;平行機半在線排序問題[D];上海大學;2005年

9 季敏;當代工業(yè)中的若干排序問題研究[D];浙江大學;2006年

10 葉德仕;通訊網絡中排序問題的若干在線和高性能算法[D];浙江大學;2005年

相關碩士學位論文 前10條

1 李紅;多AGV的多任務分配與路徑規(guī)劃研究[D];南京郵電大學;2019年

2 陳秋宏;與誤工相關的雙代理單機排序問題研究[D];重慶師范大學;2019年

3 馬亞杰;工件具有相似加工時長的排序問題[D];湖南師范大學;2019年

4 叢穩(wěn);工件可拒絕的單機重新排序問題[D];鄭州大學;2019年

5 曹移林;平行多階段作業(yè)排序問題的研究[D];華東理工大學;2019年

6 康宇紅;具有錯位限制的重新排序問題研究[D];重慶師范大學;2019年

7 姜曉燕;MapReduce排序問題的若干算法研究[D];北京郵電大學;2019年

8 王亞男;具有退化維護和資源分配的單機排序問題[D];沈陽師范大學;2019年

9 李石;與資源相關加工時間可變的單機排序問題[D];沈陽師范大學;2019年

10 高焰紅;平行批處理機上不相容族工件的在線排序問題[D];鄭州大學;2019年

本文編號：2842772