臺灣博碩士論文加值系統

摘 要


演化式計算包括演化式規劃、演化式策略、基因演算法與基因規劃等，已經被廣泛的使用來解決最佳化的問題，尤其在大規模且複雜的系統中尋找最佳解。
演化式演算法可分為單目標演化式演算法與多目標演化式演算法兩類。在單目標演化式演算法的部分介紹兩種改良型演化式演算法：利用直交設計(Orthogonal Design)與量化技術(Quantization Technique)的量化直交基因演算法(Orthogonal Genetic Algorithm with Quantization)和使用田口方法(Taguchi Method)的混和田口基因演算法(Hybrid Taguchi-Genetic Algorithm)。多目標演化式演算法基本架構與單目標演化式演算法大致相同，但因為多個目標函數的關係，使得多目標演化式演算法在設計上產生問題，主要在適存度分配(Fitness Assignment)、差異性保持(Diversity Preservation) 與新增的精英區(Elite Set)。在本論文中，先比較兩個多目標演化式演算法：Strength Pareto Evolutionary Algorithm 2(SPEA2)與Intelligent Multiobjective Evolutionary Algorithms(IMOEA)，並對找到的最佳解進行比較。
在演化過程的初始階段，本論文提出增加一個隨機母體的方法擴展演算法的搜尋範圍，使得演算法更有機會找到好的解。在每個世代，隨機母體中的個體都重新產生且只將其中nondominated個體複製到精英區中，而其他個體不參與演化，這種方法能夠讓演算法搜尋更廣泛的空間、使得演算法能找到更好的解。之後對隨機母體中的個體使用田口方法，讓隨機母體中的個體先做進一步的篩選，保留好的個體在隨機母體，如此能讓隨機母體中個體更有代表性。最後在實驗部分可以看到增加隨機母體的方法能夠讓演算法找到更好的解。

Abstract


Evolutionary computation, such as evolutionary programming, evolution strategy, genetic algorithm, and genetic programming etc., has already been widely used for solving the optimization problems.
Evolutionary algorithms can be divided into two categories: single objective and multiple objectives. With single objective, we introduce two modified evolutionary algorithms: the orthogonal genetic algorithm with quantization (OGA/Q), which utilizes the orthogonal design and quantization technique, and the Hybrid Taguchi-Genetic Algorithm (HTGA), which utilized the Taguchi method. With multiple objectives, because of the multiple objective functions, the design of multi-objective genetic algorithms focuses on fitness assignment, diversity preservation, and the addition of elite set. In this paper, we compare two multi-objective evolutionary algorithms: Strength Pareto Evolutionary Algorithm 2(SPEA2) and Intelligent Multi-objective Evolutionary Algorithms (IMOEA).
In this paper, we propose to include an additional random population besides the original initial population, and the proposed method can expand the searching space to identify better solutions. In each generation we replace the random population and select only the non-dominated individuals into the elite set. The proposed method can explore more general solution space and locate better solutions. We then apply the Taguchi method to generate better individuals in the random population, so individuals in the random population are more representative. In the experiments, we show that the proposed method that includes random population can lead to better solutions.

目 錄


誌謝.............................................................. Ⅰ
摘要.............................................................. Ⅱ
ABSTRACT.......................................................... Ⅳ
目錄.............................................................. Ⅴ
表錄.............................................................. Ⅶ
圖錄.............................................................. Ⅷ
一、緒論............................................................... 1
1.1 研究背景與動機............................................... 1
1.2 相關研究.................................................... 3
1.3 論文架構.................................................... 4
二、演化式演算法(evolutionary algorithms).......................... 5
2.1 田口方法(Taguchi method) .................................... 6
2.1.1 直交表(orthogonal array)................................. 8
2.1.2 訊號雜音比(signal-noise ratio)........................... 11
2.2 單目標演化式演算法........................................... 12
2.3 多目標演化式演算法............................................ 16
2.3.1 演算法設計的問題(algorithm design issues)............... 16
2.3.1.1 適存度分配(fitness assignment)....................... 17
2.3.1.2 差異性保持(diversity preservation)................... 18
2.3.1.3 精英論(elitism)..................................... 18
2.3.2 較新的多目標演化式演算法.................................. 19
2.3.2.1 SPEA2.............................................. 19
2.3.2.2 IMOEA.............................................. 20
2.3.2.2.1 GPSIFF......................................... 21
2.3.2.2.2 IGC............................................ 22
三、新增隨機母體................................................... 26
3.1 最佳化large parameter optimization problems................. 27
3.2 最佳化基礎矩陣............................................... 29
四、實驗結果....................................................... 35
4.1 實驗的目標函數介紹............................................ 35
4.1.1 數值最佳化問題........................................... 35
4.1.2 基礎矩陣................................................ 35
4.2 單目標演化式演算法............................................ 37
4.3 多目標演化式演算法............................................ 37
4.3.1 求解large parameter optimization problems............... 37
4.3.2 求解基礎矩陣............................................. 39
4.4 新增隨機母體................................................. 41
4.4.1 求解large parameter optimization problems............... 42
4.4.2 求解基礎矩陣............................................. 45
五、結論與未來工作.................................................. 49
參考文獻.......................................................... 51

