資源描述：
《基于混合多智能體遺傳算法的作業(yè)車間調度問題研究》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、2017年2月第43卷第2期北京航空航天大學學報JournalofBeijingUniversityofAeronauticsandAstronauticsFebruary2017V01．43NO．2http：／／bhxb．buaa．edu．cnjbuaa@buaa．edu．cnDOI：10．13700／j．bh．1001-5965．2016．0103基于混合多智能體遺傳算法的作業(yè)車間調度問題研究李小濤，彭種+(北京航空航天大學機械工程及自動化學院，北京100083)摘要：針對作業(yè)車間調度問題(JSP)的非確定性多項式特性與解空間分布的大山谷屬性，本文提出一種多智能體遺
2、傳算法(MAGA)與自適應模擬退火算法(ASA)的混合優(yōu)化算法，用于尋找最大完工時間最短的調度。首先，將每個染色體視作獨立的智能體并采用工序編碼方式隨機初始化每個智能體，結合多智能體協作與競爭理論設計了實現智能體之間交互作用的鄰居交互算子，進而利用一定數量智能體進行全局搜索，找到多個適應度較高的可行解。其次，為避免算法陷入局部最優(yōu)，采用ASA對每個智能體開展局部尋優(yōu)。最后，通過基準測試庫中典型實例的計算結果驗證了該算法的有效性。關鍵詞：作業(yè)車間調度(JSP)；多智能體；遺傳算法；鄰居交互算子；自適應模擬退火算法(ASA)中圖分類號：TP301．6；F406．2文獻標識碼
3、：A文章編號：1001．5965(2017)02加410-07車間調度是生產加工的重要環(huán)節(jié)，基本任務之一是合理安排各機器上的待加工工件的順序，使得最大完工時間最短。作為流水車間調度問題的擴展，作業(yè)車間調度問題(JobshopSchedulingProblem，JSP)中每個工件可以有特定的工序安排，1976年Garey等?證明了它是一個非確定性多項式(Non—deterministicPolynomial，NP)難題。對于JSP，早期研究中大多采用的方法可分為近似方法和精確方法。其中近似方法以優(yōu)先規(guī)則法心1和瓶頸移動法"1為代表，其求解過程較為復雜且計算量很大；而對于基
4、準測試庫H1中10工件10機器的問題，Applegate與Cook∞1采用的分支定界法是非常有效的精確方法，但對規(guī)模更大的情形卻不太適用。近年來許多元啟發(fā)式算法相繼提出，用于求解JSP的有遺傳算法。61、模擬退火算法o“、粒子群算法舊J、生物地理學優(yōu)化算法。91等。遺傳算法的主要優(yōu)點是通用性強，它適用于各類優(yōu)化問題‘1“”。，但在求解離散空間且具有NP特性的優(yōu)化問題時容易陷入局部最優(yōu)。通過引入多智能體協同理論，Zhong等¨4。提出了用于連續(xù)空間優(yōu)化的多智能體遺傳算法(MuhiagentGeneticAlgorithm，MAGA)，Sivasubramani和Swaru
5、p¨劃將多智能體差分算法用于電力系統的無功優(yōu)化，改進后的算法不僅有良好的全局和局部尋優(yōu)能力，且具有快速收斂性和較好的魯棒性。對于復雜的組合優(yōu)化問題，一般來說沒有通用的算法框架，特別是對于解空間分布類似大山谷結構的JSP，采用單一算法往往難以找到問題的最優(yōu)解，研究的趨勢是將具有良好全局搜索能力的算法和局部搜索算法相結合‘1?。例如，Gao等?1結合遺傳算法與變鄰域算法求解JSP，Xia和wu¨¨運用粒子群算法與模擬退火算法混合尋優(yōu)。模擬退火算法是一種廣泛應用的局部搜索算法，通過以一定概率接受劣解使得算法具有跳出收稿日期：2016-01-26；錄用日期：2016-02—29
6、；網絡出版時閏：2016-03-0715：08網絡出版地址：WWW．cnki．net／kcms／detail／11．2625．V．20160307．1508．001．html基金項目：國家重大科技專項(2015ZX04005005)}通訊作者：E-mail：pch@buaa．edu．cn引用格式：李小游，彭種．基于混合多智能體遺傳算法的作業(yè)車間調度問題研究fJJ．北京航空航天大學學報，2017，43(2)：410—416．LIXT，PENGC．Hybridmuttiagentgeneticalgorithmforjobshopschedulingprobleme】1．J
7、ournalofBeqingUniversityofAeronauticsandAstronautics，2017，43f2)：410—416(inChinese)．第2期李小濤，等：基于混合多智能體遺傳算法的作業(yè)車間調度問題研究411局部最優(yōu)的能力，尋優(yōu)結果的好壞取決于退火進度表的選擇和鄰域解的產生機制。精細的退火進度表能夠使尋優(yōu)的效果更好，利用在馬爾可夫鏈平穩(wěn)分布下的目標函數均方差表達式，Romeo等¨9。成功推導出一種自適應退火策略。對于JSP的局部尋優(yōu)而言，最早被提出且較為成功的鄰域結構是由vanLaarhoven等"。提出的N2
