以儲存式粒子群演算法處理N-QUEEN問題

Solving N-Queen Problem Using Repository Particle Swarm Optimization Algorithms

吳建漳(Jane-Jang Wu)

指導教授 ： 邱昭彰

元智大學/資訊學院/資訊管理學系/碩士(2007年)

https://doi.org/10.6838/YZU.2007.00173

摘要

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

關鍵字

最佳化(Optimization),人工智慧(AI),啟發式(Heuristic),粒子演算法(PSO),儲存式粒子演算法(RPSO),基因演算法(GA)

並列摘要

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.

並列關鍵字

optimization, artificial intelligence, heuristic, particle swarm algorithms, repository particle swarm algorithms, genetic algorithms

參考文獻

[1] 陳有賢，邱昭彰，“應用多目標遺傳演算法於網際網路網告採買策略最佳化,” 全國博碩士論文資訊網國， 第13頁，2002

[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.