請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/60937完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 于天立 | |
| dc.contributor.author | Wei-Ming Chen | en |
| dc.contributor.author | 陳韋名 | zh_TW |
| dc.date.accessioned | 2021-06-16T10:37:20Z | - |
| dc.date.available | 2016-08-01 | |
| dc.date.copyright | 2013-08-27 | |
| dc.date.issued | 2013 | |
| dc.date.submitted | 2013-08-13 | |
| dc.identifier.citation | [1] D. H. Ackley. An empirical study of bit vector function optimization. Genetic
Algorithms ans Simulated Annealing, pages 170–204, 1987. [2] U. Aickelin, E. K. Burke, and J. Li. An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering. Journal of the Operational Research Society, 58(12):1574–1585, 2007. [3] J. Bacardit, M. Stout, J. D. Hirst, K. Sastry, X. Llor`a, and N. Krasnogor. Automated alphabet reduction method with evolutionary algorithms for protein structure prediction. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2007), pages 346–353, 2007. [4] A. Barron, J. Rissenen, and B. Yu. The MDL principle in coding and modeling. IEEE Transactions on Information Theory, 44(6):2743–2760, 1998. [5] T. Blickle and L. Thiele. A mathematical analysis of tournament selection. Proceed- ings of the Sixth International Conference on Genetic Algorithms (ICGA’95), pages 9–16, 1995. [6] P. A. Bosman and D. Thierens. The roles of local search, model building and optimal mixing in evolutionary algorithms from a bbo perspective. Proceedings of the Ge- netic and Evolutionary Computation Conference (GECCO-2011), pages 663–670, 2011. [7] R. Das and L. D. Whitley. The only challenging problems are deceptive: Global search by solving order-1 hyperplanes. Proceedings of the Fourth International Conference on Genetic Algorithms (ICGA’91), pages 166–173, 1991. [8] K. Deb and D. E. Goldberg. Analyzing deception in trap functions. Foundations of Genetic Algorithms 2, pages 93–108, 1993. [9] K. Deb and D. E. Goldberg. Sufficient conditions for deceptive and easy binary functions. Annals of Mathematics and Artificial Intelligence, 10(4):385–408, 1993. [10] E. Ducheyne, B. De Baets, and R. De Wulf. Probabilistic models for linkage learn- ing in forest management, volume 167 of Knowledge Incorporation in Evolutionary Computation, pages 177–214. Springer, 2004. [11] D. E. Goldberg. Simple genetic algorithms and the minimal, deceptive problem. In Genetic Algorithms and Simulated Annealing, chapter 6, pages 74–88. Pitman Publishing, London, 1987. [12] D. E. Goldberg. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989. [13] D. E. Goldberg. The design of innovation: Lessons from and for competent genetic algorithms. Kluwer Academic Publishers, Boston, MA, 2002. [14] D. E. Goldberg and K. Deb. A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms, pages 69–93. Morgan Kaufmann, 1991. [15] D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333–362, 1992. [16] D. E. Goldberg, K. Sastry, and T. Latoza. On the supply of building blocks. Pro- ceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 336–342, 2001. [17] D. E. Goldberg and S. Voessner. Optimizing global-local search hybrids. Pro- ceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), pages 220–228, 1999. [18] G. Harik. Linkage learning via probabilisticmodeling in the ECGA. IlliGAL Report No. 99010, University of Illinois at Urbana-Champaign, Urbana, IL, February 1999. [19] 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. [20] G. R. Harik. Finding multimodal solutions using restricted tournament selection. Proceedings of the Sixth International Conference on Genetic Algorithms, pages 24–31, 1995. [21] G. R. Harik, F. G. Lobo, and K. Sastry. Linkage learning via probabilistic modeling in the extended compact genetic algorithm (ECGA). In Scalable Optimization via ProbabilisticModeling, chapter 3, pages 39–61. Springer Berlin Heidelberg, Berlin, 2006. [22] W. E. Hart. Adaptive global optimization with local search. PhD thesis, La Jolla, CA, USA, 1994. UMI Order No. GAX94-32928. [23] J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, 1975. [24] M. Hutter and M. Zaffalon. Distribution of mutual information from complete and incomplete data. Computational Statistics and Data Analysis, 48(3):633–657, 2005. [25] D. Icl˘anzan and D. Dumitrescu. Overcoming hierarchical difficulty by hill-climbing the building block structure. Proceedings of the Genetic and Evolutionary Compu- tation Conference (GECCO-2007), pages 1380–1387, 2007. [26] C. F. Lima, M. Pelikan, F. G. Lobo, and D. E. Goldberg. Loopy substructural local search for the bayesian optimization algorithm. Proceedings of the Second Inter- national Workshop on Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics (SLS ’09), pages 61–75, 2009. [27] P. Lipinski. Ecga vs. boa in discovering stock market trading experts. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2007), pages 531–538, 2007. [28] P. Moscato. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Technical Report C3P Report 826, California Institute of Technology, Pasadena, CA, 1989. [29] M. Pelikan, E. Cant ’u-Paz, and D. E. Goldberg. Bayesian optimization algorithm, population sizing, and time to convergence. Proceedings of the Genetic and Evolu- tionary Computation Conference (GECCO-2000), pages 275–282, 2000. [30] 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. [31] M. Pelikan and D. E. Goldberg. Hierarchical BOA solves Ising spin glasses and MAXSAT. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003), pages 1271–1282, 2003. [32] M. Pelikan,M.W. Hauschild, and F. G. Lobo. Introduction to estimation of distribution algorithms. MEDAL Report No. 2012003, Missouri Estimation of Distribution Algorithms Laboratory (MEDAL), University of Missouri-St. Loui, 2012. [33] M. Pelikan, K. Sastry, D. E. Goldberg, M. V. Butz, and M. Hauschild. Performance of evolutionary algorithms on nk landscapes with nearest neighbor interactions and tunable overlap. Proceedings of the Genetic and Evolutionary Computation Confer- ence (GECCO-2009), pages 851–858, 2009. [34] E. Radetic, M. Pelikan, and D. E. Goldberg. Effects of a deterministic hill climber on hboa. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2009), pages 437–444, 2009. [35] K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master thesis, University of Illinois at Urbana-Champaign, Urbana, IL, 2002. [36] K. Sastry and D. E. Goldberg. Let’s get ready to rumble: Crossover versus mutation head to head. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), pages 126–137, 2004. [37] K. Sastry and D. E. Goldberg. Let’s get ready to rumble redux: crossover versus mutation head to head on exponentially scaled problems. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2007), pages 1380– 1387, 2007. [38] C. E. Shannon. Amathematical theory of communication. The Bell System Technical Journal, 27:379–423, 1948. [39] D. Sherrington and S. Kirkpatrick. Solvable model of a spin-glass. Phys. Rev. Lett., 35:1792–1796, 1975. [40] A. Sinha and D. E. Goldberg. Verification and extension of the theory of global-local hybrids. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 591–597, 2001. [41] D. V. Steward. The design structure system: A method for managing the design of complex systems. IEEE Transactions on Engineering Managment, 28:77–74, 1981. [42] D. Thierens and D. E. Goldberg. Convergence models of genetic algorithm selection schemes. Parallel Problem Solving fron Nature (PPSN III), pages 119–129, 1994. [43] M. Tsuji, M. Munetomo, and K. Akama. A crossover for complex building blocks overlapping. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2006), pages 1337–1344, 2006. [44] S. Tsutsui, M. Pelikan, and A. Ghosh. Edge histogram based sampling with local search for solving permutation problems. International Journal of Hybrid Intelligent Systems, 3(1):11–22, 2006. [45] T.-L. Yu and D. E. Goldberg. Dependency structure matrix analysis: Offline utility of the dependency structure matrix genetic algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), pages 355–366, 2004. [46] 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 (AN- NIE 2003), pages 327–332, 2003. [47] T.-L. Yu, K. Sastry, and D. E. Goldberg. Linkage learning, overlapping building blocks, and systematic strategy for scalable recombination. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005), pages 1217– 1224, 2005. [48] T.-L. Yu, K. Sastry, D. E. Goldberg, and M. Pelikan. Population sizing for entropybased model building in discrete estimation of distribution algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2007), pages 601–608, 2007. [49] Q. Zhang, J. Sun, E. Tsang, and J. Ford. Estimation of distribution algorithm with 2- opt local search for the quadratic assignment problem. Towards a New Evolutionary Computation, 192:281–292, 2006. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/60937 | - |
| dc.description.abstract | 把全域搜尋和區域搜尋做混合是一種常見的加速最佳化問題之方
法。在二元問題上，離散爬山演算法是一種常見的區域搜尋方法。對 於分佈估計演算法來說，爬山演算法加強了有關聯基因之間的信號， 這讓模塊更精確的被建立。不僅如此，爬山演算法同時降低了問題內 基因之間的變異程度，讓決策制定更加精確。因此，爬山演算法可以 降低分佈估計演算法被執行時所需要的最小群體大小和收斂時間。但 是，執行爬山演算法本身也會耗費額外的時間。本篇論文提出一個兩 階段的爬山演算法來加速分佈估計演算法，第一個階段是執行以基因 為基礎的爬山演算法，第二階段則是執行以模塊為基礎的爬山演算 法。為了確定演算法的總執行時間是下降的，我們分別去計算使用以 基因為基礎的爬山演算法與不使用的時間複雜度。在兩種測試問題 上，兩種不同的以基因為基礎的爬山演算法被用來做測試。理論推導 以及在延伸式精簡基因演算法和相依關係結構矩陣基因演算法上的實 驗結果，都證明了其中一種基因為基礎的爬山演算法可以加速分佈估 計演算法的執行時間。當進一步和以模塊為基礎的爬山演算法做結合 以後，我們使用另外三種測試問題做測試。實驗結果顯示相依關係結 構矩陣基因演算法同時加入以基因為基礎的爬山演算法和以模塊為基 礎的爬山演算法，執行效率會比只加入以基因為基礎的爬山演算法來 的高。 | zh_TW |
| dc.description.abstract | Hybridization of global and local searches is a well-known technique for
optimization algorithms. Discrete hill climbing is one of the local search methods on binary problems. On estimation of distribution algorithms (EDAs), hill climbing strengthens the signals of dependencies on correlated variables and improves the quality of model building. Moreover, hill climbing reduces the variance in the problem, which makes decision making more accurately. Therefore, hill climber reduces the required population size and convergence time for EDAs. However, hill climbing also consumes extra computational time. In this thesis, a two-stage hill climbing algorithm is proposed to improve the efficiency of EDAs. Gene-wise hill climbers are performed first, follow by building-block-wise hill climbers. To make sure the overall performance is improved, on gene-wise hill climbers, analytical models are developed to investigate the effects of combining two different gene-wise hill climbers with the extended compact genetic algorithm and the dependency structure matrix genetic algorithm. By using the one-max problem and the 5-bit non-overlapping trap problem as the test problems, the performances of different hill climbers are compared. Both analytical models and experiments reveal that the greedy hill climber reduces the number of function evaluations for EDAs to find the global optimum. After combining with building-blockwise hill climbers, experiments on the 5-bit non-overlapping trap problem, Cyclictrap, and NK-landscape are performed on the dependency structure matrix genetic algorithm with MinCut+ crossover method. Experiment results show that the number of function evaluations on the dependency structure matrix genetic algorithm with both gene-wise hill climbers and buildingblock- wise hill climbers is less than which only with gene-wise hill climbers. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T10:37:20Z (GMT). No. of bitstreams: 1 ntu-102-R00921044-1.pdf: 1337571 bytes, checksum: 36bbe53c3440fb04db9630e372f78fd6 (MD5) Previous issue date: 2013 | en |
| dc.description.tableofcontents | 口試委員會審定書i
Acknowledgments ii 中文摘要iii Abstract iv 1 Introduction 1 2 Methodology 3 2.1 Estimation of Distribution Algorithm . . . . . . . . . . . . . . . . . . . . 3 2.1.1 EDAs outperform GAs on some of the problems . . . . . . . . . 3 2.1.2 eCGA and DSMGA . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.3 Techniques on EDAs: MinCut+ and Restricted Tournament Replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.4 Experiment Setting . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Test Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 OneMax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.2 Trap-5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.3 Cyclictrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.4 NK-landscape . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Gene-Wise Hill Climber 10 3.1 Hill climbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Steepest-descent Hill Climber and Greedy Hill Climber . . . . . . 10 3.1.2 NFE requirement for SHC on Trap-5 . . . . . . . . . . . . . . . 11 3.1.3 NFE requirement for GHC on Trap-5 . . . . . . . . . . . . . . . 11 3.2 EDA without Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 EDA with SHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.4 EDA with GHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.5 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.6 EDAs on Overlapping Problems . . . . . . . . . . . . . . . . . . . . . . 23 4 Building-Block-Wise Hill Climber 26 4.1 A Simple Building-Block-Wise Hill Climber: SBBHC . . . . . . . . . . 26 4.2 SBBHC perturb a BB away from global optimum . . . . . . . . . . . . . 27 4.3 An Advanced Building-Block-Wise Hill Climber: ABBHC . . . . . . . . 30 4.4 Time Complexity of Building-Block-Wise Hill Climbers . . . . . . . . . 31 4.5 Experiments and Discussions . . . . . . . . . . . . . . . . . . . . . . . . 32 5 Conclusion 34 Bibliography 36 | |
| dc.language.iso | en | |
| dc.subject | 區域搜尋 | zh_TW |
| dc.subject | 分佈估計演算法 | zh_TW |
| dc.subject | 理論推導 | zh_TW |
| dc.subject | 表現測量 | zh_TW |
| dc.subject | Performance Measures | en |
| dc.subject | Theory | en |
| dc.subject | Estimation of Distribution Algorithms | en |
| dc.subject | Local Search | en |
| dc.title | 爬山演算法對分佈估計演算法的影響 | zh_TW |
| dc.title | Effects of Discrete Hill Climbers for Estimation of Distribution Algorithms | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 101-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 張時中,陳穎平 | |
| dc.subject.keyword | 分佈估計演算法,區域搜尋,理論推導,表現測量, | zh_TW |
| dc.subject.keyword | Estimation of Distribution Algorithms,Local Search,Theory,Performance Measures, | en |
| dc.relation.page | 40 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2013-08-14 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-102-1.pdf 未授權公開取用 | 1.31 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。