[EM] Deterministic Districting

[bql at bolson.org]

Wow, convergent evolution. Just a couple days ago I turned my attention to 
redistricting.

On Fri, 7 Jan 2005, Dr.Ernie Prabhakar wrote:

> This brings us back to the question of automated redistricting. We've often 
> discussed how the 'fairest' algorithm would use a measure such as 
> "minimizing lanes of traffic cut by the circumference" by combining census 
> tracts while ensuring equal-population districts.   Its easy to get an 
> approximate answer from this criteria using various statistical means, but is 
> there any computationally feasible way to get a *deterministic" answer that 
> is at least near-optimal?  Otherwise, I fear that people will either create 
> pseudo-statistical results, or challenge truly random results due to their 
> fear of (random) biases.

In this case, I break down and use a randomized algorithm. I wrote a 
genetic-algorithm style solver for districting. It's fitness function is a 
combination of the moment of inertia of the districts (distance from 
center of district times population for each part of each district) and 
the variance of population sizes for the districts. I didn't make equal 
population a hard rule, just something to optimize for and it turned out 
to be pretty easy to evolve for.

My first run created 80 California State Assembly districts based on 1757 
zip code blocks. This is definitely suboptimal, but satisfied me as a 
proof of concept. The result is here:

http://bolson.org/voting/dCAassembly2000_new.svgz
http://bolson.org/voting/dCAassembly2000_new.png

I also downloaded the full 2000 census data for California. There are 
344356 populated census blocks in that data set, or an average of about 
100 people per block. This data set is currently calculating. Maybe I'll 
have results by Monday. :-)


Brian Olson
http://bolson.org/