臺灣博碩士論文加值系統

近年資訊科技快速發展，行動通訊產業日漸興盛，國內行動通訊人口迅速增加，相對無線基地台數目與日俱增，而通訊業首要重視的問題即是通話品質之良窳，本研究以無線基地台配置為基礎問題，加上區域性通訊品質最低限制的條件下，要如何將不同種類功率無線基地台建置在各個區域當中並符合各個區域最低通訊品質的要求達到最小成本的無線基地台配置組合，是本研究所要探討的重要議題。對於求解最佳化的問題，在目前人工智慧是常被採用的啟發式演算法之一。本研究結合免疫演算法及粒子群最佳化演算法之混合式進化演算法，將免疫演算法決定無線基地台數量跟種類，並且利用網格技術提高運算速度與效率，傳遞至粒子群演算法中決定各無線基地台之位址，經實驗結果顯示在各別區域最低通訊品質限制下，所提出的方法可決定不同功率大小以及成本之無線基地台數目與位址，提供業者作為設置參考以及提供使用者最理想與滿意的收訊品質。

Due to the rapid development of information technology in recent years, the cellular phone users have been increased tremendously. For this reason, the signal transmission stations are widely built so as to enhance the communication quality. Inappropriate setup of stations is not only causing the unnecessary cost but also making the poor service quality. How to allocate the base stations optimally is a very important issue.
According to the above difficulties, this thesis is to investigate the a communications base station allocation problems with the restricted regional differences constraints in which the types of base stations and the corresponding numbers and locations are to be decided simultaneously so as to minimize the setup cost subject to the maximum failure rate specified in different regions .
In this study, we applied a grid computing based hybrid evolutionary algorithm containing the Immune algorithm and Particle Swarm Optimization (IAPSO). We use the IAPSO on the grid computation architecture to solve the multiple stations location problems. The computational results show that the proposed algorithm is feasibly to solve the problems. It is wished that our study can provide the Telecommunication Enterprise the optimal/near optimal strategies for the setup of base stations.

目錄
中文摘要.................................................i
英文摘要.................................................ii
誌謝....................................................iii
表目錄...................................................vi
圖目錄...................................................vii
第一章 緒論............................................. .1
1.1前言..................................................1
1.2研究背景.............................................. 1
1.3 研究目的與範圍 ........................................2
1.4研究方法與步驟......................................... 3
第二章 文獻探討........................................... 5
2.1區位配置問題........................................... 5
2.2免疫演算法..............................................9
2.2.1免疫系統介紹..........................................9
2.2.2免疫演算法組成架構.....................................13
2.2.3免疫演算法流程與步驟...................................16
2.3粒子群演算法............................................17
2.3.1粒子速度更新法則.......................................21
2.3.2粒子群最佳化之演算流程與步驟.............................23
2.4網格運算...............................................23
2.4.1何謂網格運算技術......................................24
2.4.2網格應用的類型........................................25
2.4.3網格架構.............................................26
2.5混合進化式演算法IAPSO...................................27
第三章 問題描述與基本假設....................................29
3.1問題模式...............................................29
3.1.1問題變數定義..........................................29
3.1.2問題模式和假設........................................30
3.2混合式進化演算法........................................31
3.2.1網格技術平台架構......................................31
3.2.2基因表示與解碼........................................36
3.2.3交換與突變..........................................38
3.2.4 懲罰值函數..........................................39
3.2.5 終止與輸出..........................................39
第四章 實驗與討論..........................................40
4.1參數設定..............................................40
4.2區域化通訊品質限制......................................41
4.3混和進化式演算法IAPSO求解...............................43
4.4 IAPSO結合網格運算求解時間..............................50
4.5 進化式演算法(IAPSO)求解與LNIGO比較.....................51
4.6 多類別不規則圖型求解...................................54
4.7 小結 ...............................................56
第五章 結論與未來研究......................................57
5.1結論 ...............................................57
5.2未來研究方向.........................................57
參考文獻................................................58
附錄一 田字型區域劃分限制Lingo求解限制表....................61
附錄二 回字型區域劃分限制Lingo求解限制表.....................62
附錄三 不規則三角型區域劃分限制Lingo求解限制表................63
附錄四 多類別不規則型區域劃分限制Lingo求解限制表..............64


