A Knowledge-based Evolution Algorithm approach to political districting problem

The political districting problem is to study how to partition a comparatively large zone into many minor electoral districts. In our previously works, we have mapped this political problem onto a q-state Potts model system by using statistical physics methods. The political constraints (such as contiguity, population equality, etc.) are transformed to an energy function with interactions between sites or external fields acting on the system. Several optimization algorithms such as simulated annealing method and genetic algorithm have been applied to this problem. In this report, we will show how to apply the Knowledge-based Evolution Algorithm (KEA) to the problem. Our test objects include two real cities (Taipei and Kaohsiung) and the simulated cities. The results showed the KEA can reach the same minimum which has been found by using other methods in each test case.