臺灣博碩士論文加值系統

對於微波通信鏈路來說，其重要的因素為系統兩天線間無障礙之視線通信(Line of Sight, LOS)，也就是說，如果在微波鏈路間有障礙或距離過長，系統就必須設置中繼(Relay)。目前大量使用微波系統的行動通信及無線區域網路發展迅速，使得尋找適當微波中繼，以維護通信鏈路的品質，為各方研究的重點。
本研究分別採用基因演算法( Genetic Algorithm, GA)、粒子群最佳化( Particle Swarm Optimization, PSO)及混合式基因與粒子群演算法(Hybrid Genetic Algorithm and Particle Swarm Optimization, HGAPSO)三種演算法協助規劃費用成本最低的地面微波鏈路，並於其中加入自適性機制(Self Fitting Mechanism, SFM)，使得每一次運算時皆能找到有效解，研究發現在效能方面，HGAPSO表現為最佳；在完成時間方面，PSO表現為最佳。

It is essential for microwave link to have a clear line of sight (LOS) between the pair of antennas. That is to say, there should not be any obstacles in microwave path. If there are some obstructions in the microwave link or distance too long between two terminals of microwave system, it should put relays in the link. The mobile communication system and wireless LAN that contain a lot of microwave systems develop fast now. It makes most of researches focus on fining optimal microwave relays for quality of communication link.
This paper adopts to add-in GA, PSO, and HGAPSO for aiding to plan the lowest cost relays in the microwave link. During the process, this research add-in self fitting mechanism (SFM) for all the resolutions effectively. The result shows the HGAPSO is best in efficiency of implementation, the PSO is best in time of implementation.

目錄
書名頁 i
中文摘要 iv
英文摘要 v
誌謝 vi
目錄 vii
表目錄 ix
圖目錄 x
1 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 論文架構 2
2 文獻探討 3
2.1 微波傳遞基本概念 3
2.2 基因演算法、粒子群最佳化及混合式基因與粒子群演算法 5
2.3 最短路徑及三種演算法至今前人的相關研究 9
3 研究方法 12
3.1 問題定義與範疇 13
3.2 微波中繼運用GA、PSO及HGAPSO三種演算法研究演化流程 14
3.3 研究限制 18
4 實驗說明與結果分析 19
4.1 應用程式說明 19
4.2 實驗相關參數規劃與前置說明 22
4.3 實驗參數選擇 24
4.4 實驗操作 24
4.5 實驗結果與分析 25
5 結論及未來展望 31
5.1 結論 31
5.2 未來展望 32
參考文獻 32
附錄一 37
附錄二 38
附錄三 39
附錄四 40
附錄五 41
附錄六 42
表目錄
表1、實驗結果-中繼台數量及鏈路成本值分析 26
表2、實驗結果-完成Trail及時間分析 31
圖目錄
圖1、微波視線通信(LOS)示意圖 3
圖2、基因演算法的運作流程 6
圖3、粒子群演算法運作流程 8
圖4、混合式基因與粒子群演算法運作流程 9
圖5、問題定義說明 13
圖6、微波中繼運用GA研究演化流程 15
圖7、微波中繼運用PSO研究演化流程 17
圖8、微波中繼運用HGAPSO研究演化流程 18
圖9、gnuplot graph呈現3D地形圖 20
圖10、基因演算法尋找最佳微波中繼鏈路應用程式 20
圖11、粒子群最佳化尋找最佳微波中繼鏈路應用程式 21
圖12、混合式基因及粒子群演算法尋找最佳微波中繼鏈路應用程式 21
圖13、最佳微波中繼鏈路計算結果之ㄧ圖示 25
圖14、三種演算法成本比較一(Trail) 27
圖15、三種演算法成本比較二Trail) 28
圖16、三種演算法成本比較三(時間) 29
圖17、三種演算法成本比較四(時間) 30

