Multi-objective Optimization for Establishing Geographical Boundaries and Associations Using Evolutionary Algorithms and Collaborative and Adversarial Intelligent Agents

Abstract

Evolutionary Algorithms (EAs) are useful in solving prohibitively large search problems in a limited amount of time. Where even the most efficient standard search algorithms can become unwieldy as the solution space expands, such algorithms can provide a near-optimal solution in a fraction of the time.

The application of both evolutionary and more traditional search algorithms to ge- ographic districting problems is complicated both by the need to satisfy multiple, often contradictory, quality heuristics and also by the need for geographic connectedness. Because of this connectedness constraint, the ability of Evolutionary Algorithms to recombine, or evolve, existing solutions with the aim of creating even better solutions is hampered by the high likelihood of such changes producing an unconnected, and therefore invalid, solution.

This dissertation explores the difficulties involved in solving geographic districting prob- lems with a contiguity constraint by first evaluating performance on real-world data for a small municipal area. Next, two key sub-algorithms — called Neighborhood Mutation and Local Repair — are introduced that can vastly reduce the incidence of invalid solutions in the population, and these sub-algorithms are objectively evaluated in a sandbox environ- ment. Then, the full Evolutionary Algorithm, including Neighborhood Mutation and Local Repair, are executed on a statewide scale and its effectiveness is observed for independently satisfying multiple quality heuristics.

Finally, we assess the efficacy of the Evolutionary Algorithm to solve districting problems with multiple, sometime conflicting, quality heuristics. First, a traditional weighted multi- objective heuristic function is evaluated. Next, the heuristic evaluation task is divided among multiple, independent agents tailored for a specific quality attribute. These agents, which are formed into separate pools for each heuristic, then collaborative to produce an objective value for the entire solution.

Results show that for districting problems with a geographic contiguity constraint, a generic Evolutionary Algorithm can produce high-quality candidate solutions, but the progress of such algorithms is hindered by the increasing percentage of invalid solutions that are produced over time. We show that the Neighborhood Mutation and Local Repair algo- rithms are each highly effective in independently preventing invalid solutions from entering the population — and are even more effective when combined — in both sandbox and real- world scenarios, thus allowing the Evolutionary Algorithm to converge toward more nearly optimal solutions in a similar or even shorter amount of time.

Finally, we show that multiple, independent agents can separately evaluate the quality of part of a multi-objective heuristic and then collaboratively combine those assessments into a single fitness value that can perform comparably to a traditional, weighted multi-objective heuristic function.