簡易檢索 / 詳目顯示

回結果列表
研究生： 郭奕宏
I-Hong Kuo
論文名稱： 粒子群最佳化及其應用
Particle Swarm Optimization and Its Applications
指導教授： 洪西進
Shi-Jinn Horng
口試委員: 李祖添
none
陳健輝
none
鐘嘉德
none
郭耀煌
none
學位類別： 博士
Doctor
系所名稱： 電資學院 - 電機工程系
Department of Electrical Engineering
論文出版年： 2009
畢業學年度： 97
語文別： 英文
論文頁數： 119
中文關鍵詞： 粒子群最佳化 、基因演算法 、旅行推銷員問題 、流水型工廠排程問題 、模糊時間序列 、預測
外文關鍵詞： Particle Swarm Optimization, Genetic Algorithm, Traveling Salesman Problem, Flow-Shop Scheduling Problem, Fuzzy Time Series, Forecasting
相關次數： 點閱：328  下載：14 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 在本論文中我們發展了數種混合式粒子群最佳化演算法來解決旅行推銷員問題，流水型工廠排程問題，以及預測問題。實驗結果證明我們所發展的演算法非常有效。
    旅行推銷員問題的目的是去找到一條最短路徑，使得推銷員可以從一個城市出發，然後經過其它城市各一次，最後再回到出發的城市。在本論文中我們發展了一個由粒子群最佳化演算法以及基因演算法組合而成的混合式群體智慧演算法來解決旅行推銷員問題。我們的實驗結果證明這個混合式群體智慧演算法的求解能力優於粒子群最佳化演算法及基因演算法。
    流水型工廠排程問題在過去幾十年中已經吸引了許多研究者的注意。此問題的目的是在於找到一組最佳工作排程次序，使得完成所有工作的總花費時間為最小。在本論文中我們發展了兩個混合式粒子群演算法來解決流水型工廠排程問題。實驗結果證明我們所發展的演算法優於目前其它已存在的群體智慧方法。
    最後，在本論文中我們發展了兩個基於粒子群最佳化演算法及模糊時間序列的混合式預測模型來解決預測問題，以提高預測準確率。區間的數目以及建立的模糊規則是影響預測準確率的兩大因素，因此已經有一些演算法結合了經驗法則或演化法則來調整此二因素，但是它們的效果仍未令人滿意。在本論文中我們使用粒子群最佳化演算法來將此二因素調整到最佳值。我們使用的預測問題包括入學人數預測問題，小麥產量預測問題，台股指數預測問題，農產量預測問題，及台股指數期貨預測問題。由實驗結果證明我們所提出的新模型優於其它已存在的模糊預測模型。

    In this thesis we present several hybrid particle swarm optimization algorithms to solve the traveling salesman problem, the flow-shop scheduling problem and the forecasting problems respectively. The experimental results show that the proposed algorithms are very efficient and effective.
    The objective of the traveling salesman problem is to find a shortest tour that starts from a city, visits every city once, and finally comes back to the start city. A hybrid swarm intelligence algorithm consists of the random-key search method, the individual enhancement scheme, particle swarm optimization, and genetic algorithm is proposed for the traveling salesman problem in this thesis. By the random-key search method, we can exploit the global search ability of particle swarm optimization thoroughly. By the genetic algorithm, we can expand the exploring area of individuals in the solution space. By the individual enhancement scheme, we can enhance the search ability of particle and chromosome. Based on the proposed hybrid scheme, we can improve the solution quality quite a few. Our experimental results show that the proposed hybrid swarm intelligence algorithm outperforms particle swarm optimization and genetic algorithm in solution quality.
    The flow-shop scheduling problem has got much attention from many researchers in the past decades. The objective of it is to find an appropriate sequence of jobs in order to minimize the maximum completion time (so called makespan) of executing all jobs by a predefined machine order. Two new hybrid particle swarm optimization algorithms are proposed in this thesis to solve the flow-shop scheduling problem. The experimental results show that the proposed algorithms are more efficient than the existing meta-heuristics methods based on similar particle swarm optimization and genetic algorithms, respectively.
    For the forecasting problems, two new hybrid forecast models combined particle swarm optimization with fuzzy time series are proposed to improve the forecasted accuracy respectively. The lengths of intervals and the content of forecast rules are two main factors to impact the forecasted accuracy of the forecast models created based on the fuzzy time series. How to find the suitable main factors to improve the forecasted accuracy has become an interesting research topic recently. Some fuzzy forecast models combined heuristic methods or evolutionary algorithms (such as genetic algorithms and simulated annealing) with the fuzzy time series have been proposed but their results are not satisfied. In this thesis, first we use the particle swarm optimization to find the best main factors. Then the experimental results of the forecasting problems including enrollments forecasting, wheat production forecasting, TAIEX forecasting, crop production forecasting, and TAIFEX forecasting show that the new proposed models are better than any existing fuzzy forecast models under both the first-order and the high-order fuzzy time series respectively and are more precise than four famous statistic forecast models even when historical data of the forecasting problem are highly vibration.

    論文摘要 ………………………………………………………………… I Abstract ………………………………………………………………….. III List of Figures …………………………………………………………………… IX List of Tables ……………………………………………………………………. X Chapter 1 Introduction …………………………………………………………… 1 Chapter 2 Particle Swarm Optimization …………………………………………. 6 2.1 The standard particle swarm optimization ……………………………………. 6 2.2 The modified particle swarm optimization …………………………………… 7 Chapter 3 A new hybrid swarm intelligence algorithm for the traveling salesperson problem ……………………………………………………………….. 10 3.1 The definition of the traveling salesperson problem …………………………. 10 3.2 HRKPG Model ……………………………………………………………….. 10 3.2.1 Representing an individual …………………………………………………. 11 3.2.2 IE Individual Enhancement Scheme ……………………………………….. 12 3.2.3 PSO Component ……………………………………………………………. 13 3.2.4 GA Component …………………………………………………………….. 15 3.2.5 The algorithm of HRKPG model ………………………………………….. 18 3.3 Experimental Results ………………………………………………………… 20 Chapter 4 Two new efficient flow-shop scheduling algorithms ……………....... 23 4.1 The definition of flow-shop scheduling problem ……………………………. 23 4.2 The proposed HPSO-1 Algorithm …………………………………………… 24 4.2.1 RK encoding scheme ……………………………………………………… 25 4.2.2 Representation of Individual ……………………………………………… 25 4.2.3 Individual Enhancement Scheme …………………………………………. 26 4.2.4 The whole HPSO-1 algorithm ………………………………………………. 28 4.2.5 Experimental Results of the HPSO-1 Algorithm …………………………… 29 4.3 The proposed HPSO-2 Algorithm ……………………………………………. 34 4.3.1 The hybrid local search scheme ……………………………………………. 34 4.3.2 The whole HPSO-2 algorithm ……………………………………………… 39 4.3.3 Experimental results of the HPSO-2 algorithm ……………………………. 40 Chapter 5 A new fuzzy forecasting method …………………………………….. 44 5.1 The definition of the fuzzy time series and the forecasting procedure based on it 45 5.2 The new proposed forecast model (named HPSO model) …………………… 58 5.3 Experimental Results of the HPSO model …………………………………… 64 5.3.1 Enrollments Forecasting Problem …………………………………………. 64 5.3.1.1 Experimental results for the training phase ……………………………… 64 5.3.1.2 Experimental results for the testing phase ………………………………. 68 5.3.2 The wheat production forecasting problem ……………………………….. 70 5.3.2.1 Experimental results for the training phase ……………………………... 70 5.3.2.2 Experimental results for the testing phase ……………………………… 72 5.3.3 TAIEX Forecasting Problem ……………………………………………… 75 5.3.3.1 Experimental results for the training phase …………………………….. 75 5.3.3.2 Experimental results for the testing phase ……………………………… 77 Chapter 6 An improved fuzzy forecasting method ……………………………. 80 6.1 The improved forecasting procedure ………………………………………. 80 6.2 The improved forecast model (named NPSO model) ……………………… 91 6.3 Experimental results of the NPSO model …………………………………. 97 6.3.1 The lahi production forecasting problem ………………………………… 97 6.3.1.1 Experimental results for the training phase …………………………… 98 6.3.1.2 Experimental results for the testing phase ……………………………. 99 6.3.2 The wheat production forecasting problem ………………………………. 101 6.3.2.1 Experimental results for the training phase ……………………………. 101 6.3.2.2 Experimental results for the testing phase …………………………….. 103 6.3.3 The TAIFEX forecasting problem ………………………………………. 105 6.3.3.1 Experimental results for the training phase …………………………… 106 6.3.3.2 Experimental results for the testing phase …………………………….. 108 Chapter 7 Conclusions ………………………………………………………... 111 References ……………………………………………………………………... 114

    [1]B. D. Backer, V. Furnon, P. Shaw, P. Kilby, and P. Prosser, "Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics," Journal of Heuristics, vol. 6, pp. 501-523, 2000.
    [2]H. G. Campbell, R. A. Dudek, and M. L. Smith, "A heuristic algorithm for the n-job, M-machine sequencing problem," Management Science, vol. 16, pp. 630-637, 1970.
    [3]V. Cerny, "Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm," Journal of Optimization Theory and Applications, vol. 45, pp. 41-51, 1985.
    [4]S.-M. Chen, "Forecasting enrollments based on fuzzy time series," Fuzzy Sets and Systems, vol. 81, pp. 311-319, 1996.
    [5]S.-M. Chen, "Forecasting enrollments based on high-order fuzzy time series," Cybernetics and Systems, vol. 33, pp. 1-16, 2002.
    [6]S.-M. Chen and N.-Y. Chung, "Forecasting Enrollments of Students by Using Fuzzy Time Series and Genetic Algorithms," International Journal of Information and Management Sciences, vol. 17, pp. 1-17, 2006.
    [7]S.-M. Chen and N.-Y. Chung, "Forecasting enrollments using high-order fuzzy time series and genetic algorithms: Research Articles," International Journal of Intelligent Systems, vol. 21, pp. 485-501, 2006.
    [8]C. A. C. Coello and N. C. Cortes, "Hybridizing a genetic algorithm with an artificial immune system for global optimization," Engineering Optimization, vol. 36, pp. 607-634, 2004.
    [9]M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem," IEEE Transactions on Evolutionary Computation, vol. 1, pp. 53-66, 1997.
    [10]Z. Ezziane, "Applications of artificial intelligence in bioinformatics: A review," Expert Systems with Applications, vol. 30, pp. 2-10, 2006.
    [11]H.-M. Feng, C.-Y. Chen, and F. Ye, "Evolutionary fuzzy particle swarm optimization vector quantization learning scheme in image compression," Expert Systems with Applications, vol. 32, pp. 213-222, 2007.
    [12]S. Feng and L. D. Xu, "Hybrid artificial intelligence approach to urban planning," Expert Systems: The International Journal of Knowledge Engineering and Neural Networks, vol. 16, pp. 248-261, 1999.
    [13]M. Garey, D. Johnson, and R. Sethi, "The complexity of flowshop and jobshop scheduling," Mathematics of Operations Research, vol. 1, pp. 117-129, 1976.
    [14]D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning: Addison-Wesley Longman Publishing Co., Inc., 1989.
    [15]J. J. Grefenstette, R. Gopal, B. J. Rosmaita, and D. V. Gucht, "Genetic Algorithms for the Traveling Salesman Problem " presented at Proceedings of the 1st International Conference on Genetic Algorithms, 1985.
    [16]Q. He, L. Wang, and B. Liu, "Parameter estimation for chaotic systems by particle swarm optimization," Chaos, Solitons & Fractals, vol. 34, pp. 654-661, 2007.
    [17]M. Held and R. M. Karp, "The traveling salesman problem and minimum spanning trees," Operations Research, vol. 18, pp. 1138-1162, 1970.
    [18]J. M. Holland, Adaptation in Natural and Artificial Systems: University of Michigan Press, Ann Arbor, 1975.
    [19]K. Huarng, "Heuristic models of fuzzy time series for forecasting," Fuzzy Sets and Systems, vol. 123, pp. 369-386, 2001.
    [20]K. Huarng, "Effective lengths of intervals to improve forecasting in fuzzy time series," Fuzzy Sets and Systems, vol. 123, pp. 387-394, 2001.
    [21]K. Huarng and H.-K. Yu, "A dynamic approach to adjusting lengths of intervals in fuzzy time series forecasting," Intelligent Data Analysis, vol. 8, pp. 3-27, 2004.
    [22]K. Huarng and H.-K. Yu, "A Type 2 fuzzy time series model for stock index forecasting," Physica A: Statistical Mechanics and its Applications, vol. 353, pp. 445-462, 2005.
    [23]J.-R. Hwang, S.-M. Chen, and C.-H. Lee, "Handling forecasting problems using fuzzy time series," Fuzzy Sets and Systems, vol. 100, pp. 217-228, 1998.
    [24]B. Jarboui, S. Ibrahim, P. Siarry, and A. Rebai, "A combinatorial particle swarm optimisation for solving permutation flowshop problems," Computers & Industrial Engineering, vol. 54, pp. 526-538, 2008.
    [25]S. M. Johnson, "Optimal two- and three-stage production schedules with setup times included," Naval Research Logistics Quarterly, vol. 1, pp. 61-68, 1954.
    [26]B. A. Julstrom, "Very greedy crossover in a genetic algorithm for the traveling salesman problem," presented at Proceedings of the 1995 ACM symposium on Applied computing, 1995.
    [27]J. Kennedy and R. Eberhart, "Particle Swarm Optimization," Proceedings of IEEE international Conference on Neural Network, pp. 1942-1948, 1995.
    [28]J. Kennedy, R. C. Eberhart, and Y. Shi, Swarm intelligence: Morgan Kaufmann Publishers, 2001.
    [29]S. L. a. B. W. Kernighan, "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, vol. 21, pp. 498-516, 1973.
    [30]I.-H. Kuo, S.-J. Horng, T.-W. Kao, T.-L. Lin, C.-L. Lee, Y.-H. Chen, Y. Pan, and T. Takao, "A hybrid swarm intelligence algorithm for the traveling salesman problem," Expert Systems: The International Journal of Knowledge Engineering and Neural Networks, vol. In Press.
    [31]I.-H. Kuo, S.-J. Horng, T.-W. Kao, T.-L. Lin, and P. Fan, "An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model," Lecture Notes in Artificial Intelligence, vol. 4570, pp. 303-312, 2007.
    [32]I. H. Kuo, S.-J. Horng, T.-W. Kao, T.-L. Lin, C.-L. Lee, and Y. Pan, "An improved method for forecasting enrollments based on fuzzy time series and particle swarm optimization," Expert Systems with Applications, vol. In Press, Corrected Proof, doi:10.1016/j.eswa.2008.07.043.
    [33]I. H. Kuo, S.-J. Horng, T.-W. Kao, T.-L. Lin, C.-L. Lee, T. Terano, and Y. Pan, "An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model," Expert Systems with Applications, vol. In Press, Corrected Proof, doi:10.1016/j.eswa.2008.08.054.
    [34]L.-W. Lee, L.-H. Wang, and S.-M. Chen, "Temperature prediction and TAIFEX forecasting based on fuzzy logical relationships and genetic algorithms," Expert Systems with Applications, vol. 33, pp. 539-550, 2007.
    [35]L.-W. Lee, L.-H. Wang, and S.-M. Chen, "Temperature prediction and TAIFEX forecasting based on high-order fuzzy logical relationships and genetic simulated annealing techniques," Expert Systems with Applications, vol. 34, pp. 328-336, 2008.
    [36]L. W. Lee, L. H. Wang, S. M. Chen, and Y. H. Leu, "Handling forecasting problems based on two-factors high-order fuzzy time series," IEEE Transactions on Fuzzy Systems, vol. 14, pp. 468-477, 2006.
    [37]H. X. Li and L. X. Li, "Representing diverse mathematical problems using neural networks in hybrid intelligent systems," Expert Systems: The International Journal of Knowledge Engineering and Neural Networks, vol. 16, pp. 262-272, 1999.
    [38]L.-l. Li, L. Wang, and L.-h. Liu, "An effective hybrid PSOSA strategy for optimization and its application to parameter estimation," Applied Mathematics and Computation, vol. 179, pp. 135-146, 2006.
    [39]S.-T. Li and Y.-C. Cheng, "Deterministic fuzzy time series model for forecasting enrollments," Computers & Mathematics with Applications, vol. 53, pp. 1904-1920, 2007.
    [40]Z. Lian, X. Gu, and B. Jiao, "A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan," Chaos, Solitons & Fractals, vol. 35, pp. 851-861, 2008.
    [41]H.-T. Liu, "An improved fuzzy time series forecasting method using trapezoidal fuzzy numbers," Fuzzy Optimization and Decision Making, vol. 6, pp. 63-80, 2007.
    [42]H. S. Lope and L. S. Coelho, "Particle Swarm Optimization with Fast Local Search for the Blind Traveling Salesman Problem," Fifth International Conference on Hybrid Intelligent Systems, pp. 245-250, 2005.
    [43]N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, "Equation of state calculation by fast computing machines," Journal of Chemical Physics, vol. 21, pp. 1087-1092, 1953.
    [44]M. Nawaz, E. E. Enscore, and I. Ham, "A heuristic algorithm for the m-Machine, n-Job flow shop sequencing problem," OMEGA, vol. 11, pp. 91-95, 1983.
    [45]F. A. Ogbu and D. K. Smith, "The application of the simulated annealing algorithm to the solution of the n/m/Cmax flow shop problem," Computers & Operations Research, vol. 17, pp. 243-253, 1990.
    [46]M. Padberg and G. Rinaldi, "A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems," SIAM Review, vol. 33, pp. 60-100, 1991.
    [47]D. S. Palmer, "Sequencing jobs through a multi-stage procrss in the minimun total time- A quick method of obtaining a near optimun," Operational Research Quarterly, vol. 16, pp. 101-107, 1965.
    [48]W. Pang, K. P. Wang, C. G. Zhou, L. J. Dong, M. Liu, H. Y. Zhang, and J. Y. Wang, "Modified particle swarm optimization based on space transformation for solving traveling salesman problem," Proceedings of International Conference on Machine Learning and Cybernetics, vol. 4, pp. 2342-2346, 2004.
    [49]A. Ratnaweera, S. K. Halgamuge, and H. C. Watson, "Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients," IEEE Transactions on Evolutionary Computation, vol. 8, pp. 240-255, 2004.
    [50]C. R. Reeves, "A genetic algorithm for flow shop sequencing," Computer Operational Research, vol. 22, pp. 5-13, 1995.
    [51]G. Reinelt, "TSPLIB - a Traveling Salesman Problem Library," ORSA Journal on Computing, vol. 3, pp. 376-384, 1991.
    [52]X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu, and L. M. Wang, "An improved GA and a novel PSO-GA-based hybrid algorithm," Information Processing Letters, vol. 93, pp. 255-261, 2005.
    [53]X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu, and Q. X. Wang, "Particle swarm optimization-based algorithms for TSP and generalized TSP," Information Processing Letters, vol. 103, pp. 169-176, 2007.
    [54]Y. Shi and R. C. Eberhart, "Empirical study of particle swarm optimization," Proceedings of the Congress on Evolutionary Computation, pp. 1945-1950, 1999.
    [55]S. R. Singh, "A computational method of forecasting based on fuzzy time series," Mathematics and Computers in Simulation, vol. In Press, Corrected Proof, doi:10.1016/j.matcom.2008.02.026.
    [56]S. R. Singh, "A simple method of forecasting based on fuzzy time series," Applied Mathematics and Computation, vol. 186, pp. 330-339, 2007.
    [57]S. R. Singh, "A robust method of forecasting based on fuzzy time series," Applied Mathematics and Computation, vol. 188, pp. 472-484, 2007.
    [58]Q. Song and B. S. Chissom, "Forecasting enrollments with fuzzy time series -- Part I," Fuzzy Sets and Systems, vol. 54, pp. 1-9, 1993.
    [59]Q. Song and B. S. Chissom, "Fuzzy time series and its models," Fuzzy Sets and Systems, vol. 54, pp. 269-277, 1993.
    [60]Q. Song and B. S. Chissom, "Forecasting enrollments with fuzzy time series -- part II," Fuzzy Sets and Systems, vol. 62, pp. 1-8, 1994.
    [61]E. Taillard, "Some efficient heuristic methods for the flow shop scheduling problem," European Journal of Operational Research, vol. 47, pp. 65-74, 1990.
    [62]E. Taillard, "Benchmarks for basic scheduling problems," European Journal of Operational Research, vol. 64, pp. 278-285, 1993.
    [63]M. F. Tasgetiren, Y.-C. Liang, M. Sevkli, and G. Gencyilmaz, "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem," European Journal of Operational Research, vol. 177, pp. 1930-1947, 2007.
    [64]C.-H. Yang and K. E. Nygard, "The effects of initial population in genetic search for time constrained traveling salesman problems," presented at Proceedings of the 1993 ACM conference on Computer science 1993.
    [65]A. R. Yildiz, "A novel particle swarm optimization approach for product design and manufacturing," The International Journal of Advanced Manufacturing Technology, vol. In Press, DOI:10.1007/s00170-008-1453-1.
    [66]A. R. Yildiz, "A novel hybrid immune algorithm for global optimization in design and manufacturing," Robotics and Computer-Integrated Manufacturing, vol. In Press, Corrected Proof, doi:10.1016/j.rcim.2007.08.002.
    [67]A. R. Yildiz and F. Ozturk, "Hybrid enhanced genetic algorithm to select optimal machining parameters in turning operation," Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, vol. 220, pp. 2041-2053, 2006.
    [68]A. R. Yildiz, N. Ozturk, N. Kaya, and F. Ozturk, "Hybrid multi-objective shape design optimization using Taguch's method and genetic algorithm," Structural and Multidisciplinary Optimization, vol. 34, pp. 277-365, 2007.
    [69]H.-K. Yu, "A refined fuzzy time-series model for forecasting," Physica A: Statistical and Theoretical Physics, vol. 346, pp. 657-681, 2005.
    [70]H.-K. Yu, "Weighted fuzzy time series models for TAIEX forecasting," Physica A: Statistical and Theoretical Physics, vol. 349, pp. 609-624, 2005.
    [71]T. H.-K. Yu and K.-H. Huarng, "A bivariate fuzzy time series model to forecast the TAIEX," Expert Systems with Applications, vol. 34, pp. 2945-2952, 2008.
    [72]X. H. Zhi, X. L. Xing, Q. X. Wang, L. H. Zhang, X. W. Yang, C. G. Zhou, and Y. C. Liang, "A discrete PSO method for generalized TSP problem," Proceedings of International Conference on Machine Learning and Cybernetics, vol. 4, pp. 2378-2383, 2004.

    QR CODE