本文關(guān)鍵詞：自適應(yīng)差分進(jìn)化算法解決多目標(biāo)有限緩沖車間調(diào)度問題研究

  更多相關(guān)文章： 自適應(yīng) 多目標(biāo) 差分進(jìn)化 流水車間調(diào)度 緩沖區(qū) 次解保留

【摘要】：流水車間調(diào)度問題(flow shop scheduling problem,FSSP)是優(yōu)化組合問題的一個重要分支,對該問題的研究有利于實(shí)現(xiàn)有限資源的優(yōu)化配置和合理利用。但因該問題為NP-hard(non-deterministic polynomial-hard),人工智能算法如今正逐漸代替數(shù)學(xué)方法,并取得了一定的成果。FSSP有多種類型,而帶有限緩沖的FSSP(FSSP with limited buffers,FSSPWLB)因更接近實(shí)際生產(chǎn)狀況而受到廣泛重視,對緩沖大小的探討在實(shí)際生產(chǎn)應(yīng)用中也具有重要的經(jīng)濟(jì)價(jià)值。此外,求解多目標(biāo)FSSP,可幫助決策者制定折中策略,在滿足客戶需求的前提下實(shí)現(xiàn)經(jīng)濟(jì)最大化等其他生產(chǎn)指標(biāo)。因此研究多目標(biāo)帶有限緩沖的FSSP就顯得尤為重要。差分進(jìn)化(differential evolution,DE)算法因其良好的特性而大量運(yùn)用于連續(xù)問題優(yōu)化中。該算法的參數(shù)對所優(yōu)化的問題具有敏感性,通常要根據(jù)反復(fù)實(shí)驗(yàn)的結(jié)果或經(jīng)驗(yàn)來設(shè)置,因此造成計(jì)算資源的額外開銷,同時受到先驗(yàn)經(jīng)驗(yàn)的制約。于是對自適應(yīng)差分進(jìn)化算法的研究不斷涌現(xiàn),其應(yīng)用領(lǐng)域也不斷拓寬。在使用DE對FSSPWLB進(jìn)行優(yōu)化時,因其測試實(shí)例規(guī)模不同,更需要自適應(yīng)機(jī)制的參與。綜上所述,本文提出了一種自適應(yīng)差分進(jìn)化算法及其若干變體,來解決多目標(biāo)FSSPWLB。目前看來,使用自適應(yīng)差分進(jìn)化算法優(yōu)化多目標(biāo)FSSPWLB尚屬首例。首先,本文使用最大順序值(largest order value,LOV)規(guī)則完成DE個體與工件排序的映射,為設(shè)計(jì)合理的自適應(yīng)機(jī)制,分析了DE個體、工件排序以及目標(biāo)值差異之間的關(guān)系,研究參數(shù)F和CR對目標(biāo)值的影響。在此基礎(chǔ)上提出了一種參數(shù)CR的自適應(yīng)差分進(jìn)化算法,以適應(yīng)對算法不同的搜索需求。同時為保證初始種群的質(zhì)量,使用啟發(fā)式算法構(gòu)造了兩個特殊個體。其次,為加強(qiáng)算法局部搜索性能,除選擇插入算子(Insert)外,還設(shè)計(jì)了一種基于概率模型的局部搜索算子(local search based on probability model,LSbPM),目的在于挖掘非支配解集中的優(yōu)質(zhì)子序列信息,并加以利用。引入次解保留概念,將其嵌入Insert中,保留多次插入過程中產(chǎn)生的次解,充分運(yùn)用搜索結(jié)果,在一定程度上補(bǔ)償隨即拋棄被支配解而造成的計(jì)算浪費(fèi)。接著,為驗(yàn)證本文所提出算法的各項(xiàng)性能的優(yōu)劣,設(shè)計(jì)了其他兩種變體,分別去除了LSbPM算子和次解保留機(jī)制,三種算法分別記為MPADE1、MPADE2和MPADE3,且與HDE做對比。選取三種不同基準(zhǔn)集中的12個實(shí)例,以多項(xiàng)評價(jià)指標(biāo)為參考,通過實(shí)驗(yàn)對比三種算法與HDE。實(shí)驗(yàn)表明,次解保留機(jī)制在算法中發(fā)揮了重要作用,使得MPADE1和MPADE3在性能上超越MPADE2和HDE。而LSbPM的效果并不理想,只有在評價(jià)次數(shù)較大時才能起到改善作用。整體來說,MPADE3是最好的算法,能夠獲得更多的非支配解,保證其質(zhì)量,在分布性上也比其他算法好。最后,MPADE3用以研究與HDE收斂特性的差別,并分析不同緩沖區(qū)容量對FSSPWLB優(yōu)化結(jié)果的影響。實(shí)驗(yàn)結(jié)果表明,MPADE3具有較快的收斂速度和較好的分布性。緩沖區(qū)在加工過程中具有重要作用,且所優(yōu)化目標(biāo)值的提升與緩沖區(qū)容量的增長不成正比,而是逐漸放緩的,這一結(jié)論可為機(jī)器配置提供指導(dǎo)。
【關(guān)鍵詞】：自適應(yīng) 多目標(biāo) 差分進(jìn)化 流水車間調(diào)度 緩沖區(qū) 次解保留
【學(xué)位授予單位】：鄭州大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP18;TB497
【目錄】：

