發(fā)布時(shí)間：2020-07-14 01:24

【摘要】：組合優(yōu)化問題是最優(yōu)化問題中的一類在離散狀態(tài)下求極值的問題,實(shí)際生活中的許多問題都可以抽象為組合優(yōu)化問題。典型的組合優(yōu)化問題有作業(yè)車間調(diào)度問題、旅行商問題等,由于組合優(yōu)化問題為NP-hard問題,隨著問題規(guī)模的增大,采用精確求解的方法所需的計(jì)算量和存儲空間呈指數(shù)增長,難于在有限時(shí)間內(nèi)找到最優(yōu)解,因此進(jìn)化算法等近似算法成為組合優(yōu)化問題求解的熱點(diǎn),很多研究人員利用進(jìn)化算法在可以接受的時(shí)間內(nèi)尋求這類問題的近似最優(yōu)解。其中教學(xué)算法是一種新興的群智能進(jìn)化算法,模擬了課堂中教師對學(xué)生授課的影響以及學(xué)生之間相互學(xué)習(xí)的過程。教學(xué)算法具有模型簡單、計(jì)算效率較高等優(yōu)點(diǎn)。本文對教學(xué)算法及其在來自于實(shí)際工程的幾類組合優(yōu)化問題上的應(yīng)用進(jìn)行研究,針對每一類組合優(yōu)化問題的特性設(shè)計(jì)相應(yīng)的改進(jìn)教學(xué)算法對問題進(jìn)行求解。本文主要完成如下工作:(1)對經(jīng)典離散優(yōu)化問題車間作業(yè)調(diào)度問題(JSSP)進(jìn)行研究,針對JSSP問題因其復(fù)雜度較高容易導(dǎo)致算法陷入局部最優(yōu)的不足,提出了一種新穎的多小組協(xié)同學(xué)習(xí)的教學(xué)算法(GC-TLBO)。引入了學(xué)習(xí)小組協(xié)同學(xué)習(xí)策略,通過組內(nèi)學(xué)習(xí)和組內(nèi)交流,使學(xué)習(xí)過程跳出當(dāng)前的局限;引入了基于學(xué)習(xí)能力的深度和廣度搜索策略,小組內(nèi)學(xué)生按照學(xué)習(xí)能力強(qiáng)弱進(jìn)行學(xué)習(xí),較優(yōu)的學(xué)生進(jìn)行深度的學(xué)習(xí),較差的學(xué)生進(jìn)行廣度的學(xué)習(xí)。最后,通過對OR-Library中的標(biāo)準(zhǔn)仿真實(shí)例進(jìn)行實(shí)驗(yàn),結(jié)果表明所提出的改進(jìn)教學(xué)算法在JSSP問題上的收斂精度和搜索能力均得到了有效的提高。(2)對一類具有聚類特性的旅行商問題(TSP)進(jìn)行研究,針對這類TSP問題的聚類特性,在GC-TLBO的初始化階段結(jié)合啟發(fā)式信息對算法進(jìn)行初始化。利用該方法對實(shí)際應(yīng)用系統(tǒng)——智能倉儲系統(tǒng)中的訂單排序優(yōu)化問題進(jìn)行研究與分析,將其歸納為一類帶約束和聚類性質(zhì)的TSP問題。最后利用設(shè)計(jì)的改進(jìn)教學(xué)算法對訂單排序優(yōu)化問題進(jìn)行仿真實(shí)驗(yàn),驗(yàn)證了結(jié)合啟發(fā)式初始化的GC-TLBO算法求解這一類問題的有效性。(3)對一類多人旅行商問題(MTSP)進(jìn)行研究,針對MTSP問題涉及到多個(gè)任務(wù)的分派和優(yōu)化特性,對GC-TLBO算法進(jìn)行改進(jìn),提出基于批次交叉算子的教學(xué)算法(NC-TLBO),在教師階段和學(xué)生階段采用一種新的基于批次的交叉算子,并在學(xué)生自學(xué)習(xí)階段采用新的基于批次的自學(xué)習(xí)算子。針對實(shí)際應(yīng)用系統(tǒng)——智能倉儲系統(tǒng)中的四叉機(jī)器人拿貨順序問題進(jìn)行研究與分析,將其歸納為一類帶約束的MTSP問題。利用該改進(jìn)教學(xué)算法對四叉機(jī)器人的拿貨順序優(yōu)化問題進(jìn)行仿真實(shí)驗(yàn),驗(yàn)證了所提出的NC-TLBO算法求解這一類問題的有效性。(4)對一類帶有可重入性質(zhì)的柔性車間調(diào)度問題(FJSP)進(jìn)行研究,由于這類問題帶有可重入性與柔性,具有高度復(fù)雜度,因此對GC-TLBO算法作出改進(jìn),提出一種變步長策略和基于關(guān)鍵路徑的鄰域搜索相結(jié)合的教學(xué)算法(CP-TLBO),設(shè)計(jì)了一種順序編碼方式和工序序號編碼方式相結(jié)合的編碼方式,并在學(xué)生階段設(shè)計(jì)了一種變步長的局部搜索和基于關(guān)鍵路徑的全局搜索相結(jié)合的搜索策略。針對符合這一特點(diǎn)的實(shí)際問題——免疫檢測設(shè)備的調(diào)度問題進(jìn)行分析,將其歸納為具有復(fù)雜約束和可重入特性的FJSP問題。利用該算法對其進(jìn)行設(shè)備優(yōu)化調(diào)度的仿真實(shí)驗(yàn),驗(yàn)證了CP-TLBO算法求解這一類問題的有效性。
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O224
【圖文】：

