請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57519完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 于天立(Tian-Li Yu) | |
| dc.contributor.author | Shih-Ming Wang | en |
| dc.contributor.author | 王士銘 | zh_TW |
| dc.date.accessioned | 2021-06-16T06:49:38Z | - |
| dc.date.available | 2014-07-29 | |
| dc.date.copyright | 2014-07-29 | |
| dc.date.issued | 2014 | |
| dc.date.submitted | 2014-07-24 | |
| dc.identifier.citation | [1] Qingfu Zhang, Jianyong Sun, Edward Tsang, and John Ford. Estimation of distribution algorithm with 2-opt local search for the quadratic assignment problem. In Towards a New Evolutionary Computation. Advances in Estimation of Distribution Algorithm, pages 281–292. Springer-Verlag, 2006.
[2] Hongbin Wang, Todd R. Johnson, and Jiajie Zhang. A hybrid system of abductive tactical decision making. Int. J. Hybrid Intell. Syst., 3(1):23–33, January 2006. [3] Elizabeth Radetic, Martin Pelikan, and David E. Goldberg. Effects of a deterministic hill climber on hboa. In Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, GECCO ’09, pages 437–444, New York, NY, USA, 2009. ACM. [4] Peter A.N. Bosman and Dirk Thierens. The roles of local search, model building and optimal mixing in evolutionary algorithms from a bbo perspective. In Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO ’11, pages 663–670, New York, NY, USA, 2011. ACM. [5] Dirk Thierens and Peter A.N. Bosman. Optimal mixing evolutionary algorithms. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO ’11, pages 617–624, New York, NY, USA, 2011. ACM. [6] Martin Pelikan, Mark W. Hauschild, and Dirk Thierens. Pairwise and problem-specific distance metrics in the linkage tree genetic algorithm. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO ’11, pages 1005–1012, New York, NY, USA, 2011. ACM. [7] Dirk Thierens. The linkage tree genetic algorithm. In Proceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part I, PPSN’10, pages 264–273, Berlin, Heidelberg, 2010. Springer-Verlag. [8] D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA, 1989. [9] Georges R. Harik. Finding multimodal solutions using restricted tournament selection. In Proceedings of the 6th International Conference on Genetic Algorithms, pages 24–31, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. [10] Georges Harik. Finding multimodal solutions using restricted tournament selection. In Proceedings of the Sixth International Conference on Genetic Algorithms, pages 24–31. Morgan Kaufmann, 1995. [11] M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511–518, 2001. [12] Gerhard M ̈uhlenbein, Heinz Paaas. From recombination of genes to the estimation of distributions i. binary parameters. In Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, PPSN IV, pages 178–187, London, UK, UK, 1996. Springer-Verlag. [13] G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm. Proceedings of IEEE International Conference on Evolutionary Computation, pages 523–528, 1998. [14] Jeremy S. De Bonet, Charles L. Isbell, and Paul Viola. Mimic: Finding optima by estimating probability densities. In Advances in Neural Information Processing Systems, page 424. The MIT Press, 1997. [15] G. Harik. Linkage learning via probabilistic modeling in the ECGA. IlliGAL Report No. 99010, University of Illinois at Urbana-Champaign, Urbana, IL, February 1999. [16] R. Etxeberria and P. Larra ̋naga. Global optimization using bayesian networks. Proceedings of the Second Symposium on Artificial Intelligence Adaptive Systems, pages 332–339, 1999. [17] M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. BOA: The bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), pages 525–532, 1999. [18] 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. Proceedings of Artificial Neural Networks in Engineering (ANNIE 2003), pages 327–332, 2003. [19] D. E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, USA, 2002. [20] J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, 1975. [21] K. Deb and D. E. Goldberg. Analyzing deception in trap functions. Foundations of Genetic Algorithms 2, pages 93–108, 1993. [22] D. E. Goldberg. Simple genetic algorithms and the minimal, deceptive problem. Genetic Algorithms and Simulated Annealing, pages 74–88, 1987. [23] D. Thierens and D. E. Goldberg. Convergence models of genetic algorithm selection schemes. Parallel Problem Solving fron Nature (PPSN III), pages 119–129, 1994. [24] D. E. Goldberg, K. Sastry, and T. Latoza. On the supply of building blocks. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 336–342, 2001. [25] D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, vol. 6:333–362, 1992. [26] G. Harik, E. Cant ́u-Paz, D. E. Goldberg, and B. L. Miller. The gambler’s ruin problem, genetic algorithms, and the sizing of populations. Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, pages 7–12, 1997. [27] Tian-Li Yu, Kumara Sastry, David E. Goldberg, and Martin Pelikan. Population sizing for entropy-based model building in discrete estimation of distribution algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2007), pages 601–608, 2007. [28] K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master thesis, University of Illinois at Urbana-Champaign, Urbana, IL, 2002. [29] C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, vol. 27:379–423, 1948. [30] Martin Pelikan, Kumara Sastry, David E. Goldberg, Martin Volker Butz, and Mark Hauschild. Performance of evolutionary algorithms on nk landscapes with nearest neighbor interactions and tunable overlap. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2009), pages 851–858, 2009. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57519 | - |
| dc.description.abstract | 最佳混合演化式演算法(optimal mixing evolutionary algorithm)使用由一組遮罩組成的鏈結集合(linkage set)以交換一對解之間的變數,交換的結果僅當在交換造成解的品質進步時才會被採用。最佳混合演化式演算法的表現高度相依於其使用得鏈結集合。本論文展示了之前所提出稱為鏈結樹(linkage tree)的鏈結集合並沒有達到最好的表現。更進一步的研究指出,遮罩的效用隨著代數而改變。為了找出利用遮罩最好的方法,本論文從模型效率以及族群成長兩方面分析了最佳混合演化式演算法。具體而言,成本性能指標(cost-performance index)被提出並用以度量一組遮罩的效率。當族群大小固定時，最佳混合演化式演算法搭配擁有較高成本性能指標的鏈結集合所需的適應度函數計算次數較少。然而, 擁有較高成本性能指標的鏈結集合可能導致最佳混合演化式演算法需要較大的族群大小來解決問題。因此 遮罩對於族群成長的效果被納入考量以正規化成本性能指標。兩個名為OMCPE1及OMCPE2、利用正規化成本性能指標選擇遮罩 的演算法接著被提出。OMCPE1及OMCPE2兩者皆採用兩階段的交配。在第一階段，原本的交配被執行以估計鏈節樹遮罩的正規化成本性能指標之值。在第一階段產生的解的基礎下，第二階段用擁有較高正規化成本性能指標值的遮罩產生解。一般而言,不同估計成本性能指標的方法導致OMCPE2比OMCPE1更為穩 健。同樣的,在大部分測試的完全可分的問題(fully separable problem)上,OMCPE2比起最佳混合演化式演算法搭配鏈結樹，不僅在適應度函數計算次數上,在擴展性上也表現得更好。至於有重疊之問題(problems with overlap)，儘管OMCPE2在過半數測試的實例上仍展現了性能的增進，它卻較為不穩建。在一些極端的實例上，它會需要更大的族群大小。 | zh_TW |
| dc.description.abstract | The optimal mixing evolutionary algorithm (OM) utilizes a linkage set (LS) which is composed of a set of masks to exchange variables between a pair of solutions, and the result of such exchange is adopted only if the exchange leads to improvement of the solution quality. The performance of OM highly depends on the LS it utilizes. This thesis demonstrates that previously proposed LS, the linkage tree model (LT), does not yield the optimal performance. Further investigation shows that the effectiveness of each mask varies from generation to generation. To find out the best way of utilizing the masks, this thesis analyzes OM from the perspective of model efficiency and population sizing. Specifically, cost-performance (CP) index is proposed to measure the efficiency of a set of masks. If fixed population is used, OM with LSs of higher CP values require less number of function evaluations (NFEs). However, a LS with higher CP values might lead to larger population size for OM to solve the problem. Therefore, the effect of the masks on population sizing are considered to normalize CP index. Two algorithms named OMCPE1 and OMCPE2 are then proposed with normalized CP index as the mask selecting metric. Both OMCPE1 and OMCPE2 adopts two stage crossover. In the first stage, normalized CP values of the masks in the LT are estimated by performing the original crossover. In the second stage, masks of higher normalized CP values are utilized to generate solutions based on the solutions generated in the first stage. Generally speaking, the different methods of CP value estimation make OMCPE2 more robust than OMCPE1. Also, OMCPE2 outperforms OM with LT in terms of both NFEs and scalability on most tested fully separable problems. As for problems with overlap, although OMCPE2 still shows performance gain on more than half of the tested instances, it is less robust such that it might require much larger population size on some extreme instances. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T06:49:38Z (GMT). No. of bitstreams: 1 ntu-103-R01921055-1.pdf: 500456 bytes, checksum: 35718369ea53e702e739d49fea28512e (MD5) Previous issue date: 2014 | en |
| dc.description.tableofcontents | 中 文 摘 要 i
Abstract ii List of Figures iv List of Tables v List of Symbols vii Introduction viii 1 Genetic Algorithms and Optimal Mixing 1 1.1 Genetic Algorithms 1 1.1.1 Evaluation and Selection 2 1.1.2 Crossover and Mutation 3 1.1.3 Replacement 3 1.2 Optimal Mixing Evolutionary Algorithm 4 1.2.1 Model Building Genetic Algorithm 4 1.2.2 Optimal Mixing 5 2 Definitions and Notations 8 2.1 Problem Definition 8 2.2 Linkage Set Definition 9 2.2.1 Marginal Product Model 10 2.2.2 Linkage Tree Model 10 2.2.3 Linkage Set 11 3 Facet-wise Analysis on Optimal Mixing 13 3.1 Model Efficiency 13 3.1.1 Definition of Model Efficiency 13 3.1.2 Dual CP Value 15 3.2 Experiments on Model Efficiencies 15 3.2.1 Experiments Setting 16 3.2.2 Model Efficiency on the Trap Problem 16 3.2.3 Model Efficiency on the One-max Problem 17 3.2.4 Model Efficiency on the Atrap Problem 20 3.3 Population Sizing 22 3.3.1 Discussion on Population Sizing for OM 22 3.3.2 CP Index Revisited 24 3.3.3 Definition of Normalized CP 26 4 Optimal Mixing with Mask Selection 28 4.1 Mask Selection 28 4.2 Two Stage OM With Mask Selection 29 4.2.1 Rank Estimation 30 4.2.2 CP Values Estimation 32 4.3 Experiments 35 4.4 Discussions on Problem with Overlap 38 5 Conclusion 40 Bibliography 42 | |
| dc.language.iso | en | |
| dc.subject | 模型效率 | zh_TW |
| dc.subject | 模形建構基因演算法 | zh_TW |
| dc.subject | 局部搜索 | zh_TW |
| dc.subject | 最佳混合 | zh_TW |
| dc.subject | 族群成長 | zh_TW |
| dc.subject | Model Efficiency | en |
| dc.subject | Local Search | en |
| dc.subject | Optimal Mixing | en |
| dc.subject | Population Sizing | en |
| dc.subject | Model Building GA | en |
| dc.title | 最佳混合搭配鏈結集合之分析及其應用 | zh_TW |
| dc.title | Investigation on Optimal Mixing With Linkage Sets and Its
Application | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 102-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳穎平(Ying-Ping Chen),張時中(Shi-Chung Chang) | |
| dc.subject.keyword | 模形建構基因演算法,局部搜索,最佳混合,模型效率,族群成長, | zh_TW |
| dc.subject.keyword | Model Building GA,Local Search,Optimal Mixing,Model Efficiency,Population Sizing, | en |
| dc.relation.page | 44 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2014-07-24 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-103-1.pdf 未授權公開取用 | 488.73 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。