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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:許儲羽
研究生(外文):Chu-Yu Hsu
論文名稱:對排列問題的演化式模型調適基於多臂吃角子老虎技術
論文名稱(外文):Multi-armed Bandit Based Evolutionary Model Adaptationfor Permutation Problems
指導教授:于天立
指導教授(外文):Tien-Li Yu
口試委員:陳穎平張時中
口試委員(外文):Ying-ping ChenShi-Chung Chang
口試日期:2014-07-03
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:43
中文關鍵詞:分配估計演算法模型適應排列問題多臂吃角子老虎問題
外文關鍵詞:EDApermutation problemmodel adaptationmulti-armed bandit problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:204
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本篇論文提供了一種針對分配估計演算法解排列問題之模型適應方
法。分配估計演算法為演化式計算中的一支,特徵在於以機率模型表
示問題解與問題解中變數間的相依關係,同時也因其能解決廣泛的問
題而為人所知。但因排列問題特徵個不相同,為其開發的模型僅能各
自解決一部分問題。因此模型的選擇影響效能甚鉅。更甚者,存在某
些排列問題是存在的模型無法描述的。這些難題促使作者們嘗試了數
種模式適應架構。列舉法同時對所有模型採樣出新的子代,並留下最佳
者。列舉法在線性排序問題得到更好的效能。為了減少在不合適的模
型上浪費計算資源,貝氏法計算每個模型的品質。但因選擇階段與樣
板技術讓貝氏法傾向節點統計模型。基於與多臂吃角子老虎問題的相
似性,我們提出了基於多臂吃角子老虎技術的模型適應架構。該架構
混合了不同的模型並動態地決定使用什麼模型。為了證明此架構的潛
力,測試了幾種排列問題。結果顯示,在當前還沒有專門的模型的問
題,此架構得到相較於單一模型的分配估計演算法還好的效能。另一
方面,在已有專門模型的問題,效能也是最接近專門模型演算法。

This thesis has provided a framework of model adaptation for estimation of distribution algorithms (EDA) on permutation problems.
Characterized by the use of probabilistic models to represent the solutions and the dependencies between the variables of the problem, EDAs are known as powerful evolutionary algorithms that have been widely used for diverse types of problems.
However, since the semantics of permutation problems differs, each model developed for EDAs can only deal with a subset of permutation problems.
The performance suffers from inappropriate model choice.
Furthermore, permutation problem may go beyond the existing models can handle.
Motivated by these difficulties mentioned above, several model adaptation frameworks, which incorporate multiple models and dynamically decide to use which model, are trialled.
In the first trial, the enumeration method samples multiple models simultaneously and shows better performance on Linear Ordering Problem.
To reduce the waste of sampling unpromising models, the Bayesian method has been proposed characterized by measuring the
quality of each model.
However, the Bayesian method tends to choose inappropriate model because of the selection and the template mechanism.
Considering the similarity between model adaptation and multi-armed bandit problem, a multi-armed bandit based model adaptation framework has been proposed.
In order to prove the potential of the proposed framework, different permutation problems have been tested.
The results show that the proposed framework outperforms the other single model EDA on problems that don''t have dedicated models like the vehicle routing problem with time window, and is close to the EDAs with dedicated models on the specific problem like the traveling salesman problem.

Introduction 1
1 Permutation Problems 5
1.1 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Capacitated Vehicle Routing Problem . . . . . . . . . . . . . . . . . . 6
1.3 Permutation Flow-Shop Scheduling Problem . . . . . . . . . . . . . . 8
1.4 Linear Ordering Problem . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Quadratic Assignment Problem . . . . . . . . . . . . . . . . . . . . . 9
2 Related Work 11
2.1 The Edge Histogram Matrix . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 The Node Histogram Matrix . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 The Plackett-Luce Model . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Essence of Adaptation 17
3.1 E ects of Model-Choosing . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 The Sweep method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Methodology 22
4.1 The Enumeration Method . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 The Bayesian Method . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2.1 The Bayesian Posterior Probability . . . . . . . . . . . . . . . 25
4.2.2 Model Adaptation . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.3 Empirical Study . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Multi-armed Bandit Based Model Adaptation . . . . . . . . . . . . . 30
4.3.1 Multi-armed Bandit Problem . . . . . . . . . . . . . . . . . . 31
4.3.2 Upper Con dence Bound Algorithms . . . . . . . . . . . . . . 31
4.3.3 The Proposed Framework . . . . . . . . . . . . . . . . . . . . 32
4.3.4 Empirical Study . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 Conclusion 38
Bibliography 39