華南理工大學(xué)碩士學(xué)位論文生階段除了會向老師學(xué)習(xí)以外，還會相互學(xué)習(xí)相互交流獲得新知識，取長補(bǔ)短響共同進(jìn)步。在學(xué)生階段，學(xué)生個(gè)體 Xi向 Xj的學(xué)習(xí)過程按下式進(jìn)行[38]。(),()()new,i old,iiijijX X rX X當(dāng)FX FX(),()()new,i old,iijiijX X rX X當(dāng)FX FX，F(xiàn)(Xi)表示個(gè)體 Xi的適應(yīng)值，ir 為[0,1]間的隨機(jī)數(shù)。當(dāng) F(Xnew,i) <F(Xold的學(xué)習(xí)過程，保留個(gè)體 Xnew,i，否則保留 Xold,i。本 TLBO 算法的流程算法的基本流程如圖 2-1 所示。

符號 cik和 pik分別為 i 工件在機(jī)器 k 上的完成時(shí)間和加工時(shí)間；M 是一個(gè)足夠大的正數(shù)； aihk和 xijk分別為指示系數(shù)和指示變量，其意義如下： 非上述情況若機(jī)器先于機(jī)器加工工件01 hkiaihk（3-5） 非上述情況若工件先于工件在機(jī)器上加工01 ijkxijk（3-6）式（3-1）表示目標(biāo)函數(shù)，即最大完工時(shí)間；式（3-2）表示鏈?zhǔn)郊s束條件；式（3-3）為加工工件過程不可中斷約束；式（3-4）表示工件在每個(gè)機(jī)器上都要加工。3.3 基于小組的協(xié)同學(xué)習(xí)教學(xué)算法3.3.1 改進(jìn)的 TLBO 算法基于多小組協(xié)同學(xué)習(xí)的改進(jìn)教學(xué)算法的基本流程圖如圖 3-1 所示。