1. Abdalla, A.G.E.; and Zain, A.F.M., "A Software Tool for Cost Optimization of Microwave Radio Relay Link," Antennas and Propagation Society International Symposium, Vol. 2, pp. 1078-081, June 1995.
2.Ahn, C. W., R. S. Ramakrishna, Kang, C. G.., and Choi, I. C., "Shortest Path Routing Algorithm Using Hopfield Neural Network," Electron. Letter, Vol. 37, No. 19, pp. 1176-1178, Sep 2001.
3. Ahn, C. W., and Ramakrishna, R. S., "A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations," IEEE Transactions on Evolutionary Computation, Vol. 6, No. 6, pp. 566-579, December 2002.
4. Awerbuch, B., Bar-Noy, A. and Gopal, M. "Approximate Distributed Bellman-Ford Algorithm,"IEEE Transactions on Communications, Vol. 42, No. 8, pp. 2515-2517, August 1994.
5. Bih, J. Z., "The Microwave Technology," 13th Int. Crimean Conference on Microwave & Telecommunication Technology, pp. 16-21, Sep 2003.
6. Chakraborty G., "Genetic Algorithm to Solve Optimum TDMA Transmission Schedule in Broadcast Packet Radio Networks," IEEE Transactions on Communications, Vol. 52, No. 5, pp. 765-777, May 2004.
7. Ciuprina,G., Ioan, D., and Munteanu I., "Use of Intelligent-Particle Swarm Optimization in Electromagnetics," IEEE Transactions on Magnetics, Vol. 38, No. 2, pp. 1037-1040, Mar 2002.
8. Eberhart, R.C., and Shi, Y., "Comparison between Genetic Algorithms and Particle Swarm Optimization," Proceedings of the 7th Annual Conference on Evolutionary Programming, pp. 611-616, 1998.
9. Ergün, C., and Hacioglu, K., "Multiuser Detection Using a Genetic Algorithm in CDMA Communications Systems," IEEE Transactions on Communications, Vol. 48, No. 8, pp. 1374-1383, Aug. 2000.
10. Holland, J. H., "Adaptation in Natural and Artificial Systems, "University of Michigan Press, 1975.
11. Hussein,Y. A., and El-Ghazaly, S. M., "Modeling and Optimization of Microwave Devices and Circuits Using Genetic Algorithms, "IEEE Transactions on Microwave Theory and Techniques, Vol. 52, No. 1, pp. 329-336, Jan 2004.
12. Janson, S., and Middendorf, M. "A Hierarchical Particle Swarm Optimizer and Its Adaptive Variant," IEEE Transactions on Systems, Man, and Cybernetics—part B: Cybernetics, Vol. 35, No. 6, pp. 1272-1282, Dec 2005.
13. Jatmiko, W., Sekiyama, K., and Fukuda, T., "A PSO-based Mobile Sensor Network for Odor Source Localization in Dynamic Environment: Theory, Simulation and Measurement," 2006 IEEE Congress on Evolutionary Computation, pp. 1036-1043, July, 2006.
14. Jocha ,D., "The Configuration Problem of Microwave Connections in UTRAN," Periodic Polytechnic Ser. El. Eng. Vol. 48, No.1-2, pp. 23-39, 2004.
15. Juang, C.F., "A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design," IEEE tran. On System, Man, and Cybernetics—part B: Cybernetics, Vol. 34, No. 2, pp. 997-1006, Apr 2004.
16. Kennedy, J., and Eberhart, R., "Particle Swarm Optimization ," Proceedings of the 1995 IEEE International Conference on Neural Networks, Vol. 4, pp. 1942-1948, 1995.
17. Laki, I., Farkas, L., and Nagy L., "Cell Planning in Mobile Communication Systems using SGA Optimization," EUROCON''2001, Trends in Communications, International Conference, Vol. 1, pp. 124-127, July 2001.
18. Leung, Y., LI, G., and Xu, Z. B., "A Genetic Algorithm for the Multiple Destination Routing Problems," IEEE Transactions on Evolutionary Computation, Vol. 2, No. 4, pp. 150-161, Nov, 1998
19. Løvbjerg, M., Rasmussen, T., and Krink, T., "Hybrid Particle Swarm Optimizer with Breeding and Subpopulations," Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pp. 469-476, 2001.
20. Mohan, C. K., and Al-kazemi, B., "Discrete Particle Swarm Optimization," Proceedings of the Workshop on Particle Swarm Optimization, pp. 60-66, 2001.
21. Monaco, F. "Introduction to Microwave Technology," Merrill Publishing Company, 1989
22. Park, D. C., Choi, S. E. "A neural network based multi-destination routing algorithm for communication network,"in Proc. Joint Conf. Neural Networks, pp. 1673-1678, 1998
23. Puthenpura, S., "Interesting Optimization Problems in the Planning of Microwave Transmission Networks," Local Computer Networks 2000, Proceedings, 25th Annual IEEE Conference, pp. 384-391, Nov 2000.
24. Saab, Y., and VanPutte, M. "Shortest Path Planning on Topographical Maps," IEEE Transactions on Systems, Man, and Cybernetics –Part A: Systems and Humans, Vol. 29, No. 1, pp. 139-150, Jan 1999.
25. Settles, M., and Soule, T., "Breeding Swarms: a GA/PSO Hybrid," Proceedings of the Genetic and Evolutionary Computation Conference, GECCO_2005, pp. 161-168, 2005.
26. Shi, Y., and Eberhart, R. C., "A Modified Particle Swarm Optimizer, "Proceedings of IEEE International Conference on Evolutionary Computation, pp. 69-73, 1998.
27. Shi, Y., Lu, Y., Zhou, C., Lee, H., Lin, W., and Liang, Y.,"Hybrid Evolutionary Algorithms Based on PSO and GA," Proceedings of the IEEE 2003 Congress on Evolutionary Computation, Canberra, pp. 2393-2399, 2003.
28. Vlachogiannis, J., and Lee, K. Y., "Determining Generator Contributions to Transmission
System Using Parallel Vector Evaluated Particle Swarm Optimization," IEEE Transactions on Power Systems, Vol. 20, No. 4, pp. 1765-1774, Nov 2005.
29. Zomaya, A. Y., and Wright M., "Observations on Using Genetic-Algorithms for Channel Allocation in Mobile Computing," IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No 9, pp. 948-962, Sep 2002.