混合遺傳模擬退火算法解決多機(jī)調(diào)度問題

　　摘要：將模擬退火引入遺傳算法，構(gòu)造混合遺傳模擬退火算法。通過對具體多機(jī)調(diào)度問題的求解，表明混合遺傳模擬退火算法的效率要優(yōu)于單一的遺傳算法和模擬退火算法。
　　關(guān)鍵詞：多機(jī)調(diào)度；遺傳算法；模擬退火算法；混合遺傳模擬退火算法
　　
　　作業(yè)調(diào)度問題是生產(chǎn)管理與控制的一個(gè)基本問題。按照加工設(shè)備數(shù)量和加工作業(yè)的流動(dòng)方式，一般可分為單機(jī)調(diào)度、并行機(jī)調(diào)度、Flowshop調(diào)度、可重入式調(diào)度和Jobshop調(diào)度等多種類型。作業(yè)調(diào)度中的許多問題，不僅具有隨機(jī)性、約束復(fù)雜、規(guī)模大及多目標(biāo)沖突等特點(diǎn)，而且許多都屬于NP完全問題，即使在單機(jī)情形也是如此。因此，如何尋求有效可行的調(diào)度求解方案，一直是生產(chǎn)管理與控制研究的熱點(diǎn)和難點(diǎn)。
　　
　　一、多機(jī)調(diào)度問題的數(shù)學(xué)模型
　　
　　二、算法分析
　　
　　自Davis首次將遺傳算法（Genetic Algorithms，GA）引入到調(diào)度問題的研究中以來，進(jìn)化算法（包括遺傳算法）在制造生產(chǎn)零件和生產(chǎn)調(diào)度研究領(lǐng)域獲得了廣泛的應(yīng)用，并取得了較好的優(yōu)化效果。遺傳算法用于求解某些并行多機(jī)調(diào)度問題也有不少的研究成果。遺傳算法的優(yōu)點(diǎn)是：不受搜索空間的限制性假設(shè)的約束，不必要求諸如連續(xù)性、導(dǎo)數(shù)存在和單峰的假設(shè)，并且具有內(nèi)在的并行性，收斂速度快，能夠解決非常困難的尋優(yōu)問題。當(dāng)然，傳統(tǒng)的遺傳算法也有許多缺點(diǎn)，其中最為嚴(yán)重的是“過早收斂”問題。所謂“過早收斂”是指在搜索的初期，由于優(yōu)良個(gè)體急劇增加使種群失去多樣性，從而造成程序陷入局部，達(dá)不到全局最優(yōu)解的現(xiàn)象。遺傳算法的另一個(gè)缺陷是“GA欺騙”問題，即在GA的搜索過程中，有可能搜索到最優(yōu)解然后又發(fā)散出去的現(xiàn)象。另外，遺傳算法還有參數(shù)選擇未能定量和不能精確定位最優(yōu)解等缺陷。
　　模擬退火算法（Simulated Annealing，SA）又稱為模擬冷卻法、統(tǒng)計(jì)冷卻法、Monte－Carlo退火法、隨機(jī)松弛法和概率爬山法等。模擬退火算法是一種新的統(tǒng)計(jì)優(yōu)化方法，其思想最早是由N．Metropolis等人借鑒統(tǒng)計(jì)力學(xué)中物質(zhì)退火方法而提出的。1983年Kirkpatrick等人開展了一些富有成效的工作，成功地將該思想引入組合優(yōu)化理論。模擬退火算法源于對固體退火過程的模擬，采用Meteropolis接受準(zhǔn)則，并用一組稱為冷卻進(jìn)度表的參數(shù)控制算法進(jìn)程，使算法在多項(xiàng)式時(shí)間里給出一個(gè)近似最優(yōu)解。模擬退火算法的主要優(yōu)點(diǎn)之一就是能以一定的概率接收目標(biāo)函數(shù)值不太好的狀態(tài)。即算法不但往好的方向走也可向差的方向走；這使得算法即便落入局部最優(yōu)的陷阱中，理論上經(jīng)過足夠長的時(shí)間后也可跳出來從而收斂到全局最優(yōu)解。模擬退火算法的主要缺點(diǎn)是解的質(zhì)量與求解時(shí)間長短之間的矛盾。為得到一個(gè)好的近似最優(yōu)解，需要進(jìn)行反復(fù)迭代運(yùn)算，當(dāng)問題的規(guī)模不可避免地增大時(shí)，缺乏可行的解決途徑。
　　
　　三、多機(jī)調(diào)度問題的混合遺傳模擬退火算法
　　
　　從測試結(jié)果來看，混合遺傳模擬退火算法在搜優(yōu)率上較遺傳算法和模擬退伙算法有了較大的提高。從運(yùn)算過程中的數(shù)據(jù)可以看出，由于混合遺傳模擬退火算法中鄰域的選擇、變異發(fā)生的概率都取自模擬退火的接受概率，再加上它采取了適應(yīng)度拉伸系數(shù)λ，使得遺傳算法的“早熟”現(xiàn)象得到很好的解決。另外本文所采用的混合遺傳模擬算法的還具有以下優(yōu)點(diǎn)：①優(yōu)化行為的增強(qiáng)。它具有GA算法的優(yōu)化時(shí)間性能和SA算法可以最終趨于全局最優(yōu)的優(yōu)點(diǎn)，克服了GA算法“過早收斂”問題和SA算法優(yōu)化時(shí)間性能較差的缺點(diǎn)。②優(yōu)化效率的提高。它是一種并行而且具有自動(dòng)保優(yōu)功能的算法，同時(shí)利用GA和SA各自不同的鄰域搜索結(jié)構(gòu)相結(jié)合，這樣使得算法在解空間中的搜索能力所增強(qiáng)，優(yōu)化效率得到提高。③魯棒性的提高。它的多點(diǎn)搜索消弱了SA算法對初值的依賴性，同時(shí)它還利用GA算法不影響平穩(wěn)分布的特性，提高了整個(gè)算法的魯棒性。
　　遺傳算法和模擬退火兩種算法均屬于基于概率分布機(jī)制的優(yōu)化算法。遺傳算法是通過概率意義下的“優(yōu)勝劣汰”思想的群體遺傳操作實(shí)現(xiàn)優(yōu)化；模擬退火算法的優(yōu)化機(jī)制是通過賦予搜索過程一種時(shí)變和最終趨于零的概率突變性，來避免陷入局部極小而達(dá)到全局最優(yōu)。本文結(jié)合這兩種算法的優(yōu)缺點(diǎn)，將模擬退火的思想引入遺傳算法，將模擬退火的接受概率應(yīng)用于種群的選取以及變異操作，并采用適應(yīng)值拉伸的方法，極大地緩解了遺傳算法的選擇壓力。它不但豐富和優(yōu)化了整個(gè)過程，而且增強(qiáng)了全局和局部意義下的搜索能力和效率。從試驗(yàn)結(jié)果可以看出，本文的混合遺傳模擬退火算法在解決多機(jī)任務(wù)調(diào)度問題時(shí)較單一的遺傳算法、模擬退火算法在優(yōu)化行為與效率上有了很大的提高。
　　
　　參考文獻(xiàn)：
　　1、許國平，葉效鋒，鮑立威.基于模擬退火遺傳算法的車輛路徑問題研究[J].工業(yè)控制計(jì)算機(jī).2004.24(3):58-62.
　　2、黃德才，郭海東，沈良忠.基于JIT的多目標(biāo)并行多機(jī)調(diào)度問題的混合遺傳算法[J].系統(tǒng)工程理論與實(shí)踐.2004.24(3):58-62.
　　3、張婧，楊炳儒.基于混合遺傳算法的聚類模式數(shù)據(jù)挖掘方法[J].微計(jì)算