2007年国际大学生数学建模竞赛A题获奖论文（一）[精品专业论文].pdfVIP

GETTING THE VOTES TO COUNT: A GENETIC ALGORITHM FOR NON-PARTISAN LEGISLATIVE DISTRICTING Abstract. For decades, district gerrymandering has given incumbents an unfair advan- tage over their opponents, resulting in artificially high reelection rates. This gerrymandering has become so severe that Iowa [1] has implemented a non- partisan district-drawing method, and other states are sure to follow. Such efforts may have many different objectives in creating districts. In this paper we describe a redistricting algorithm which is flexible enough to accommodate a wide variety of district criteria. We use a genetic algorithm, wherein an arbi- trary user-selected number of districts compete for population on a map of the state region. By adjusting the probability formulae for district reassignment events, we can tailor our algorithm to create districts satisfying a wide range of criteria. This algorithm is then tested on the state of New York, by requiring it to produce district shapes that maximize the interior regions of the districts in proportion to their boundaries. The resulting district divisions produced by the algorithm clearly exhibit this property. After presenting the results of our tests, we will discuss the merits and defects of our chosen algorithm, along with its possibility for extension. Date: February 11, 2007. 1 Team 1035 2 Contents 1. Introduction 2 2. Specifications