請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/2715完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 于天立 | |
| dc.contributor.author | Ping-Lin Chen | en |
| dc.contributor.author | 陳品霖 | zh_TW |
| dc.date.accessioned | 2021-05-13T06:48:49Z | - |
| dc.date.available | 2017-08-24 | |
| dc.date.available | 2021-05-13T06:48:49Z | - |
| dc.date.copyright | 2017-08-24 | |
| dc.date.issued | 2017 | |
| dc.date.submitted | 2017-08-20 | |
| dc.identifier.citation | [1] P. A. Bosman and D. Thierens. Linkage neighbors, optimal mixing and forced improvements in genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 585–592, 2012.
[2] F. Chicano, D. Whitley, G. Ochoa, and R. Tinós. Optimizing one million variable nk landscapes by hybridizing deterministic recombination and local search. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 753–760, 2017. [3] L. Davis. Applying adaptive algorithms to epistatic domains. In Proceedings of the International Joint Conference on Artificial Intelligence, volume 1, pages 162–164, 1985. [4] K. Deb and D. E. Goldberg. Sufficient conditions for deceptive and easy binary functions. Annals of mathematics and Artificial Intelligence, 10(4):385–408, 1994. [5] K.-C. Fan, T.-L. Yu, and J.-T. Lee. Linkage learning by number of function evaluations estimation: Practical view of building blocks. Information Sciences, 230:162–182, 2013. [6] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1 edition, 1989. [7] D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333–362, 1992. [8] D. E. Goldberg and R. Lingle. Alleles, loci, and the traveling salesman problem. In Proceedings of the International Conference on Genetic Algorithms, pages 154–159, 1985. [9] D. E. Goldberg, K. Sastry, and T. Latoza. On the supply of building blocks. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 336–342, 2001. [10] J. Grefenstette, R. Gopal, B. Rosmaita, and D. Van Gucht. Genetic algorithms for the traveling salesman problem. In Proceedings of the International Conference on Genetic Algorithms, pages 160–168, 1985. [11] G. Harik. Linkage learning via probabilistic modeling in the ecga. Technical report, University of Illinois, 1999. [12] J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975. [13] S.-H. Hsu and T.-L. Yu. Optimization by pairwise linkage detection, incremental linkage set, and restricted/back mixing: DSMGA-II. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 519–526, 2015. [14] S. Kullback and R. A. Leibler. On information and sufficiency. Annals of Mathematical Statistics, 22:79–86, 1951. [15] P. Larranaga. A review on estimation of distribution algorithms. In Estimation of distribution algorithms, pages 57–100. Springer, 2002. [16] I. Oliver, D. Smith, and J. R. Holland. Study of permutation crossover operators on the traveling salesman problem. In Proceedings of the International Conference on Genetic Algorithms, 1987. [17] M. Pelikan and D. E. Goldberg. Hierarchical BOA solves Ising spin glasses and MAXSAT. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1271–1282, 2003. [18] M. Pelikan, D. E. Goldberg, and F. G. Lobo. A survey of optimization by building and using probabilistic models. Computational optimization and applications, 21(1):5–20, 2002. [19] M. Pelikan, M. W. Hauschild, and D. Thierens. Pairwise and problem-specific distance metrics in the linkage tree genetic algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1005–1012, 2011. [20] M. Pelikan, K. Sastry, and E. Cantú-Paz. Scalable optimization via probabilistic modeling: From algorithms to applications, volume 33. Springer, 2007. [21] D. Thierens. The linkage tree genetic algorithm. In International Conference on Parallel Problem Solving from Nature, pages 264–273, 2010. [22] D. Thierens and P. A. Bosman. Optimal mixing evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 617–624, 2011. [23] D. Thierens and D. E. Goldberg. Mixing in genetic algorithms. In Proceedings of the International Conference on Genetic Algorithms, pages 38–47, 1993. [24] R. L. R. Thomas H. Cormen, Charles E. Leiserson and C. Stein. Introduction to Algorithms. MIT Press, 2 edition, 1992. [25] R. Tintos, D. Whitley, and F. Chicano. Partition crossover for pseudo-boolean optimization. In Proceedings of the ACM Conference on Foundations of Genetic Algorithms XIII, pages 137–149, 2015. [26] M. Tsuji, M. Munetomo, and K. Akama. A crossover for complex building blocks overlapping. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1337–1344, 2006. [27] L. D. Whitley, T. Starkweather, and D. Fuquay. Scheduling problems and traveling salesmen: The genetic edge recombination operator. In Proceedings of the International Conference on Genetic Algorithms, pages 133–140, 1989. [28] T.-L. Yu, D. E. Goldberg, A. Yassine, and Y.-p. Chen. Genetic algorithm design inspired by organizational theory: Pilot study of a dependency structure matrix driven genetic algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1620–1621, 2003. [29] T.-L. Yu, K. Sastry, and D. E. Goldberg. Linkage learning, overlapping building blocks, and systematic strategy for scalable recombination. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1217–1224, 2005. [30] T.-L. Yu, K. Sastry, D. E. Goldberg, and M. Pelikan. Population sizing for entropybased model building in discrete estimation of distribution algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 601–608, 2007. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/2715 | - |
| dc.description.abstract | 相依性結構矩陣遺傳演算法二代是一個模型建構的基因演算法，它能夠利用探索問題的子結構來解出許多的最佳化問題。此演算法在許多指標性問題，其中包含兩個現實問題上，已經顯示了比起兩個具有代表性的演算法表現得更加卓越。在這篇論文之中，我提出了一個客製化的模型稱作雙邊圖鏈結模型，這個模型針對了每一個接收者客製化了相對應的遮罩，使得相依性結構矩陣遺傳演算法二代擁有進一步的性能提升。這個新的模型比起原來的版本，提供了夠多種可能的重組方式。為了減少一些不必要的嘗試，這個模型和供給限制的技術一起搭配使用。此外，這篇論文也提供了一個新的技術稱作提早終止判定，些微地增進了重組的效率。結合以上提出的技術，性能在指標性問題的結果上比起原版的相依性結構矩陣遺傳演算法二代有了平均十二個百分點的提升。 | zh_TW |
| dc.description.abstract | DSMGA-II, a model building genetic algorithm, is able to solve optimization problems via exploiting sub-structures of the problem. DSMGA-II has shown superior optimization ability to LT-GOMEA and hBOA on several benchmark problems including two real-world problems, Ising spin-glass and MAX-SAT. In this thesis, I propose a customized model called two-edge graphical linkage model, which customizes the recombination masks for each receiver according to its alleles, to further improve the performance of DSMGA-II. The new linkage model provides far more possible linkage combinations than the original version. To reduce unnecessary trails, the two-edge model is combined with the supply bounds from the original model. A new techniques called early stop criterion is also proposed to slightly enhance the efficiency in mixing. Combining these proposed techniques, the empirical results show an average of 12% NFE reduction on the benchmark problems compared with the original DSMGA-II. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-13T06:48:49Z (GMT). No. of bitstreams: 1 ntu-106-R04921043-1.pdf: 3075598 bytes, checksum: 94cc1d55204c7a10c06a90ae98f1e977 (MD5) Previous issue date: 2017 | en |
| dc.description.tableofcontents | Contents
誌謝 v 摘要 vii Abstract ix 1 Introduction 1 2 Related Works 7 2.1 DSMGA . . . . . . . . . . . . . . . . . 7 2.2 OM . . . . . . . . . . . . . . . . . . . 9 2.3 DSMGA-II . . . . . .. . . . . . . . . . 10 2.3.1 Framework of DSMGA-II . . . . . . 11 2.3.2 Incremental Linkage Set . . . . . 13 2.3.3 Restricted Mixing and Back Mixing . . . . 14 3 Test Problems 19 3.1 Concatenated Trap . . . . . . . . . . . 20 3.2 Cyclic Trap . . . . . . . . . . . . . . 21 3.3 Folded Trap . . . . . . . . . . . . . . 22 3.4 NK-landscape . . . .. . . . . . . . . . 23 3.5 Ising Spin-glass . . . . . . . . . . . 24 3.6 MAX-SAT . . . . . . . . . . . . . . . . 25 4 Two-edge Graphical Linkage Model 27 4.1 Two-edge Graph . .. . . . . . . . . . . . . 27 4.2 Supply Overfitting . . . . . . . . . . . . 32 4.3 Representative Supply Check . . . . . . . . 34 4.4 One-edge Supply Bound . . . . . . . . . . . 36 5 Early Stop Criterion 41 6 Experiment Results 45 6.1 Experiment Setup .. . . . . . . . . . . . . 45 6.2 Results and Discussions . . . . . . . . . . 46 7 Conclusion and Future Works 55 Bibliography 57 | |
| dc.language.iso | en | |
| dc.title | 以雙邊圖鏈結模型改良相依性結構矩陣遺傳演算法二代 | zh_TW |
| dc.title | Improving DSMGA-II with Two-edge Graphical Linkage Model | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 105-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 張時中,雷欽隆 | |
| dc.subject.keyword | 演化式演算法,基因演算法,鏈結學習,模型建構, | zh_TW |
| dc.subject.keyword | Evolutionary Algorithm,Genetic Algorithm,Linkage Learning,Model Building, | en |
| dc.relation.page | 60 | |
| dc.identifier.doi | 10.6342/NTU201704045 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2017-08-21 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-106-1.pdf | 3 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。