簡易檢索 / 詳目顯示

回結果列表
研究生： 李韋廷
Wei-ting Lee
論文名稱： 多目標基因演算法之研究
A Study on Genetic Algorithm for Multiobjective Optimization Problem
指導教授： 陳維美
Wei-mei Chen
口試委員: 陳省隆
H.-L. Chen
陳健輝
Gen-huey Chen
學位類別： 碩士
Master
系所名稱： 電資學院 - 電子工程系
Department of Electronic and Computer Engineering
論文出版年： 2007
畢業學年度： 95
語文別： 中文
論文頁數： 47
中文關鍵詞： 多目標 、基因演算法
外文關鍵詞： multiobjective, genetic algorithm
相關次數： 點閱：231  下載：11 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本論文對於多目標最佳化問題的研究，提出了一套有效率的基因演算法。利用marked k-d tree資料結構來做運算，能夠減少演算法的執行時間。此外，為了使每個在archive內的個體免於受不當機制的執行結果導致被刪除的可能，我們使用不受限制的archive ( unconstrained archive )來保留所有優良的後代。最後，我們以simple test problem和著名的knapsack problem作為實驗問題，並且與NSGA-Ⅱ、SPEA以及SPEA2這三個著名的基因演算法，作執行時間上的比較。另外，在解集合的比較上，我們使用了常用的C metric來當作實驗量測準則，可以從實驗結果發現，我們的方法可以保有較佳的解集合，即便是在多目標的情況下也是如此。

    An efficient genetic algorithm for the multiobjective optimization problems is proposed. To reduce the computational cost, a variant of k-d tree which is called marked k-d tree is used in our approach. And we also use the unconstrained archive to preserve all non-dominated solutions. Finally, we compare the performance of our proposed algorithm with those of using C metric on the final Pareto set for simple test problem and 0/1 knapsack problem. Our experiments demonstrate that the algorithm we proposed outperforms the other popular multiobjective genetic algorithm, especially for the higher dimensional cases.

    圖目錄……………………………………………………………………………iii 表格目錄…………………………………………………………………………v Abstract…………………………………………………………………………1 中文摘要…………………………………………………………………………2 第一章 緒論……………………………………………………………………3 1.1 研究動機與目的…………………………………………………………3 1.2 過去之相關研究…………………………………………………………4 1.3 研究方法概述……………………………………………………………6 1.4 本文大綱…………………………………………………………………7 第二章 多目標最佳化問題………………………………………………………8 2.1 問題描述…………………………………………………………………8 2.1.1 多目標最佳化問題數學定義…………………………………………8 2.1.2 Pareto Set ……………………………………………………………9 2.2 基因演算法………………………………………………………………10 2.2.1 基因演算法流程………………………………………………………11 2.3 多目標基因演算法…………………………………………………………14 第三章 多目標基因演算法…………………………………………………………17 3.1 資料結構……………………………………………………………………17 3.1.1 Linked List……………………………………………………………17 3.1.2 Dominated Free Quad-Trees…………………………………………17 3.1.3 Marked k-d Trees ……………………………………………………24 3.2 改良的基因演算法……………………………………………………………29 3.2.1 Constrained / Unconstrained Archive…………………………………30 3.2.2 Mating Pool……………………………………………………………32 3.2.3 Proposed Approach……………………………………………………33 第四章 實驗結果與討論……………………………………………………………35 4.1 實驗問題描述………………………………………………………………35 4.1.1 Simple Test Problem………………………………………………………35 4.1.2 0/1 Knapsack Problem……………………………………………………36 4.2 執行效能比較………………………………………………………………38 4.3 Pareto Set比較……………………………………………………………42 4.4 資料結構比較………………………………………………………………43 第五章 結論…………………………………………………………………………45 參考文獻…………………………………………………………………………………46

    參考文獻
    [1] Adam Berry, Peter Vamplew, An efficient approach to unbounded bi-objective archives – introducing the mak-tree algorithm, GECCO’06, July 8-12, 2006.
    [2] W.-M Chen, H.-K. Hwang, and T.-H. Tsai, Efficient maxima-finding algorithms for multidimensional samples, submitted.
    [3] K. Deb, Multi-objective optimization using evolutionary algorithms, New York : Wiely, 2001.
    [4] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II, In Proceedings of Parallel Problem Solving from Nature - PPSN VI, pages 849-858. Springer, 2000.
    [5] J.E. Fieldsend, R.M. Everson, and S. Singh, Using unconstrained elite archives for multi-objective optimization, IEEE Trans. Evol. Comput, 7(3):305-323, 2003.
    [6] R.A. Finkel and J.L. Bentley, Quad trees: A data structure for retrieval on composite keys. Acta informatica, 1974.

    [7] C.M Fonseca and P.J Fleming, Genetic algorithms for multiobjective optimization: formulation, discussion and generalization, in Proc. 5th Int. Conf. Genetic Algorithms, S. Forrest, Ed, 1993.

    [8] C.M Fonseca and P.J Fleming, An overview of evolutionary algorithms in multiobjective optimization. Evolutionary Computation, 3(1):1-16, 1995.

    [9] J. Horn, N. Nafpliotis, Multiobjective optimization using the niched Pareto genetic algorithm. IlliGAL technical Report 93005, Illinois genetic algorithms laboratory, University of Illinois, Urbana, Illinois, 1994.

    [10] J. Horn, N. Nafpliotis, and D. E. Goldberg, A niched Pareto genetic algorithm for multiobjective optimization, in Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence. Piscataway, NJ: IEEE Press, 1994, vol.1, pp. 82–87.
    [11] J.Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press: Ann Arbor, MI. 1975.
    [12] J.D. Knowles and D. Corne, Approximating the nondominated font using the Pareto archived evolution strategy, Evol. Comput, vol. 8, no.2, pp. 149-172, 2000.
    [13] J. D. Schaffer, Multiple objective optimization with vector evaluated genetic algorithms, in Proc. 1st Int. Conf. Genetic Algorithms, 1985, pp. 99–100.
    [14] N. Srinivas and K. Deb, Multiobjective optimization using nondominated sorting in genetic algorithms, Evol. Comput., vol. 2, no. 3, pp. 221–248, 1995.
    [15] Sanaz Mostaghim , Jurgen Teich, Quad-trees: A Data Structure for storing Pareto-sets in Multi-objective Evolutionary Algorithms with Elitism, in Evolutionary Computation Based Multi-Criteria Optimization : Theoretical Advances and Applications Springer Verlag, 2005.
    [16] H. Zhao, Z. Hu and M.Takeichi, Multidimensional searching trees with minimum attribute. JSSST Computer Software, 19(1):22—28, Jan. 2002.

    [17] E. Zitzler, K. Deb, and L. Thiele, Comparison of multiobjective evolutionary algorithms: Empirical results, Evol. Comput., vol. 8, no. 2, pp. 173–195, 2000.
    [18] E. Zitzler and L. Thiele, Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., vol. 3, pp. 257–271, Nov. 1999.
    [19] E. Zitzler and L. Thiele, SPEA2 : Improving the Strength Pareto Evolutionary Algorithm, TIK-Report 103, 2001.
    [20] E. Zitzler, Evolutionary algorithms for multiobjective optimization:Methods and applications, Ph.D dissertation, Swiss Fed Inst. Technol. Zurich(ETH), Comput. Eng. Commun. Networks Lad, Lausanne, Switzerland, Diss ETH no.13398,1999

    QR CODE