Bibliography
[1] A. Allahverdi, C. Ng, T. E. Cheng, and M. Y. Kovalyov. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3):985{1032, 2008.

[2] J.-Y. Audibert, R. Munos, and C. Szepesv ari. Exploration{exploitation tradeo using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876{1902, 2009.

[3] P. Auer. Finite-time Analysis of the Multiarmed Bandit Problem *. pages 235{256, 2002.

[4] P. Auer. Using Con dence Bounds for Exploitation-Exploration Trade-o s. 3:397{422, 2002.

[5] H. J. Barbosa and A. S a. On adaptive operator probabilities in real coded genetic algorithms. In Workshop on Advances and Trends in Arti cial Intelligence for Problem Solving (SCCC''00), 2000.

[6] P. A. Bosman, D. Thierens, et al. Crossing the road to e cient ideas for permutation problems. In Proc. of the Genetic and Evolutionary Computation Conf.{GECCO, pages 219{226, 2001.

[7] A. E. Brownlee, M. Pelikan, J. A. McCall, and A. Petrovski. An application of a multivariate estimation of distribution algorithm to cancer chemotherapy. In Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 463{464. ACM, 2008.

[8] J. Ceberio, E. Irurozki, A. Mendiburu, and J. A. Lozano. A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems. Progress in Arti cial Intelligence, 1(1):103{117, 2012.

[9] J. Ceberio, A. Mendiburu, and J. A. Lozano. Introducing the mallows model on estimation of distribution algorithms. In Neural Information Processing, pages 461{470. Springer, 2011. 39

[10] J. Ceberio, A. Mendiburu, and J. A. Lozano. The plackett-luce ranking model on permutation-based optimization problems. In Evolutionary Computation (CEC), 2013 IEEE Congress on, pages 494{501. IEEE, 2013.

[11] L. Davis. Adapting operator probabilities in genetic algorithms. In Proceedings of the Third International Conference on Genetic Algorithms, pages 61{69, San Francisco, CA, USA, 1989. Morgan Kaufmann Publishers Inc.

[12] F.-M. De Rainville, M. Sebag, C. Gagn e, M. Schoenauer, and D. Laurendeau. Sustainable cooperative coevolution with a multi-armed bandit. In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, GECCO ''13, pages 1517{1524, New York, NY, USA, 2013. ACM.

[13] A. Fialho, L. Da Costa, M. Schoenauer, and M. Sebag. Extreme value based adaptive operator selection. In Parallel Problem Solving from Nature{PPSN X, pages 175{184. Springer, 2008.

[14] A. Fialho, L. Da Costa, M. Schoenauer, and M. Sebag. Analyzing bandit-based adaptive operator selection mechanisms. Annals of Mathematics and Artifficial Intelligence, 60(1-2):25{64, 2010.

[15] A. Fialho, M. Schoenauer, and M. Sebag. Analysis of adaptive operator selection techniques on the royal road and long k-path problems. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 779{786. ACM, 2009.

[16] S. French. Sequencing and scheduling: an introduction to the mathematics of the job-shop, volume 683. Ellis Horwood Chichester, 1982.

[17] S. Gelly, J. B. Hoock, A. Rimmel, and O. Teytaud. THE PARALLELIZATION OF MONTE-CARLO PLANNING Parallelization of MC-Planning. 2008.

[18] S. Gelly and D. Silver. Combining online and o ine knowledge in UCT. Proceedings of the 24th international conference on Machine learning - ICML ''07, pages 273{280, 2007.

[19] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1989.

[20] D. E. Goldberg and R. Lingle. Alleles, loci, and the traveling salesman problem. In Proceedings of an International Conference on Genetic Algorithms and Their Applications, volume 154. Lawrence Erlbaum, Hillsdale, NJ, 1985. 40

[21] J. N. Gupta and E. F. Sta ord Jr. Flowshop scheduling research after ve decades. European Journal of Operational Research, 169(3):699{711, 2006.

[22] G. Harik and S. M. Ave. Linkage Learning via Probabilistic Modeling in the ECGA. (January), 1999.

[23] M. Hauschild. An Introduction and Survey of Estimation of Distribution Algorithms. 2011004(2011004), 2011.

[24] S. Jiang, A. Ziver, J. Carter, C. Pain, A. Goddard, S. Franklin, and H. Phillips. Estimation of distribution algorithms for nuclear reactor fuel management optimisation. Annals of Nuclear Energy, 33(11):1039{1057, 2006.

[25] S. M. Johnson. Optimal two-and three-stage production schedules with setup times included. Naval research logistics quarterly, 1(1):61{68, 1954.

[26] B. A. Julstrom. What have you done for me lately? adapting operator probabilities in a steady-state genetic algorithm. In Proceedings of the 6th International Conference on Genetic Algorithms, pages 81{87, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.

[27] L. Kocsis and C. Szepesv. Bandit Based Monte-Carlo Planning. pages 282{293, 2006.

[28] T. C. Koopmans and M. Beckmann. Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, pages 53{76, 1957.

[29] V. Kuleshov. Algorithms for the multi-armed bandit problem. 1:1{32, 2000.

[30] T. L. Lai and H. Robbins. Asymptotically e cient adaptive allocation rules. Advances in applied mathematics, 6(1):4{22, 1985.

[31] P. Larra~naga and J. A. Lozano. Estimation of distribution algorithms: A new tool for evolutionary computation, volume 2. Springer, 2002.

[32] P. M. Lee. Bayesian statistics: an introduction. John Wiley &; Sons, 2012.

[33] F. G. Lobo and D. E. Goldberg. Decision making in a hybrid genetic algorithm. In Evolutionary Computation, 1997., IEEE International Conference on, pages 121{125. IEEE, 1997.

[34] J. A. Lozano. Towards a new evolutionary computation: Advances on estimation of distribution algorithms, volume 192. Springer, 2006. 41

[35] R. D. Luce. Individual choice behavior: A theoretical analysis. Courier Dover Publications, 2005.

[36] J. I. Marden. Analyzing and modeling rank data. CRC Press, 1996.

[37] R. Mart and G. Reinelt. The linear ordering problem: exact and heuristic methods in combinatorial optimization, volume 175. Springer, 2011.

[38] A. Mendiburu, J. Miguel-Alonso, J. A. Lozano, M. Ostra, and C. Ubide. Parallel edas to create multivariate calibration models for quantitative chemical applications. Journal of Parallel and Distributed Computing, 66(8):1002{1013, 2006.

[39] M. Mohri. Multi-armed Bandit Algorithms and Empirical Evaluation. pages 437{448, 2005..

[40] H. Muhlenbein, J. Bendisch, and H.-M. Voigt. From recombination of genes to the estimation of distributions ii. continuous parameters. In Parallel Problem Solving from Nature|PPSN IV, pages 188{197. Springer, 1996.

[41] M. Pelikan. Hierarchical Bayesian optimization algorithm. Springer, 2005.

[42] 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.

[43] M. Pelikan, S. Tsutsui, and R. Kalapala. Dependency trees, permutations, and quadratic assignment problem. In Genetic And Evolutionary Computation Conference: Proceedings of the 9 th annual conference on Genetic and evolutionary computation, volume 7, pages 629{629, 2007.

[44] R. L. Plackett. The analysis of permutations. Applied Statistics, pages 193{202, 1975.

[45] H. Robbins. Some aspects of the sequential design of experiments. In Herbert Robbins Selected Papers, pages 169{177. Springer, 1985.

[46] R. Santana, P. Larra~naga, and J. A. Lozano. Protein folding in simplified models with estimation of distribution algorithms. Evolutionary Computation, IEEE Transactions on, 12(4):418{438, 2008.

[47] T. Schiavinotto and T. Stutzle. The linear ordering problem: Instances, search space analysis and algorithms. Journal of Mathematical Modelling and Algorithms, 3(4):367{402, 2004. 42

[48] E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278{285, 1993.

[49] P. Toth and D. Vigo. The vehicle routing problem. Siam, 2001.

[50] S. Tsutsui. Probabilistic model-building genetic algorithms in permutation representation domain using edge histogram. In Parallel Problem Solving from Nature|PPSN VII, pages 224{233. Springer, 2002.

[51] S. Tsutsui. A comparative study of sampling methods in node histogram models with probabilistic model-building genetic algorithms. In Systems, Man and Cybernetics, 2006. SMC''06. IEEE International Conference on, volume 4, pages 3132{3137. IEEE, 2006.

[52] 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.

[53] S. Tsutsui, M. Pelikan, and D. E. Goldberg. Node histogram vs. edge histogram: A comparison of pmbgas in permutation domains. MEDAL Report, (2006009), 2006.

[54] S. Tsutsui and G. Wilson. Solving capacitated vehicle routing problems using edge histogram based sampling algorithms. In Evolutionary Computation, 2004. CEC2004. Congress on, volume 1, pages 1150{1157. IEEE, 2004.

[55] A. Tuson and P. Ross. Adapting operator settings in genetic algorithms. Evolutionary computation, 6(2):161{184, 1998.

[56] T.-L. Yu, D. E. Goldberg, K. Sastry, C. F. Lima, and M. Pelikan. Dependency structure matrix, genetic algorithms, and e ective recombination. Evolutionary computation, 17(4):595{626, Jan. 2009.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