傳統之選區劃分多採用人工方式進行，不但費時耗力，同時不容易維持公平公正之原則，導致客觀性受扭曲而產生爭議。歷史上透過選區劃分來操弄選舉最有名的例子首推美國麻州的傑利蠑螈劃分方式，因此後人在選區劃分時必須堅守公平客觀之原則，自動化之選區劃分應運而生。以電腦科技自動劃分選區不但省時省力，同時也能滿足公平公正等客觀的選區劃分要求。 過去我們提出了一系列的選區劃分方法，著重於產生大量的劃分解集合，並從中挑選形狀較佳之解，卻沒有考慮到維持鄉鎮市層級行政區之完整性。本論文中，我們提出了一套新的選區劃分方式，除了考慮鄉鎮市層級行政區之完整性外，同時考慮選取較佳之起始點，以獲得較佳之選區形狀，成功的劃分出良好的選區。 我們首先從挑選較佳之起始點，透過質心范諾圖的觀念劃分出形狀較完整之初始選區，然後修正各選區之人口至合理的誤差範圍內，再進行鄉鎮市層級行政區分割數之修正，以避免該層級行政區被過渡分割。由於行政區分割數修正可能影響並擴大人口誤差，為確保人口誤差維持在合理範圍內，我們進行第二次人口修正，以免人口誤差過大，隨後進行形狀調整以提高凸包面積比，最後再度進行鄉鎮市層級行政區分割數修正，儘量少分割鄉鎮市層級之行政區域。 實作中我們以台北市為例，採用四組不同的起始點進行選區劃分，結果都十分良好。我們將中選會公佈之劃分法與這四組結果進行比較，中選會的劃分方式在行政區分割數上比我們的結果好，但在人口誤差與形狀上都不及我們的劃分方式優異。另外我們也選取行政中心為起始點進行劃分並將結果與中選會的結果比較，也獲得相同的結論。至於選情預估方面，我們也證實了不同的選區劃分方式的確將造成選舉結果之改變。 / Traditionally, electoral redistricting was done manually which was time consumming, inefficient, and hard to maintain fairness. One of the most famous biased electoral redistricting in human history was proposed by Elbridge Gerry in 1812, socalled the Gerrymandering districting. After that, fairness and objectivity are required in every electoral redistricting and, hence, come to the era of automatic redistricting. We have proposed a series of automatic electoral redistricting mechanisms that were emphasized on producing huge amount of feasible solutions and selecting the right solutions from them. However, we did not consider avoiding over partitioning a county in the proposed mechanisms. In this thesis, we developed a new mechanism for electoral redistricting which not only avoiding the over partitioning problem but also start the redistricting by chosing a better set of seeds. Using a set of better seeds, we can get a better set of initial electoral districts through the help of centroidal Voronoi diagram. Then, we adjust the population in every district followed by reducing the partitioning number of each county. Since adjusting the county partitioning number may violate the population requirement of the districts, we shall check the population requirement of all the districts again before checking compactness of all the districts. Finally, we applied the county partitioning number reduction process once more to reduce the partitioning number as many as we can. In the experiments, we used Taipei city to verify our mechanism. Four set of seeds were used to generate different redistricting solutions. We compared our results with the result announced by the Central Election Commission (CEC) and found that CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also used the administrative districts’ center as the seeds to generate the fifth redistricting solutions and obtained the same conclusion, i. e., CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also demonstrated that different redistricting results may change the election outcomes.

為因應選舉法規變更或時代變遷，往往必須重劃選區。傳統上，選區重劃都是以人工方式劃分。以人工方式劃分選區固然能考慮較多因素，包括最難數據化的人文因素，但人力成本高，也容易引起爭議。 本研究中，我們提出一個有系統的方式以自動劃分選區。主要的考慮因素為選區之人口數、選區形狀及二級行政區之完整性。我們的劃分方式主要分為三部份：產生起始選區、二級行政區分割修正及選區形狀調整。在產生起始選區步驟，我們根據位能場的觀念，劃分出人口數符合標準之起始選區，再經過行政區分割修正以維持二級行政區之完整性，最後採用基因演算法來調整選區形狀，以避免傑利蠑螈的狀況。 我們以台北市為例，來闡述我們的方法，實做的結果顯示我們的方法能有效的做正確的選區重劃。 / 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.