博碩士論文 974203052 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:16 、訪客IP:3.94.129.211
姓名 孫銘輝(Ming-hui Sun)  查詢紙本館藏   畢業系所 資訊管理學系
論文名稱 生物式基因演算法-以避難據點之人員分配與賑災物資配送規劃為例 與賑災物資配
(Biological-based Genetic Algorithm-the cases of human shelter resource allocation andemergency relief distribution planning )
相關論文
★ 利用資料探勘技術建立商用複合機銷售預測模型★ 應用資料探勘技術於資源配置預測之研究-以某電腦代工支援單位為例
★ 資料探勘技術應用於航空業航班延誤分析-以C公司為例★ 全球供應鏈下新產品的安全控管-以C公司為例
★ 資料探勘應用於半導體雷射產業-以A公司為例★ 應用資料探勘技術於空運出口貨物存倉時間預測-以A公司為例
★ 使用資料探勘分類技術優化YouBike運補作業★ 特徵屬性篩選對於不同資料類型之影響
★ 資料探勘應用於B2B網路型態之企業官網研究-以T公司為例★ 衍生性金融商品之客戶投資分析與建議-整合分群與關聯法則技術
★ 應用卷積式神經網路建立肝臟超音波影像輔助判別模型★ 基於卷積神經網路之身分識別系統
★ 能源管理系統電能補值方法誤差率比較分析★ 企業員工情感分析與管理系統之研發
★ 資料淨化於類別不平衡問題: 機器學習觀點★ 基於關鍵點篩選於袋字模型之影像分類
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   至系統瀏覽論文 ( 永不開放)
摘要(中) 天然災害造成人民生命與財產的損失,而有效的災害應變將有助於減少損失,如何快速統籌現有的資源進行災害應變成為重要的課題。
  統籌資源進行災害應變可視為資源最佳化的問題,基因演算法為一個被廣泛應用於各領域最佳化問題中進行搜尋最佳解的主要技術,然而基因演算法透過世代接替的進行最佳解搜尋,在世代接替中複製機制、交配與突變運算可能使得優良染色體消失,而無法充分運用先前搜尋經驗。此外在搜尋中由於染色體族群缺乏多樣性而產生過早收斂現象而陷入區域最佳解。最後基因演算法需要對每一個染色體計算適應值而需要花費大量的運算成本。
  為了改善上述問題,本研究提出以菁英保留區、非適應值轉換、遷徙三個機制修改基因演算法的生物式基因演算法。本研究以旅行者問題與避難據點人員分配規劃、賑災物資配送規劃情境模擬問題進行基因演算法、類免疫演算法和生物式基因演算法之比較,經由實驗模擬結果顯示生物式基因演算法在搜尋最佳解上與執行時間皆優於基因演算法。與類免疫演算法比較之下,雖然在旅行者銷售問題與避難據點之人員分配規劃搜尋最佳解上則是略輸於類免疫演算法,然而在賑災物資配送規劃搜尋最佳解上則是優於類免疫演算法,並且在三個實驗中所需要的執行時間則是大幅少於類免疫演算法。透過實驗結果顯示,生物式基因演算法具備快速搜尋最佳解能力且僅需要較少的運算時間,能夠在災害應變中資源最佳化問題中快速提供有效的參考決策資源。
