混合遺傳模擬退火算法解決多機調度問題

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