(3.227.0.150) 您好!臺灣時間:2021/05/08 08:44
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:鍾偉信
研究生(外文):Wei-Shin Chung
論文名稱:市場分區之模擬退火演算法
論文名稱(外文):A Simulated Annealing Algorithm for Market Based Redistricting Problems
指導教授:林峰田林峰田引用關係
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:建築與城鄉研究所
學門:建築及都市規劃學門
學類:其他建築及都市規劃學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:95
中文關鍵詞:市場分區模擬退火法最適解
外文關鍵詞:feasible solutionmarket based redistricting problemssimulated annealing algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:84
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在都市研究中,有許多依據活動強度而劃設的分區問題。過去服務範圍分區多以最短服務距離為目標,但在許多情形下,距離並非最重要的考量因子,市場規模可能才是業者關心的重點(如電業、通訊業、有線電視等),故需有新的求解方法。
由於分區問題屬於多極值問題類型,且因模擬退火法具有跳脫區域最適解進而找到全域最適解的能力,故本研究採用模擬退火法做為分區問題的演算法核心,以電業分區為研究案例,求解在市場規模相等(近)目標下的合理分區。在空間屬性的處理上係將空間視為一個網格系統,以需求者觀點設計一電量分派模式,將用戶實際用電需求分派於網格系統中以為分區依據;在演算法的處理上則提出結合「有效參數設定」及「初始條件設定策略」,能夠有效提昇模擬退火法求解分區問題的演算效率與演算品質,進而得到符合研究者需求之全域最適解。
研究獲致成果如下:第一,模擬退火法可提供有效之分區劃設工具;第二,網格系統設計以2×2公里2之單位網格設計表現最佳,並可於合理時間內求解;第三,對於模擬退火法的演算機制之運算效率提昇,本研究提出最大搜尋次數設定為Lmax= ,可有效降低模擬退火法應用於分區問題之演算時間;輔以初始條件設定策略,可使分區演算品質符合本研究提出之「可接受上限」,並可進一步依據抽樣分配理論求得負向5%最小值區間(最適解信任區間)之「可信任最適解」,提昇分區結果之可信度
In urban study, there are many redistricting problems (RP), which subdivide spaces based on various activity intensities. In the past, such problems usually set their objective functions in accordance with the Euclidian distance from certain points. However, distance is not the only consideration, in stead, market shares is probably the other factor to determine the service areas of some industries, like electronic power, telecommunications or cable TV. Therefore, a new algorithm for market based RP (MRP) is needed.
In this study, to comply with the MRP which has multi-minimal solutions, the simulated annealing algorithm (SA), capable of escaping from a local minimal to seek a global one, is adopted by taking power service MRP as an illustrative case. The study area is represented as a grid system. After estimating the volumes of power consumption for every grid, the study area is partitioned into a given number of contiguously grid regions subject to the total difference of power consumptions of all the regions is minimized. This research focuses on finding appropriate initial values of some parameters of SA to improve computational efficiency while satisfied solutions can still be obtained.
In the illustrative case, it concludes that: (1) SA is confirmed to be a valid algorithm for MRP; (2) A grid size representing a 2×2 KM2 area is recommended; (3) Given a tolerable error, the number of iteration times can be sufficiently set to to have credible solutions with 95% confidence level.
目 錄
第一章 緒論
  第一節 研究動機與目的 1
  第二節 研究內容與範圍 3
  第三節 分區問題定義 4
  第四節 研究方法與流程 4
  第五節 研究架構 6
第二章 文獻回顧
  第一節 傳統規劃模型之限制 7
  第二節 模擬退火法理論基礎 10
  第三節 相關分區研究回顧 14
第三章 研究方法
  第一節 電量分派模式 17
  第二節 最短距離分區法 18
  第三節 模擬退火法 19
  第四節 退火方法特性 23
第四章 電量分派模式
  第一節 前言 25
  第二節 分派準則及分派來源對應 26
  第三節 網格套疊分區 34
  第四節 網格分派結果 36
第五節 最適解可接受上限 39
第五章 分區演算程序與結果分析
  第一節 分區問題之模擬退火演算程序 47
  第二節 程式驗證 51
  第三節 分區結果分析 53
第四節 綜合分析 74
第六章 結論與建議
  第一節 結論 81
  第二節 建議 82
參考文獻 85
附錄
附錄一 分區類別對應之電量分派來源 89

圖 目 錄

