臺灣博碩士論文加值系統

摘 要

利用生物群體智慧所衍生出的啟發式演算技術，在求解最佳化問題上，以不同概念不斷地推陳出新，演算策略朝效益更好、效率更佳的方向改善；另一方面也要求演算法能適用於不同領域、不同性質的問題上。對此，本研究應用粒子群演算法中粒子族群具有探測(Exploration)與開發(Exploitation)的特質，於工程結構設計及組合最佳化問題之兩種不同性質問題上。
在工程結構設計方面，先針對粒子群演算法的相關參數做一系列的測試及探討，試圖找出粒子群演算法參數的相互關係及應用特性，再者，加入懲罰函數方法處理有限制條件，並利用網路拓撲的概念來改良粒子族群相互連繫的行為模式，處理有限制條件的工程結構設計問題，測試結果顯示粒子群算法不僅能有效地搜尋到問題最佳解且具有相當不錯的計算效率。而在組合最佳化問題中，零工式生產排程問題在生產管理方面是個相當複雜且重要的問題，也是屬於NP-hard問題；本文利用粒子族群的共同性(Nomothetic)及異質性(Idiographic)，提出群集合式概念的粒子群演算法，並於其標竿測試問題上，探討此粒子群演算法對於零工式排程的搜尋成效。

Abstract

For the global optimization problems, heuristic algorithms based on the bio-swarm intelligence recently have been developing and their search strategies are also driven to be more efficiency so such that different concepts and methodologies have developed to deal with different problems. In this regard, the particle swarm optimization (PSO) with characteristics of exploration and exploitation is proposed to deal with problems of structural designs and combinatorial optimization.
For the structural design problems, a series of testing problems and their discussions are carried out for the suitable ranges of parameters and relation of parameters and their further application can be clearly identified. Besides, the penalty function is introduced for the constraint conditions and the network topology concept is also used to improve the modeling of the particle swarm behaviors especially for the structural design problems. It is found that the PSO with the network topology can not only make the search quickly convergent to the global optimum for each structural design problem but also have better efficiency than several other algorithms. As known, the job-shop scheduling problem, the NP-hard combinatorial problem, is usually encountered for the production management. Based on the nomothetic and idiographic characteristics of the particle swarm, the PSO with the set concept is developed and then to examine several benchmark examples of job-shop scheduling. Test results show that the proposed algorithm can effectively handle such problems.

目 錄
中文摘要 I
英文摘要 II
目 錄 III
圖目錄 V
表目錄 VII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 文獻回顧 2
1.3 研究目的 7
1.4 論文架構與流程 8
第二章 粒子群演算法 11
2.1 粒子群演算法簡介 11
2.2 PSO模式 12
2.3 鄰域型PSO(Neighborhood PSO)17
2.4 群集合模式PSO(Set PSO) 20
第三章 工程結構設計問題之應用 25
3.1 PSO的測試問題描述 25
3.2 PSO參數於無限制問題搜尋之影響測試與討論 27
3.3 NPSO於工程結構設計之應用 39
3.4 結果討論 55
第四章 零工式生產排程之應用 57
4.1 零工式生產排程系統 57
4.2 系統模型 60
4.3 SPSO於JSP問題之測試與討論 67
4.4 績效評估 78
第五章 結論及未來展望 80
5.1 結論 80
5.2 未來展望 82
參考文獻 84
附錄一 91
附錄二 94

圖目錄
圖1-1 論文總體架構圖 10
圖2-1 粒子速度與位置搜尋示意圖 13
圖2-2 粒子群演算法流程圖 15
圖2-3 模擬粒子搜尋過程示意圖 16
圖2-4 粒子間相互連繫示意圖 18
圖2-5 鄰域型搜尋策略 19
圖3-1 f6函數測試學習因子之成功率等高線圖 31
圖3-2 f7函數測試學習因子之成功率等高線圖 31
圖3-3 f9函數測試學習因子之成功率等高線圖 32
圖3-4 f10函數測試學習因子之成功率等高線圖 32
圖3-5 f6函數測試學習因子之平均世代數等高線圖 33
圖3-6 f7函數測試學習因子之平均世代數等高線圖 33
圖3-7 f9函數測試學習因子之平均世代數等高線圖 34
圖3-8 f10函數測試學習因子之平均世代數等高線圖 34
圖3-9 環狀鄰域型搜尋策略 41
圖3-10 格架結構示意圖 41
圖3-11 格架結構搜尋世代圖 45
圖3-12 壓力容器問題示意圖 46
圖3-13 壓力容器搜尋世代圖 48
圖3-14 懸臂樑問題示意圖 50
圖3-15 懸臂樑問題搜尋世代圖 53
圖4-1 SPSO於零工式生產排程系統之流程圖 62
圖4-2 3工作 3機器所對應的工作順序以及作業機器 63
圖4-3 3工作 3機器未調整前之甘特圖 63
圖4-4 3工作 3機器向左調整後之甘特圖 64
圖4-5 Ft06問題以粒子數50的搜尋結果 68
圖4-6 Ft06問題以粒子數100的搜尋結果 68
圖4-7 Ft06問題以粒子數150的搜尋結果 69
圖4-8 Ft06問題以粒子數200的搜尋結果 69
圖4-9 Ft10問題以粒子數50的搜尋結果 72
圖4-10 Ft10問題以粒子數100的搜尋結果 72
圖4-11 Ft10問題以粒子數150的搜尋結果 73
圖4-12 Ft10問題以粒子數200的搜尋結果 73
圖4-13 Ft20問題以粒子數50的搜尋結果 76
圖4-14 Ft20問題以粒子數100的搜尋結果 76
圖4-15 Ft20問題以粒子數150的搜尋結果 77
圖4-16 Ft20問題以粒子數200的搜尋結果 77

