A Clustering Approach for <scp>NSGA</scp> ‐ <scp>II</scp> in Political Redistricting

ABSTRACT Political redistricting is a complex, multi‐objective problem that has been extensively studied. One approach to solve this geographical partitioning problem is to use multiobjective genetic algorithms applied to the adjacency graph of precincts. Following the work of Vanneschi et al., we develop an algorithm using a Non‐Dominated Sorting Genetic Algorithm (NSGA‐II) to build electoral plans in the state of South Carolina. Our work (which we name Cluster‐NSGA‐II) utilizes a novel clustering approach to breed children rather than the standard crossover step. We find that this approach is competitive with other similar algorithms in terms of both solution diversity and Pareto optimality.