粒子群與禁忌搜尋演算法之整合及其於上行正交分頻多重存取系統載波頻率偏移估計之應用

Mixing Particle Swarm Optimization and Tabu Search Algorithm and Its Application to Estimation of Carrier Frequency Offsets for Uplink OFDMA System

張博凱(Bo-Kai Chang)

指導教授 ： 譚旦旭

國立臺北科技大學/電資學院/電機工程系所/碩士(2013年)

https://doi.org/10.6841/NTUT.2013.00253

摘要

禁忌搜尋(Tabu Search, TS)與粒子群演算法(Particle Swarm Optimization, PSO)均屬演化式演算法(Evolutionary Algorithm)，且被廣泛應用在許多最佳化問題中，其中TS的效能相當依賴初始解，因此本研究利用PSO提供TS合適的初始解。另外，待解變數的增加會導致候選解(Candidate Solutions)的多樣性(Diversity)不足而讓求解的效果銳減，故本研究進一步加上突變(Mutation)機制，以增加族群個體多樣性，同時提升區域搜尋能力。
此一混合型演算法經一系列測試函數驗證，其效果優於其他方法。接著我們將此一演算法應用於估計上行正交分頻多重存取(Orthogonal Frequency Division Multiple Access, OFDMA)系統之載波頻率偏移(Carrier Frequency Offsets, CFOs)。模擬結果顯示，與整合田口運算及突變之粒子群演算法(Taguchi-based Mutation PSO, THM-PSO)相較，本研究提出的方法可以估計出較精確的CFOs。

關鍵字

粒子群演算法 ； 禁忌搜尋演算法 ； 正交分頻多重存取 ； 載波頻率偏移

並列摘要

The Tabu search (TS) and particle swarm optimization (PSO) algorithm are developed based on evolutionary computation, which have been extensively applied in many optimization problems. Since PSO and TS are relatively more capable for global exploration and local search, respectively, than many other heuristic algorithms, a new approach combining PSO and TS is proposed in this study. Because of the performance of TS is highly dependent on the initial solution, this study employs PSO to provide suitable initial solution for TS. Furthermore, the lack of diversity of candidate solution can easily trap the final solution into local optimum as the dimension of solution space increases. Hence, mutation operation is further introduced to increase the diversity of candidate solution for enhancement of local search capability of the proposed scheme.
The proposed approach has been verified based on a number of benchmark functions, which demonstrates the best performance as compared to other schemes. This approach is then applied to estimate the carrier frequency offsets (CFOs) encountered in the uplink orthogonal frequency division multiple access (OFDMA) system. Experimental results indicate that the proposed approach is superior to Taguchi-based Mutation PSO (THM-PSO) in terms of mean square error, symbol error rate, and computational burden per generation.

並列關鍵字

Particle Swarm Optimization (PSO) ； Tabu Search (TS) ； Orthogonal Frequency Division Multiple Access (OFDMA) ； Carrier Frequency Offset (CFO)

參考文獻

[1] K. Ishaque and Z. Salam, “A Deterministic Particle Swarm Optimization Maximum Power Point Tracker for Photovoltaic System Under Partial Shading Condition,” IEEE Transactions on Industrial Electronics, Vol. 60, No. 8, pp. 3195-3206, Aug. 2013.

[2] A. C. Adamuthe and R. S. Bichkar, “Tabu Search for Solving Personnel Scheduling Problem,” ICCICT, pp. 1-6, Oct. 2012

[3] F. Wang, J. Ma, D. Song, W. Liu, and X. Lu, “Research on Repair Operators in the Whole Space Search Genetic Algorithm of Assembly Job Shop Scheduling Problem,” IEEE Conference on ICIEA, pp. 1922-1927, July 2012.

[4] I. Develi and A. Akdagli, “Approximate Expression of Bit Error Rate in Uplink MC-CDMA Systems with Equal Gain Combining,” IEEE Journal of Communications and Networks, Vol. 15, No. 1, pp. 25-30, Feb. 2013.

[5] T. H. Tan, Y. F. Huang, L. C. Hsu, and C. H. Wu, “Joint Channel Estimation and Multi-user Detection for MC-CDMA System Using Genetic Algorithm and Simulated Annealing,” IEEE International Conference on SMC, pp. 249-256, Oct. 2010.