Title

整合免疫遺傳演算法與向量式粒子群最佳化演算法於二階線性規劃問題之研究-以供應鏈之配銷模型為例

Translated Titles

Integration of Immune Genetic Algorithm and Vector-Controlled Particle Swarm Optimization for Bi-level Linear Programming Problems- A Case Study on Supply Chain Distribution Model

Authors

李永濠

Key Words

免疫遺傳演算法 ; 粒子群最佳化演算法 ; 二階線性規劃 ; 供應鏈 ; IGA ; PSO ; Bi-level linear programming ; Supply chain

PublicationName

臺北科技大學工業工程與管理系碩士班學位論文

Volume or Term/Year and Month of Publication

2009年

Academic Degree Category

碩士

Advisor

田方治;郭人介

Content Language

繁體中文

Chinese Abstract

隨著資訊技術的蓬勃發展,溝通與資訊交流的距離已經走向全球化。若是企業經營模式可以擁有良好的配銷管理讓供應鏈流程更加流暢、成本的降低,那最終的利潤以及績效都會有相當大的提升。基於以上的原因,本研究透過二階規劃技術模擬了供應鏈中也具有分層式以及資訊分享性的特性,再將供應鏈中配銷模式各階的目標以數學模式套入目標函數中進行規劃,試圖找出最佳的配銷系統。 本研究提出了一種改良式演算法,它整合了遺傳演算法以及向量式粒子群最佳化演算法的特性,提出了Immune Genetic Vector-Controlled Particle Swarm Optimization Algorithm (IGVPSO) 演算法。並透過不同配銷模式的供應鏈模型來進行驗證的動作。求解的結果證明了所提出的改良式演算法的精確性即穩定性皆優於傳統的遺傳演算法、粒子群最佳化演算法,以及韓永祥 (2008) 所提出的GAPSO演算法。

English Abstract

With the rapid development of information technology, communication and information is moving toward globalization. If the business model could have a good management of supply chain management to make the flow more smooth and reduce the costs, the profit and performance will have a considerable improvement. Based on the above reasons, this research utilized bi-level linear programming technique to simulate the hierarchical relationship and information sharing between upper and lower levels of supply chain by transforming each level's objective of the supply chain into the mathematical model's objective function in order to determine the best distribution model. This research also proposes a hybrid method which integrates the characteristic of immune genetic algorithm (IGA) and the vector-controlled particle swarm optimization algorithm. The proposed method is called Immune Genetic Vector-Controlled Particle Swarm Optimization Algorithm (IGVPSO). It is validated by using different distribution models. The results demonstrated that the modified algorithm is more accurate and stable than genetic algorithm, particle swarm optimization algorithm and GAPSO designed by Han (2008).

