臺灣博碩士論文加值系統

近年來，無線射頻辨識 (Radio Frequency Identification, RFID) 技術已經被廣泛應用於各項領域。由於讀取器的詢問區 (Interrogation Zone) 範圍有限，如何使用最少的讀取器覆蓋空間內所有標籤就形成讀取器網路規劃 (Reader Network Planning, RNP) 問題。在本論文中，我們提出基因演算法(Genetic Algorithm, GA)、微基因演算法 (Micro Genetic Algorithm, mGA)和粒子群演算法 (Particle Swarm Optimization, PSO)解決三維讀取器網路規劃(Three Dimensional Reader Network Planning, 3DRNP)問題。由於傳統基因演算法 (Traditional Genetic Algorithm, TGA)和傳統粒子群演算法 (Traditional Particle Swarm Optimization, TPSO)不保證標籤覆蓋率100%，為了克服這個問題，我們提出了修正方案使標籤覆蓋率保證100%，另外我們還提出空間交叉取代基因演算法和微基因演算法的傳統交配，以提升搜索能力。最後結果顯示有加入修正方案之演算法標籤覆蓋率為100%。

In recent years, radio frequency identification (RFID) technique has been widely used in various fields. Due to the limited interrogation zone, how to use the minimum reader to cover all the tags in the space to form the Reader Network Planning (RNP) problem. In this thesis, we proposed genetic algorithm (GA)、micro genetic algorithm (mGA) and particle swarm optimization (PSO) to solve the three-dimensional space reader network planning problem. Due to the traditional genetic algorithm and the traditional particle swarm optimization do not guarantee 100% tag coverage. To overcome the point, we proposed the correction scheme to guarantee 100% tag coverage. In addition, we proposed the spatial crossover to replace the traditional crossover of genetic algorithm and a micro genetic algorithm to improve the search ability. The comparison results show that the algorithms with correction scheme have 100% tag coverage.

目錄
指導教授推薦書
口試委員會審定書
授權書
致謝 iii
摘要 iv
ABSTRACT v
目錄 vi
圖目錄 ix
表目錄 xii
第一章 緒論 -1-
1.1研究背景 -1-
1.2研究動機與目的 -1-
1.3 RFID系統和設備介紹 -3-
1.4論文架構 -5-
第二章 問題描述 -7-
2.1問題介紹 -7-
2.2符號定義和數學模式的建立 -8-
第三章 解決方法 -11-
3.1基因演算法的介紹與應用 -11-
3.1.1基因演算法介紹 -11-
3.1.2 初始化 -13-
3.1.3複製機制 -15-
3.1.4交配 -17-
3.1.5突變 -20-
3.1.6修正方案 -21-
3.1.7基因演算法流程 -22-
3.1.8微基因演算法流程 -25-
3.1.9傳統基因演算法流程 -27-
3.2以粒子群演算法解決三維空間讀取器網路規劃問題 -29-
3.2.1粒子群演算法介紹 -29-
3.2.2 粒子群演算法原理 -29-
3.2.3粒子群演算法應用於三維空間讀取器網路規劃問題 -31-
3.2.4粒子群演算法之修正方案 -34-
3.2.5粒子群演算法流程 -36-
3.2.6傳統粒子群演算法流程 -38-
第四章 模擬結果與討論 -40-
4.1參數設定 -40-
4.2模擬結果與比較 -41-
第五章 結論 -55-
參考文獻 -56-


圖目錄
圖 1-1 RFID 系統示意圖........................................................................ -4-
圖 1-2 讀取器示意圖.............................................................................. -4-
圖 1-3 電子標籤示意圖.......................................................................... -5-
圖 2-1 儲存標籤和讀取器的正方體空間示意圖................................ -10-
圖 2-2 小型正方體中心和讀取器詢問區範圍關係示意圖................ -10-
圖 3-1 基因編碼方式............................................................................ -12-
圖 3-2 候選讀取器位置示意圖............................................................ -15-
圖 3-3 輪盤式選擇示意圖.................................................................... -17-
圖 3-4 空間交叉示意圖........................................................................ -20-
圖 3-5 突變示意圖................................................................................ -21-
圖 3-6 基因演算法流程圖.................................................................... -24-
圖 3-7 微基因演算法流程圖................................................................ -26-
圖 3-8 傳統基因演算法流程圖............................................................ -28-
圖 3-9 在空間內之次粒子示意圖........................................................ -33-
圖 3-10 圖 3-9 對應到的 CRPs 狀況示意圖 ....................................... -33-
圖 3-11 粒子群演算法流程圖.............................................................. -37-
圖 3-12 傳統粒子群演算法流程圖...................................................... -39-
圖 4-1 模擬正方體空間中的標籤分佈位置示意圖............................ -41-
圖 4-2 比較 GA、mGA、PSO 在 Case 1 最佳適應函數值和迭代次數
................................................................................................................ -43-
圖 4-3 比較 GA、PSO 和 mGA 在 Case 1 經過時間和迭代次數..... -44-
圖 4-4 比較 GA、TGA 在 Case 1 最佳適應函數值和迭代次數....... -44-
圖 4-5 比較 PSO 和 TPSO 在 Case 1 最佳適應函數值和迭代次數.. -45-
圖 4-6 比較 GA 和 TGA 在 Case 1 最佳適應函數值的標籤覆蓋率和迭
代次數 ................................................................................................... -45-
圖 4-7 比較 PSO 和 TPSO 在 Case 1 最佳適應函數值的標籤覆蓋和迭
代次數 ................................................................................................... -46-
圖 4-8 比較 GA、mGA、PSO 在 Case 2 最佳適應函數值和迭代次數
................................................................................................................ -47-
圖 4-9 比較 GA、PSO 和 mGA 在 Case 2 經過時間和迭代次數..... -48-
圖 4-10 比較 GA、PSO 和 mGA 在 Case 2 經過時間和迭代次數... -48-
圖 4-11 比較 PSO 和 TPSO 在 Case 2 最佳適應函數值和迭代次數 -49-
圖 4-12 比較 GA 和 TGA 在 Case2 最佳適應函數值的標籤覆蓋率和迭
代次數 ................................................................................................... -49-
圖 4-13 比較 PSO 和 TPSO 在 Case 2 最佳適應函數值的標籤覆蓋和迭
代次數 ................................................................................................... -50-
圖 4-14 比較 GA、mGA、PSO 在 Case 3 佳適應函數值和迭代次數
................................................................................................................ -51-
圖 4-15 比較 GA、PSO 和 mGA 在 Case 3 過時間和迭代次數....... -52-
圖 4-16 比較比較 GA、TGA 在 Case 3 佳適應函數值和迭代次數. -52-
圖 4-17 比較 PSO 和 TPSO 在 Case 3 佳適應函數值和迭代次數.... -53-
圖 4-18 比較 GA 和 TGA 在 Case3 佳適應函數值的標籤覆蓋率和迭代
次數........................................................................................................ -53-
圖 4-19 比較 PSO 和 TPSO 在 Case 3 佳適應函數值的標籤覆蓋和迭代
次數........................................................................................................ -54-


