臺灣博碩士論文加值系統

Cyber Swarm Algorithm(CSA)結合粒子群演算法(PSO)與Scatter Search/Path relinking (SS/PR)的概念，已被實證能有效率地求解連續最佳化問題。然而在現實世界中亦存在著許多離散最佳化問題，因此，本篇論文提出一個Discrete Cyber Swarm Algorithm(DCSA)來解決離散組合最佳化問題。DCSA除了應用PSO與SS/PR之外，也融合了機器學習技術中的漸老、挑選引導解及測不準原理的概念。另外又應用資料探勘技術中的Apriori演算法來找出關聯性。實驗結果顯示本演算法能夠比傳統粒子群演算法(PSO)、混合式粒子群演算法(HPSO)以及novel global harmony search(NGHS)有更好的表現。

Cyber Swarm Algorithm (CSA) combining Particle Swarm Optimization (PSO) and Scatter Search/Path relinking (SS/PR) concepts has been empirically shown to effectively solve continuous optimization problems. However, the extension to discrete optimization problems is still uncharted. This motivates the thesis for proposing a Discrete Cyber Swarm Algorithm (DCSA). In addition to the applications of PSO and SS/PR, DCSA also marries with techniques such as aging, solution guide selection, and uncertainty principle in the machine learning domain. Further, DCSA applies the Apriori algorithm in data mining domain to find the association between attributes. Experimental results manifest that the proposed algorithm outperforms PSO, hybrid PSO, and novel global harmony search.

誌　謝 I
摘　要 II
Abstract III
目　錄 IV
圖　目　錄 VI
表　目　錄 VII
第一章 緒論 1
1.1 研究動機與研究背景 1
1.2 研究目的 2
1.3 論文架構 2
第二章 研究文獻 3
2.1 次經驗演算法 3
2.1.1 Particle swarm optimization 3
2.1.2 Scatter Search 4
2.1.3 Path Relinking 5
2.1.4 Cyber Swarm Algorithms 6
2.2資料探勘 8
2.2.1 關聯式規則 9
2.2.2 Apriori 演算法 9
第三章 研究方法 12
3.1 問題定義 12
3.1.1 任務指派問題 12
3.1.2 資源分配問題 13
3.2 Discrete Cyber Swarm Algorithms 15
3.2.1以path relinking做為粒子移動方式 15
3.2.1.1 Aging 16
3.2.1.2 Solution Guide Selection 16
3.2.1.3 Uncertainty principle 18
3.2.2 更新資訊 19
3.2.2.1 Multi-Start 19
3.2.2.2 區域搜尋 19
3.2.2.3差異化控制 20
3.2.3 結合Apriori演算法 20
3.2.4 流程圖 22
第四章　實驗結果 23
4.1 測試問題資料集設計 23
4.1.1 任務指派問題 23
4.1.2 資源分配問題 23
4.2 實驗結果 24
4.2.1 TAP結果比較 24
4.2.2 RAP結果比較 27
4.2.3 效能分析 28
4.2.4 最差例分析 28
第五章 結論 38
參考文獻 39

Agrawal, R., & Srikant, R. (1994), Fast algorithm for mining association rules, Proc. Conf. Very Large Databases, 487-499.
Agrawal, T., Imielinski, T., & Swami, A. (1993), Mining association rules between sets of items in large datasets, Proc. SIGMOD Conf., 207-216.
Campos, V., Glover, F., Laguna, M., & Martí, R. (2001), An experimental evaluation of a scatter search for the linear ordering problem, Journal of Global Optimization, 21(4), 397-414.
Dorigo, M., & Gambardella, L.M. (1997), Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1(1), 53-66
Glover, F. (1989), Tabu search - part I, ORSA Journal of Computing 1, 190-206.
Glover, F., & Laguna, M. (2000), Fundamentals of Scatter Search and Path Relinking, Control and Cybernetics
Goldberg D. E. (1989), Genetic algorithms in search, Optimization and Machine Learning, Addison Wesley.
Hou, Y. C., & Chang, Y. H. (2004), A new efficient encoding mode of genetic algorithms for the generalized plant allocation problem, Journal of Information Science Engineering, 20(5), 1019-1034.
Han, J., & Kamber, M. (2001), Data Mining: concepts and techniques, Morgan Kaufmann Publishers, San Francisco.
James, T., Rego, C., & Glover, F. (2009), Multistart tabu search and diversification strategies for the quadratic assignment problem, IEEE Transactions on Systems, Man, and Cybernetics-part A: Systems and Humans, 39(3), 579-596.
Kennedy, J., & Eberhart, R. (1995), Particle swarm optimization, IEEE International Conference, 4, 1942-1948.
Koopmans, T., & Beckmann, M. (1957), Assignment problems and the location of economic activities, Econometrica, 25(1), 53–76.
Lo, V.M. (1988), Heuristic algorithms for task assignment in distributed systems, IEEE Transactions on Computers, 37(11), 1384-1397.
Rajamani, K., Cox, A., Iyer, B., & Chadha, A. (1999), Efficient mining for association rules with relational database systems, Database Engineering and Applications, 148-155.
Salman, A., Ahmad, I., & Al-Madani, S. (2002), Particle swarm optimization for task assignment problem, Microprocessors and Microsystems, 26, 363-371
Stinnett, A. A., & Paltiel, A. D. (1996), Mathematical programming for the efficient allocation of health care resources, Journal of Health Economics, 15(5), 641-653.
Yin, P.Y., Glover, F., Laguna, M., & Zhu, J.X. (2010), Cyber swarm algorithms – improving particle swarm optimization using adaptive memory strategies, European Journal of Operational Research, 201(2), 377-389
Yin, P.Y., Yu, S.S., Wang, P.P., & Wang, Y.T. (2006), A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems, Computer Standards, & Interfaces, 28(4), 441-450
Yin, P.Y., & Wang, J.Y. (2006), A particle swarm optimization approach to the nonlinear resource allocation problem, Applied Mathematics and Computation, 183(1), 232-242
Ziegler, H. (1982), Solving certain singly constrained convex optimization problems in production planning. Operations Research Letters, 1, 246-252.
Zou, D., Gao, L. Li, S., Wu, J., & Wang, X. (2010), A novel global harmony search algorithm for task assignment problem, Journal of Systems and Software, 83(10), 1678-1688
Zou, D., Liu, H., Gao, L., & Li, S. (2011), An improved differential evolution algorithm for the task assignment problem, Engineering Applications of Artificial Intelligence, 24, 616-624.