臺灣博碩士論文加值系統

本研究提出一種儲存型的粒子群演算法(Reposition PSO)簡稱(RPSO)，透過RPSO的啟發式方法與儲存經驗值的記憶方式，使PSO在問題求解上更具有效率，同時我們也透過N-Queen的問題來驗證RPSO的效能，本文將每粒子個體透過維度的轉換成矩陣方式進而處理N-Queen問題，透過此方法建構模型來處理N-Queen問題，同時以陣列的方法來儲存粒子的離散狀態並提供演算法饋入使用，合理的應用於N-Queen問題上，本文將以RPSO與其他型粒子演算法及基因演算法(Genetic Algorithms, Ga)來驗證RPSO的效能優於其他型演算法，並驗證了儲存型的粒子群演算法較具有效性與一致性。

This research studies a storage grain of PSO algorithm method (Reposition PSO) to be called (RPSO), through RPSO the heuristic method and the storage empirical value memory way, makes PSO to solve in the question on has the efficiency, this article then processes each particle individual penetration dimension transformation matrix way the N-Queen Problem, through this method construction model to deal with the N-Queen Problem issue, simultaneously stores up the granule by the array method the discrete state and provides the calculating method to feed into the use, the reasonable application in the N-Queen Problem, this article by RPSO with other type of Algorithm method and the Gas Algorithm method (Genetic Algorithms, Ga) will confirm RPSO the potency to surpass other algorithm method, and confirmed the RPSO algorithm to compare has the validity and the uniformity.

書名頁 i
論文口試委員審定書 ii
授權書 iii
中文提要 iv
英文提要 v
誌謝 vi
目錄 vii
表目錄 ix
圖目錄 x
1 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 2
1.3 研究流程 3
1.4 論文架構 4
2 文獻探討 5
2.1 PSO的演化概念流程與衍生的相關文獻 5
1 PSO之發展背景 5
2 PSO 之理論介紹 6
3 離散型DPSO 8
4 基因演算法GA 10
2.2 N-Queen問題 11
3 研究方法 15
3.1 研究架構 15
3.2 RPSO之演算虛擬碼: 21
3.3 RPSO流程圖 22
4 儲存式粒子群最佳演算法之應用與說明 23
4.1 系統架構 23
4.2 實驗描述 23
5 實驗結果與分析 26
5.1 以10-Queen問題分別以RPSO及PSO演算法分析效能 26
5.2 以20-Queen問題分別以RPSO及PSO演算法分析效能 27
5.3 以50-Queen問題分別以RPSO及PSO演算法分析效 27
5.4 以100-Queen問題分別以RPSO及PSO演算法分析效 29
5.5 以200-Queen問題分別以RPSO及PSO演算法分析 29
5.6 以N-Queen分別以 10,20,50,100,200 個Queen及三種演算法與代數分析效能彙總分析圖表: 30
5.7 以N-Queen分別以 10,20,50,100,200 個Queen及三種演算法與時間分析效能彙總分析圖表: 31
5.8 實驗總結說明 32
6 結論與後續研究建議 33
參考文獻 35
附錄 38
附錄一. 10-QUEEN的30次實驗結果 38
附錄二. 20-QUEEN的30次實驗結果 40
附錄三. 50-QUEEN的30次實驗結果: 42
附錄四. 100-QUEEN的30次實驗結果: 44
附錄五. 200-QUEEN的30次實驗結果: 46
自 傳 48

