生物式基因演算法-以避難據點之人員分配與賑災物資配送規劃為例與賑災物資配;Biological-based Genetic Algorithm-the cases of human shelter resource allocation andemergency relief distribution planning

NCUIR > School of Management at National Central University > Graduate Institute of Information Management > Electronic Thesis & Dissertation > Item 987654321/54945

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/54945

Title:	生物式基因演算法-以避難據點之人員分配與賑災物資配送規劃為例與賑災物資配;Biological-based Genetic Algorithm-the cases of human shelter resource allocation andemergency relief distribution planning
Authors:	孫銘輝;Sun,Ming-hui
Contributors:	資訊管理研究所
Keywords:	基因演算法;類免疫演算法;最佳化問題;賑災物資配送;避難據點資源;shelter resource allocation planning;Immune algorithm;Genetic Algorithm;Optimization problem;emergency relief distribution planning
Date:	2012-07-12
Issue Date:	2012-09-11 19:13:12 (UTC+8)
Publisher:	國立中央大學
Abstract:	天然災害造成人民生命與財產的損失，而有效的災害應變將有助於減少損失，如何快速統籌現有的資源進行災害應變成為重要的課題。　　統籌資源進行災害應變可視為資源最佳化的問題，基因演算法為一個被廣泛應用於各領域最佳化問題中進行搜尋最佳解的主要技術，然而基因演算法透過世代接替的進行最佳解搜尋，在世代接替中複製機制、交配與突變運算可能使得優良染色體消失，而無法充分運用先前搜尋經驗。此外在搜尋中由於染色體族群缺乏多樣性而產生過早收斂現象而陷入區域最佳解。最後基因演算法需要對每一個染色體計算適應值而需要花費大量的運算成本。　　為了改善上述問題，本研究提出以菁英保留區、非適應值轉換、遷徙三個機制修改基因演算法的生物式基因演算法。本研究以旅行者問題與避難據點人員分配規劃、賑災物資配送規劃情境模擬問題進行基因演算法、類免疫演算法和生物式基因演算法之比較，經由實驗模擬結果顯示生物式基因演算法在搜尋最佳解上與執行時間皆優於基因演算法。與類免疫演算法比較之下，雖然在旅行者銷售問題與避難據點之人員分配規劃搜尋最佳解上則是略輸於類免疫演算法，然而在賑災物資配送規劃搜尋最佳解上則是優於類免疫演算法，並且在三個實驗中所需要的執行時間則是大幅少於類免疫演算法。透過實驗結果顯示，生物式基因演算法具備快速搜尋最佳解能力且僅需要較少的運算時間，能夠在災害應變中資源最佳化問題中快速提供有效的參考決策資源。　　Nature disaster can cause heavy loss in people’s lives and properties. It is the fact that the effective disaster response can reduce the damage and the number of lives lost. Therefore, how to plan and apply existing resources to the disaster response efficiently is always a key problem. In general, existent resource planning for the disaster response is a resource optimization problem. Particularly, the genetic algorithm (GA) is a well-known technique for the optimization problem in many domains. However, there are three limitations of GA. First, since good individuals may be changed to degeneracy in the selection mechanism, crossover operation and mutation operation, GA cannot utilize historical search experience soundly. Second, as the lack of population diversity takes place too early in iterations, GA is likely to be trapped in a region not containing the global optimum. This problem is called premature convergence. Finally, GA usually requires large computational time when evaluating the fitness function for every individuals.　　In this thesis, a biological-based genetic algorithm (BGA) is proposed by modifying GA with “elite preserve set”, “nonlinear fitness value transformation” and “migration”. By comparing GA and the immune algorithm (IA) with BGA in terms of three simulation experiments including the traveling-salesman problem, human shelter resource allocation planning and emergency relief distribution planning. The experimental results show that BGA outperforms GA in computational time and solution results. In the traveling-salesman problem and human shelter resource allocation planning experiments the solution of IA is slightly better than BGA. However, in the emergency relief distribution planning experiments BGA is superior to IA. Moreover, the BGA’s computational time is significantly less than IA. In summary, BGA can provide reasonably well solution with less computational time, which allows to efficient decision making for the disaster response.
Appears in Collections:	[Graduate Institute of Information Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	589	View/Open

社群 sharing

Loading...