生物式基因演算法-以避難據點之人員分配與賑災物資配送規劃為例
與賑災物資配

天然災害造成人民生命與財產的損失，而有效的災害應變將有助於減少損失，如何快速統籌現有的資源進行災害應變成為重要的課題。　　統籌資源進行災害應變可視為資源最佳化的問題，基因演算法為一個被廣泛應用於各領域最佳化問題中進行搜尋最佳解的主要技術，然而基因演算法透過世代接替的進行最佳解搜尋，在世代接替中複製機制、交配與突變運算可能使得優良染色體消失，而無法充分運用先前搜尋經驗。此外在搜尋中由於染色體族群缺乏多樣性而產生過早收斂現象而陷入區域最佳解。最後基因演算法需要對每一個染色體計算適應值而需要花費大量的運算成本。　　為了改善上述問題，本研究提出以菁英保留區、非適應值轉換、遷徙三個機制修改基因演算法的生物式基因演算法。本研究以旅行者問題與避難據點人員分配規劃、賑災物資配送規劃情境模擬問題進行基因演算法、類免疫演算法和生物式基因演算法之比較，經由實驗模擬結果顯示生物式基因演算法在搜尋最佳解上與執行時間皆優於基因演算法。與類免疫演算法比較之下，雖然在旅行者銷售問題與避難據點之人員分配規劃搜尋最佳解上則是略輸於類免疫演算法，然而在賑災物資配送規劃搜尋最佳解上則是優於類免疫演算法，並且在三個實驗中所需要的執行時間則是大幅少於類免疫演算法。透過實驗結果顯示，生物式基因演算法具備快速搜尋最佳解能力且僅需要較少的運算時間，能夠在災害應變中資源最佳化問題中快速提供有效的參考決策資源。

關鍵字

基因演算法；類免疫演算法；最佳化問題；賑災物資配送；避難據點資源

並列摘要

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.

並列關鍵字

shelter resource allocation planning ； Immune algorithm ； Genetic Algorithm ； Optimization problem ； emergency relief distribution planning

參考文獻

[29] 李志華，「基因演算法於震災路網搶修排程問題之研究」，國立成功大學交通管理研究所，碩士論文，民國92年。

[21] Darwin, C., (1859), "The origin of species by means of natural selection," 1st ed. London: John Murray.

[1] Dilley, M., Chen, R.S., Deichmann, U., Lerner-Lam, A.L., Arnold, M., Agwe, J., Buys, P., Kjekstad, O., Lyon, B., and Yetman, G., (2005), "Natural Disaster Hotspots: A Global Risk Analysis," The World Bank Group, Washington, D.C., USA.

[4] McLoughlin, D., (1985), "A framework for integrated emergency management," Public Administration Review, vol.45, pp. 165-72.

[5] Tzeng, G.H., Cheng, H.J., and Huang, T.D., (2007), " Multi-objective optimal planning for designing relief delivery systems," Transportation Research Part E, vol. 43, no. 6, pp. 673-686.

國際替代計量

生物式基因演算法-以避難據點之人員分配與賑災物資配送規劃為例與賑災物資配

未授權

主題瀏覽