Title

應用基因演算法及平行禁忌搜尋混合模式於自動化分類及山崩潛感分析

Translated Titles

Application of Genetic Algorithm and Tabu Search to the Automatic Classification and Landslide Susceptibility Analysis

DOI

10.6845/NCHU.2010.01221

Authors

楊曄芬

Key Words

基因演算法 ; 禁忌搜尋法 ; 混合模式 ; 山崩潛感分析 ; 非監督式分類 ; Genetic Algorithm ; Tabu Search ; Hybrid Model ; Landslide Susceptibility Analysis ; Unsupervised Classification

PublicationName

中興大學土木工程學系所學位論文

Volume or Term/Year and Month of Publication

2010年

Academic Degree Category

博士

Advisor

楊明德

Content Language

繁體中文

Chinese Abstract

本研究主要目的在藉由比較基因演算法(Genetic Algorithm)及結合基因演算法與禁忌搜尋法(Tabu Search)混合模式,透過光譜波段知識庫之建立,提出一個較傳統ISODATA、K-Means及單一基因演算法為佳之全自動化的非監督式影像分類方式。 參考過去文獻及其相關理論論述,可知基因演算法在其基礎操作4大程序(初始化、選擇、交配及突變)演算過程中,每一個操作程序均有相當多樣化的設定及演算方式。而不同設定及演算方式對於其進行非監督式分類之結果具有的影響,於影像分類文獻中並未被充分探討。因此,本研究第一部份即針對基因演算法不同操作程序中相關設定及演算方式、不同之目標函數透過Davies-Bouldin Index(DBI)及Fuzzy c-Means(FCMI)基礎理論之結合新發展之目標函數(DBFCMI)作一分析及比較,期能透過這些分析比較提出一個較一般設定為佳的設定組合來進行全自動化之非監督式分類。此部分結果亦將透過不同性質之影像進行分析結果之驗證。 另外,雖然於第一部份透過基因演算法可求得相當高精度的分類結果,但受限於啟發式演算法本身的缺點--即無法確定最佳解是否是解空間內全域最佳解或是區域最佳解。而禁忌搜尋法由於具有針對過去最佳解之記憶表單設計(Memory List),透過此記憶表單可以讓基因演算法於找到區域最佳解時仍可擴展其搜尋空間至區域外部,藉此不斷向外擴展搜尋區域外部解的方式以修正其搜尋到之解為全域最佳解或是近似全域最佳解。因此,本研究第二部分即透過第一部份提出之最佳化基因演算法參數組合與禁忌搜尋法與禁忌搜尋法進行整合以建立一個新的搜尋方法,藉由禁忌搜尋法搜尋最佳解紀錄之優勢,擴展基因演算法解空間至全域或近似全域之搜尋。 本研究混合模式基於基因演算法上採用前後幾次分類中心不再有變化後即停止之自動化終止條件,不同於傳統ISODATD及K-Means分類方式,使用者須給定起始分類數或是一些門檻值設定。另外,在群集分析後,群集結果須另外透過人為判釋才能對應到地物類別,而本研究藉由Access所建立之知識庫,透過「IF」「THEN」之「規則」推理邏輯機制,並結合基因演算法自動化群集分析方式,可完全自動化判釋各群集所屬之地物類別。 本研究以SPOT-5衛星影像進行基因演算法不同參數設定組合之比較與評估,另外將評估後分類準確度較高之基因演算法組合參數應用於IKONOS及DMC影像上,同樣也可獲得高於ISODADA及K-Means分類之準確度,以再次確認此組合參數分類準確度之可信度。最後將此基因演算法之組合參數應用於新建模式內,透過新模式結合禁忌搜尋法之記憶表單設計之優勢,提升原有單一基因演算法模式之分類精度,並將此高準確度分類結果應用於山崩潛感分析應用研究上,以改善傳統上應用土地使用(Land Use) 指標在製作上耗費時間以致於無法提供即時監測資料之缺憾。 本研究相關數值模式均透過MATLAB 2008b版本進行程式撰寫及分析,後端知識庫之設計則以MATLAB透過ODBC連結Access之方式,進行影像歷史資料之地物光譜灰階值之自動化搜尋與比對。山崩潛勢分析之相關彩色影像則利用ERDAS IMAGINE及Arc GIS 9版進行圖層套疊與主題圖層次類別展示。

