1. NCCU Academic Hub
  2. 學術產出
  3. College of Informatics
  4. Theses
  5. Item

學術產出-Theses

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

  • No doi shows Citation Infomation
題名 應用基因演算法重劃選區
Electoral Redistricting In Genetic Algorithm
作者 李俊瑩
貢獻者 何瑁鎧
李俊瑩
關鍵詞 選區重劃
基因演算
位能場
electoral redistrictiing
genetic algorithm
potential field
日期 2007
上傳時間 17-Sep-2009 13:56:37 (UTC+8)
摘要 　　為因應選舉法規變更或時代變遷，往往必須重劃選區。傳統上，選區重劃都是以人工方式劃分。以人工方式劃分選區固然能考慮較多因素，包括最難數據化的人文因素，但人力成本高，也容易引起爭議。
本研究中，我們提出一個有系統的方式以自動劃分選區。主要的考慮因素為選區之人口數、選區形狀及二級行政區之完整性。我們的劃分方式主要分為三部份：產生起始選區、二級行政區分割修正及選區形狀調整。在產生起始選區步驟，我們根據位能場的觀念，劃分出人口數符合標準之起始選區，再經過行政區分割修正以維持二級行政區之完整性，最後採用基因演算法來調整選區形狀，以避免傑利蠑螈的狀況。
我們以台北市為例，來闡述我們的方法，實做的結果顯示我們的方法能有效的做正確的選區重劃。
Electoral redistricting is normally required when election regulations changed. Traditionally, electoral redistricting is done manually. Though manual redistricting could consider humane or cultural factor, which may be very difficult to be included in the computation model, the cost of manual redistricting normally is high. In addition, manual redistricting may induce controversial issues.
In this thesis, we propose a systematic way that could do the electoral redistricting automatically. Our major considerations are: (1) the population must be evenly partitioned, within an acceptable error; (2) the shape of the redistricted region is reasonably good; (3) the integrity of the second level district must be kept reasonably well. Our method consists of three major parts: initial district production, district’s integrity fixing, and district reshaping. The concept of potential is used in producing the initial districts. A heuristic is used in fixing the district’s integrity. And, finally, Genetic Algorithm is used in district reshaping.
We use Taipei City as an example to illustrate our idea. Experimental results show that our method can do electoral redistricting effectively.
參考文獻 [1] 何瑁鎧、李俊瑩、劉克壙與游清鑫，「選區重劃之分析與探討」，第十一屆人工智慧與應用研討會，高雄，民國94年12月。
[2] 柯義峰與鄭道明，「應用基因演算法於營建作業流程模擬」，私立朝陽科技大學營建工程研究所碩士論文，2004。
[3] 謝相慶，「單一選舉區界線劃分及其政治效應─以我國第七屆立法委員選舉為例」，2004年台灣政治學會年會「關鍵年代與多元政治」學術研討會論文，民國94年。
[4] 潘誠財，「從選區劃分論我國立法委員選制改革」，復興崗學報第七十二期，民國91年。
[5] 「第七屆立法委員直轄市、縣（市）選舉區劃分原則」，中華民國中央選舉委員會，民國94年8月。
[6] Chang Kang-tsung. 2002. Introduction to Geographic Information Systems, McGraw-Hill Higher Education.
[7] M.de Berg, M.van Kreveld, M.Overmars and O.Schwarzkopf. 2000. Computational Geometry: Algorithms and Applications, Springer-Verlag
[8] Randy L. Haupt and Sue Ellen Haupt. 2004. Practical Genetic Algorithms.
[9] dBase format, http://www.inprise.com
[10] ESRI shape file, http://www.esri.com
描述 碩士
國立政治大學
資訊科學學系
93753011
96
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0093753011
資料類型 thesis
dc.contributor.advisor 何瑁鎧zh_TW
dc.contributor.author (Authors) 李俊瑩zh_TW
dc.creator (作者) 李俊瑩zh_TW
dc.date (日期) 2007en_US
dc.date.accessioned 17-Sep-2009 13:56:37 (UTC+8)-
dc.date.available 17-Sep-2009 13:56:37 (UTC+8)-
dc.date.issued (上傳時間) 17-Sep-2009 13:56:37 (UTC+8)-
dc.identifier (Other Identifiers) G0093753011en_US
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/32651-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 93753011zh_TW
dc.description (描述) 96zh_TW
dc.description.abstract (摘要) 　　為因應選舉法規變更或時代變遷，往往必須重劃選區。傳統上，選區重劃都是以人工方式劃分。以人工方式劃分選區固然能考慮較多因素，包括最難數據化的人文因素，但人力成本高，也容易引起爭議。
本研究中，我們提出一個有系統的方式以自動劃分選區。主要的考慮因素為選區之人口數、選區形狀及二級行政區之完整性。我們的劃分方式主要分為三部份：產生起始選區、二級行政區分割修正及選區形狀調整。在產生起始選區步驟，我們根據位能場的觀念，劃分出人口數符合標準之起始選區，再經過行政區分割修正以維持二級行政區之完整性，最後採用基因演算法來調整選區形狀，以避免傑利蠑螈的狀況。
我們以台北市為例，來闡述我們的方法，實做的結果顯示我們的方法能有效的做正確的選區重劃。		zh_TW
dc.description.abstract (摘要) Electoral redistricting is normally required when election regulations changed. Traditionally, electoral redistricting is done manually. Though manual redistricting could consider humane or cultural factor, which may be very difficult to be included in the computation model, the cost of manual redistricting normally is high. In addition, manual redistricting may induce controversial issues.
In this thesis, we propose a systematic way that could do the electoral redistricting automatically. Our major considerations are: (1) the population must be evenly partitioned, within an acceptable error; (2) the shape of the redistricted region is reasonably good; (3) the integrity of the second level district must be kept reasonably well. Our method consists of three major parts: initial district production, district’s integrity fixing, and district reshaping. The concept of potential is used in producing the initial districts. A heuristic is used in fixing the district’s integrity. And, finally, Genetic Algorithm is used in district reshaping.
We use Taipei City as an example to illustrate our idea. Experimental results show that our method can do electoral redistricting effectively.		en_US
dc.description.tableofcontents 第一章 緒論 1
1.1 前言 1
1.2 研究動機 2
1.3 問題描述 3
第二章 相關文獻 4
2.1 選區劃分 4
2.2 基因演算法之介紹 6
第三章 選區重劃系統架構 12
第四章 地圖資料前處理 16
4.1 地圖資料格式 17
4.2 修正地圖資料 19
4.3 範圍框 19
4.4 建立相鄰關係 19
第五章 產生起始選區 20
5.1 起始選區劃分方式 21
5.2 以鄉村包圍城市法劃分起始選區 22
5.2.1 鄉村包圍城市原則 23
5.2.2 決定起始點 23
5.2.3 建立村里位能值 25
5.2.4 開始劃分起始選區 25
5.2.5 起始選區完整性修正 26
5.3 劃分結果 26
5.3.1 第一組劃分結果 26
5.3.2第二組劃分結果 28
5.3.3 第三組劃分結果 30
5.4 劃分結果比較 31
第六章 行政區分割修正演算 34
6.1 挑選欲進行修正之行政區 35
6.2 減少行政區中所包含之選區數 35
6.3 選區修正結果 37
6.3.1 第一組修正結果 38
6.3.2 第二組修正結果 39
6.3.3 第三組修正結果 41
6.4 修正結果討論 42
第七章 應用基因演算最佳化選區形狀 44
7.1 以基因演算調整選區形狀之流程 44
7.2 進行編碼 45
7.3 選區適存函式 46
7.4 基因演算─選取及交配 47
7.5 終止條件 48
7.6 選區調整結果 49
7.6.1 第一組調整結果 49
7.6.2第二組調整結果 51
7.6.3第三組調整結果 53
7.7調整結果討論 55
第八章 結論與討論 57
8.1 結論 57
8.2 討論及未來展望 58
參考資料 60		zh_TW
dc.format.extent 80390 bytes-
dc.format.extent 92150 bytes-
dc.format.extent 126395 bytes-
dc.format.extent 93842 bytes-
dc.format.extent 205634 bytes-
dc.format.extent 598783 bytes-
dc.format.extent 264725 bytes-
dc.format.extent 314932 bytes-
dc.format.extent 1041023 bytes-
dc.format.extent 690549 bytes-
dc.format.extent 899380 bytes-
dc.format.extent 249324 bytes-
dc.format.extent 103244 bytes-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0093753011en_US
dc.subject (關鍵詞) 選區重劃zh_TW
dc.subject (關鍵詞) 基因演算zh_TW
dc.subject (關鍵詞) 位能場zh_TW
dc.subject (關鍵詞) electoral redistrictiingen_US
dc.subject (關鍵詞) genetic algorithmen_US
dc.subject (關鍵詞) potential fielden_US
dc.title (題名) 應用基因演算法重劃選區zh_TW
dc.title (題名) Electoral Redistricting In Genetic Algorithmen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] 何瑁鎧、李俊瑩、劉克壙與游清鑫，「選區重劃之分析與探討」，第十一屆人工智慧與應用研討會，高雄，民國94年12月。zh_TW
dc.relation.reference (參考文獻) [2] 柯義峰與鄭道明，「應用基因演算法於營建作業流程模擬」，私立朝陽科技大學營建工程研究所碩士論文，2004。zh_TW
dc.relation.reference (參考文獻) [3] 謝相慶，「單一選舉區界線劃分及其政治效應─以我國第七屆立法委員選舉為例」，2004年台灣政治學會年會「關鍵年代與多元政治」學術研討會論文，民國94年。zh_TW
dc.relation.reference (參考文獻) [4] 潘誠財，「從選區劃分論我國立法委員選制改革」，復興崗學報第七十二期，民國91年。zh_TW
dc.relation.reference (參考文獻) [5] 「第七屆立法委員直轄市、縣（市）選舉區劃分原則」，中華民國中央選舉委員會，民國94年8月。zh_TW
dc.relation.reference (參考文獻) [6] Chang Kang-tsung. 2002. Introduction to Geographic Information Systems, McGraw-Hill Higher Education.zh_TW
dc.relation.reference (參考文獻) [7] M.de Berg, M.van Kreveld, M.Overmars and O.Schwarzkopf. 2000. Computational Geometry: Algorithms and Applications, Springer-Verlagzh_TW
dc.relation.reference (參考文獻) [8] Randy L. Haupt and Sue Ellen Haupt. 2004. Practical Genetic Algorithms.zh_TW
dc.relation.reference (參考文獻) [9] dBase format, http://www.inprise.comzh_TW
dc.relation.reference (參考文獻) [10] ESRI shape file, http://www.esri.comzh_TW