[1]陳有賢，邱昭彰，“應用多目標遺傳演算法於網際網路網告採買策略最佳化,” 全國博碩士論文資訊網國， 第13頁，2002
[2]郭信川, 張建仁, 劉清祥, “粒子群演算法於最佳化問題之研究,” 第一屆台灣作業研究學會學術研討會暨, 2004年科技與管理學術研討會, 2004
[3]黃春福, “演算法策略–回溯法,” http://alfu.csie.vnu.edu.tw/algorithm/strategy_backtracking.pdf, Data accessed: 2007/4/10.
[4]Angeline, P., “Evolutionary Optimization versus Particle Swarm Optimization: Philosophy and Performance Differences,” Proceedings of the Evolutionary programming, Vol. 1447, pp. 601-610, 1998.
[5]Boeringer, D. W. and Werner, D. H., “Particle Swarm Optimization versus Genetic Algorithms for Phased Array Synthesis,” IEEE Transactions on Antennas and Propagation , Vol. 52, pp. 771-779, 2004.
[6]Bryan, C., Lam, Leung and H-f., “Progressive Stochastic Search for Solving Constraint Satisfaction Problems,” Proceedings of 15th IEEE International Conference, Tools with Artificial Intelligence, pp. 487-491, 2003.
[7]Dozier, G., Bowen, J. and Bahler, D., “Solving Small and Large Scale Constraint Satisfaction Problems Using a Heuristic-Based Microgenetic Algorithm,” IEEE World Congress on Computational Intelligence, pp. 306-311, 1994.
[8]Du, S., Li, W. and Cao, K., “A Learning Algorithm of Artificial Neural Network Based on GA – PSO,” Intelligent Control and Automation, pp. 3633-3637, 2006.
[9]Eberhart, R.C. and Shi, Y., ”Comparison Between Genetic Algorithms and Particle Swarm Optimization,” Proceedings of the 7th International Conference on Evolutionary Programming VII, Vol. 1447, pp. 611-616, 1998.
[10]“Eight queens puzzle, ” From Wikipedia, the free encyclopedia , http://en.wikipedia.org/wiki/Eight_queens_puzzle#History ,Data accessed: 2007/4/1.
[11]“Evolver Developer''s Kit,” http://www.palisade-europe.com/devkits/edk.asp, Data accessed: 2007/4/10.
[12]Gwee, B-H. and Lim, M. H., “An Evolution Search Algorithm for Solving N-queen Problems,” International Journal of Computer Applications in Technology, Vol. 24, No.1, pp. 43-48, 2005.
[13]Homaifar, A., Turner, J. and Ali, S., “The N-Queens Problem and Genetic Algorithms,” Proceedings of the IEEE Southeast Conference, pp. 262-261, 1992.
[14]Hu, X., Eberhart, R. C. and Shi, Y. “Swarm Intelligence for Permutation Optimization: a Case Study of N-Queens Problem,” Proceedings of the 2003 IEEE 24-26 April 2003, pp. 243-246, 2003.
[15]Kennedy, J. and Eberhart, R.C., “Particle Swarm Optimization,” Proceedings of the 1995 IEEE International Conference on Neural Networks, Vol. 4, pp. 1942-1948, 1995.
[16]Kennedy, J. and Eberhart, R., “A Discret Binary version of The Particle Swarm,” Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, Piscataway, NJ, pp. 4104-4108, 1997.
[17]Krohling, R. A. and Coelho, L. D. S. C., “Coevolutionary Particle Swarm Optimization Using Gaussian Distribution for Solving Constrained Optimization Problems,” IEEE Transactions on Digital Object Identifier, Vol. 36, pp. 1407-1416, 2006.
[18]Kwok, T. and Smith, K.A., “A Noisy Self-organizing Neural Network with Bifurcation Dynamics for Combinatorial Optimization,” IEEE Transactions on Digital Object Identifier, Vol. 6, pp. 84-98, 2006.
[19]Liu, J., Zhong, W. and Jiao, L., “A Multiagent Evolutionary Algorithm for Constraint Satisfaction Problems,” IEEE Transactions on Digital Object Identifier , Vol. 36, pp. 54–73, 2006.
[20]Lin, I-L. , “Paticle Swarm Optimztion for Solving Constraint Satisfaction Problems,” Simon Fraser University, 2002.
[21]Marko, B., Marin, G. and Leo, B., “Solving N-Queen Problem Using Global Parallel Genetic Algorithm,“ EUROCON 2003. Computer as a Tool, The IEEE Region 8, Vol. 2, pp. 104-107, 2003.
[22]Nakaguchi, T., Jin''no, K. and Tanaka, M., “Theoretical Analysis of Hysteresis Neural Network Solving N-Queens problems,” Proceedings of the IEEE International Symposium, pp. 555 - 558, 1999.
[23]Pan, Q. K.,Tasgetiren, M. F. and Liang, Y. C., “A Discrete Particle Swarm Optimization Algorithm for Single Machine Total Earliness and Tardiness Problem with a Common Due Date,” Proceedings of IEEE Congress on Evolutionary Computation, pp. 3281-3288, 2006.
[24]Sanchaik , Benedicl and Paranjar ,”A Dynamic Extension of the Asynchonous Weak Commitment,” Proceedings of IEEE Electrical and Computer Engineering, 2005. Canadian Conference on 1-4 May 2005, pp. 112-115, 2005.
[25]Shi, Y., “Particle Swarm Optimization,” Data Systems, Kokomo, IN 46902, USA, 2004.
[26]Sosic, R. and Gu, J. “Efficient Local Search with Conflict Minimization: a Case Study of the n-Queens,” Proceedings of IEEE Transations on Knowledge and Data Englineering, Vol. 6, pp. 661-668, 1994.
[27]Topon, K. P. and Hitoshi, I., ”Linear and Combinatorial Optimizations by Estimation of Distribution Algorithms,” 9th MPS Symposium on Evolutionary Computation, (Information Processing Society of Japan, IPSJ), Japan, 2002.
[28]Ting, T.O., Rao, M.V.C., Loo, C.K., “A Nnovel Approach for Unit Commitment Problem via an Effective Hybrid Particle Swarm Optimization,” IEEE Transactions on Digital Object Identifier, Vol. 21, pp. 411–418, 2006.
[29]Wang, C. N., Yang, S. W., Liu, C. M. and Chiang, T., “A Hierarchical Decimation Lattice Based on N-Queen with an Application for Motion Estimation,” Signal Processing Letters, IEEE Volume 10, Issue 8, Aug. 2003, Vol. 6, pp. 228-231, 2003.
[30]Wang, G., Zhang, M., Xu, X. and Jiang, C.,”Optimization of Controller Parameters Based on The Improved Genetic Algorithms,” Proceedings of Intelligent Control and Automation, 2006. WCICA 2006. The Sixth World Congress on Vol. 1, pp. 21-23 June 2006, Vol. 1, pp. 3695-3698, 2006.
[31]Wu, M. I., Shu, W. and Gu, J. “Local Search for DAG Scheduling and Task Assignment,” Proceedings of the 1997 International Conference on 11-15 Aug, pp. 174-180, 1997.
[32]Ying, T., Yang, Y., Zeng and J. C., “An Enhanced Hybrid Quadratic Particle Swarm Optimization,” Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications, Vol. 15, pp. 980-985, 2004.