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

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

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

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

【參考文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關碩士學位論文 前3條

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

2 游佳;基于Petri網的生化免疫檢測設備調度問題的研究[D];華南理工大學;2015年

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

本文編號：2754273