參考文獻


[1]M. Z. Brown, D. Burschka, and G. D. Hager, “Advances in Computational Stereo,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 25, No. 8, Aug. 2003, pp. 993-1008.
[2]M. Carcassoni, and E. R. Hancock, “Correspondence Matching with Modal Clusters,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 25, No. 12, Dec. 2003, pp. 1609-1615.
[3]J. Chai and S. D. Ma, “Robust Epipolar Geometry Estimation Using Genetic Algorithm,” Pattern Recognition Letters, Vol. 19, 1998, pp. 829-838.
[4]L. Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1996.
[5]Y.W. Leung and Y.Wang, “An Orthogonal Genetic Algorithm with Quantization for Global Numerical Optimization,” IEEE Trans. Evolutionary Computation, Vol.5, Feb. 2001, pp. 41-53.
[6]S.Y. Ho, L.S. Shu, and J.H. Chen, “Intelligent Evolutionary Algorithms for Large Parameter Optimization Problems,” IEEE Trans. Evolutionary Computation, Vol.8, No.6, December 2004, pp. 522-541.
[7]T. Jones. Evolutionary Algorithms, Fitness Landscapes and Search. Ph.D. Dissertation, University of New Mexico, May 1995.
[8]J. M. Renders and S. P. Flasse, “Hybrid Methods Using Genetic Algorithms for Global Optimization,” IEEE Trans. Systems, Man, and Cybernetics-part B: Cybernetics, Vol. 26, No. 2, April 1996, pp. 243-258.
[9]C. T. Tang, H. L. Chou, Y. H. Yeh, M. W. Lin, S. T. Tzou, and Y. H. Ding, “Feature Selection for Estimating Fundamental Matrices using Disparity Constraint,” Proc. of CVGIP, 2004.
[10]J. T. Tsai, T. K. Liu, and J. H. Chou, “Hybrid Taguchi-Genetic Algorithm for Global Numerical Optimization,” IEEE Trans. Evolutionary Computation, Vol. 8, No. 4, Aug. 2004, pp. 365-377.
[11]Z. Tu and Y. Lu, “A Robust Stochastic Genetic Algorithm (StGA) for Global Numerical Optimization,” IEEE Trans. Evolutionary Computation, Vol. 8, No. 5, October 2004, pp. 456-470.
[12]W. Zhong, J. Liu, M. Xue, and L. Jiao, “A Multiagent Genetic Algorithm for Global Numerical Optimization,” IEEE Trans. Systems, Man, and Cybernetics—part B: Cybernetics, Vol. 34, no. 2, April 2004, pp. 1128-1141.
[13]Vlasis K. Koumousis and Christos P. Katsaras, “A Saw-Tooth Genetic Algorithm Combining the Effects of Variable Population Size and Reinitialization to Enhance Performance,” IEEE Trans. Evolutionary Computation, Vol. 10, No. 1, February 2006, pp. 19-28.
[14]E. Zitzler, M. Laumanns, and S. Bleuler, “A Tutorial on Evolutionary Multiobjective Optimization,” Metaheuristics for Multiobjective Optimization, Lecture Notes in Economics and Mathematical Systems, Springer, Vol. 535, 2004, pp. 3-37.
[15]Qingfu Zhang and Yiu-Wing Leung, “An Orthogonal Genetic Algorithm for Multimedia Multicast Routing,” IEEE Trans. Evolutionary Computation, Vol. 3, No. 1, Apr 1999, pp. 53-62.
[16]Yimin Liu, Tansel Özyer, Reda Alhajj and Ken Barker “Integrating Multi-Objective Genetic Algorithm and Validity Analysis for Locating and Ranking Alternative Clustering,” Informatica 29 (2005), pp. 33-40.
[17]Zitzler and L. Thiele. “Multiobjective Evolutionary Algorithms: A Comparative Case Study and The Strength Pareto Approach,” IEEE Trans. Evolutionary Computation, Vol. 3, No. 4,257–271, 1999, pp. 257-271.
[18]李輝煌，田口方法-品質設計的原理與實務，高立圖書有限公司。
[19]孫春在，『演化式計算』http://cindy.cis.nctu.edu.tw/EC/main/ ec_ind.htm.
[20]蘇朝墩，『田口式品質工程』 http://www.qrc.nthu.edu.tw/QRC/ studyQ/pdf/田口式品質工程簡介.pdf.
[21]Yueh-Hung Lai. Research on Optimization Using Evolutionary Computation. Master Thesis, Department of Information Management, Huafan University, Taiwan, 2005.
[22]D. A. Forsyth and J. Ponce. Computer Vision: A Modern Approach. Prentice Hall, 2003.
[23]Yan-Hung Ding. 3D Reconstruction of Buildings from Uncalibrated Image Sequences. Master Thesis, Department of Information Management, Huafan University, Taiwan, 2005.