本論文提出一種改良式粒子群最佳化演算法，其目的為改善傳統粒子群最佳化演算法在多目標最佳化問題的效能。演化的過程分成兩個階段：階段一，將問題的搜尋空間分割成數個子空間，並利用多個粒子群找到搜尋空間中大多數的區域最佳解，且在演化的過程中粒子們會在族群間移動；階段二，利用階段一所找到的數個區域最佳解組成一組新的粒子群，並繼續對整個空間作全域最佳解的搜尋。根據最後的實驗結果顯示改良式粒子群最佳化演算法在解決多數的多目標最佳化問題上有很好的結果。

This paper presents an improved particle swarm optimization which improved the efficiency on the multimodal optimization problems. The new algorithm has two stages: In the first stage, we split the problem’s search space into k sub-space, and then using k particle swarms to find the optimum in each sub-space, the local optimum in the original search space. During this stage, particles can move to different swarms. In the second stage, we organize the several local optimums finding in the first stage into a new swarm, and continue searching for the global optimum. Empirical examination of the evolution shows that the improved PSO has better efficiency than PSO.

目錄 ii
表目錄 iii
圖目錄 iv
1 緒論 1
1.1 研究背景 1
1.2 研究動機與目標 1
1.3 論文架構與流程 3
2 文獻探討 4
2.1 粒子群最佳化演算法（PSO） 4
2.1.1 PSO 之發展背景 4
2.1.2 PSO 之理論介紹 4
2.1.3 PSO 之更新法則 7
2.1.4 GCPSO（Guaranteed Convergence PSO） 8
2.2 PSO 之相關研究 9
2.3 PSO 與 GA 之比較 12
2.3.1 優缺點比較 12
3 方法論 14
3.1 IPSO 之演化概念 14
3.2 IPSO 之演化流程 14
3.2.1 切割搜尋空間 16
3.2.2 各子空間之粒子群運作 18
3.2.3 粒子在各族群間移動之運作 19
3.2.4 新族群成員之挑選方式 19
3.2.5 新粒子群之運作 20
3.3 IPSO 之完整演化流程圖 21
4 實驗說明與結果分析 22
4.1 測試函式 22
4.2 實驗設計 24
4.3 相關參數 24
4.4 實驗結果與分析 25
5 結論與未來展望 31
參考文獻 33
附錄一 35
附錄二 36
附錄三 37

1.Angeline, P., "Evolutionary Optimization versus Particle Swarm Optimization: Philosophy and performance differences", Proceedings of the Evolutionary programming, vol.1447, pp. 601-610, 1998.
2.Bergh, F., "An Analysis of Particle Swarm Optimizers", PhD thesis, Department of Computer Science, University of Pretoria, 2002a.
3.Bergh, F., Engelbrecht, A.P., "A New Locally Convergent Particle Swarm Optimiser," Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, pp. 96-101, October 2002b.
4.Bergh, F. D., Engelbrecht, A, “A Cooperative Approach to Particle Swarm Optimization,” Proceeding of IEEE Trans., vol. 8, no. 3, pp. 225-239, 2004.
5.Brits, R., Engelbrecht, A., Bergh, F., "A Niche Particle Swarm Optimization," Proccedings of 4th Asia-Pacific Conference on Simulated Evolution and Learning, pp. 692-696, 2002.
6.Brits, R., Engelbrecht, A., Bergh, F., "Scalability of Niche PSO," Proceedings of IEEE Swarm Intelligence Symposium, pp. 228–234, 2003.
7.Clerc, M., "The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization," Proceedings of ICEC, pp.1951-1957, 1999.
8.Dorigo, M., "Optimization, Learning and Natural Algorithms", PH.D Thesis, Dipartimento di Elettronica, Politecnico di Milano, 1992.
9.Eberhart, R.C., Shi, Y., “Comparison between genetic algorithms and particle swarm optimization,” Proceedings of the 7th Annual Conference on Evolutionary Programming, pp.611-619, 1998.
10.Holland, J.H., "Adaptation in Natural and Artificial Systems," University of Michigan Press, 1975.
11.Iwamatsu, M., "Multi-Species Particle Swarm Optimizer for Multimodal Function Optimization," Proceedings of the IEICE Transactions on Information and Systems 2006, pp. 1181-1187, 2006.
12.Kennedy, J., Eberhart, R.C., “Particle swarm optimization,” Proceedings of the 1995 IEEE International Conference on Neural Networks, vol. 4, pp. 1942-1948, 1995.
13.Kennedy, J., Mendes, R., “Population structure and particle swarm performance,” Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), pp. 1671-1676, 2002.
14.Løvbjerg, M., Rasmussen, T., Krink, T., “Hybrid particle swarm optimiser with breeding and subpopulations,” Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pp.469-476, 2001.
15.Mendes, R., Kennedy, J., Neves, J., “Watch Thy Neighbor Or How The Swarm Can Learn From Its Environment,” Proceedings of the IEEE on Swarm Intelligence Symposium (SIS-2003), pp. 88-94, 2003.
16.Mohan, C. K., Al-kazemi, B., "Discrete Particle Swarm Optimization," Proceedings of the Workshop on Particle Swarm Optimization, 2001.
17.Peram, T., Veeramachaneni, K., Mohan, C., "Fitness-Distance Ratio Based Particle Swarm Optimization," Proceedings of IEEE Swarm Intelligence Symposium, pp. 174-181, 2003.
18.Seo, J -H, Im C -H, Heo C -G, Kim J -K, Jung H -K, Lee C -G,“Multimodal Function Optimization Based on Particle Swarm Optimization,” Proceeding of IEEE Trans. Magn., vol. 42, pp. 1095-1098, 2006.
19.Settles, M., Soule, T., “Breeding swarms: a GA/PSO hybrid,” Proceedings of the Genetic and Evolutionary Computation Conference, GECCO_2005, pp. 161-168, 2005.
20.Shi, Y., Eberhart, R. C., “A Modified Particle Swarm Optimization Algorithm,” Proceedings of IEEE International Conference on Evolutionary Computation, 1998.
21.Shi, Y., Lu, Y., Zhou, C., Lee, H., Lin, W., Liang, Y., “Hybrid Evolutionary Algorithms Based on PSO and GA,” Proceedings of the IEEE 2003 Congress on Evolutionary Computation, Canberra, pp. 2393-2399, 2003.
22.Xie, X., Zhang, W., Yang, Z., “Adaptive Particle Swarm Optimization on Individual Level,” Proceedings of the 6th International Conference on Signal Processing (ICSP 2002), pp. 1215-1218, 2002.
23.胡曉輝，"粒子群優化算法介紹"，http://web.ics.purdue.edu/hux/. tutorials.shtml， 民國91 年4 月。