適應(yīng)值（完工時(shí)間）由小到大進(jìn)行排名，將排名在前半部分的學(xué)生定義為學(xué)習(xí)能力較強(qiáng)的學(xué)生，將排名在后半部分的學(xué)生定義為學(xué)習(xí)能力較差的學(xué)生。對于學(xué)習(xí)能力較強(qiáng)的學(xué)生，進(jìn)行加強(qiáng)局部搜索能力的深度學(xué)習(xí)操作，而對于學(xué)習(xí)能力較弱的學(xué)生，則進(jìn)行加強(qiáng)隨機(jī)搜索能力的廣度學(xué)習(xí)操作。a）學(xué)生深度學(xué)習(xí)對于學(xué)習(xí)能力較好的學(xué)生，其更善于進(jìn)行知識的深度挖掘。因此對學(xué)習(xí)能力較強(qiáng)的個(gè)體 Xi，進(jìn)行 Num(i)次自學(xué)習(xí)算子操作，根據(jù)文獻(xiàn)[36]中給予學(xué)習(xí)能力強(qiáng)的個(gè)體更多的學(xué)習(xí)機(jī)會和次數(shù)的思想，Num(i)按照公式（3-7）進(jìn)行計(jì)算獲得，自學(xué)習(xí)算子利用文獻(xiàn)[67]所提到的三種經(jīng)典變異算子：單點(diǎn)交叉算子、倒位算子與移位算子，如圖 3-2 所示。每次自學(xué)習(xí)隨機(jī)選擇三種自學(xué)習(xí)算子中的一種，若本次學(xué)習(xí)得到的新個(gè)體比當(dāng)前個(gè)體 Xi更優(yōu)，則對當(dāng)前個(gè)體 Xi進(jìn)行更新，否則本次的學(xué)習(xí)成果不被接受，個(gè)體 Xi不更新，以此類推，個(gè)體共完成 Num(i)次學(xué)習(xí)，學(xué)生的深度學(xué)習(xí)過程如圖 3-3 所示。與文獻(xiàn)[36]中以當(dāng)前個(gè)體為起點(diǎn)一次性產(chǎn)生多個(gè)鄰域個(gè)體然后取最好個(gè)體的差異性自學(xué)習(xí)不同，本章

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王紅琳;常翠寧;李志南;南新元;;改進(jìn)教與學(xué)優(yōu)化算法的IIR數(shù)字濾波器設(shè)計(jì)[J];計(jì)算機(jī)仿真;2015年11期

2 吳菁們;;亞馬遜倉庫Kiva機(jī)器人的應(yīng)用分析與前景展望[J];物流技術(shù)與應(yīng)用;2015年10期

3 李雍容;;澳大利亞首例貨到人揀選系統(tǒng)[J];物流技術(shù)與應(yīng)用;2015年09期

4 于坤杰;王昕;王振雷;;基于反饋的精英教學(xué)優(yōu)化算法[J];自動化學(xué)報(bào);2014年09期

5 陳得寶;魏華;鄒鋒;王江濤;楊一軍;李崢;方振國;;模擬退火教學(xué)式優(yōu)化算法[J];計(jì)算機(jī)應(yīng)用研究;2014年12期

6 張凱波;李斌;;合作型協(xié)同演化算法研究進(jìn)展[J];計(jì)算機(jī)工程與科學(xué);2014年04期

7 于坤杰;王昕;王振雷;;改進(jìn)的教學(xué)優(yōu)化算法及其應(yīng)用[J];化工進(jìn)展;2014年04期

8 高立群;歐陽海濱;孔祥勇;劉宏志;;帶有交叉操作的教-學(xué)優(yōu)化算法[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年03期

9 趙建文;陳艷寧;路士州;;化學(xué)發(fā)光免疫檢測儀涉及的關(guān)鍵技術(shù)[J];發(fā)光學(xué)報(bào);2012年12期

10 曾強(qiáng);楊育;王小磊;文穎;;并行機(jī)作業(yè)車間等量分批多目標(biāo)優(yōu)化調(diào)度[J];計(jì)算機(jī)集成制造系統(tǒng);2011年04期

相關(guān)碩士學(xué)位論文 前3條

1 吳凱華;基于群智能算法的免疫分析檢測設(shè)備優(yōu)化調(diào)度問題研究[D];華南理工大學(xué);2016年

2 游佳;基于Petri網(wǎng)的生化免疫檢測設(shè)備調(diào)度問題的研究[D];華南理工大學(xué);2015年

3 胡善德;全自動生化免疫分析儀多任務(wù)優(yōu)化調(diào)度研究及其軟件系統(tǒng)實(shí)現(xiàn)[D];華南理工大學(xué);2014年

本文編號：2754273