跳到主要內容

臺灣博碩士論文加值系統

(18.205.192.201) 您好!臺灣時間:2021/08/06 06:07
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳家輝
研究生(外文):Jia-Hui Wu
論文名稱:用限制競爭式取代法與模型關聯法改進在排列問題上的模型適應
論文名稱(外文):Improving Model Adaptation for Permutation Problems by RTR with Model-associated Method
指導教授:于天立
指導教授(外文):Tian-Li Yu
口試委員:陳穎平李宏毅
口試委員(外文):Ying-Ping ChenHung-Yi Lee
口試日期:2015-06-23
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:46
中文關鍵詞:分配估計演算法模型適應排列問題距離選擇小生境技術限制競爭式取代法
外文關鍵詞:EDApermutation problemmodel adaptationdistance choosingnichingRTR
相關次數:
  • 被引用被引用:0
  • 點閱點閱:55
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文提供了針對排列問題利用限制競爭式取代法改善分配估計演算法的效能並提出限制競爭式取代法的距離量測選擇方法。限制競爭式取代法是在分配估計演算法領域中著名的小生境技術,它需要距離量測方法來評量兩個解之間的距離,但是排列問題的特徵各不相同,為其開發的距離只能正確衡量一部份的問題,在這篇論文中我們會簡單的介紹限制競爭式取代法與模型適應方法,定義三種排列的距離測量方式,然後基於模型適應方法選擇的模型來選擇限制競爭式取代法所用的距離測量方式並探討限制錦標替代法設定的視窗大小以及改進模型自適應中的報酬策略設定。在我們的實驗中,結果顯示了使用限制競爭式取代法可以增進解排列問題效能。在實驗中的,本研究方法改進了原有的方法平均十六個百分比的效能。

This thesis integrates the restricted tournament replacement (RTR) into estimation of distribution algorithms (EDAs) to effectively solve permutation problems and provides a method for choosing the distance measure of RTR. Since the semantics of permutation problems differ, the performance depends on distance-measure choosing. Inspired by RTR and the technique of the model adaptation for EDAs on permutation problems, the proposed method chooses the distance measure according to the selected model. We also investigate the setting of window size and modify reward policy by the feedback from our proposed method. Some experiments are used to test the efficiency of the proposed method. The results indicate that EDAs for permutation problems with RTR using the correct distance measure outperform the originals, semantic niching technique provides additional knowledge to learn the semantics of permutation problems and distance-measure choosing helps to model adaptation. Combining these features, our proposed method is close to the best performing model and may outperform any single models on problems without semantic model specially designed for that. In this thesis, our proposed method improves the performance by 16 percent in average.

Contents
Acknowledgments i
致謝ii
中文摘要iii
Abstract iv
1 Introduction 1
2 Permutation Problems 5
2.1 Travelling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Capacitated Vehicle Routing Problem . . . . . . . . . . . . . . . . . . 7
2.3 Permutation Flow-Shop Scheduling Problem . . . . . . . . . . . . . . 8
2.4 Linear Ordering Problem . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Quadratic Assignment Problem . . . . . . . . . . . . . . . . . . . . . 11
3 Related Work 13
3.1 Existing Semantic Models For
Permutation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1 The Edge-Histogram Matrix . . . . . . . . . . . . . . . . . . . 13
3.1.2 The Node-Histogram Matrix . . . . . . . . . . . . . . . . . . . 15
3.1.3 The Plackett-Luce model . . . . . . . . . . . . . . . . . . . . . 17
3.2 Model Adaptation for permutation problems . . . . . . . . . . . . . . 19
3.2.1 Multi-armed Bandit Problem . . . . . . . . . . . . . . . . . . 19
3.2.2 Multi-armed bandit based model adaptation . . . . . . . . . . 21
3.3 Niching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.1 Niching Techniques . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Restricted Tournament Replacement . . . . . . . . . . . . . . 23
4 Methodology 26
4.1 Distance Measure of RTR for
Permutation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Essence of Distance-measure Choosing . . . . . . . . . . . . . . . . . 31
4.3 Model-associated Method . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4 Reward Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.5 Window Size of RTR for
Permutation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.6 Empirical Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 Conclusion 40
Bibliography 41

