基于混合多智能體遺傳算法的作業(yè)車間調(diào)度問題研究

《基于混合多智能體遺傳算法的作業(yè)車間調(diào)度問題研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、2017年2月第43卷第2期北京航空航天大學(xué)學(xué)報(bào)JournalofBeijingUniversityofAeronauticsandAstronauticsFebruary2017V01．43NO．2http：／／bhxb．buaa．edu．cnjbuaa@buaa．edu．cnDOI：10．13700／j．bh．1001-5965．2016．0103基于混合多智能體遺傳算法的作業(yè)車間調(diào)度問題研究李小濤，彭種+(北京航空航天大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，北京100083)摘要：針對(duì)作業(yè)車間調(diào)度問題(JSP)的非確定性多項(xiàng)式特性與解空間分布的大山谷屬性，本文提出一種多智能體遺

2、傳算法(MAGA)與自適應(yīng)模擬退火算法(ASA)的混合優(yōu)化算法，用于尋找最大完工時(shí)間最短的調(diào)度。首先，將每個(gè)染色體視作獨(dú)立的智能體并采用工序編碼方式隨機(jī)初始化每個(gè)智能體，結(jié)合多智能體協(xié)作與競爭理論設(shè)計(jì)了實(shí)現(xiàn)智能體之間交互作用的鄰居交互算子，進(jìn)而利用一定數(shù)量智能體進(jìn)行全局搜索，找到多個(gè)適應(yīng)度較高的可行解。其次，為避免算法陷入局部最優(yōu)，采用ASA對(duì)每個(gè)智能體開展局部尋優(yōu)。最后，通過基準(zhǔn)測試庫中典型實(shí)例的計(jì)算結(jié)果驗(yàn)證了該算法的有效性。關(guān)鍵詞：作業(yè)車間調(diào)度(JSP)；多智能體；遺傳算法；鄰居交互算子；自適應(yīng)模擬退火算法(ASA)中圖分類號(hào)：TP301．6；F406．2文獻(xiàn)標(biāo)識(shí)碼

3、：A文章編號(hào)：1001．5965(2017)02加410-07車間調(diào)度是生產(chǎn)加工的重要環(huán)節(jié)，基本任務(wù)之一是合理安排各機(jī)器上的待加工工件的順序，使得最大完工時(shí)間最短。作為流水車間調(diào)度問題的擴(kuò)展，作業(yè)車間調(diào)度問題(JobshopSchedulingProblem，JSP)中每個(gè)工件可以有特定的工序安排，1976年Garey等?證明了它是一個(gè)非確定性多項(xiàng)式(Non—deterministicPolynomial，NP)難題。對(duì)于JSP，早期研究中大多采用的方法可分為近似方法和精確方法。其中近似方法以優(yōu)先規(guī)則法心1和瓶頸移動(dòng)法"1為代表，其求解過程較為復(fù)雜且計(jì)算量很大；而對(duì)于基

4、準(zhǔn)測試庫H1中10工件10機(jī)器的問題，Applegate與Cook∞1采用的分支定界法是非常有效的精確方法，但對(duì)規(guī)模更大的情形卻不太適用。近年來許多元啟發(fā)式算法相繼提出，用于求解JSP的有遺傳算法。61、模擬退火算法o“、粒子群算法舊J、生物地理學(xué)優(yōu)化算法。91等。遺傳算法的主要優(yōu)點(diǎn)是通用性強(qiáng)，它適用于各類優(yōu)化問題‘1“”。，但在求解離散空間且具有NP特性的優(yōu)化問題時(shí)容易陷入局部最優(yōu)。通過引入多智能體協(xié)同理論，Zhong等¨4。提出了用于連續(xù)空間優(yōu)化的多智能體遺傳算法(MuhiagentGeneticAlgorithm，MAGA)，Sivasubramani和Swaru

5、p¨劃將多智能體差分算法用于電力系統(tǒng)的無功優(yōu)化，改進(jìn)后的算法不僅有良好的全局和局部尋優(yōu)能力，且具有快速收斂性和較好的魯棒性。對(duì)于復(fù)雜的組合優(yōu)化問題，一般來說沒有通用的算法框架，特別是對(duì)于解空間分布類似大山谷結(jié)構(gòu)的JSP，采用單一算法往往難以找到問題的最優(yōu)解，研究的趨勢是將具有良好全局搜索能力的算法和局部搜索算法相結(jié)合‘1?。例如，Gao等?1結(jié)合遺傳算法與變鄰域算法求解JSP，Xia和wu¨¨運(yùn)用粒子群算法與模擬退火算法混合尋優(yōu)。模擬退火算法是一種廣泛應(yīng)用的局部搜索算法，通過以一定概率接受劣解使得算法具有跳出收稿日期：2016-01-26；錄用日期：2016-02—29

6、；網(wǎng)絡(luò)出版時(shí)閏：2016-03-0715：08網(wǎng)絡(luò)出版地址：WWW．cnki．net／kcms／detail／11．2625．V．20160307．1508．001．html基金項(xiàng)目：國家重大科技專項(xiàng)(2015ZX04005005)}通訊作者：E-mail：pch@buaa．edu．cn引用格式：李小游，彭種．基于混合多智能體遺傳算法的作業(yè)車間調(diào)度問題研究fJJ．北京航空航天大學(xué)學(xué)報(bào)，2017，43(2)：410—416．LIXT，PENGC．Hybridmuttiagentgeneticalgorithmforjobshopschedulingprobleme】1．J

7、ournalofBeqingUniversityofAeronauticsandAstronautics，2017，43f2)：410—416(inChinese)．第2期李小濤，等：基于混合多智能體遺傳算法的作業(yè)車間調(diào)度問題研究411局部最優(yōu)的能力，尋優(yōu)結(jié)果的好壞取決于退火進(jìn)度表的選擇和鄰域解的產(chǎn)生機(jī)制。精細(xì)的退火進(jìn)度表能夠使尋優(yōu)的效果更好，利用在馬爾可夫鏈平穩(wěn)分布下的目標(biāo)函數(shù)均方差表達(dá)式，Romeo等¨9。成功推導(dǎo)出一種自適應(yīng)退火策略。對(duì)于JSP的局部尋優(yōu)而言，最早被提出且較為成功的鄰域結(jié)構(gòu)是由vanLaarhoven等"。提出的N2