摘要(英) 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
論文目次 摘要 i
Abstract ii
致謝辭 iii
目錄  iv
圖目錄  vi
表目錄 viii
第一章 緒論  1
1-1研究背景  1
1-2研究動機  1
1-3研究目的  3
1-4論文架構  4
第二章 文獻回顧  5
2-1基因演算法  5
2-1-1編碼(encode)與解碼(decode)  6
2-1-2適應函數(fitness function)  8
2-1-3複製(reproduction)與選擇(selection)  8
2-1-4交配(crossover)  9
2-1-5突變(mutation)  14
2-1-6終止條件  15
2-1-7重要參數(parameters)  15
2-2 類免疫演算法  16
2-2-1免疫系統簡介  16
2-2-2類免疫演算法相關研究  17
2-3災害應變資源規劃相關研究  21
第三章 生物式基因演算法  24
3-1菁英保留區  25
3-2非線性適應值轉換  26
3-3遷徙  29
3-4生物式基因演算法流程  30
3-5生物式基因演算法虛擬碼  31
3-6生物式基因演算法與基因演算法之比較  33
第四章 實驗結果  34
4-1參數挑選方式  34
4-2實驗一  35
4-2-1旅行銷售員問題  35
4-2-2旅行銷售員問題數學模式  36
4-2-3演算法編碼、交配與突變方式之設定  37
4-2-4測試例題eil51實驗結果  37
4-2-5測試例題kroA100實驗結果  45
4-3實驗二  52
4-3-1情境模擬-避難據點之人員分配規劃  52
4-3-2避難據點資源分配數學模式  53
4-3-3避難據點之人員分配規劃資料  54
4-3-4演算法編碼、交配與突變方式之設定  54
4-3-5避難據點之人員分配規劃實驗結果  56
4-3-6避難據點之人員分配規劃結果  63
4-4實驗三  66
4-4-1情境模擬-賑災物資配送規劃  66
4-4-2賑災物資配送規劃數學模式  67
4-4-3賑災物資配送規劃資料集  70
4-4-4演算法編碼、交配與突變方式之設定  71
4-4-5賑災物資配送規劃實驗結果  72
4-4-6賑災物資配送規劃規劃結果  78
4-5實驗結果小結  80
第五章 結論與未來研究方向  83
5-1結論  83
5-2未來研究方向  84
參考文獻  85
附錄一  91
附錄二  93
參考文獻 [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.
[2] 內政部消防署全球資訊網,2012年3月15日取自http://www.nfa.gov.tw/ 。
[3] 交通部中央氣象局,2012年3月15日取自, http://www.cwb.gov.tw/V7/。
[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.
[6] Kirkpatrick, S., Gelatt, C.D., Jr., and Vecchim, M.P., (1983), "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp. 671-680
[7] Holland, J.H., (1975), "Adaptation in Natural and Artificial Systems," MIT Press, Cambridge, MA.
[8] Kennedy, J. and Eberhart, R.C., (1995), "Particle swarm optimization," IEEE International Conference on Neural Networks, pp.1942-1948.
[9] Gen, M. and Cheng R., (1997), "Genetic Algorithms and Engineering Design," Wiley, New York, USA.
[10] Tsai, C.F. and Hsiao, Y.C., (2010), "Combining multiple feature selection methods for stock prediction: Union, intersection, and multi-intersection approaches," Decision Support Systems, vol. 50, no. 1, pp. 258-69.
[11] Cano, J.R., Herrera, F., and Lozano, M., (2003), "Using evolutionary algorithms as instance selection for data reduction in KDD: an experimental study," IEEE Transactions on Evolutionary Computation, vol. 7, no. 6, pp. 561-75.
[12] Goldberg, D.E., (1989), "Genetic Algorithm in Search, Optimization, and Machine Learning," Addison-Wesley, Boston, MA, USA.
[13] Jiao, L. and Wang, L., (2000), "A novel genetic algorithm based on immune," IEEE Transactions on Systems, Man and Cybernetics, Part A, vol. 30, no. 5, pp. 552-561.
[14] Povinelli, R.J, (2000), "Improving computational performance of genetic algorithms: a comparison of techniques," Proc. Genetic and Evolutionary Computation Conf, (GECCO-2000) Late Breaking Papers, pp. 297-302.
[15] Cooper, J. and Hinde, C., (2003), "Improving genetic algorithms’ efficiency using intelligent fitness functions," Developments in Applied Artificial Intelligence, vol. 2718, pp. 1-58.
[16] Povinelli, R.J. and Feng, X., (1999), "Improving Genetic Algorithms Performance By Hashing Fitness Values," In Proceedings Artificial Neural Network, pp. 399-404.
[17] Chen, Y., Hu, J., Hirasawa, K., and Yu, S., (2007), "GARS: an improved genetic algorithm with reserve selection for global optimization," Proceedings of the 9th annual conference on Genetic and evolutionary computation: ACM, pp. 1173-1178.
[18] Jung, S.H., (2009), "Selective Mutation for Genetic Algorithms," World Academy of Science, Engineering and Technology 56, pp. 478-481.
[19] Park, T. and Ryu, K.R., (2010), "A dual-population genetic algorithm for adaptive diversity control," IEEE Transactions on Evolutionary Computation, vol. 14, no. 6, pp. 865-84.
[20] Lozano, M., Herrera, F., and Cano, J.R., (2008), "Replacement strategies to preserve useful diversity in steady-state genetic algorithms," Information Sciences, vol. 178, no. 23, pp. 4421-4433.
[21] Darwin, C., (1859), "The origin of species by means of natural selection," 1st ed. London: John Murray.
[22] Kindt, T.J., Osborne, B.A., and Goldsby, R.A, (2006), " Kuby Immunology (6th ed)," W.H. Freeman and Company, New York, USA.
[23] Liu, F., Wang, Q., and Gao, X., (2006), "Survey of artificial immune system," International Symposium on Systems and Control in Aerospace and Astronautics
, pp. 985-989.
[24] Wang, X., Gao, X.Z., and Ovaska, S.J., (2004), "Artificial immune optimization methods and applications – a survey," IEEE International Conference on Systems, Man and Cybernetics, vol. 4, pp. 3415-3420.
[25] Chun, J.S., Kim, M.K., and Jung, H.K., (1997), "Shape Optimization of electromagnetic devices using Immune Algorithm," IEEE Transactions on Magnetics, vol. 33, no. 2, pp. 1876-1879.
[26] Chun, J.S., Jung, H.K., and Hahn, S.Y., (1998), "A study on comparison ofoptimization performances between immune algorithm and otherheuristic algorithms," IEEE Transactions on Magnetics. vol. 34, no. 5, pp. 2972 - 2975.
[27] de Castro, L.N. and Von Zuben, F.J., (2002), "Learning and optimization using the clonal selection principle," IEEE Transactions on Evolutionary Computation, vol.6, no. 3, pp. 239-251.
[28] Chen, T.C. and Hsieh, Y.C., (2008),"Using immune-based genetic algorithms for single trader’’s periodic marketing problem", Mathematical and Computer Modelling, vol. 48, no. 3-4, pp. 420-428.
[29] 李志華,「基因演算法於震災路網搶修排程問題之研究」,國立成功大學交通管理研究所,碩士論文,民國92年。
[30] 陳昭蓉,「以倒傳遞類神經網路作為規劃震災後災民疏散系統之應用」,國立台北科技大學建築與都市設計研究所,碩士論文,民國93年。
[31] Hsueh, C., Chen, H., and Chou, H., (2008), "Dynamic vehicle routing for relief logistics innatural disasters," In: Vehicle routing problem, chap. 5, pp. 71-84, I-Tech Education and Publishing, Vienna, Austria.
[32] Lin, N. and Li, Z., (2009), "Emergency Relief Goods Multi-Mode Transportation Based on Genetic Algorithm," Conference on Intelligent Computation Technology and Automation, vol. 1, pp. 181-184.
[33] Zhang, L., Lin, Y., Yang, G., and Chang, H., "Emergency resources scheduling based on adaptively mutate genetic algorithm," Computers in Human Behavior, vol. 27, no. 5, pp. 1493-1498.
[34] Berkoune, D., Renaud, J., Rekik, M., and Ruiz, A., (2012), "Transportation in disaster response operations," Socio-Economic Planning Sciences, vol. 46, no. 1, pp. 23-32.
[35] Stern, C., (1962),"Wilhelm Weinberg", Genetics, vol. 47, pp. 1-5.
[36] Emigh, T.H., (1980), "Comparison of Tests for Hardy–Weinberg Equilibrium," Biometrics, vol. 36, no. 4, pp. 627-642.
[37] Koepfli, K.P., Gompper, M.E., Eizirik, E., Ho, C.C., Linden, L., Maldonado, J.E., and Wayne, R.K., (2007), "Phylogeny of the Procyonidae (Mammalia: Carnivora): molecules, morphology and the Great American InterchangeMol," Molecular Phylogenetics and Evolution., vol. 43, no. 3, pp. 1076-1095.
[38] Flynn, J.J. and Wyss, A.R., (1998), "Recent advances in South American mammalian paleontology," Trends in Ecology and Evolution, vol. 13, no. 11, pp. 449-454.
[39] Flood, M.M., (1956), "The Traveling-Salesman Problem", Operations Research, vol. 4, no. 1, pp. 61-75.
[40] Larranaga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I., and Dizdarevic, S., (1999), "Genetic algorithms for the Travelling Salesman Problem: A review of representations and operators", Artificial Intelligence Review, vol. 13 no. 2, pp. 129-170.
[41] Orman, A.J. and Williams, H.P., (2004), "A survey of different integer programming formulations of the travelling salesman problem," Operational Research working papers, LSEOR04.67. Department of Operational Research, London School of Economics and Political Science, London, UK.
[42] Laporte, G., (1986), "Generalized subtour elimination constraints and connectivity constraints, "The Journal of the Operational Research Society, vol. 37, no. 5, pp. 509-514.
[43] Potvin, J.Y., (1996), "Genetic algorithms for the traveling salesman problem," Annals of Operations Research, vol. 63 no. 3, pp. 337-370.
[44] Reinelt, G., (1991), "TSPLIB- A Traveling Salesman Problem Library," ORSA Journal on Computing, vol. 3, no. 4, pp. 376-384.
[45] Wang, H.F. and Chen, Y.Y., (2012), "A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time Window", Computers and Industrial Engineering, vol. 62, no. 1, pp. 84-95.
[46] Rieck, J. and Zimmermann, J., (2009). "A hybrid algorithm for vehicle routing of less-than-truckload carriers, "Lecture Notes in Economics and Mathematical Systems, vol.624, pp. 155-171.
[47] Ngueveu, S.U., Prins C., and Wolfler-Calvo, R., (2010), "An effective memetic algorithm for the cumulative capacitated vehicle routing problem," Computers & Operations Research, vol. 37, no. 11, pp. 1877-1885.
[48] Karlaftis, M.G., Kepaptsoglou, K., and Sambracos, E., (2009), "Containership routing with time deadlines and simultaneous deliveries and pick-ups," Transportation Research Part E: Logistics and Transportation Review, vol. 45, no. 1, pp. 210-221.
[49] Detlhoff, J., (2001), "Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up," OR Spektrum, vol. 33, no. 1, pp. 79-96
[50] Solomon, M.M., (1987), "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, vol. 35, no. 2, pp. 254-265.
[51] Prins, C., (2004), "A simple and effective evolutionary algorithm for the vehicle routing problem," Computers & Operations Research, vol. 31, no. 12, pp. 1985-2002.
[52] Bean, J.C., (1994), "Genetic algorithms and random keys for sequencing andoptimization," ORSA Journal on Computing, vol. 6, no. 2, pp. 154-160.
指導教授 蔡志豐(Chih-Fong Tsai) 審核日期 2012-7-12
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明