表目錄
表2-1　3工作×3機器的JSP問題 21
表3-1 17個測試函數例 26
表3-2 全域搜尋最佳解的各種演算法 27
表3-3 函數於不同慣性權重值下之測試結果 28
表3-4 17個測試函數的搜尋成功率及平均世代次數 36
表3-5 PSO與其他方法於搜尋成功率次數之比較 37
表3-6 PSO與其他方法於計算目標函數次數之比較 38
表3-7 格架結構於二種負荷在PSO 與NPSO測試結果 44
表3-8 NPSO於格架結構測試結果與文獻[4,60]比較 45
表3-9 壓力容器問題在PSO 與NPSO測試結果 48
表3-10 NPSO於壓力容器測試結果文獻比較 49
表3-11 懸臂樑問題在PSO 與NPSO測試結果 53
表3-12 NPSO於懸臂樑問題測試結果與文獻[64]比較 54
表3-13 NPSO測試結果的限制條件與文獻[64]比較 55
表4-1 零工式生產派工法則 59
表4-2 零工式生產的績效衡量準則 60
表4-3 Ft06問題於5次測試中所需搜尋世代數結果 67
表4-4 Ft10問題於5次測試中最少總完工時間 70
表4-5 Ft10問題於不同粒子數設定值的測試結果比較表 71
表4-6 Ft20問題於5次測試中最少總完工時間 74
表4-7 Ft20問題於不同粒子數設定值的測試結果比較表 75
表4-8 SPSO測試最佳結果表 78
表4-9 SPSO測試最佳結果與文獻績效最佳值之比較 79