圖1-1:研究流程圖 5
圖2-1:區域最適解與全域最適解示意 9
圖2-2:exp(-△E/T )與△E/T之對應關係 11
圖2-3:模擬退火法演算流程 13
圖3-1:Moore八鄰近概念 20
圖3-2:模擬退火法最大搜尋次數及迭代次數圖解 20
圖3-3:接受機率與ΩE/Tf之關係 22
圖4-1:電量分派至不同土地使用分區概念 30
圖4-2:網格電量分派情境 35
圖4-3:8216電量分派網格矩陣 36
圖4-4:8216電量分派值之標準化分配 36
圖4-5:分派查核一 36
圖4-6:分派查核二 36
圖4-7:2080電量分派網格矩陣 37
圖4-8:2080電量分派值之標準化分配 37
圖4-9:945電量分派網格矩陣 37
圖4-10:945電量分派值之標準化分配 37
圖4-11:520電量分派網格矩陣 38
圖4-12:520電量分派值之標準化分配 38
圖4-13:336電量分派網格矩陣 38
圖4-14:336電量分派值之標準化分配 38
圖4-15:8216極端值網格分佈 41
圖4-16:2080極端值網格分佈 42
圖4-17:945極端值網格分佈 43
圖4-18:520極端值網格分佈 44
圖4-19:336極端值網格分佈 45
圖5-1:Moore八鄰近移步策略 48
圖5-2:第一次經驗參數修正之分區結果 55
圖5-3:第二次經驗參數修正之分區結果 57
圖5-4:最大搜尋次數之設定探討 58
圖5-5:正規化參數配合第一次最大搜尋次數修正之分區結果 60
圖5-6:二元樹搜尋最小值概念圖 61
圖5-7:正規化參數配合第二次最大搜尋次數修正之分區結果 62
圖5-8:隨機選取策略測試樣本最小值之分區結果 65
圖5-9:電量排序策略測試樣本最小值之分區結果 68
圖5-10:電量排序分區結果涵蓋範圍–以520最小值為例 69
圖5-11:市鎮中心候選網格位置示意 70
圖5-12:市鎮中心策略測試樣本最小值之分區結果 72
圖5-13:分區結果顯示演算機制可有效涵蓋初始策略之種子網格–以2080最小值為例 73
圖5-14:研究範圍內台電各營業區處之轄區範圍與售電量統計 76
圖5-15:電量排序520分區結果最小值之電量統計 76
圖5-16:市鎮中心2080分區結果最小值之電量統計 76
圖5-17:分區結果與土地使用分區套疊驗證 77
圖5-18:分區結果標準差之標準化分配圖 78
圖5-19:最適解信任區間示意 80

表 目 錄

表4-1:台灣地區1999-2003年行業別售電量統計 26
表4-2:營造業行業別項目 27
表4-3:台灣地區1999-2003「電燈」及「電力」售電結構 27
表4-4:住宅區及商業區分派比例 28
表4-5:四縣市1999-2003年電燈及電力售電結構 29
表4-6:行業別電量分派比例及對應之土地使用分區 31
表4-7:基隆市行業別電量分派結果 32
表4-8:台北市行業別電量分派結果 32
表4-9:台北縣行業別電量分派結果 33
表4-10:桃園縣行業別電量分派結果 33
表4-11:網格電量分派計算表示意 35
表4-12:分派結果統計 39
表4-13:8216電量分派極端值分佈 41
表4-14:2080電量分派極端值分佈 42
表4-15:945電量分派極端值分佈 43
表4-16:520電量分派極端值分佈 44
表4-17:336電量分派極端值分佈 45
表4-18:不同網格矩陣大小之最適解可接受上限 46
表5-1:測試結果一 51
表5-2:測試結果二 52
表5-3:測試結果三 53
表5-4:第一次經驗參數修正之最適解判定結果 54
表5-5:第二次經驗參數修正之最適解判定結果 56
表5-6:正規化參數配合第一次最大搜尋次數修正之最適解判定結果 59
表5-7:正規化參數配合第二次最大搜尋參數修正之最適解判定結果 61
表5-8:隨機選取策略之測試結果 64
表5-9:電量排序策略之測試結果 67
表5-10:電量排序分區結果涵蓋鄉鎮區整理–以520最小值為例 69
表5-11:市鎮中心策略之測試結果 71
表5-12:網格大小判定分析 75
表5-13:電量排序策略符合負向5%最小值區間之分區結果 79
表5-14:市鎮中心策略符合負向5%最小值區間之分區結果 80
台灣經濟研究院(2003)。電業營業區域之研究。經濟部能源委員會。
交通部運輸研究所(1999)。第三期台灣地區整體運輸系統規劃–整體運輸系統供需預測與分析。
林國慶(1995)。農業區劃分與農地變更使用指標之研究與應用。國立台灣大學農業經濟研究所。
林峰田(2002)。科學哲學課程講義。未出版。
林峰田、林建元、孫志鴻、李培芬、李萬凱、與林士弘(2002)〈宮格自動機於土地利用變遷模擬之結合機制〉。《2002中華地理資訊學會年會暨學術研討會》,B-16。台中:中華地理資訊學會。
許志義(1994)《多目標決策》。臺北:五南。
許家源(2003)《應用模擬退火法優選台北盆地水文地質參數最佳分區》。國立台灣大學生物環境系統工程研究所碩士論文。
黃書禮(1991)。台灣地區有線電視分區之研究。行政院有線電視規劃小組。
劉漢奎、王敬甯(2003)〈學區規劃之動態區位分派模式〉。《都市計畫及區域科學學會2003聯合年會暨論文研討會》。新竹:中華大學。
賴俊良(1994)。台灣地區生態分區及環境敏感地劃設之研究。邱穀工程顧問公司。
薛殿啟(1995)《非都市土地農業區劃分之研究》。國立台灣大學農業經濟研究所碩士論文。
藍國賓(1998)《地理資訊系統輔助土地分區劃設之研究–以陽明山國家公園一般管制區為例》。國立台灣大學建築與城鄉研究所碩士論文。
蘇鴻潤(1997)《模擬退火法之參數選擇》。國立台灣工業技術學院機械工程技術研究所碩士論文。
Chang, H. H., & Su, C. T. (2000). Optimization of parameter design: an intelligent approach using neural network and simulated annealing. International Journal of Systems Science, 31(12), 1543-1549.

