(3.210.184.142) 您好!臺灣時間:2021/05/13 17:35
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:黃盟勛
研究生(外文):Meng-Hsun Huang
論文名稱:解組合最佳化問題C(N,n)的繼承式雙目標基因演算法與其應用
論文名稱(外文):An Inherutable Bi-criteria Genetic Algorithm for Combinatorial Optimization Problem C(N,n) and Its Applications
指導教授:何信瑩
指導教授(外文):Shinn-Ying Ho
學位類別:碩士
校院名稱:逢甲大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:67
中文關鍵詞:繼承式基因演算法C(nr) 組合最佳化輪廓近似問題K-NNR分類器Pareto解集合
外文關鍵詞:combinatorial problemgenetic algorithmmulticriteria optimizationnearest neighbor rulePareto solutionsshape approximation
相關次數:
  • 被引用被引用:1
  • 點閱點閱:423
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:47
  • 收藏至我的研究室書目清單書目收藏:1
本篇論文提出了一種通適化可求C(n, r) 組合最佳化問題之Pareto解集合的高效能繼承式雙目標基因演算法。雙目標C(n, r) 組合最佳化問題的特性為: 1)增加選取數r可以提升系統效能但是相對地成本將會增加;2) C(n, r) 問題為NP-hard的問題,在真實世界應用中輸入的資料r通常很大,使得此問題不易找出最佳解;3)在不借用任何領域資訊的情況下,一個解決雙目標C(n, r) 組合最佳化問題並有效找出其Pareto解集合的通適化演算法將對決策決定有很大的幫助。本文所提出之繼承式基因演算法的主要優點為: 1)使用直交表的系統推理來輔助基因演算法中交配的運算,加強了傳統基因演算法中處理大量參數不易的問題。所謂大量參數最佳化問題即是當搜尋空間很大時,此搜尋空間將直接影響降低基因搜尋最佳解的效果;2)在基因演化過程中,加入了繼承的概念。即是當r值在連續求解C(n, r) 問題時改變的情況下,保留了此次r的基因族群的內容,並繼承給下一次r+1的基因族群。此種方法取代了每次變動r值時,以亂數初始的形態,繼承前一次所得優良答案和搜尋方向,在大量節省計算時間和提高效能的前提下,得到一Pareto解集合。為了證明此演算法是通適化且非針對特定問題設計,本演算法將會應用於輪廓近似問題和k-NNR分類器問題,而在計算時間遠小於目前最優良的演算法的情況下,所得到的Pareto解集合更加優良。如此,便可看出繼承式雙目標基因演算法在求C(n, r) 組合最佳化問題的Pareto解集合上有很好的效果。

In this paper, an inheritable genetic algorithm (IGA) with an orthogonal array crossover (OAX) is proposed to efficiently find a complete set of Pareto-optimal solutions to bi-criteria combinatorial optimization problems BCCOPs. The investigated BCCOP has an NP-hard search space of C(n, r) instances, i.e., the number of ways of choosing r out of n samples, and two incommensurable and often competing objectives: minimizing the number r of selected instances while maximizing the system performance. The merits of IGA are as follows: 1) OAX with the systematic reasoning ability based on orthogonal experimental design can efficiently explore and exploit the search space of BCCOP, especially for large BCCOP which is intractable for conventional GAs; 2) An inheritable mechanism of IGA can efficiently find the solution of C(n, r 1) when the solution of C(n, r) has been obtained; and 3) IGA is a general purpose algorithm without need of domain knowledge for finding a complete set of Pareto-optimal solutions or solutions to single objective problems C(n, r) with a constant value r. To illustrate the effectiveness of the proposed algorithm, IGA is applied to solving both shape approximation problems and the problem of editing the minimal reference set of a k-NNR classifier. The high performance of IGA is compared with those of some existing GA-based algorithms. It is shown empirically that IGA is superior to existing algorithms in finding a complete set of Pareto-optimal solutions to BCCOPs in terms of convergence speed and solution quality, especially in solving large BCCOPs.

第一章 導論……………………………………………………1
1.1 背景…………………………………………………………1
1.2雙目標問題簡介…………………………………………2
1.3雙目標C(n, r)組合問題 ………………………………3
1.4 論文概要……………………………………………………4
1.5 論文架構……………………………………………………5
第二章 雙目標問題研究…………………………………………7
2.1單目標函數解法………………………………………………7
2.2多目標函數解法……………………………………………7
2.3雙目標函數解法……………………………………………14
第三章 繼承式雙目標基因演算法……………………………15
3.1基因演算法……………………………………………………15
3.1.1傳統基因演算法……………………………………………15
3.1.2智慧型基因演算法…………………………………………18
3.3 繼承特性與染色體編碼……………………………………20
3.4 繼承式雙目標基因演算法…………………………………23
3.5 繼承式雙目標基因演算法分析……………………………24
第四章 多邊形輪廓近似問題……………………………………28
4.1 問題定義與相關研究………………………………………28
4.2 染色體編碼與評估函數設定………………………………29
4.3 實驗數據與圖表分析………………………………………29
第五章 k-NNR分類器問題………………………………………35
5.1 問題定義與相關研究………………………………………35
5.2 染色體編碼與評估函數設定………………………………36
5.4 實驗數據與圖表分析………………………………………37
第六章 結論……………………………………………………45
參考文獻………………………………………………………46

