針對總拖期時(shí)間最小化的零空閑置換流水車間調(diào)度問題,提出了一種基于關(guān)鍵塊結(jié)構(gòu)的混合進(jìn)化算法。該算法以遺傳算法為框架,設(shè)計(jì)了依據(jù)關(guān)聯(lián)規(guī)則計(jì)算染色體上基因之間關(guān)聯(lián)強(qiáng)度的方法,以便挖掘優(yōu)勢染色體上的優(yōu)勢基因組成關(guān)鍵塊,并在優(yōu)勢關(guān)鍵塊的基礎(chǔ)上構(gòu)建具有較優(yōu)解的人工染色體種群。同時(shí),引入雙精英進(jìn)化機(jī)制,提高算法交叉和變異的有效性,避免算法的無效交叉。精英進(jìn)化產(chǎn)生的子代種群依據(jù)關(guān)聯(lián)規(guī)則挖掘關(guān)鍵塊,基于交換鄰域結(jié)構(gòu),結(jié)合NEH算法的思想,互換非關(guān)鍵塊上工件之間的位置,得到局部搜索解。最后,通過對Taillard基準(zhǔn)問題進(jìn)行仿真測試,并將本文算法運(yùn)行結(jié)果與其他算法進(jìn)行比較,驗(yàn)證了算法的有效性。

【文章頁數(shù)】：9 頁

【部分圖文】：

圖3關(guān)鍵塊篩選2．3構(gòu)建人工染色體種群

，直到窮盡所有大于閾值的基因關(guān)鍵塊。圖2給出上述步驟關(guān)鍵塊挖掘構(gòu)建的過程。2．2．3關(guān)鍵塊篩選本研究運(yùn)用關(guān)聯(lián)規(guī)則數(shù)據(jù)分析方法產(chǎn)生關(guān)鍵塊，將單個(gè)基因作為候選項(xiàng)目集向外延伸。將關(guān)鍵塊的長度設(shè)置為2，對關(guān)鍵塊暫存器中的關(guān)鍵塊的工件與機(jī)器進(jìn)行對比，若關(guān)鍵塊之間出現(xiàn)重復(fù)的工件或涵蓋的機(jī)器出....

圖1數(shù)據(jù)編碼

(7)lift=c(x→y)s(y)(8)為使關(guān)聯(lián)法則成立且有意義，需設(shè)立最小支持度和最小信心水平，當(dāng)運(yùn)用關(guān)聯(lián)規(guī)則進(jìn)行挖掘時(shí)，超過所設(shè)立的閾值，才能認(rèn)定為有意義的信息。2．2．2構(gòu)建與挖掘區(qū)塊關(guān)鍵塊是一個(gè)具有高度競爭優(yōu)勢的基因結(jié)構(gòu)，對于降低所求問題的復(fù)雜度具有顯著的效果。本研究通....

圖4人工染色體組合機(jī)制2．4雙精英協(xié)同進(jìn)化

排的機(jī)器位置，直到人工染色體完成組合。人工染色體的組合方式如圖4所示。圖4人工染色體組合機(jī)制2．4雙精英協(xié)同進(jìn)化2．4．1協(xié)作變異機(jī)制協(xié)同進(jìn)化是改善進(jìn)化算法性能的有效途徑［21］，它將個(gè)體拆分成多個(gè)子集，每個(gè)子集對應(yīng)一類決策，子集獨(dú)立進(jìn)化，將進(jìn)化后的子集組合成完整的解，對完整的解....

圖9優(yōu)勢種群保留

?邢亂皇來?難莼?。符號表示及步驟如下所示:AC:代表人工染色體種群，AC={AC1，AC2，…，ACn};O:代表精英進(jìn)化染色體種群，O={O1，O2，…，On}。步驟1將人工染色體種群AC及所產(chǎn)生的精英進(jìn)化染色體種群O混合放入選擇池中;步驟2從選擇池中隨機(jī)選擇兩條解，將適應(yīng)度....

本文編號：4029348