簡易檢索 / 詳目顯示

回結果列表
研究生： 陳萌智
Chen, Min-Chih
論文名稱： 分佈估計演算法解決排程問題之有效指引原則
Guidelines for Developing Effective Estimation of Distribution Algorithms in Solving Scheduling Problems
指導教授： 陳裕民
Chen, Min-Chih
學位類別： 博士
Doctor
系所名稱： 電機資訊學院 - 製造資訊與系統研究所
Institute of Manufacturing Information and Systems
論文出版年： 2012
畢業學年度： 100
語文別： 英文
論文頁數： 125
中文關鍵詞： 分佈估計演算法 、啟發式演算法 、排程問題
外文關鍵詞： Estimation of Distribution Algorithms, Heuristic Algorithms, Scheduling Problems
相關次數： 點閱：103  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本研究的目的是提出設計分佈估計演算法(Estimation of Distribution Algorithms)有效指引原則。分佈估計演算法由於使用機率模式產生可行解，因此具有不會拆解可行解良好結構的特色，然而卻可能造成分佈估計演算法過早趨於收斂的問題，本研究的第一個指引原則是控制群體的多樣性(diversity)，使其能在多樣性與收斂性之間取得平衡，因此提出二個策略：逐步增加群體多樣性與結合超啟發式演算法(meta-heuristic)。分佈估計演算法的另一個問題是機率模式(probabilistic model)可能無法真正描述群體的資訊，本研究第二個指引原則是加強全域搜尋的資訊模式，為此提出二個策略，其一是加入變數之間互動的資訊，其二是在演化初始時加入特定領域的知識。分佈估計演算法另一個問題是缺乏探究(exploitation)最佳解的能力，本研究第三個指引原則是加入局部搜尋演算法，為此提出的策略是在演化過程中將有希望的可行解改良成局部最佳解，再持續演化使其最後能趨近於全域最佳解。為了進一步說明與驗證這些指引原則，本研究將二個有名的分佈估計演算法(EA/G、ACGA)分別加以改良成Adaptive EA/G、EA/G-GA、eACGA、eACGAHYBRID，並分別運用在解決單機、單機具整備時間與流線型機台的排程問題，實驗結果指出改良的演算法在求解品質上比原本的演算法較佳且具有顯著差異，因此這些原則將能提供分佈估計演算法的研究者進一步提升演算法效率的參考，同時證明本研究對於改良分佈估計演算法的效率有重要的貢獻。

    The goal of this research is to deduce important guidelines for designing effective Estimation of Distribution Algorithms (EDAs). Most EDAs have the advantage of incorporating probabilistic models which can generate chromosomes with non-disruption of salient genes. This advantage, however, may result in premature convergence of EDAs. In order to enhance the design of algorithms in balancing the intensification and diversification effects of EDAs, we propose two strategies to control the diversity of population: by increasing the population diversity gradually and by hybridizing EDAs with other meta-heuristics. There is still a second EDAs question that remains: simple probabilistic models may not be truly representative of the population. To address this concern, two strategies are presented to enhance the information model in global search: by combining ordinal probabilistic model with dependent probabilistic model to represent information model of the population and by embedding domain specific knowledge. Having tackled the problems of diversity and representation, the only item left to discuss is that a promising solution needs a refining method to approach the local optimal solution in evolution. In order to improve the solution quality, exploitative behavior is hybridized into the searching process. For illustrating and validating these guidelines, we employ two well known EDAs as improvements, EA/G and ACGA. The enhanced algorithms based on these guidelines are named as Adaptive EA/G, EA/G-GA, eACGA and eACGAHYBRID respectively. These algorithms are applied in a just-in-time single objective scheduling environment to solve single machine scheduling problems, single machine scheduling problems with setup time, and permutation flowshop scheduling problems. Overview of the experimental results shows that, in terms of solution quality, all of our improved algorithms outperformed original EDAs as well as some algorithms in the literature. Thus, these guidelines can provide references for researchers to improve their EDAs performance in the future, and this study is important for the same reason.

    Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Scope of the Research 5 1.3 Contribution of the Research 6 Charter 2 Literature Review 9 2.1 Review of EDAs 9 2.2 Review of Scheduling Problems 14 2.2.1 Single Machine Scheduling Problems 14 2.2.2 Single Machine Scheduling Problems with Setup Time 15 2.2.3 Permutation Flowshop Scheduling Problems 19 Chapter 3 Methodology 21 3.1 Framework of the Research 21 3.2 Review of Related Algorithms 27 3.2.1 Review of EA/G 27 3.2.2 Introduction of ACGA 30 3.3 Methodology of Revised Algorithms 33 3.3.1 Adaptive EA/G 33 3.3.2 EA/G-GA 36 3.3.3 Extend ACGA 38 3.3.4 Hybrid eACGA 53 Chapter 4 Experiment Results 56 4.1 Adaptive EA/G and EA/G-GA for Single Machine Scheduling Problems 56 4.1.1 Experiment Statement 56 4.1.2 Experiment Results 57 4.2 Experiment of eACGA 65 4.2.1 eACGA for Single Machine Scheduling Problems with Setup Time 66 4.2.2 eACGA for Flowshop Scheduling Problems 72 4.3 Experiment of eACGAHYBRID 83 4.3.1 For Single Machine Scheduling Problems with Setup Time 84 4.3.2 For Flowshop Scheduling Problems 88 Chapter 5 Discussions 94 5.1 Observation of Diversity 94 5.2 Different Combinations for EA/G - GA 97 5.3 Discussion on Proposed Algorithms for Large Size Scheduling Problems 100 Chapter 6 Conclusions 104 References 108 Appendix A Parameter Configuration of eACGA 116 A.1 In Single Machine Scheduling Problems with Setup Time 116 A.2 In Flowshop Scheduling Problems 118 A.2.1 Population Size, Crossover Rate, and Mutation Rate 119 A.2.2 Starting Generation and Interval 123 A.2.3 Ordinal and Dependent Probability Learning Rate 124

    1. Ahn, C., An, J., Yoo, J. Estimation of Particle Swarm Distribution Algorithms: Combining the Benefits of PSO and EDAs. Information Sciences, 2010.
    2. Ackley, D. H. A connectionist machine for genetic hillclimbing. Kluwer Academic Publishers Norwell, MA, USA, 1987.
    3. Aickelin, U., Burke, E. K., Li, J. 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.
    4. Alves, M.J.; Almeida, M. MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem. Comput. Oper. Res. 34, 3458–3470, 2007.
    5. Baker, K. R. Introduction to sequencing and scheduling. Wiley, 1974.
    6. Baluja, S. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, 1994.
    7. Baluja, S. An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics, 1995.
    8. Baluja, S. Davies, S., Using Optimal Dependency-Trees for Combinational Optimization. Proceedings of the Fourteenth International Conference on Machine Learning table of contents, 30–38, 1997.
    9. Baluja, S.; Davies, S. Fast Probabilistic Modeling for Combinatorial Optimization. In Proceedings of the fifteenth National/Tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence, Menlo Park, CA, USA, 1998.
    10. Belouadah, H.; Posner, M.; Potts, C. Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Appl. Math. 36, 213–231, 1992.
    11. Bengoetxea, E., Larra˜naga, P., Bloch, I., Perchant, A., Boeres, C. Inexact graph matching by means of estimation of distribution algorithms. Pattern Recognition 35 (12), 2867–2880, 2002.
    12. Branke, J., Lode, C., Shapiro, J. Addressing sampling errors and diversity loss in UMDA. In: Proceedings of the 9th annual conference on Genetic and evolutionary computation. ACM, p. 515, 2007.
    13. Brownlee, A. E. I., McCall, J. A. W., Zhang, Q., Brown, D. F. Approaches to selection and their effect on fitness modelling in an estimation of distribution algorithm. In: IEEE Congress on Evolutionary Computation, 2008. IEEE, pp. 2621–2628, 2008.
    14. Ceberio, J., E. Irurozki, A. M., Lozano, J. A review on Estimation of Distribution Algorithms in Permutation-based Combinatorial Optimization Problems. Accepted by Progress in Artificial Intelligence , 2011.
    15. Chang, P.C.; Lee, H.C. A greedy heuristic for bicriterion single machine scheduling problems. Comput. Ind. Eng. 22, 121–131, 1992.
    16. Chang, P.C. A branch and bound approach for single machine scheduling with earliness and tardiness penalties. Comput. Math. Appl. 37, 133–144, 1999.
    17. Chang, P. C., Chen, S. H., Liu, C. H. Sub-population genetic algorithm with mining gene structures for multiobjective flowshop scheduling problems. Expert Systems with Applications 33 (3), 762–771, 2007.
    18. Chang, P. C., Chen, S. H., Fan, C. Y. Mining gene structures to inject artificial chromosomes for genetic algorithm in single machine scheduling problems. Applied Soft Computing Journal 8 (1), 767–777, 2008.
    19. Chang, P., Chen, S. H., Fan, C. Y. Generating Artificial Chromosomes by Mining Gene Structures with Diversity Preservation for Scheduling Problems. Annals of Operations Research, 2009a.
    20. Chang, P., Hsieh, J., Chen, S., Lin, J., Huang, W. Artificial chromosomes embedded in genetic algorithm for a chip resistor scheduling problem in minimizing the makespan. Expert Systems With Applications 36 (3, Part 2), 7135–7141, 2009b.
    21. Chang, P. C., Chen, S. H., Fan, C. Y. Generating Artificial Chromosomes by Mining Gene Structures with Diversity Preservation for Scheduling Problems, Annals of Operations Research 180 (1), 197–211, 2010.
    22. Chang, P. C., Lie, T., Liu, J. Y., Chen, S. H. A genetic algorithm enhanced by dominance properties for single machine scheduling problems with setup cost. International Journal of Innovative Computing, Information and Control 7 (5), 1– 21., 2011.
    23. Chen, S. H., Chang, P. C., Zhang, Q. Self-Guided genetic algorithm. Lecture Notes in Artificial Intelligence 5227, 292–299, 2008.
    24. Chen, S. H., Chang, P. C., Chen, M. C., and Chen, Y. M., A Self-guided Genetic Algorithm with Dominance Properties for Single Machine Scheduling problems, 2009 IEEE Symposium on Computational Intelligence in Scheduling (CISched 2009), Nashville, TN, U.S.A, 2009.
    25. Chen, S. H., Chang, P. C., Zhang, Q., Wang, C. B. A guided memetic algorithm with probabilistic models. International Journal of Innovative Computing, Information and Control 5 (12), 4753–4764, 2009.
    26. Chen, S. H., Chen, M. C., Chang, P. C., Zhang, Q., Chen, Y. M. Guidelines for developing effective Estimation of Distribution Algorithms in solving single machine scheduling problems. Expert Systems with Applications 37 (9), 6441–6451, 2010.
    27. Chen, S. H., Chang, P. C., Cheng, T. C. E., Zhang, Q. A self-guided genetic algorithm for permutation flowshop scheduling problems. Computers & Operations Research, 39(7), 1450–1457, 2012.
    28. Eiben, A., Smith, J. Introduction to Evolutionary Computing. Springer, 2003.
    29. Framinan, J. M., Gupta, J. N. D., Leisten, R. A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Journal of the Operational Research Society 55 (12), 1243–1255, 2004.
    30. Glover, F., Laguna, M. Tabu Search. Kluwer Academic Publishers Norwell, MA, USA, 1998.
    31. Gordon, V., Proth, J., Chu, C. A survey of the state-of-theart of common due date assignment and scheduling research. European Journal of Operational Research 139 (1), 1–25, 2002.
    32. Hansen, P., Mladenovi, N. Variable neighborhood search: Principles and applications. European Journal of Operational Research 130 (3), 449– 467, 2001.
    33. Hansen, P., Mladenovi´c, N., Perez-Britos, D. Variable Neighborhood Decomposition Search. Journal of Heuristics 7 (4), 335–350, 2001.
    34. Hauschild, M., Pelikan, M. An introduction and survey of estimation of distribution algorithms. Accepted by Swarm and Evolutionary Computation, 2011.
    35. Harik, G., Lobo, F., Goldberg, D. The compact genetic algorithm. Evolutionary Computation, IEEE Transactions on 3 (4), 287–297, 1999.
    36. Hejazi, S., Saghafian, S. Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research 43 (14), 2895–2929, 2005.
    37. Hofmeyr, S., Forrest, S. Architecture for an Artificial Immune System. Evolutionary Computation 8 (4), 443–473, 2000.
    38. Hunt, J., Cooke, D. Learning using an artificial immune system. Journal of Network and Computer Applications 19 (2), 189–212, 1996.
    39. Jarboui, B., Ibrahim, S., Siarry, P., Rebai, A. A combinatorial particle swarm optimisation for solving permutation flowshop problems. Computers & Industrial Engineering 54 (3), 526–538, 2008.
    40. Jarboui, B., Eddaly, M., Siarry, P. An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems. Computers & Operations Research 36 (9), 2638–2646, 2009a.
    41. Jarboui, B., Eddaly, M., Siarry, P and Rebaï, A. An Estimation of Distribution Algorithm for Minimizing the Makespan in Blocking Flowshop Scheduling Problems. Computational Intelligence in Flow Shop and Job Shop Scheduling, 151–167, 2009b.
    42. Kanet, J. Minimizing the average deviation of job completion times about a common due date. Naval Research Logistics Quarterly 28 (4), 643–651, 1981.
    43. Larra˜naga, P., Lozano, J. A. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers , 2002.
    44. Lenstra, J.; Kan, A.; Brucker, P. Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343–362, 1975.
    45. Lima, C., Pelikan, M., Lobo, F., Goldberg, D. Loopy substructural local search for the bayesian optimization algorithm. Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, 61–75, 2009.
    46. Lin, S., Kernighan, B. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research 21 (2), 498–516, 1973.
    47. Liu, H., Gao, L., Pan, Q. A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem. Expert Systems with Applications 38 (4), 4348–4360, 2011.
    48. Lozano, J. A. Towards a New Evolutionary Computation: Advances in the Estimation of Distribution Algorithms. Springer, 2006.
    49. Hansen, P. and Mladenovic, N. Variable neighborhood search: Principles and applications. European Journal of Operational Research 130 (3), 449–467, 2001.
    50. Mladenovic, N., Hansen, P. Variable neighborhood search. Computers and Operations Research 24 (11), 1097–1100, 1997.
    51. Montgomery, D.C. Design and Analysis of Experiments; 2001.
    52. Muhlenbein, H., Paaß, G. From recombination of genes to the estimation of distributions I. Binary parameters. Lecture Notes in Computer Science 1141, 178–187, 1996.
    53. Nagano, M., Ruiz, R., Lorena, L., 2008. A Constructive Genetic Algorithm for permutation flowshop scheduling. Computers & Industrial Engineering.
    54. Nareyek, A. Constraint-Based Agents: An Architecture for Constraint Based Modeling and Local-Search-Based Reasoning for Planning and Scheduling in Open and Dynamic Worlds. Springer, 2001.
    55. Nawaz, M., Enscore, E., Ham, I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA 11 (1), 91–95, 1983.
    56. Okabe, T., Jin, Y., Sendoff, B., Olhofer, M. Voronoi-based estimation of distribution algorithm for multi-objective optimization. Evolutionary Computation, CEC2004. Congress on 2, 2004.
    57. Ow, P. S., Morton, T. E. The Single Machine Early/Tardy Problem. Management Science 35 (2), 177–191, 1989.
    58. Pan, Q., Tasgetiren, M., Liang, Y. A discrete dierential evolution algorithm for the permutation owshop scheduling problem. Computers & Industrial Engineering 55 (4), 795-816, 2008.
    59. Pan, Q. K., Ruiz, R. An estimation of distribution algorithm for lot-streaming flowshop problems with setup times. Omega 40 (2), 166-180, 2012.
    60. Pasti, R., de Castro, L. Bio-inspired and gradient-based algorithms to train MLPs: The influence of diversity. Information Sciences, 2009.
    61. Pe˜na, J., Robles, V., Larra˜naga, P., Herves, V., Rosales, F., Perez, M., 2004. GA-EDA: Hybrid Evolutionary Algorithm Using Genetic and Estimation of Distribution Algorithms. Innovations In Applied Artificial Intelligence: 17th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2004, Ottawa, Canada, May 17-20, 2004.
    62. Pelikan, M., Goldberg, D. E., Lobo, F. G. A Survey of Optimization by Building and Using Probabilistic Models. Computational Optimization and Applications 21 (1), 5–20, 2002.
    63. Rabadi, G., Mollaghasemi, M., Anagnostopoulos, G., A branch and bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time, Computers & Operations Research 31 (10) 1727-1751, 2004.
    64. Rabadi, G., Anagnostopoulos, G., Mollaghasemi, M. A heuristic algorithm for the just-in-time single machine scheduling problem with setups: a comparison with simulated annealing. The International Journal of Advanced Manufacturing Technology 32 (3), 326-335, 2007.
    65. Reeves, C. R. A genetic algorithm for flowshop sequencing. Computers and Operations Research 22 (1), 5–13, 1995.
    66. Ruiz, R., Maroto, C. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research 165 (2), 479–494, 2005.
    67. Santana, R., Larra˜naga, P., Lozano, J. Combining variable neighborhood search and estimation of distribution algorithms in the protein side chain placement problem. Journal of Heuristics 14, 519–547, 2008.
    68. Sastry, K., Pelikan, M., Goldberg, D. E. Efficiency enhancement of estimation of distribution algorithms. Computational Intelligence 33, 161–185, 2006.
    69. Sevkli, M., Aydin, M. Variable Neighbourhood Search for job shop scheduling problems. Journal of Software 1 (2), 34, 2009.
    70. Shapiro, J. Drift and scaling in estimation of distribution algorithms. Evolutionary computation 13 (1), 99–123, 2005.
    71. Shapiro, J. Diversity loss in general estimation of distribution algorithms. Parallel Problem Solving from Nature-PPSN IX, 92–101, 2006.
    72. Sourd, F., Kedad-Sidhoum, S. The One-Machine Problem with Earliness and Tardiness Penalties. Journal of Scheduling 6 (6), 533–549, 2003.
    73. Sourd, F. Earliness–tardiness scheduling with setup considerations. Computers and operations research 32 (7), 1849–1865, 2005.
    74. Syswerda, G. Simulated crossover in genetic algorithms. Foundations of Genetic Algorithms 2, 239–255, 1993.
    75. Taillard, E. Benchmarks for basic scheduling instances. European Journal of Operational Research 64, 278-285, 1993.
    76. Tsutsui, S., Miki, M. Solving flow shop scheduling problems with probabilistic model-building genetic algorithms using edge histograms. In: Proc. of the 4th Asia-Pacific Conference on Simulated Evolution And Learning (SEAL02), 2002.
    77. Tsutsui, S. A comparative study of sampling methods in node histogram models with probabilistic model-building genetic algorithms. In: Systems, Man and Cybernetics, SMC’06. IEEE International Conference on. Vol. 4. IEEE, pp. 3132–3137, 2006.
    78. Tsutsui, S. Effect of using partial solutions in edge histogram sampling algorithms with different local searches. In: IEEE International Conference on Systems, Man and Cybernetics. IEEE, pp. 2137–2142, 2009.
    79. Tasgetiren, M., Liang, Y., Sevkli, M., Gencyilmaz, G. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research 177 (3), 1930–1947, 2007.
    80. Valente, J.M.S.; Alves, R.A.F.S. Heuristics for the early/tardy scheduling problem with release dates. Int. J. Prod. Econ. 106, 261–274, 2007.
    81. Valente, J.M.S.; Alves, R.A.F.S. Improved heuristics for the early/tardy scheduling problem with no idle time. Comput. Oper. Res. 32, 557–569, 2005.
    82. Wang, J., Cai, Y., Zhou, Y., Wang, R., Li, C. Discrete particle swarm optimization based on estimation of distribution for terminal assignment problems. Computers & Industrial Engineering 60 (4), 566–575, 2011.
    83. Wu, S.D.; Storer, R.H.; Chang, P.C. One-machine rescheduling heuristics with efficiency and stability as criteria. Comput. Oper. Res. 20, 1–14, 1993.
    84. Zhang, Q., Muhlenbein, H. On the convergence of a class of estimation of distribution algorithms. Evolutionary Computation, IEEE Transactions on 8 (2), 127–136, 2004.
    85. Zhang, J., Szeto, K. Y. Mutation matrix in evolutionary computation: An application to resource allocation problem. Lecture Notes in Computer Science 3612, 112–119, 2005.
    86. Zhang, Q., Sun, J., Tsang, E. An Evolutionary Algorithm With Guided Mutation for the Maximum Clique Problem. Evolutionary Computation, IEEE Transactions on 9 (2), 192–200, 2005.
    87. Zhang, Y., Li, X. Estimation of distribution algorithm for permutation flow shops with total flowtime minimization. Computers & Industrial Engineering 60 (4), 706–718, 2011.
    88. Zhou, A., Zhang, Q., Jin, Y., Tsang, E., Okabe, T. A model-based evolutionary algorithm for bi-objective optimization. Vol. 3. pp. 2568–2575, 2005.

    無法下載圖示 校內：2015-01-10公開
    校外：不公開
    電子論文尚未授權公開，紙本請查館藏目錄
    QR CODE