[1] C. M. Fonseca and P. J. Fleming, “An overview of evolutionary algorithms in multiobjective optimization,” Evol. Comput., vol. 3, no.1, pp. 1—16, 1995.
[2] M. Valenzuela-Rend´ on and E. Uresti-Charre, “A nongenerational genetic algorithm for multiobjective optimization,” in Proc. of the 7th Int. Conf. Genetic Algorithms, pp. 658-665, 1997.
[3] P. Sen and J.-B. Yang, Multiple Criteria Decision Support in Engineering Design. Springer-Verlag Berlin Heidelberg New York, 1998.
[4] S.-Y. Ho, H.-M. Chen, and L.-S. Shu, “Solving large knowledge base partitioning problems using an intelligent genetic algorithm,” in Proc. of the Genetic and Evolutionary Computation, pp. 1567-1572, 1999.
[5] M. Gen and L. Yinzhen, “Spanning tree-based genetic algorithm for the bicriteria fixed charge transportation problem,” in Proc. of the Evolutionary Computation, vol. 3, pp. 2265-2271, 1999.
[6] R. K. Jong and M. Gen, “Genetic algorithm for solving bicriteria network topology design problem,” in Proc. of the Evolutionary Computation, vol. 3, pp. 2272-2279, 1999.
[7] M. Gen, K. Ida, and J. Kim, “A spanning tree-based genetic algorithm for bicriteria topological network design,” in Proc. of the Evolutionary Computation, pp. 15-20, 1998.
[8] M. Gen, K. Ida, and L. Yinzhen, “Solving bicriteria solid transportation problem by genetic algorithm,” in Proc. of IEEE: Systems, Man, and Cybernetics, vol. 2, pp. 1200-1207, 1994.
[9] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.
[10] T. Blickle and L. Thiele, “A comparison of selection schemes used in evolutionary algorithms,” Evol. Comput., vol. 4, no. 4, pp. 361—394, 1996.
[11] J. Horn and N. Nafpliotis, “Multiobjective optimization using the niched Pareto genetic algorithm,” IlliGAL Report 93005, Illinois Genetic Algorithms Lab., Univ. Illinois, Urbana-Champaign, July 1993.
[12] J. Horn, N. Nafpliotis, and D. E. Goldberg, “A niched Pareto genetic algorithm for multiobjective optimization,” in Proc. of the 1st IEEE Conf. Evolutionary Computation, vol. 1, pp. 82—87, 1994.
[13] P. Hajela and C.-Y. Lin, “Genetic search strategies in multicriterion optimal design,” Structural Optimization, vol. 4, pp. 99—107, 1992.
[14] E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach,” IEEE Trans. Evolutionary Computation, vol. 3, no. 4, pp. 257-271, 1999.
[15] A. Kunjur and S. Krishnamurty, “A robust multi-criteria optimization approach.” Mech. Mach. Theory, vol. 32, no. 7, pp. 797-810, 1997.
[16] T. Pavilids and S. Horowitz, “Segmentation of plane curves,” IEEE Trans. Comput. vol. 23, pp. 860-870, 1974.
[17] J. G. Leu and L. Chen, “Polygonal approximation of 2-D shapes through boundary merging,” Pattern Recognition, vol. 28, pp. 571-579, 1988.
[18] B. K. Ray and K. S. Ray, “A new split-and-merge technique for polygonal approximation of chain coded curves,” Pattern Recognition Letters, vol. 16, pp. 161-169, 1995.
[19] T. Y. Phillips and A. Rosenfeld, “An ISODATA algorithm for straight line fitting,” Pattern Recognition Letters, vol. 7, pp. 291-297, 1988.
[20] P. Y. Yin, “Algorithms for straight line fitting using K-means,” Pattern Recognition Letters, vol. 19, pp. 31-41, 1998.
[21] T. Pavlidis, “Polygonal approximation by Newton’s method,” IEEE Trans. Comput. vol. 26, pp. 800-807, 1977.
[22] Y. Kurozumi and W. A. Davis, “Polygonal approximation by the minimax method,” Computer Graphics Image Processing, vol. 19, pp. 248-264, 1982.
[23] K. Wall and P. E. Danielsson, “A fast sequential method for polygonal approximation of digitized curves, computer vision,” Graphics, Image Processing, vol. 28, pp. 220-227, 1984.
[24] J. M. Inesta, M. Buendia, and M. A. Sarti, “Reliable polygonal approximations of imaged real objects through dominant point detection,” Pattern Recognition, vol. 31, pp. 685-697, 1998.
[25] B. K. Ray and K. S., Ray, ”An algorithm for detection of dominant points and polygonal approximation of digitized curves,” Pattern Recognition Letters, vol. 13, pp. 849-856, 1992.
[26] C. H. The and R. T. Chin, “On the detection of dominant points on digital curves,” IEEE Trans. Pattern Anal. March Intell., vol. 11, no. 8, pp. 859-872, 1989.
[27] W. Y. Wu and M. J. Wang, “Detecting the dominant points by the curvature-based polygonal approximation,” CVGIP: Graphical Models and Image Processing, vol. 55, pp. 79-88, 1993.
[28] A. Pikaz and A. Averbuch, “On automatic threshold selection for polygonal approximations of digital curves,” Pattern Recognition, vol. 11, pp. 1835-1845, 1996.
[29] P. Cornic, “Another look at the dominant point detection of digital curves,” Pattern Recognition Letters, vol. 18, pp. 13-25, 1997.
[30] M. Alhanaty and M. Bercovier, “Curve fitting and design by optimal control methods,” in Procs. of IEEE Conf. on Information Visualization, pp. 108 —113, 1998.
[31] S.-C. Pei and J.-H. Horng, “Fitting digital curve using circular arcs,” Pattern Recognition, vol. 28, pp. 107-116, 1995.
[32] A. Pikaz and I. Dinstein, “An algorithm for polygonal approximation of digital curves based on iterative points elimination,” Pattern Recognition Letters, vol. 16, pp. 557-563, 1995.
[33] P. Y. Yin, “A new method of polygonal approximation using genetic algorithm,” Pattern Recognition Letters, vol. 19, pp. 1017-1026, 1998.
[34] S.-Y. Ho and Y.-C. Chen, "An efficient evolutionary algorithm for accurate polygonal approximation," Pattern Recognition (to press).
[35] B. V. Dasarathy, “Minimal consistent set (MCS) identification for optimal nearest neighbor decision systems design,” IEEE Trans. System, Man and Cybernet. vol. 24, pp. 511-517, 1994.
[36] L. I. Kuncheva, “Editing for the k-nearest neighbors rule by a genetic algorithm,” Pattern Recognition Letter, vol. 16, pp. 809-814, 1995.
[37] M.-S. Yang and C.-H. Chen, “On the edited fuzzy k-nearest neighbor rule,” IEEE Trans. System, Man and Cybernet. -Part B: Cybernetics, vol. 28, no. 3, pp.461-466, 1998.
[38] J. C. Bezdek, T. R. Reichherzer, G. S. Lim, and Y. Attikiouzel, “Multiple-prototype classifier design, ”IEEE Trans. System, Man, and Cybernet. -Part C: Applications and Reviews, vol. 28, no. 1, pp.67-79, 1998.
[39] L. I. Kuncheva and J. C. Bezdek, “Nearest prototype classification: clustering, genetic algorithms, or random search?” IEEE Trans. System, Man and Cybernet. -Part C: Applications and Reviews, vol. 28, no. 1, pp.160-164, 1998.
[40] L. I. Kuncheva, “Fitness functions in editing k-NN reference set by genetic algorithms,” Pattern Recognition, vol. 30, no. 6, pp. 1041-1049, 1997.
[41] Y. Chien, Interactive Pattern Recognition. Marcel Dekker, New York. 1978.
[42] L. Prechelt, “PROBEN1- A set of neural network benchmark problems and benchmarking rules,” Technical Report, #21/94, 1994.
[43] C. M. Fonseca and P. J. Fleming, “An overview of evolutionary algorithms in multiobjective optimization,” Evol. Comput., vol. 3, no. 1, pp. 1—16, 1995.
[44] S. W. Mahfoud, “Niching methods for genetic algorithms,” Ph.D. dissertation, Univ. Illinois, Urbana-Champaign, 1995.
[45] S.-Y. Ho and C.-C. Yang, “An efficient algorithm for the design of a k-NNR classifier,” Journal of Feng Chia University, vol. 36, pp. 53-72, 1999.
[46] N. Srinivas and K. Deb, “Multiobjective optimization using nondominated sorting in genetic algorithms,” Evol. Comput., vol. 2, no. 3, pp.221—248, 1994.
[47] K. Sohn, W. E. Alexander, J. H. Kim, and W. E. Snyder, “A constrained regularization approach to robust corner detection,” IEEE Trans. System, Man,and Cybernet., vol. 24, no. 5, pp.820-828, 1994.
[48] J. H. Holland, Adaption in Natural and Artificial System. Ann Arbor, Univ. of Michigan Press, 1975.
[49] F. Yoshi and S. Hidefumi, “Evolutionary computation applied to mesh optimization of a 3-D facial image,” IEEE Trans. Evol. Comput., vol 3, no 2, 1999.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