Topic Category 管理學院 > 工業工程與管理系碩士班
工程學 > 工程學總論
社會科學 > 管理學
Reference
  1. [4] 黃駿傑,應用粒子群最佳化求解二街線性規劃,國立台北科技大學工管所,碩士論文,台北,2007。
    連結:
  2. [5] 韓永祥,整合遺傳演算法與粒子群最佳化演算法於二階線性規劃問題之應用—以供應鏈之配銷模型為例,國立台北科技大學工管所,碩士論文,台北,2008。
    連結:
  3. [6] 闕仲輝,應用於工程最佳化之免疫演算法,大同大學機械工程研究所,博士論文,台北,2004。
    連結:
  4. [8] 鄭國村,整合粒子群最佳化與模擬退火法求解彈性零工式生產排程問題之研究,國立台北科技大學工管所,碩士論文,台北,2006。
    連結:
  5. [10] 葉麗雯,供應商產能有限及價格折扣下多產品多供應商最佳化採購決策,元智大學工業工程與管理學系,碩士論文,桃園,2002。
    連結:
  6. [14] Bard, J.F., “A branch and bound algorithm for the bi-level programming problem,” SIAM Journal of Scientific and Statistical Computing, Vol. 11, No. 2, 1990, pp. 281-292.
    連結:
  7. [16] Bard, J.F. and Falk J.E., “An explicit solution to the multi-level programming problem,” Computers and Operations Research, Vol. 9, No.1, 1982, pp. 77-100.
    連結:
  8. [17] Bialas, W.F. and Karwan, M.H., “On two-level optimization,” IEEE Trans. Automatic Control Vol. 26, No. 1, 1982, pp. 211–214.
    連結:
  9. [19] Cai, X., Zhang N., Venayagamoorthy G. and Wunsch D., “Time series prediction with recurrent neural networks using a hybrid PSO-EA algorithm,” Proceeding of the 2nd IEEE International Conference on Neural Networks, Budapest, 2004, pp. 1647-1652.
    連結:
  10. [20] Chiang, W.C., Fitzsimmons, J., Huang, Z. and Li, S.X., “A game-theoretic approach to quantity discount problems,” Decision Sciences, Vol. 25, No. 1, 1994, pp. 153–168.
    連結:
  11. [21] Christopher, M., Logistics and Supply Chain Management: Strategies for Reducing Costs and Improving Services, Pitman, London, 1992.
    連結:
  12. [22] Clerc, M., “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization”, Proceedings of the IEEE Congress on Evolutionary Compution, 1999, pp. 1951-1957.
    連結:
  13. [25] Dasci, A. and Verter, V., “A continuous model for production-distribution system design,” European Journal of Operational Research, Vol. 129, No. 2, 2001, pp.287-298.
    連結:
  14. [26] Dasgupta, D. and Okine, N.A., “Immunity-based systems: a survey,” Proceeding of the IEEE Transactions on Systems, Man and Cybernetics, Vol. 1, 1997, pp. 369-374.
    連結:
  15. [27] Du, S., Li, W., and Cao, K., “A learning algorithm of artificial neural network based on GA-PSO,” IEEE, Intelligent Control and Automation, WCICA. The Sixth World Congress, Vol. 1, 2006, pp. 3633-3637.
    連結:
  16. [29] Eberhart, R.C. and Kennedy, J., “A new optimizer using particle swarm theory,” Proceedings of the 6th International Symposium on Micro Machine and Human Science, Nagoya Japan, 1995, pp. 39-43.
    連結:
  17. [30] Eberhart, R. and Kennedy, J., “A discrete binary version of the particle swarm algorithm.” Proceedings of the IEEE International Conference on Systems, Vol 5, 1997, pp. 4104-4108.
    連結:
  18. [31] Eberhart, R.C. and Shi, Y., “Particle swarm optimization: Developments, applications and resources,” Proceedings of the IEEE Congress on Evolutionary Computatio, 2001, pp.81-86.
    連結:
  19. [32] Eberhart, R.C., and Shi, Y., “Particle swarm optimization: developments, application and resources,” Proceedings of the IEEE, Congress on Evolutionary Computation, Vol. 1, 2001, pp. 81 - 88.
    連結:
  20. [35] Eberhart, R.C. and Shi, Y., “Comparing inertia weights and constriction factors in particle swarm optimization,” Proceedings of the IEEE Congress on Evolutionary Computation, 2000, pp. 84-88.
    連結:
  21. [37] Fan, S.K.S. Liang, Y.C. and Zahara, E., “A genetic algorithm and a particle swarm optimizer hybridized with Nelder-Mead simplex search,” Computer and Industrial Engineering, Vol. 50, 2006, pp.401-425.
    連結:
  22. [39] Gudise, V.G. and Venayagamoorthy, G.K., “Comparison of particle swarm optimization and backpropagation as training algorithms for neural networks.” Proceeding of IEEE Swarm Intelligence Symposium, Indianapolis, Indiana, 2003, pp. 110-117.
    連結:
  23. [40] Guoyan, Y., Zhen, H., Chaoan, L. and Yanming, S., “An optimization design system with hybrid intelligence,” Fifth World Congress of Intelligent Control and Automation, Vol. 3, 2004, pp. 2790-2794.
    連結:
  24. [41] Harmer, P.K., Williams, P.D., Gumsch, H., and Laamont, B., “An artificial immune system architecture for computer security applications,” IEEE Transactions on Evolutionary Computation, Vol.6, No. 3, 2002, pp 252-279.
    連結:
  25. [43] Holland, J.H., Adaptation in natural and artificial systems, University of Michigan Press, Michigan, U.S, 1975.
    連結:
  26. [44] Hu, H., “PSO Tutorial,” Particle Swarm Optimization,
    連結:
  27. [45] Hunt, J.E. and Cooke, D.E., “Learning using an artificial immune system,” Journal of Network and Computer Applications, Vol. 19, 1996, pp. 189-212.
    連結:
  28. [47] Jeroslow, R.G. “The polynomial hierarchy and a simple model for competitive analysis,” Mathematical Programming Vol. 32 No. 2, 1985, pp. 146-164.
    連結:
  29. [50] Jose, B. Cruz, JR., “Leader-follower strategies for multilevel systems,” IEEE Transactions on Automatic Control, Vol. AC-23, No. 2, 1978, pp. 244-255.
    連結:
  30. [51] Juang, C.F, “A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design,” IEEE, Systems, Man, and Cybernetics, Part B, Vol. 34, No. 1, 2004, pp. 997-1006.
    連結:
  31. [52] Kalakota, R. and Robinson, M., E-Business: Roadmap for Success, U.S, Addison-Wesley Pub, Mass, 1999.
    連結:
  32. [53] Kao, Y.T. and Zahara, E., “A hybrid genetic algorithm and particle swarm optimization for multimodal functions,” Applied Soft Computing, Vol. 8, Issue 2, 2007, pp. 849-857.
    連結:
  33. [54] Keith, O. and Webber, M., Supply-Chain Management: Logistics catches up with strategy, London, The strategic issues, Chapman and Hall, 1992.
    連結:
  34. [55] Ko, C. N., Chang, Y. P., and Wu, C.J., “A PSO method with nonlinear time-varying evolution for optimal design of harmonic filters,” IEEE Transactions on Power Systems, Vol. 24, Issue 1, 2009, pp. 437-444.
    連結:
  35. [56] Koray, D., and Marc, G., “A primal decomposition method for the integrated design of multi-period production-distribution systems,” IIE Transactions, Vol. 31, No. 11, 1999, pp.1027-1036.
    連結:
  36. [58] Lin, C.J., “An efficient immune-based symbiotic particle swarm optimization learning algorithm for TSK-type Neuro-Fuzzy networks design,” Fuzzy Sets and Systems, Vol. 159, No. 21, 2008, pp.2890–2909.
    連結:
  37. [61] Liu, Y.H and Hart S.M., “Characterizing an optimal solution to the linear bi-level programming problem,” European Journal of Operational Research, Vol. 73, No. 1, 1994, pp.164-166.
    連結:
  38. [65] Melachrinoudis, E., and Min, H., “The dynamic relocation and phase-out of a hybrid, two-echelon plant/warehousing facility: a multiple objective approach,” European Journal of Operational Research, Vol. 123, Issue 1, 2000, pp. 1-15.
    連結:
  39. [66] Mersha, A.G., and Dempe, S., “Linear bilevel programming with upper level constraints depending on the lower level solution,” Applied Mathematics and Computation, Vol. 180, No. 1, 2006, pp. 247-254.
    連結:
  40. [70] Qie, H. and Wang, L., “A hybrid particle swarm optimization with a feasibility-based rule for constrained optimization,” Applied mathematics and computation vol. 186, No. 2, 2007, pp. 1407-1422.
    連結:
  41. [72] Ross, A.D., “Performance-based strategic resource allocation in supply networks,” International Journal of Production Economics, Vol. 63, No. 2, pp. 255-266, 2000.
    連結:
  42. [73] Salerno, J., “Using the particle swarm optimization technique to train a recurrent neural model,” Proceedings of the Ninth IEEE International Conference on Tools with Artificial Intelligence, 1997, pp. 45-49.
    連結:
  43. [74] Satapathy, S.C., Katari, V., Parimi, R., Malireddi, S., Srujan K.V.N.K., Misra B.B. and Murthy, J.V.R., “A new approach of integrating PSO and improved GA for clustering with parallel and transitional technique,” Proceedings of 3rd International Conference Natural Computation, ICNC, 2007, pp. 40-47.
    連結:
  44. [75] Shelokar, P.S., Partick Siarry, Jayaraman, V.K., and Kulkarni, B.D., “Particle swarm and ant colony algorithms hybridized for improved continuous optimization,” Applied Mathematic and Computation, Vol. 188, Issue 1, 2006, pp.129-142.
    連結:
  45. [76] Shi, C., Lu, J., Zhang, G., “An extended Kuhn-Tucker approach for linear bi-level programming,” Applied Mathematics and Computation, Vol. 162, No. 1, 2005, pp.51-63.
    連結:
  46. [77] Shi, X.H., Liang Y.C., Lee, H.P., Lu, C. and Wang, L.M., “An improved GA and a novel PSO-GA-based hybrid algorithm,” Information Processing Letters, Vol. 93, 2005, Issue 5, pp. 255-261.
    連結:
  47. [78] Shi, Y. and Eberhart, R., “Empirical study of particle swarm optimization,” Proceedings of Congress on Evolutionary Computation, Vol. 3, 1999, 1945-1950.
    連結:
  48. [80] Shih, H.S., Wen, U.P., Lee, E.S., Lan, K.M., and Hsiao, H.C., “A neural network approach to multiobjective and multilevel programming problems,” Computers Mathematic with Applications, Vol. 48, 2004, pp. 95-108.
    連結:
  49. [81] Stackelberg, H. V., Marktform und Gleichgewicht, Berlin, Springer, 1934.
    連結:
  50. [83] Strader, T.J., Lin, F.R. and Shaw, M.J., “The impact of information sharing on order fulfillment in divergent differentiation supply chains,” Journal of Global Information Management, Vol. 7, No. 1, 1998, pp.16-24.
    連結:
  51. [85] Taheri, S. A. and Calva, G., “Imitating the human immune system capabilities for multi-agent federation formation,” Proceedings of the IEEE International Symposium on Intelligent Control, 2001, pp. 25-30.
    連結:
  52. [86] Tazawa, I., Koakutsu, S. and Hirata, H., “An immunity based genetic algorithm and its application to the VLSI floor plan design problem”, Proceedings of the IEEE Conference on Evolutionary Computation, 1996, pp. 417–421.
    連結:
  53. [88] Wayne, F.B., and Mark, H.K., “On two-level optimization,” IEEE Transaction Automatic Control, Vol. 27, 1982, pp. 211-214.
    連結:
  54. [89] Wen, U.P. and Hsu, S.T., “Algorithms for solving integer two-level linear programming problem,” Computers and Operational Research, Vol. 17, No. 2, 1991, pp. 133-142.
    連結:
  55. [90] Wen, U.P., and Hsu, S.T, “Linear bi-level programming problem─ A review,” Journal of Operations Research Society, Vol. 42, No. 2, 1991, pp. 125-133.
    連結:
  56. [91] Wen, U.P. and Huang, A.D., “A simple Tabu Search method to solve the mixed-integer problem bi-level programming problem,” European Journal of Operational Research, Vol. 88, 1996, pp. 563-571.
    連結:
  57. [93] Zhou, S. and Chen, R., “A decision model for selecting participants in supply chain,” Journal of Shanghai University, Vol. 5, No. 4, 2001, pp. 341-344.
    連結:
  58. [1] 廖子銘,類免疫演算法於多目標最佳化問題之研究與應用,大同大學機械工程研究所,碩士論文,台北,2001。
  59. [2] 李秋賢,退貨政策下多次折扣存貨模式,中央大學工業管理研究所,碩士論文,桃園,2000。
  60. [3] 郭人介譯,供應鏈與物流管理─全球案例•本土觀點,台北:美商麥格羅•希爾,第4-25頁,2005。
  61. [7] 卓佳慧,結合退貨與獎勵機制下之最佳訂購定價政策,碩士論文,國立中央大學工管所,桃園,2004。
  62. [9] 蔡翠旭編譯,Charles C. Poirier and Stephen E. Reiter著,強勢供應鏈;Supply Chain Optimization,書華出版,1998。
  63. [11] 王立志,系統化運籌與供應鏈管理,滄海書局,第3-30頁,1999。
  64. [12] 王家隆,零售商之退貨與訂價模式,中央大學工業管理研究所,碩士論文,桃園,2000。
  65. [13] 楊思駿,應用免疫演算法於逆物流存貨模式之研究,南台科技大學工業管理研究所,碩士論文,台南,2006。
  66. [15] Bard J.F., “Practical bilevel optimization: algorithms and applications,” Kluwer Academic Publishers, Boston, 1998.
  67. [18] Bialas, W.F. and Karwan, M.H., “Two-level linear programming,” Management Science, Vol. 30, No. 8, 1984, pp. 1004-1020.
  68. [23] Cooper, M.C., Gardner, J.H. and Noordewier, T.G., “Understanding shipper-carrierand shipper-warehouser relationships: partnerships revistited,” Journal of Business Logistics, Vol. 15, No. 2, 1994, pp. 30-32.
  69. [24] Cox, A., “Pro-Activity, value engineering and strategic procurement management: An entrepreneurial contractual model for the firm,” Proceedings of 1st Worldwide Research Symposium on Purchasing and Supply Chain Management, 1995, pp. 72–89.
  70. [28] Eberhart, R.C. and Kennedy, J., “Particle swarm optimization,” Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia, 1995, pp. 1942-1948.
  71. [33] Eberhart, R.C. and Shi, Y., “A modified particle swarm optimizer,” Proceedings of the IEEE International Conference on Evolutionary Computation, Piscataway, 1998, pp.69-73.
  72. [34] Eberhart, R.C. and Shi, Y., “Parameter selection in particle swarm optimization,” Evolutionary Programming VII: Proceedings of the Seventh Annual Conference on Evolutionary Programming, 1998, pp. 591-600.
  73. [36] Ellram, L.M., “Supply chain management,” International Journal of Physical Distribution and Logistics Management, Vol. 21, Issue 1, 1991, pp. 13-33.
  74. [38] Frazelle, E.H., “Plan on these trends,” Transportation and Distribution, Vol. 39, Issue 12, 1998, pp. 4.
  75. [42] Hejazi, S.R., Memariani, A., Jahanshahloo, G., and Sepehri, M.M., “Linear bi-level programming solution by genetic algorithm,” Computers and Operations research, Vol. 29, 2002, pp. 1913-1925.
  76. http://www.swarmintelligence.org/index.php, 2003.
  77. [46] Jerne, N.K., “Towards a network theory of the immune system,” Annals of Immunology, Vol. 125C, Issue 1-2, 1973, pp. 373-389.
  78. [48] Jiao, L. and L. Wang, “Novel genetic algorithm based on Immunity,” IEEE Proceeding of the IEEE Transactions on Systems, Man and Cybernetics, Vol. 30, No. 5, 2000, pp. 552-561.
  79. [49] Johnson, J.C and Wood, D.J "Contemporary Logistics ", Prentice-Hall, Upper Saddle Creek, New Jersey, 1996.
  80. [57] Langley, C.J. and Holcomb M.C., “Creating logistics customer value,” Journal of Business Logistics, Vol. 13, No. 2, 1992, pp. 1-27.
  81. [59] Ling, C., Wee, S., Yu, Z.L. and Rahardja, S., “An improved genetic algorithm for aperiodic array synthesis” Proceedings of IEEE International Acoustics, Speech and Signal Processing, 2008, pp.2465-2468.
  82. [60] Liu, D.K., Kwok, N.M., Fang, G., and Ha, Q.P., “An enhanced particle swarm optimization algorithm for multi-modal functions,” Proceedings of the IEEE International Conference on Mechatronics and Automation, Harbin, Heilongjiang, China, 2007, pp. 457-462.
  83. [62] Luce, R., and Raiffa, H., Game and Decisions, New York: Wiley, 1957.
  84. [63] Luo, X. and Wei, W., “Discussion on the convergence rate of immune genetic algorithm,” Proceedings of the World Congress on Intelligent Control and Automation Vol. 3, 2004, pp. 2275-2278.
  85. [64] Marcos, B., Scott, D. and Vince, C., “The globalization of logistics,” Manufacturing System, Vol. 16, Issue 2, 1999, pp.132-141.
  86. [67] Oduguwa, V. and Roy, R., “Multi-objective optimisation of rolling rod product design using meta-modelling approach,” Proceedings of The Genetic and Evolutionary Computation Conference, 2002, pp. 1164-1171.
  87. [68] Oliver, K. R. and Webber, M. D., “Supply-chain management: logistics catches up with strategy,” Logistics. The Strategic Issues, Chapman and Hall, London, (reprint), 1982, pp.63-75.
  88. [69] Pang, W. and Wang, K.P., Huang, L., Zhou C.G., “Particle swarm optimization for traveling salesman problem,” Proceedings of the Second International Conference on Machine Learning and Cybernetics, 2003, pp.1583-1585.
  89. [71] Robeson, J.F., Copacino, W.C. and Howe, R.E., The Logistics Handbook, Andersen Consulting, Macmillam, New York, 1994.
  90. [79] Shih, H.S., Lai Y.J., and Lee, E.S., “Fuzzy approach for multi-level programming problems,” Computers and Operation Researches, Vol. 23, No.1, 1996, pp.73-91.
  91. [82] Stevens, G., “Integrating the supply chain,” International Journal of Physical Distribution and Materials Management, Vol. 19, No. 8, 1989, pp. 3-8.
  92. [84] Sue, A.H., “Network design in supply chain management,” International Journal of Agile Management Systems, Vol. 1, No. 2, 1999, pp.99-106.
  93. [87] Wang, G.M., Wang, X.J., Wan, Z.P, and Chen, Y.L, “Genetic Algorithms for Solving Linear Bilevel Programming,” Proceedings of the IEEE Sixth international Conference on Parallel and Distributed Computing, 2005, pp. 920-924.
  94. [92] Weng, W.T. and Wen, U.P., “A primal-dual interior point algorithm for solving bi-level programming problem,” Asia-Pacific Journal of Operational Research, Vol. 17, 2000, pp. 213-231.