表目錄
表 3-1 染色體之基因和 CRPs 座標對應表......................................... -14-
表 4-1 演算法使用參數........................................................................ -41-

[1] G. M. Gaukler, “Item-level RFID in a retail supply chain with stock-out-based substitution,” IEEE Trans. Ind. Inf., vol. 7, no. 2, pp. 362–370, May 2011.
[2] T.-M. Choi, “Coordination and risk analysis of VMI supply chains with RFID technology,” IEEE Trans. Ind. Inf., vol. 7, no. 3, pp. 497–504, Aug. 2011.
[3] J. Vales-Alonso, V. Bueno-Delgado, E. Egea-Lopez, F. J. Gonzalez-Castano, and J. Alcaraz, “Multiframe maximum-likelihood tag estimation for RFID anti-collision rotocols,” IEEE Trans. Ind. Inf., vol. 7, no. 3, pp. 487–496, Aug. 2011.
[4] Y.-H. Chen, S.-J. Horng, R.-S. Run, J.-L. Lai, R.-J. Chen, W.-C. Chen, Y. Pan, and T. Takao, “A novel anti-collision algorithm in RFID systems for identifying passive tags,” IEEE Trans. Ind. Inf., vol. 6, no. 1, pp. 105–121, Feb. 2010.
[5] S. Chalasani and R. Boppana, “Data architectures for RFID transactions, ” IEEE Trans. Ind. Inf., vol. 3, no. 3, pp. 246–257, Aug. 2007.
[6] S.-Y. Lin and H.-F. Tsai, "Micro genetic algorithm with spatial crossover and correction schemes for constrained three-dimensional reader network planning," Expert Systems with Applications, vol. 4, no. 1, pp. 344-353, 2016.
[7] Ahn, C.W., and Ramakrishna, R.S. Elitism-Based Compact Genetic Algorithms. IEEE Transactions on Evolutionary Computation, 7, 4 (2003), 376-385.
[8] H. Jun and Z. Qingbao, Multi-objective mobile robot path planning based on improved genetic algorithm. in 2010 IEEE International Conference on Intelligent Computation Technology and Automation, 752-756.
[9] Q. B. Zhu and S. Chen, "A new ant evolution algorithm to resolve TSP problem," IEEE Proc. Int. Conf. Machine Learning and Applications, pp. 62-66, 2007.
[10] Y. Weiwei, L. -Yan and H Jinlei.,"Reactive power optimization based on genetic algorithm of improved crossover operation," In Control and Decision Conference (CCDC), IEEE, pp. 883-888, 2012.
[11] Z., Bao and T. Watanabe, "A novel genetic algorithm with cell crossover for circuit design optimization," IEEE International Symposium on Circuits and Systems, pp. 2982-2987, 2009.
[12] H. Wang, Y. Liu, H. Wen, and Y. Chen. "A self-crossover Genetic Algorithm for job shop scheduling problem. " IEEE International Conference In Industrial Engineering and Engineering Management, pp. 549-554,2011.
[13] J. Kennedy and R. Eberhart,, “Particle swarm optimization, IEEE Int. Conf. on Neueal Networks, vol. 4, pp. 1942-1948, 1995.
[14] Y. Shi and R. C. Eberhart, “Empirical study of particle swarm optimization.” in Proc. Congr. Evol. Comput., 1999, pp. 1945–1950.
[15] P. N. Suganthan, “Particle Swarm optimizer with neighborhood operator” in Proc. IEEE Cong. Evol. Comput. Jul. 1999, pp. 1958-1962