表目錄
表1 運用演算法進行區位配置最佳化...........................8
表2 網格網路類型........................................26
表3 變數定義說明........................................29
表4 去除相似性過高之抗體示意..............................34
表5 多類別無線基地台數目與種類之二元基因編碼表示..............37
表6 無線基地台種類與特性.................................40
表7 求解多類別無線基地台配置之演算法參數的設定...............41
表8 混和進化式演算法求解田字型區域差異限制之無線基地台配置圖解...43
表9 田字型區域限制差異之無線基地台配置數據...................44
表10 回字型區域限制差異之無線基地台配置數據...................46
表11 不規則三角型區域限制差異之無線基地台配置數據..............48
表12 網格運算與對應電腦之求解時間...........................50
表13 田字型區域限制求解比較................................51
表14 回字型區域限制求解比較................................52
表15 不規則三角型區域限制求解比較...........................53
表16 多類別不規則型區域劃分限制求解.........................54
表17 多類別不規則型區域劃分限制比較.........................55



圖目錄
圖1 區域化示意圖 ........................................3
圖2 研究架構與流程圖.......................................4
圖3 流行性感冒病毒與免疫系統結合示意圖........................11
圖4 株落選擇示意圖........................................12
圖5 單點交換過程示意圖....................................14
圖6 兩點交換過程示意圖....................................15
圖7 單點突變的過程示意圖..................................15
圖8 免疫演算法系統流程與步驟...............................17
圖9 粒子群活動示意圖......................................19
圖10 粒子移動位置與速度向量圖................................20
圖11 粒子群最佳化演算法架構流程..............................23
圖12 網格運算架構圖........................................27
圖13 伺服端與客戶端之matlab COM檔程式名稱圖..................33
圖14 結合進化演算法於網格技術之組成流程圖.....................36
圖15 多類別無線基地台位置配置之粒子表示.......................37
圖16 單點交換...........................................38
圖17 雙點交換............................................38
圖18 單點突變............................................38
圖19 田字型區域劃分示意圖..................................41
圖20 回字型區域劃分示意圖..................................42
圖21 不規則型區域劃分示意圖................................42
圖22 田字型區域差異限制之無線基地台配置圖解...................45
圖23 回字型區域差異限制之無線基地台配置圖解...................47
圖24 不規則三角型區域限制差異之無線基地台配置圖解...............49
圖25 網格時間差異分析......................................50
圖26多類別不規則型區域劃分示意圖.............................54
圖27多類別不規則型區域劃分求解圖.............................54
圖28多類別不規則型區域劃分3D示意圖...........................55