English Abstract

In this research, the best composed setting of Genetic Algorithm (GA) is discovered by means of testing many different composed settings of chromosome length, population size, and crossover way and so on one another and a newly established hybrid method by integrating Tabu Search (TS) into GA to provide a completely automatic unsupervised classification method. The main objective of this research is to accquire the higher interpretating accuracy with the hybrid model than traditional unsupervised classification such as ISODATA and K-Means. Referring to the literatures and the applicable theories of GA, various composed settings and schemes of the four operations (Initialization, Selection, Crossover, and Mutation) of GA have been developed and discussed. Nevertheless, how these composed settings and schemes applicable to the four operations effect the accuracy has not been considered and discussed adequately. Therefore, in the first part of this research, a best composed setting for the automatic unsupervised classification of GA can be verified by means of the comparison between the various composed settings and schemes related to each operation of GA and between the different fitness functions such as Davies-Bouldin Index, Fuzzy c-Means Index, K-Means Index, Partition Separation Index, Separation Index, and DBFCMI Index. Furthermore, this optimal composed setting of GA is applied to SPOT-5, IKONOS, and DMC images in which the SPOT-5 image was used to verify the accuracy of the performance. The best composed setting of GA searches a solution with a relatively high accuracy, but can only guarantee within a local domain instead of the global space. Tabu Search has the superiority of the memory list and thus the solution searching can be expanded from the current searching district out to the global domain or the approximately global domain. The global optimum or the approximately global optimum can be found in stead of the only local optimum by means of this way, therefore, the second part of this research is to establish a new hybrid model based on the GA and TS to search the maximum solution space of the domain so that the global optimum can be found certainly and expectably. Unlike ISODATA and K-Means, which the user should set up either the classified numbers or the threshold for the searching in the beginning, the hybrid model on the basis of GA and TS needs the termination criterion built based on the constantly unchanged outcomes instead of cluster numbers or thresholds. The research is combining this mechanism and the rule of (IF….THEN) of the knowledge base for the following mapping step between the clusters and species so to turn the unsupervised classification into automatic operation. All the results of the various composed settings of GA, hybrid model based on GA and TS, ISODATA and K-Means are mainly evaluated based on K-HAT. Furthermore, the interpreted image, which is evaluated by the best model through the foregoing comparison, can be provided to the application of the landslide susceptible analysis. With replacing the land use layer by the classified image as an affecting factor of the landslide susceptible analysis, the information of land cover can be update frequently so that the terrain condition can be acquired immediately after a disaster occures. In this research, all of the calculating programs were coded in MATLAB, version R2008b. The database is designed on the basis of MATLAB connecting with Access by ODBC (Open Database Connectivity) for the automatic labeling of the unsupervised classification. The application software, ERDAS IMAGINE, version 8.5 and Arc GIS, version 9, which is specifically good at multi-spectral images processing was applied here to processe the satellite image and to present the colorized thematic maps the for the landslide susceptibility analysis. The statistic analyses and the consistency credibility analysis were implemented by SPSS, version 10.

