(3.237.178.91) 您好!臺灣時間:2021/03/02 21:37
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳品霖
研究生(外文):Ping-Lin Chen
論文名稱:以雙邊圖鏈結模型改良相依性結構矩陣遺傳演算法二代
論文名稱(外文):Improving DSMGA-II with Two-edge Graphical Linkage Model
指導教授:于天立
口試日期:2017-07-27
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:英文
論文頁數:60
中文關鍵詞:演化式演算法基因演算法鏈結學習模型建構
外文關鍵詞:Evolutionary AlgorithmGenetic AlgorithmLinkage LearningModel Building
相關次數:
  • 被引用被引用:0
  • 點閱點閱:85
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
相依性結構矩陣遺傳演算法二代是一個模型建構的基因演算法,它能夠利用探索問題的子結構來解出許多的最佳化問題。此演算法在許多指標性問題,其中包含兩個現實問題上,已經顯示了比起兩個具有代表性的演算法表現得更加卓越。在這篇論文之中,我提出了一個客製化的模型稱作雙邊圖鏈結模型,這個模型針對了每一個接收者客製化了相對應的遮罩,使得相依性結構矩陣遺傳演算法二代擁有進一步的性能提升。這個新的模型比起原來的版本,提供了夠多種可能的重組方式。為了減少一些不必要的嘗試,這個模型和供給限制的技術一起搭配使用。此外,這篇論文也提供了一個新的技術稱作提早終止判定,些微地增進了重組的效率。結合以上提出的技術,性能在指標性問題的結果上比起原版的相依性結構矩陣遺傳演算法二代有了平均十二個百分點的提升。
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.
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
[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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