Bibliography
[1] K. Adusumilli, D. Bein, and W. W. Bein. A genetic algorithm for the two
machine flow shop problem. In HICSS, page 64. IEEE Computer Society, 2008.
[2] A. Allahverdi, C. T. Ng, T. C. 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.
[3] J.-Y. Audibert, R. Munos, and C. Szepesv´ari. Exploration–exploitation tradeoff
using variance estimates in multi-armed bandits. Theoretical Computer Science,
410(19):1876–1902, 2009.
[4] P. Auer. Using confidence bounds for exploitation-exploration trade-offs. The
Journal of Machine Learning Research, 3:397–422, 2003.
[5] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed
bandit problem. Machine learning, 47(2-3):235–256, 2002.
[6] 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.
[7] R. E. Burkard, S. E. Karisch, and F. Rendl. QAPLIB - a quadratic assignment
problem library. Technical report, Department of Mathematics, Graz University
of Technology, Graz, Austria, 1996.
[8] 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.
[9] J. Ceberio, A. Mendiburu, and J. A. Lozano. The plackett-luce ranking model
on permutation-based optimization problems. In 2013 IEEE Congress on Evolutionary
Computation (CEC), pages 494–501. IEEE, 2013.
41
[10] H. B. Chenery and T. Watanabe. International comparisons of the structure of
production. Econometrica, 26(4):pp. 487–521, 1958.
[11] G. B. Dantzig and J. H. Ramser. The truck dispatching problem. Management
Science, 6(1):80–91, 1959.
[12] K. A. De Jong. An analysis of the behavior of a class of genetic adaptive
systems. PhD thesis, University of Michigan, Ann Arbor, 1975. (University
Microfilms No. 76-9381).
[13] S. French. Sequencing and scheduling: an introduction to the mathematics of
the job-shop, volume 683. Ellis Horwood Chichester, 1982.
[14] S. Gelly, J.-B. Hoock, A. Rimmel, O. Teytaud, Y. Kalemkarian, et al. On the
parallelization of monte-carlo planning. In ICINCO, 2008.
[15] S. Gelly and D. Silver. Combining online and offline knowledge in uct. In
Proceedings of the 24th international conference on Machine learning, pages
273–280. ACM, 2007.
[16] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine
Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA,
1st edition, 1989.
[17] 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.
[18] D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal
function optimization. In Proceedings of the Second International Conference
on Genetic Algorithms and Their Applications, pages 41–49. Lawrence
Erlbaum, Hillsdale, NJ, 1987.
[19] P. B. Grosso. Computer simulation of genetic adaptation: Parallel subcomponent
interaction in a multilocus model. PhD thesis, University of Michigan,
1985. University Microfilms Number 8520908.
[20] J. N. Gupta and E. F. Stafford Jr. Flowshop scheduling research after five
decades. European Journal of Operational Research, 169(3):699–711, 2006.
[21] G. R. Harik. Finding multimodal solutions using restricted tournament selection.
In ICGA, pages 24–31, 1995.
42
[22] G. R. Harik, E. Cant´u-Paz, D. E. Goldberg, and B. L. Miller. The gambler’s
ruin problem, genetic algorithms, and the sizing of populations. Evolutionary
Computation, 7(3):231–253, 1999.
[23] M. Hauschild and M. Pelikan. An introduction and survey of estimation of
distribution algorithms. Swarm and Evolutionary Computation, 1(3):111–128,
2011.
[24] C.-Y. Hsu. Multi-armed bandit based evolutionary model adaptation for permutation
problems. Master thesis, National Taiwan University, Taiwan, TW,
2014.
[25] D. R. Hunter. Mm algorithms for generalized bradley-terry models. Annals of
Statistics, pages 384–406, 2004.
[26] 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.
[27] J. G. Kemeny. Mathematics without Numbers. Daedalus, 88(4), 1959.
[28] L. Kocsis and C. Szepesv´ari. Bandit based monte-carlo planning. Springer, New
York, NY, 2006.
[29] T. C. Koopmans and M. Beckmann. Assignment problems and the location of
economic activities. Econometrica: journal of the Econometric Society, pages
53–76, 1957.
[30] V. Kuleshov and D. Precup. Algorithms for multi-armed bandit problems.
arXiv preprint arXiv:1402.6028, 2000.
[31] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules.
Advances in applied mathematics, 6(1):4–22, 1985.
[32] P. Larra˜naga and J. A. Lozano. Estimation of distribution algorithms: A new
tool for evolutionary computation, volume 2. Springer, 2002.
[33] E. M. Loiola, N. M. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and
T. Querido. A survey for the quadratic assignment problem. European Journal
of Operational Research, 176:657–690.
[34] J. A. Lozano. Towards a new evolutionary computation: Advances on estimation
of distribution algorithms, volume 192. Springer, New York, NY, 2006.
43
[35] R. D. Luce. Individual choice behavior: A theoretical analysis. Courier Dover
Publications, Mineola, New York, 2005.
[36] J. I. Marden. Analyzing and modeling rank data. CRC Press, Boca Raton,
Florida, 1996.
[37] R. Mart´ı and G. Reinelt. The linear ordering problem: exact and heuristic
methods in combinatorial optimization, volume 175. Springer, New York, NY,
2011.
[38] R. A. J. Matthews. The use of genetic algorithms in cryptanalysis. Cryptologia,
17(2):187–201, 1993.
[39] 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.
[40] M. Mohri. Multi-armed Bandit Algorithms and Empirical Evaluation. pages
437–448, 2005.
[41] H. Muhlenbein, 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.
[42] P. M. Pardalos, F. Rendl, and H. Wolkowicz. The quadratic assignment problem:
A survey and recent developments. In In Proceedings of the DIMACS
Workshop on Quadratic Assignment Problems, volume 16 of DIMACS Series
in Discrete Mathematics and Theoretical Computer Science, pages 1–42. American
Mathematical Society, 1994.
[43] M. Pelikan. Hierarchical Bayesian optimization algorithm. Springer, New York,
NY, 2005.
[44] 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.
[45] 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.
44
[46] R. L. Plackett. The analysis of permutations. Applied Statistics, pages 193–202,
1975.
[47] G. Reinelt. Tsplib. http://comopt.ifi.uni-heidelberg.de/software/
TSPLIB95/index.html, January 1995.
[48] H. Robbins. Some aspects of the sequential design of experiments. In Herbert
Robbins Selected Papers, pages 169–177. Springer, 1985.
[49] S. Sahni and T. Gonzalez. P-complete approximation problems. J. ACM,
23(3):555–565, 1976.
[50] 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.
[51] T. Schiavinotto and T. Sttzle. The linear ordering problem: Instances, search
space analysis and algorithms. Journal of Mathematical Modelling and algorithms
3, pages 367–402, 2004.
[52] P. Slater. Inconsistencies in a schedule of paired comparisons. Biometrika,
48(3-4):303–312, Dec. 1961.
[53] R. Spillman, M. Janssen, B. Nelson, and M. Kepner. Use of a genetic algorithm
in the cryptanalysis of simple substitution ciphers. Cryptologia, 17(1):31–44,
Jan. 1993.
[54] P. Toth and D. Vigo. The vehicle routing problem. Siam, Philadelphia, PA,
2001.
[55] 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.
[56] 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.
[57] 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
[58] S. Tsutsui, M. Pelikan, and D. E. Goldberg. Node histogram vs. edge histogram:
A comparison of pmbgas in permutation domains. MEDAL Report, (2006009),
2006.
[59] S. Tsutsui and G. Wilson. Solving capacitated vehicle routing problems using
edge histogram based sampling algorithms. In IEEE Congress on Evolutionary
Computation(CEC), 2004., volume 1, pages 1150–1157. IEEE, 2004.
[60] T.-L. Yu, D. E. Goldberg, K. Sastry, C. F. Lima, and M. Pelikan. Dependency
structure matrix, genetic algorithms , and effective recombination. Evolutionary
Computation, vol. 17, no. 4, pp. 595–626, 2009.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top