Topic Category 工學院 > 土木工程學系所
工程學 > 土木與建築工程
Reference
  1. 林昭遠、劉祐如、林文賜,久久峰崩塌區位植生復育影響因子之研究,水土保持學報,38(3),pp.267-278,2006。
    連結:
  2. 洪蜜琪,整合光譜與空間資訊於影像分類-應用於覆蓋與管理因子(C值)之研究,國立中興大學土木工程學系碩士論文,81頁,2007。
    連結:
  3. 溫振宇,結合地震與颱風因子之山崩模式分析,國立成功大學地球科學研究所碩士論文,103頁,2005。
    連結:
  4. Bäck, T., Fogel, D.B., and Michalewicz, Z., Handbook of Evolution Computation, Taylor & Francis Group, Great Britain, 1130p., 1997.
    連結:
  5. Bandyopadhyay, S., and Maulik, U., Genetic clustering for automatic evolution of clusters and application to image classification, IEEE pattern recognition, 35(2002), pp.1197-1208, 2002 (a).
    連結:
  6. Bandyopadhyay, S., and Maulik, U., An evolution technique based on K-Means algorithm for optimal clustering, Information Seiences, 146(2002), pp.221-237. 2002 (b).
    連結:
  7. Bezdek, J.C., Pattern Recognition with Fuzzy Objective Function Algorithms, New Yourk, Plenum Press, 256p., 1981.
    連結:
  8. Chalermwat, P., El-Ghazawi, T., and LeMoigne, J., 2-phase GA-based image registration on parallel clusters, Future Generation Computer Systems, 17(2001), pp.467-476, 2001.
    連結:
  9. Chen, Y.R., Chen, J.W., Hsieh, S.C., and Ni, P.N., The application of Remote Sensing Technology to the Interpretation of Land Use for Rainfall-Induced Landslides Based on Genetic Algorithms and Artificial Neural Networks, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2(2), pp.87-95, 2009.
    連結:
  10. Clausi, D.A., K-means Iterative Fisher (KIF) Unsupervised Clustering Algorithm Applied to Inage Texture Segmentation, Pattern Recognitiion, 35(2002), pp.1959-1972, 2002.
    連結:
  11. Davies, D.L., and Bouldin, D.W., A clusster separation measure, IEEE Trans. Pattern Anal. Machine Intell., 1(4), pp.224-227, 2000.
    連結:
  12. De Alwis, D.A., Easton, Z.M., Dahlke, H.E., Philpot, W.D., and Steenhuis, T.S., Unsupervised classification of saturated areas using a time series of remotely sensed images, Hydrology and Earth System Sciences, Vol.11, pp1609-1620, 2007.
    連結:
  13. Deb, K., Multi-objective optimization using evolutionary algorithms, John Willy & Sons. Ltd., New York, 473p., 2001.
    連結:
  14. Denna, M., Mauri, G., and Zanaboni, A.M., Learning Fuzzy Rules with Tabu Search An Application to Control, IEEE Transactions on Fuzzy Systems, 7(2), pp.295-318, 1999.
    連結:
  15. Dunn, J.C., A fuzzy relative of the ISODATA process and its in detecting compact well-separated clusters, J. Cybernet., Vol. 3, pp.32-57, 1974.
    連結:
  16. Hajji, O., Brisset, S., and Brochet, P., A New Tabu Search Method for Optimization with Continuous Parameters, IEEE Transactions on Magnetic, 40(2), pp.1184-1187, 2004.
    連結:
  17. Kim, H.C., Hayashi, Y., and Nara, K., An Algorithm for Thermal Unit Maintenance Scheduling Through Combined Use of GA SA and TS, IEEE Transaction on Power Systems, 12(1), pp.329-335, 1997.
    連結:
  18. Kim, J.B., and Kim, H. J., GA-Based Image Restoration by Isophote Constraint Optimazation, Eurasip Journal on applied Signal Processing, 2003(3), pp.238-243, 2003.
    連結:
  19. Koza, J.R., Genetic programming: on the programmping of computers by means of natural selection, 4th Edition, Massachusetts Institute of Technology, 805p., 1992.
    連結:
  20. Li, J.X., Su, H., Chen, H.S., and Futscher, B.W., Optimal Search-Based Gene Subset Selection for Gene Array Cancer Classification, IEEE Transactions on Information Technology in Biomedicine, 11(4), pp.398-405, 2007.
    連結:
  21. Liu, ZJ.., Liu, A.X., Wang, C.Y., and Niu, Z., Evolving neural network using real coded genetic algorithm (GA) for multispectral image classification, Future Generation Computer System, 20(7), pp.119-1129, 2004.
    連結:
  22. MacQueen, J.B., Some Methods for clasification and Analysis of Multivariate Obervations, Proceedings of 5th Berkeley Symposium on Mathematical Stastics and Probability, Berkeley, Vol.1, pp.281-297, 1967.
    連結:
  23. Maiti, A.K., and Maiti, M., Discounted multi-item inventory model via genetic algorithm with Roulette wheel selection, arithmetic crossover and uniform mutation in constraints bounded domains, International Journal of Computer Mathematics, 85(9), pp.1341-1353, 2008.
    連結:
  24. Mantawy, A.H., Abdel-Magid, Y.L., and Selim, S.Z., Integrating Genetic Algorithms, Tabu Search, and Simulated Annealing for the Unit Commitment Problem, IEEE Transaction on Power Systems, 14(3), pp.829-836, 1999.
    連結:
  25. Martini, H., and Schöbel, A., Median and center hyperplanes in Minkowski spaces -- a unified approach, Discrete Mathematics, 241(1), pp.407-426, 2001.
    連結:
  26. Mather, P.M., Computer processing of remotely-sensed images: an introduction,‎ John Wiley & Sons, Ltd., England, 324p., 2004.
    連結:
  27. Minami, M., Agbanhan, J., and Asakura, T., Robust scene recognition using a GA and real-world raw-image, Measurement, 29(2001), pp.249-267, 2001.
    連結:
  28. Mishra, A., Dutta, P.K., and Ghosh, M.K., A GA based approach for boundary detection of left ventricle with echocardiographic image sequences, Image and Vision Computing, Vol.21, pp.967-976, 2003.
    連結:
  29. Rau, J.Y., Chen L.C., Liu, J.K., and Wu, T.H., Dynamics Monitoring and Disaster Assessment for Watershed Management Using Time-Series Satellite Images, IEEE Transactions Geoscience and Remote Sensing, 45(6), pp.1641-1649, 2007.
    連結:
  30. Rawlins, G.J.E., (Ed.), Foundation of Genetic Algorithms, Morgan Kaufmann Publishers, Inc., USA, 341p., 1991.
    連結:
  31. Sivanandam, S.N., and Deepa, S.N., Introduction to Genetic Algorithms, Springer, Berlin, 442p., 2008.
    連結:
  32. Tahir, M.A., and Bouridane, A., Novel Round-Robin Tabu search Algorithm for Prostage Cancer Classification and Diagnosis Using Multispectral Imagery, IEEE Transactions on Information Technology in Biomedicine, 10(4), pp.782-793, 2006.
    連結:
  33. Van Oort, P.A.J., Interpreting the change detection error matrix, Remote Sensing of Environment, 108(1), pp.1-8, 2007.
    連結:
  34. Victoire, T.A.A., and Jeyakumar, A.E., Unit commitment by a Tabu-search-based hybrid-optimisation technique, IEEE Proceedings-Generation, Transmission, and Distribution, 152(4), pp.563-574, 2005.
    連結:
  35. Xie, X.L., and Beni, G., A Validity Measure for Fuzzy Clustering, IEEE Transaction on Pattern Analysis and Machine Inteligence, 13(8), pp.841-847, 1991.
    連結:
  36. Yang, G., Reinstein, L.E., Pai, S.,and Xu, Z., Carroll, and D.L., A new genetic algorithm technique in optimization of prostate implants, Medical Physics, 35(5), pp.104-112, 2000.
    連結:
  37. Yang, M.D., A genetic algorithm (GA) based automated classifier for remote sensing imagery, Canadian Journal of Remoting Sensing, 33(3), pp.203-213, 2007.
    連結:
  38. Yang, M.D., and Yang, Y.F., Genetic algorithm for unsupervised classification of remote sensing imagery, proceedinga of SPIE/IS and T Electronic Imaging, SPIE5298, pp.395-402, 2004.
    連結:
  39. Yang, M.D., Yang, Y.F., and Hsu, S.C., Application of remotely sensed data to the assessment of terrain factors affecting the Tsao-Ling landslide, Canadian Journal of Remoting Sensing, 30(4), pp.593-603, 2004.
    連結:
  40. Yang, M.S., and Wu, K.L., A new validity index for fuzzy clustering, IEEE International Fuzzy Systems Conference, pp.89-92, 2001.
    連結:
  41. Zhang, L.P., Zhao Y.D., Huang, B., and Li, P.X., Texture Feature Fusion with Neighborhood-Oscillating Tabu Search for High Resolution Image Classification, Photogrammetric Engineering and Remote Sensing, 74(3), pp.323-331, 2008.
    連結:
  42. (一)、中文文獻
  43. 林書毅,區域性山坡穩定評估方法探討-以林口台地為例,國立中央大學應用地質研究所碩士論文,92頁,1999。
  44. 林鼎鈞、陳紫娥、林祥偉、徐弘明、游麗方,應用地理資訊系統技術探討知本溪集水區崩塌地特性,資源與環境學術研討會,pp.499-508,2009。
  45. 張榮峻、蔡知耕,運用遙測技術與人工智慧方法於山崩潛勢之研究,台灣地理資訊學會年會暨學術研討會論文集,第1-11頁, 2005。
  46. 莊雲翰,結合影像區塊及知識庫分類之研究--以IKONOS衛星影像為例,國立中央大學土木工程學系,94頁,2002。
  47. 陳怡睿、謝舜傑、陳信達,應用知識庫分類法判釋SPOT衛星影像坡地崩塌之研究,台灣地理資訊學會年會暨學術研討會論文集,第1-10頁, 2005。
  48. 陳彥宏,運用紋理資訊輔助高解析度衛星影像於都會區水稻田萃取之研究,私立逢甲大學土地管理學系碩士論文,121頁, 2004。
  49. 黃明哲,應用航測影像及光達資料探討以知識庫為基礎之都市地物特徵分類之研究,國立中山大學海洋環境及工程學系博士論文,219頁,2007。
  50. 黃崇賢,山坡地山崩災害管理之研究-以台南現為例,私立長榮大學土地管理與開發研究所碩士論文,116頁,2004。
  51. 楊錦釧、蔡東霖、張胤隆、姜世偉、蘇歆婷,石門水庫集水區崩塌與庫區淤積風險評估研究(2/3),經濟部水利署,pp.57-78,2007。
  52. 劉盈利,螞蟻演算法與禁忌搜尋法混合模式於配水管網設計最佳化之應用,國立中興大學環境工程研究所碩士論文,151頁,2004。
  53. 蔡光榮、劉明忠、戴君翰、施俊廷,台灣中部山區道路邊波崩塌特性之數值分析模式建置,台灣公路工程,32(12),pp.33-45,2006。
  54. 羅佳明,GPS/GIS/RS應用於地震災區坡地災害防治工程調查及其風險評估模式之建置與應用,國立屏東科技大學土木工程研究所碩士論文,233頁,2002。
  55. (二)、英文文獻
  56. Arai, K.H., and Bu, X.Q., ISODATA clustering with parameter (threshold for merge and split) estimation based on GA: Genetic Algorithm, Reports of Faculty of Science and Engineering, Saga University, 36(1), pp.17-23, 2007.
  57. Avery, T.E. and Berlin, G.L., Fundamentals of remote sensing and airphoto interpretation, MacMillan Publishing Company, New York, 472 p., 1992.
  58. Bäck, T., Fogel, D.B., and Michalewicz, Z., Evolutionary compution 1:basic algorithm and operators, Taylor & Francis Group, Great Britain, 301p., 2000.
  59. Bezdek, J.C., Fellow IEEE., and Nikhil, R.P., Some New Indexes of Cluster Validity, IEEE Transaction on Systems, Man, and Cybernetics—Part B: Cybernetics, 28(3), pp.301-315, 1998.
  60. Burke, E., and Kendall, G. (Editors), Search methodologies: introductory tutorials in optimization and decision support techniques, Springer, 620p., 2005.
  61. Chen, C.C., and Lin, C.S., A GA-based Nearly Optimal Image Authentication Approach, International Journal of Innovative Computing, Information and Control, 3(3), pp.631-640, 2007.
  62. Coley, D.A., An introduction to genetic algorithms for scientists and engineers, World Scientific Publishing Co. Pte. Ltd., USA, 203p., 1999.
  63. Duda, R.O., Hart, P.E., and Stork, D.G., Pattern Classification, 2th Edition, John Wiley & Sons, 654p., 2000.
  64. Glover, F., and Laguna, M., Tabu Search, 6th Printing, Kluwer Academic Publishers, USA, 357p., 2002.
  65. Jadaan, O.A., Rajamani, L., and Rao, C.R., Improved Selection Operator for GA, Systems, Man, and Cybernetics, 1999. IEEE SMC '99 Conference Proceedings, 1999 IEEE International Conference on, Vol.1, pp.625-630, 1999.
  66. Jiang T.Z., and Yang, F.G., An Evolutionary Tabu Search for Cell Image Segmentation, Systems, Man, and Cybernetics Society─Part B: Cybernetic, IEEE Transactions on, 32(5), pp.675-678, 2002.
  67. Kawaguchi, T., Baba, T., and Nagata, R., 3-D object recognition using a genetic algorithm-based search scheme, IEICE transactions on information and systems, E80D(11), pp.1064-1073, 1997.
  68. Lillesand, T.M., and Kipper, R.W., Remote Senesing and Image Interpretation, 4th Edition, John Wiley & Sons, Inc., USA, 724p., 2000.
  69. Lillesand, T.M., Kiefer, R.W., and Chipman, J.W., Remote sensing and image interpretation, 6th Edition, John Wiley & Sons, New York. 768 p., 2007.
  70. Martini, A., Ferro-Famil, L., Pottier, E., and Dedieu, J.P., Dry snow extent monitoring in strong topography conditions, Geoscience and Remote Sensing Symposium, IGARSS '05. Proceedings, IEEE International, Vol.8, pp5440-5443, 2005.
  71. Pham, D.T., and Karaboga, D., Intelligent Optimisation Techniques, Springer, London, 261p., 2000.
  72. Ross, T.J., Fuzzy logic with engineering application, John Wiley and Sons, 628p., 2004.
  73. Röver C., and Szepannek, G., Application of a Genetic Algorithm to Variable Selection in Fuzzy Clustering, Technical Report, Sonderforschungsbereich 435, Universität Dortmund 44227, Dortmund, Germiny, 76(2004), pp.1-9, 2004.
  74. Theodoridis, S., and Koutroumbas, K., Pattern recognition, Elsevier, USA, 3rd edition, 837p., 2006.
  75. Wu, J.K., Neural networks and simulation methods‎, Marcel Dekker Inc., New York, 431p., 1994.
  76. Wu, M.L., SPSS Operation an Application – The Practice of Quantitative Analysis of Questionaire Data, Wunan Book Co., Ltd., Taiwan, 2nd edition, 758p., 2009.
  77. Yang, Y.F., Lohmann P, and Heipke, C., Genetic Algorithms For The unsupervised classification of satellite images, Symposium of ISPRS Commission III, Photogrammetric Computer Vision PCV’6, 36(3), pp.179-184, 2006.
Times Cited
  1. 鄧源昌(2012)。廣域山崩之統計與最佳化分析-以莫拉克風災小林村鄰近地區為例。中央大學土木工程學系學位論文。2012。1-169。