• 摘要4-6
• Abstract6-11
• 1 緒論11-18
• 1.1 研究背景及意義11-13
• 1.2 國內(nèi)外研究現(xiàn)狀13-16
• 1.3 論文的主要工作及章節(jié)安排16-18
• 2 差分進(jìn)化算法發(fā)展18-28
• 2.1 差分進(jìn)化算法18-20
• 2.2 多目標(biāo)自適應(yīng)差分進(jìn)化算法20-26
• 2.2.1 多目標(biāo)優(yōu)化問題（MOP）20-25
• 2.2.2 多目標(biāo)自適應(yīng)差分進(jìn)化算法25-26
• 2.3 本章小結(jié)26-28
• 3 有限緩沖流水車間調(diào)度28-37
• 3.1 數(shù)學(xué)模型28-30
• 3.2 目標(biāo)函數(shù)30-32
• 3.3 測試基準(zhǔn)集32-33
• 3.4 解的表示33-36
• 3.5 緩沖區(qū)大小36
• 3.6 本章小結(jié)36-37
• 4 自適應(yīng)差分進(jìn)化算法設(shè)計(jì)37-60
• 4.1 PADE算法設(shè)計(jì)38-46
• 4.1.1 差分進(jìn)化個體、工件序列與目標(biāo)值的關(guān)系39-41
• 4.1.2 排序多樣性41-45
• 4.1.3 參數(shù)自適應(yīng)機(jī)制45-46
• 4.2 MPADE算法實(shí)現(xiàn)及流程46-54
• 4.2.1 種群初始化46-47
• 4.2.2 局部搜索47-52
• 4.2.3 非支配解集更新52
• 4.2.4 算法流程52-54
• 4.3 MPADE算法性能測試54-59
• 4.3.1 參數(shù)設(shè)置54
• 4.3.2 多目標(biāo)優(yōu)化評價(jià)指標(biāo)54-55
• 4.3.3 實(shí)驗(yàn)結(jié)果與分析55-59
• 4.4 本章小結(jié)59-60
• 5 基于MPADE3的特定分析60-64
• 5.1 收斂性分析60-61
• 5.2 緩沖區(qū)影響研究61-63
• 5.3 本章小結(jié)63-64
• 6 結(jié)論與展望64-66
• 6.1 論文總結(jié)64
• 6.2 工作展望64-66
• 參考文獻(xiàn)66-73
• 致謝73-74
• 個人簡歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果74

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 王艷宜;;改進(jìn)差分進(jìn)化算法及其應(yīng)用[J];機(jī)械設(shè)計(jì)與研究;2010年05期

2 張鵬;;基于差分進(jìn)化的混合地面等待優(yōu)化策略[J];桂林航天工業(yè)高等�？茖W(xué)校學(xué)報(bào);2012年03期

3 寧桂英;周永權(quán);;一種求解二重積分的差分進(jìn)化算法[J];哈爾濱理工大學(xué)學(xué)報(bào);2013年02期

4 王惠卿;;結(jié)合機(jī)械設(shè)計(jì)約束處理的差分進(jìn)化算法[J];電子制作;2013年13期

5 蔡亮;楊啟文;岳興漢;;一種基于混合差分策略的改進(jìn)差分進(jìn)化算法[J];河海大學(xué)常州分校學(xué)報(bào);2007年04期

6 譚躍;譚冠政;;混沌局部搜索策略的差分進(jìn)化算法[J];重慶工學(xué)院學(xué)報(bào)(自然科學(xué)版);2009年05期

7 萬東;;差分進(jìn)化算法研究及其應(yīng)用[J];科學(xué)技術(shù)與工程;2009年22期

8 喬英;高岳林;江巧永;;一種新局部搜索策略的差分進(jìn)化算法[J];太原理工大學(xué)學(xué)報(bào);2011年04期

9 曲福恒;胡雅婷;楊勇;谷欣超;;改進(jìn)差分進(jìn)化算法及其在模糊聚類分析中的應(yīng)用[J];長春理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年04期

10 黃林峰;;基于離散差分進(jìn)化算法的多維0/1背包問題求解[J];硅谷;2012年20期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 陸絲馨;肖健梅;王錫淮;;基于改進(jìn)差分進(jìn)化算法的艦船電網(wǎng)重構(gòu)[A];第二十九屆中國控制會議論文集[C];2010年

2 樓洋;李均利;陳剛;;基于個體排序的差分進(jìn)化算法[A];'2010系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會議論文集[C];2010年

3 張倩;李海港;;多目標(biāo)問題的差分進(jìn)化算法研究[A];2009年中國智能自動化會議論文集（第一分冊）[C];2009年

