并行遺傳算法求解應急系統(tǒng)最短路徑的研究.pdf

1、近年來突發(fā)事件頻繁爆發(fā)，我國格外重視危機管理、突發(fā)事件的預警與應急決策系統(tǒng)的建設。現有應急系統(tǒng)大多通過專家系統(tǒng)和方法庫進行知識的搜索和定位，以輔助決策。而決策系統(tǒng)知識的準確性與系統(tǒng)反應的時效性是衡量應急決策系統(tǒng)性能的兩個重要指標。為加速決策的時效性和準確性，本文以應急系統(tǒng)中的救援物資調度為背景，對實現并行遺傳算法求解應急系統(tǒng)中的最短路徑問題進行了研究。 首先，本文對應急決策支持系統(tǒng)和并行遺傳算法的發(fā)展和特點進行綜述，并介紹并行處

2、理的硬件系統(tǒng)及其并行環(huán)境下的支撐軟件，其中主要敘述工作站機群平臺上所采用的高效的編程環(huán)境MPI。在此基礎上針對應急系統(tǒng)中的救援物資調度決策過程，對原始道路圖進行預處理，建立其相應的網絡拓撲關系，將應急決策支持系統(tǒng)中最短路徑問題用圖論術語描述。 其次，論文重點分析遺傳算法固有的隱式并行性，結合主從并行程序設計特點，提出了工作站機群環(huán)境中基于MPI求解最短路徑的并行遺傳算法，并將模擬退火算法和多種群并行遺傳算法相結合，對并行算法加以

3、改進，即利用Boltzmann機制接收交叉和變異后的個體，避免遺傳算法中存在的早熟收斂問題，增強算法的全局收斂性。在該算法并行設計的劃分、通訊、組合和映射四個過程中，提出遺傳算法初始種群的劃分原則；利用MPI消息傳遞的六個基礎通信子集在各種群間進行通信和傳播各子種群的最優(yōu)解；運用組合法，以保持靈活性，減少通信開銷；將該算法映射為主從式工作站機群上的粗粒度并行遺傳算法，并使用靜態(tài)負載平衡任務調度技術改善映射質量。 最后，在實驗部分