Cunha, M. C., & Sousa, J. (1999). Water distribution network design optimization: Simulated annealing approach. Journal of Water Resources Planning and Management. 215-221.
Dounis, A.I., & King, R.E. (2003). Optimum fuzzy sliding mode semi-active control of structures subjected to earthquakes. Journal of Intelligent & Fuzzy Systems, 14, 37-47.
Day, P. N., Pachter, R., Gordon, M. S., & Merrill, G. N. (2000). A study of water clusters using the effective fragment potential and Monte Carlo simulated annealing. Journal of Chemical Physics, 112(5).
Gupta, D. K. (2003). A new algorithm to solve vehicle routing problems (VRPs). International Journal of Computer Mathmatics, 80(3), 267-274.
Hedar, A. R., & Fukushima, M. (2002). Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization. Optimization Methods and Software, 17, 891-912.
Hota, P. K., Chakrabarti, R., & Chattopadhyay, P. K. (2000). A simulated annealing-based goal-attainment method for economic emission load dispatch with nonsmooth fuel cost and emission level functions. Electric Machines and Power Systems, 28, 1037-1051.
Jiang, T., Luo. A., Li, X., & Kruggel F. (2003). A comparative study of global optimization approaches to meg source location. Intern. J. Computer Math., 80(3), 305-324.
Simon, H. A. (1977). Models of Discovery. Boston studies in the Philosophy of Science, 54.
Moreno, J. J., Katzgraber, H. G., & Hartmann, A. K. (2003). Finding low-temperature states with Parallel Tempering, Simulated Annealing and simple Monte Carlo. International Journal of Modern Physics C, 14(3), 285-302.
Maropolus, P.G., Mckay, K., Bramall, D.G., Rogers, B., & Chapman, P. (2003). Dynamic and distributed early planning assessment by a hybrid simulated annealing and greedy algorithm. Proceedings of the Institution of Mechanical Engineers–Part B.
Macmillan, W. (2001). Redistricting in a GIS environment: An optimization algorithm using switching-points. Journal of Geograph System, 3, 167-180.

Maulik, U., & Pakhira, M. K. (2001). Clustering using simulated annealing with probabilistic redistribution. International Journal of Pattern Recognition and Artificial Intelligence, 15(2), 269-285.
Nelson, J. (2003). Forest-level models and challenges for their successful application. Can. J. For. Res., 33, 422-429.
Purushothama, G. K., Narendranath, U. A., & Jenkins, L. (2003). Unit commitment using a stochastic extended neighborhood search. IEE Proc.-Gener. Transm. Distrib., 150(1).
Roberts, G. O., & Rosenthal, J. S. (2001). Markov chains and de-initializing process. Board of the Foundation of the Scandinavian Journal of Statistics, 28, 489-504.
Salter, L. A., & Pearl, D. K. (2001). Stochastic search strategy for estimation of maximum likelihood phylogenetic trees. Systematic Biology, 50(1), 7-17.
Tropsha, A., & Zheng, W. (2002). Rational principles of compound selection for combinatorial library design. Combinatorial Chemistry & High Throughput Screening, 5(2), 111-123.
Wan, B. W., & Wang, T. (2000). Tuning strategies in constrained simulated annealing for nonlinear global optimization. International Journal on Artificial Intelligence Tools, 9(1), 3-25.
Wey, Wann-Ming (2003). Dynamic school facility location with time dependent demand: The progressive p-Median problem. In International Symposium on Urban Planning, 2003 (pp.B1-1-1 - B1-1-9). Taipei: NTU.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