4 裴振奎;劉真;趙艷麗;;差分進(jìn)化算法在多目標(biāo)路徑規(guī)劃中的應(yīng)用[A];中國運(yùn)籌學(xué)會模糊信息與模糊工程分會第五屆學(xué)術(shù)年會論文集[C];2010年

5 劉國帥;楊侃;陳靜;周景舒;周冉;鄭姣;;差分進(jìn)化算法在三峽電站廠內(nèi)經(jīng)濟(jì)運(yùn)行中的應(yīng)用[A];中國水文科技新發(fā)展——2012中國水文學(xué)術(shù)討論會論文集[C];2012年

6 劉瀟;桂衛(wèi)華;王雅琳;王曉麗;陽春華;;一種改進(jìn)的多目標(biāo)差分進(jìn)化算法研究[A];中國自動化學(xué)會中南六�。▍^(qū)）2010年第28屆年會·論文集[C];2010年

7 趙娟;蔡濤;鄧方;楊紅偉;;基于改進(jìn)差分進(jìn)化算法的脈沖控制方法[A];中國自動化學(xué)會控制理論專業(yè)委員會B卷[C];2011年

8 袁沈堅(jiān);顧幸生;;基于差分進(jìn)化的膜計(jì)算優(yōu)化算法[A];上海市化學(xué)化工學(xué)會2010年度學(xué)術(shù)年會論文集（自動化專題）[C];2010年

9 姜立強(qiáng);郭錚;劉光斌;;差分進(jìn)化算法縮放因子取值策略研究[A];2007'儀表，自動化及先進(jìn)集成技術(shù)大會論文集（二）[C];2007年

10 倪惠康;杜文莉;錢鋒;;基于改進(jìn)差分進(jìn)化算法的PID參數(shù)優(yōu)[A];2009年中國智能自動化會議論文集（第一分冊）[C];2009年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 孫浩;差分進(jìn)化多目標(biāo)優(yōu)化算法及其在鋁熱連軋軋制規(guī)程中應(yīng)用[D];燕山大學(xué);2015年

2 陳盈果;面向任務(wù)的快速響應(yīng)空間衛(wèi)星部署優(yōu)化設(shè)計(jì)方法研究[D];國防科學(xué)技術(shù)大學(xué);2014年

3 謝宇;差分進(jìn)化的若干問題及其應(yīng)用研究[D];南京理工大學(xué);2015年

4 丁青鋒;基于元胞自動機(jī)的差分進(jìn)化算法及其在通信系統(tǒng)中的應(yīng)用研究[D];上海大學(xué);2015年

5 賈東立;改進(jìn)的差分進(jìn)化算法及其在通信信號處理中的應(yīng)用研究[D];上海大學(xué);2011年

6 劉榮輝;多階段自適應(yīng)差分進(jìn)化算法及應(yīng)用研究[D];東華大學(xué);2012年

7 郭鵬;差分進(jìn)化算法改進(jìn)研究[D];天津大學(xué);2012年

8 王旭;改進(jìn)差分進(jìn)化算法及其在可逆邏輯綜合中的應(yīng)用[D];東華大學(xué);2013年

9 董明剛;基于差分進(jìn)化的優(yōu)化算法及應(yīng)用研究[D];浙江大學(xué);2012年

10 王天意;大地電磁迭代有限元與改進(jìn)差分進(jìn)化正反演算法研究[D];中國地質(zhì)大學(xué)(北京);2015年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 高靜;量子差分進(jìn)化算法在油田開發(fā)中的應(yīng)用研究[D];浙江大學(xué);2015年

2 萬婧;基于離散微粒群算法和混合差分進(jìn)化算法的復(fù)雜生產(chǎn)調(diào)度問題求解[D];昆明理工大學(xué);2015年

3 張轉(zhuǎn);基于差分進(jìn)化算法的混凝土德拜模型的研究[D];長安大學(xué);2015年

4 江華;差分進(jìn)化算法的改進(jìn)及其在K-means聚類算法中的應(yīng)用[D];華中師范大學(xué);2015年

5 周志剛;基于差分進(jìn)化算法的信用風(fēng)險(xiǎn)度量模型研究[D];華中師范大學(xué);2015年

6 任甜甜;差分進(jìn)化算法在反演問題中的研究與應(yīng)用[D];新疆大學(xué);2015年

7 楊洋;基于差分進(jìn)化的模糊C-均值聚類算法研究[D];電子科技大學(xué);2015年

8 王丹;基于輔助函數(shù)的自適應(yīng)差分進(jìn)化算法研究[D];西安電子科技大學(xué);2014年

9 劉家華;基于進(jìn)化計(jì)算的軋制生產(chǎn)過程操作優(yōu)化算法與系統(tǒng)開發(fā)[D];東北大學(xué);2013年

10 王旦平;圓形對稱振子陣列天線基于差分進(jìn)化算法的綜合[D];西安電子科技大學(xué);2014年

，

本文編號：579656