參考文獻
中文部分
[1] 交通部統計處，http://www.motc.gov.tw
[2] 行政院交通部電信總局，http://www.dgt.gov.tw/flash/index.shtml
[3] 洪子盛，(民92)。以模糊多目標規劃法求解消防站配置問題之最佳化，國立成功大學工業管理研究所碩士學位論文。
[4] 吳永裕，(民94)。鄰避設施之廠址選擇及車輛途程問題，國立雲林科技大學工業工程與管理研究所碩士學位論文。
[5] 衷嵐焜，(民85)。離散區位模型應用於速食外送業態區位評選之研究，國立中央大學土木工程學系，碩士論文。
[6] 黃格威，(民95)。混合式進化演算法於無線基地台配置決策之應用，ICIM2006第十七屆國際資訊管理學術研討會論文。
[7] 徐建樑，(民94)。網格式地理資訊系統應用於區位選址之研究─以行動電話無線基地台設置為例，朝陽科技大學建築及都市設計研究所碩士論文。
[8] 曾建銘，(民97)。以網格技術擷取即時股市資料以支援資料倉儲之建置，中國文化大學資訊管理研究所，碩士論文。
[9] 陳靜慧，(民92)。應用類免疫演算法於串並聯系統複置分配最佳化問題之研究，長榮大學經營管理研究所，碩士論文。
[10] 羅意茹，(民93)。應用免疫演算法於可控退化率存貨問題之研究，國立嘉義大學運輸與物流工程研究所，碩士論文。
[11] 廖子銘，(民90)。類免疫演算法於多目標最佳化問題之研究應用，大同大學機械工程研究所，碩士論文。
[12] 張慶彬，(民93)。應用分散式類免疫演算法於散熱片之最佳化設計，大同大學，碩士論文。
[13] 蘇木春、張孝德，(民89)。機器學習類神經網路、模糊系統以及基因演算法則，全華科技圖書股份有限公司。
英文部分
[14] Chen, M.C., Tsai, D.M., & Tseng, H.Y. (1999). “A stochastic optimization approach for roundness measurements”, Pattern Recognition Letters, 20, pp. 707-719.
[15] Chen, T.C., & Fischer, G.W. (2000). “A GA-based search method for the tolerance allocation problem”, Artificial Intelligence in Engineering, 14, pp. 133-141.
[16] Drezner, Z. (1995). “Dynamic facility location: The progressive p-median problem”, Location Science, 3(1), pp. 1-7.
[17] Drezner, Z., & Wesolowsky, G.O. (1997). “On the best location of signal detectors”, IIE Transaction, 29, pp. 1007-1015.
[18] Flint, S.J., Enquist, L.W., Racaniello, V.R., Skalka, A.M. (2004). “Principles of virology”, Washington, DC, USA.
[19] Van den Bergh, F., & Engelbrecht, A.P.E. (2003). “A new locally convergent particle swarm optimiser “, The Proceedings of IEEE International Conference on Systems Man and Cybernetics, Vol. 3.
[20] Hsieh, Y. C., Chen, T. C., & Bricker, D. L. (1998). “Genetic algorithms for reliability design problems”, Microelectronics & Reliability, 38(10), pp 1599-1605.
[21] Weissman, I. L., & Cooper, M. D. (1993). “How the immune system develops”, Scientific American, 269(3), pp. 33- 40.
[22] Foster, I., & Carl, C. (1999). “The grid: blueprint for a new computing infrastructure”, Morgan Kaufmann, San Francisco.
[23] Foster, I., Carl, K., & Steven, T. (2001). “The anatomy of the grid: Enabling scalable virtual organizations”, International Journal of Supercomputer Applications, 15(3), 200-222.
[24] Foster, I., & Kesselman, Carl. (1998). “The grid: blueprint for a new computing infrastructure”, Morgan Kaufmann, California.
[25] Friedman, J. (1996). “Another approach to polychotomous classification”, technical report, department of statistics, Stanford, Palo Alto, CA.
[26] Foster, Ian, Kesselman, Carl, Nick Jeffrey, & Tuecke. Steve (2002). “The physiology of the grid: an open grid services architecture for distributed systems integration”, Open Grid Service Infrastructure WG, Global Grid Forum.
[27] Ilmari, Karonen. (2006). Clonal selection, http://en.wikipedia.org.
[28] Jerne, N. K. (1973). “The immune system “, Scientific America, 229(1), pp. 52-60.
[29] Kennedy, J., & Eberhurt, R. (1995). “Particle swarm optimization”, Proceedings of IEEE Conference on Neural Networks, Perth, Australia, 4, pp. 1942-1948.
[30] De Castro, L. N., & Von Zuben, F. J. (2000). “The clonal selection algorithm with engineering applications”, In workshop proceedings of the GECCO, pp. 36-37.
[31] Michalewicz, Z. (1996). “Genetic algorithms + Data structures = Evolution programs”, 3rd edition, Springer-Verlag Berlin Heidelberg.
[32] Haupt, R.L., & Haupt, S.E. (1998). “Practical genetic algorithms”, John Wiley & Sons, New York.
[33] Shi, Y., & Eberhart, R. C. (1998). “A modified particle swarm optimizer”, Proceedings of the IEEE Congress on Evolutionary Computation, pp. 69-73.
[34] Suzuki, Atsuo & Drezner, Z. (1996). “The p-center location problem in an area”, Location Science, 4, pp. 68-82.
[35] Weber, A. (1929). “Uber den standort der industrien(alfred Weber’s theory of the location of industries”, University of Chicago, Chicago, IL.
[36] You, P. S., & Chen, T. C. (2005). “An efficient heuristic for series-parallel redundant reliability problems”, computers and operations research, 32, pp. 2117-2127.