參考文獻
1. Parkinson, A. and Wilson, M., “Development of a Hybrid SQP-GRG Algorithm for Constrained Nonlinear Programming,” Transactions of ASME, Journal of Mechanisms and Automation in Design, Vol. 110, No.1, pp.73-83 1989.
2. Lim, O.K. and Arora, J.S., “An Active Set RQP-Algorithm for Engineering Design Optimization,” Comput, Math. Appl. Mechanics and Engineering, Vol.57, pp.51-65 1986.
3. 蘇木春、張孝德，機械學習：類神經網路、模糊系統以及基因演算法則，全華圖書，1997。
4. 官佳慶，“改良式單純形法用於結構動態參數之修正”， 海洋大學造般工程研究所，碩士論文，民國88年。
5. 曾俊傑，“一個智慧型指紋辨識系統的設計方法論”，義守大學電機工程系，碩士論文，民國90年。
6. Mattfeld, D.C. and Vaessens, R. J. M., “Job Shop Problem Test Instances Set”, <http://www.ms.ic.ac.uk/jeb/pub/jobshop1.txt >, 2003.
7. 蔡清欉，“以粒子群最佳化為基礎之電腦遊戲角色設計之研究”，東海大學資訊工程與科學研究所，碩士論文，2003。
8. Reynolds, C., “Flocks, herds and schools: A distributed behavioral model,” Proc. ACM SIGGRAPH’87, pp.25-34, 1987.
9. IEEE Swarm Intelligence Symposium, <http://www.ieeeswarm.org>, 2005.
10. Kennedy, J., Eberhart. R.C., Swarm Intelligence, Morgan Kaufmann Press, 2001.
11. Dorigo, M., Maniezzo, V., and Coloni, A., “Positive feedback as a search strategy,” Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, IT, 1991.
12. Reynolds, R.G., Sverdlik, W., “Problem solving using cultural algorithms,” Evolutionary Computation, IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference on Vol.2, pp.645 – 650, 1994.
13. Kennedy, J. and Eberhart, R.C., “Particle Swarm Optimization,” Proc. IEEE International Conf. Neural Networks, Vol. 4, pp. 1942-1948, 1995.
14. 劉惟信，機械最佳化設計，全華圖書，民國92年。
15. Arora, J.S. and Li. G., “Constrained Conjugate Direction Methods for Design Optimization of Large Systems,” AIAA Journal, Vol.31, No.2, pp.388-395, 1993.
16. Holland, J., “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Michigan, 1975.
17. Davis, L., Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991.
18. Mitchell, M., An Introduction to Genetic Algorithms, Cambridge, MIT press, 1996.
19. Hajela, P., “Genetic Search-An Approach to the Nonconvex Optimization Problem,” AIAA Journal, Vol.28, pp.1205-1210, 1990.
20. 魏川原，“遺算演算法於般舶結構多目標最佳化設計之應用”，海洋大學造船工程研究所，民國88年。
21. 賴士葆，生產作業管理理論與實務，華泰書局，民國84年。
22. 陳建良，排程概述，機械工業雜誌，1995。
23. Panwalkar, S.S., Dudek, R.A. and Smith, M.L., Sequencing Research and the Industrial Scheduling Problem, In Symposium on the Theory of Scheduling and its Applications, S.E. Elmaghraby (ed.), Springer, New York, 1973.
24. Van Laarhoven, P. J. M., Aarts, E. H. L. and Lenstra, J. K., “Job shop scheduling by simulated annealing,” Operations Research, 40, 113-125, 1992.
25. Gen, M., Tsujimura Y. and Kubota, E., “Solving Job-Shop Scheduling Problems by Genetic Algorithm,” IEEE International Conference on, Vol. 2, pp. 1577-1582, 1994.
26. Zwaan, S. and Marques, C., “Ant colony optimization for job shop scheduling,” Proceeding of the Third Workshop on Genetic Algorithms and Artificial Life (GAAL 99), 1999.
27. Ponnambalam, S.G., Aravindan, P. and Rajesh, S.V., “A tabu search algorithm for job shop scheduling,” International Journal of Advanced Manufacturing Technology, Vol. 16, pp.765-771, 2000.
28. 李宜原，“改良式遺傳演算法於零工式生產排程系統之應用”，海洋大學系統工程暨造船學系研究所，碩士論文，2004。
29. 黃國凌，“螞蟻/塔布混合演算法求解零工型排程問題”，台灣科技大學工業管理系研究所，碩士論文，2004。
30. Kennedy, J. and Eberhart, R.C., “Particle swarm optimization,” Proc. IEEE International Conference on Neural Networks, pp. IV：1942-1948, 1995.
31. Eberhart, R.C. and Kennedy, J., “A new optimizer using particle swarm theory,” Proc. Sixth International Symposium on Micro Machine and Human Science, pp.39-43, 1995.
32. 胡曉輝，「粒子群優化算法介紹」，<http://web.ics.purdue.edu/ ~hux/tutorials.shtml>，民國91年4月。
33. Kennedy, J., Eberhart, R.C., Swarm Intelligence, Morgan Kaufmann Press, 2001.
34. Eberhart, R.C. and Shi, Y. “Comparison between genetic algorithms and particle swarm optimization,”1998 Annual Conference on Evolutionary Programming, 1998.
35. Angeline, P.J., “Using selection to improve particle swarm optimization,” IEEE World Congress on Computational Intelligence, pp. 84-89, 1998.
36. Brandstatter, B. and Baumgartner, U., “Particle Swarm Optimization-mass-spring System Analogon,” IEEE Transactions on Magnetics, Vol.38, pp. 997-1000, 2002.
37. Fukuyama, Y., and Yoshida, H., “A Particle Swarm Optimization for Reactive Power and Voltage Control in Electric Power Systems,” Proc. IEEE Congress Evolutionary Computation, Vol. 1, pp. 87-93, 2001.
38. Srinivasan, D., Loo, W.H. and Cheu, R.L., “Traffic Incident Detection Using Particle Swarm Optimization,” Proceedings of the 2003 IEEE Swarm Intelligence Symposium, pp. 144-151, 2003.
39. Yin, P.Y., “A Discrete Particle Swarm Algorithm for Optimal Polygonal Approximation of Digital Curves,” Journal of Visual Communication and Image Representation, Vol. 15, pp. 241-260, 2004.
40. Shi, Y. and Eberhart, R.C., “A Modified Particle Swarm Optimizer,” IEEE Int. Conf. on Evolutionary Programming, pp. 69-73, 1998.
41. Shi, Y. and Eberhart, R.C, “Empirical Study of Particle Swarm Optimization,” Proceedings of the Evolutionary Computation 1999 Congress, Vol. 3, pp. 1945-1950, 1999.
42. Clerc, M., “The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization,” Proc.1999 Congress on Evolutionary Computation, Vol. 3, pp. 1951-1957, 1999.
43. Eberhart, R.C. and Shi, Y., “Particle Swarm Optimization: Developments, Applications and Resources,” Proc. IEEE Int. Conf. On Evolutionary Computation, Vol. 1, pp. 81-86, 2001.
44. Suganthan, P.N., “Particle Swarm Optimizer with Neighbourhood Operator,” Proc. Congress on Evolutionary Computation, Vol. 3, pp. 1958-1962, 1999.
45. Ratnaweera, A., Halgamuge, S.K. and Watson, H.C., “Self-Organizing Hierarchical Particle Swarm Optimizer With Time-Varying Acceleration Coefficients,” Evolutionary Computation, IEEE Transactions, Vol. 8, pp. 240-255, 2004.
46. Kennedy, J., “Stereotyping: Improving Particle Swarm Performance with Cluster Analysis,” Proc. IEEE Int. Conf. on Evolutionary Computation, Vol. 2 pp. 1507-1512, 2000.
47. Shi, Y. and Eberhart, R.C., “Parameter Selection in Particle Swarm Optimization,” 7th Int. Conf. on Evolutionary Programming, Vol. 1447, pp. 591-600, 1998.
48. Watts, D.J. and Strogatz, S.H. “Collective dynamics of ‘small-world’ networks,” Nature, 393, pp. 440-442, 1998.
49. Kennedy, J., Mendes, R., “Population structure and particle swarm performance,” Evolutionary Computation, Proceedings of the Congress, Vol. 2, pp.1671-1676, 2002.
50. Kennedy, J., Mendes, R., “Neighborhood topologies in fully-informed and best-of-neighborhood particle swarms,” Proceedings of the 2003 IEEE International Workshop, pp.45-50, 2003.
51. Chin Aik Koay and Srinivasan, D., “Particle swarm optimization-based approach for generator maintenance scheduling,” Proceedings of the IEEE Swarm Intelligence Symposium, pp.167-173, 2003.
52. Chang, R.F., Lu, C.N., “Feeder reconfiguration for load factor improvement,” Power Engineering Society Winter Meeting, IEEE, Vol. 2, pp. 980-984, 2002.
53. Bessaou, M. and Siarry, P., “A Genetic Algorithm with Real-value Coding to Optimize Multimodal Continuous Functions,” Structural and Multidisciplinary Optimization, Vol.23 pp. 63-74, 2001.
54. Chelouah, R. and Siarry, P., “A Continuous Genetic Algorithm Designed for the Global Optimization of Multimodal Functions,” Journal of Heuristics, Vol. 6, pp. 191-213, 2000.
55. Chelouah, R. and Siarry, P., “Genetic and Nelder-Mead Algorithms Hybridized for a More Accurate Global Optimization of Continuous Multiminima Functions,” European Journal of Operational Research, Vol. 148, pp. 335-348, 2003.
56. Chelouah, R. and Siarry, P., “Tabu Search Applied to Global Optimization,” European Journal of Operational Research, Vol. 123, pp.256-270, 2000.
57. Chelouah, R. and Siarry, P., “A Hybrid Method Combining Continuous Tabu Search and Nelder-Mead Simplex Algorithms for The Global Optimization of Multiminima Functions,” European Journal of Operational Research, Vol. 161, pp.636-654, 2005.
58. Kuo, H.C., Chang, J.R. and Shyu, K.S., “A Hybrid Algorithm of Evolution and Simplex Methods Applied to Global Optimization,” Journal of Marine Science and Technology, Vol. 12, pp. 280-289, 2004.
59. Kirsh, U., Optimum Structural Design, McGraw-Hill, 1981.
60. 許博傑，“實數編碼與二位元編碼遺傳演算法之性能比較研究”，國立台灣科技大學機械工程所，碩士論文，民國89年。
61. Xiaohui, Hu., Eberhart, R.C. and Shi, Y., “Engineering Optimization with Particle Swarm,” Swarm Intelligence Symposium, pp.53-57, 2003.
62. Carlos A. Coello Coello, “Use of a self-adaptive penalty approach for engineering optimization problems,” Computers in Industry, Vol. 41, pp. 113-127, 2000.
63. Deb, K., “GeneAS:a robust optimal design technique for mechanical component design,” Evolutionary Algorithms in Engineering Application Berlin: Springer-Verlag, pp.497-514, 1997.
64. Gupta, Krishna C.; Jianmin, Li, “Robust design optimization with mathematical programming neural networks,” Computers & Structures, Vol. 76, pp.507-516, 2000.