划分彩色网格
Partitioning a colored grid
我想划分网格。这意味着给定一个带有黄色和红色正方形的 n x m 网格，我想以这样一种方式划分网格，即黄色将成为尽可能多的分区中的主要颜色，如下图所示：
所有分区必须是连续的，相同数量的方块，并且所有方块都将被着色（尽管如果算法可以推广到具有一些未着色的方块的网格，那就太棒了）。
我什至不确定如何解决 'algorithmitizing' 这个问题，过去暴力破解每个可能的分区，这本身就足够困难，而且效率低得令人难以置信。
完成此任务的最佳方法是什么？
tl;dr：使用模拟退火，在选区之间交换选民。
底部的演示可让您执行交换步骤（随机进化）并针对不公平区域进行优化（退火）
常规优化
我们可以将其定义为优化问题，我们试图最大化选区的数量
红色获胜并最小化蓝色获胜的地区数量。
让我们正式化：
function heuristic(state) {
return state.districts_that_red_wins - state.districts_that_blue_wins;
}
其中 state 是选民对选区的分配。
这会起作用，但可以稍微改进一下。
让我们引入 wasted votes 的概念来推动我们的优化朝着正确的方向发展。
我们希望最大化浪费的蓝色选票并最小化浪费的红色选票。
由于每个选区有 10 名选民，因此我武断地将它们加权为一个选区的 1/10。
这给了我们一个函数来最大化：
function heuristic(state) {
let {red_wins, blue_wins, tied, wasted_red_votes, wasted_blue_votes} = get_winners(state, voters);
return red_wins - blue_wins - 0.1 * wasted_red_votes + 0.1 * wasted_blue_votes;
}
您可能想要优化其他内容，例如区的紧凑性。您可以将这些添加到启发式函数中。
模拟退火
让我们选择一个优化算法来优化state。
我们受到一些限制，很难生成符合这些条件的随机地图。
而且我怀疑没有蛮力就不可能找到最佳的区域分配，这是不可能的。
因此，让我们使用一种算法来迭代改进我们的解决方案。
我喜欢 simulated annealing 因为它易于实现和理解，并且通过防止我们陷入早期局部最优而比爬山法表现得更好。
我的温度函数简直就是max(0.8 - iterations/total_iterations, 0)。一开始，20% 的时间我们会选择一个新的状态，当且仅当它更好；其他 80% 无论如何我们都会采用新状态。
这慢慢变得更像爬山，直到我们完成计算预算的 80%，然后我们只有在它提高我们的启发式得分时才改变状态。 80%的选择完全是随意的。
要实现 SA，我们需要一个初始状态（或一种生成它的方法）。为简单起见，我将使用 "Perfect Representation" 作为初始状态，主要是因为我不知道如何生成随机连接的、大小相等的区域。
我们还需要一种对状态进行微小更改的方法。我将在下一节中讨论这个问题。
最后，我们需要一种对状态进行评分的方法。让我们使用上一节中的函数，因为它的计算成本非常低。
如果您有兴趣，请查看 anneal 函数，或者直接阅读维基百科文章。
状态演化
对于这个问题，给定一个状态，我们需要找到另一个不会对启发式得分产生太大影响的相似状态，看看我们是否在朝着正确的方向前进。
我选择从两个不同的区中找到一对点并将它们交换。
我们需要维护一些不变量：
- 保持所有地区连续
- 保持所有区的大小相同
第二个很简单：总是交换点数，从不（永久）从一个地区分配到另一个地区。
第一个比较棘手，我们需要简要介绍一下图论。 连接点（见图）是一个在不平分图形的情况下无法删除的点。
对我们来说，这意味着我们不能在不使地区不连续的情况下删除关节点。
一旦我们有了一个可以删除的点，我们需要确保将它添加到与其相邻的区域中。这很简单。
由于我们在一个网格上，所有的区域必须是连续的，我们可以只考虑一个点的直接邻居来判断它是否是一个关节点。
如果你看不到这个，那也不是特别重要，你可以使用通常在图表上起作用的 algorithm 。
我发现网格版本更容易，因为它不涉及递归。
如果您有兴趣，请参阅 is_swappable 函数。这就是演示中 "Randomly evolve" 按钮的作用。
高层，我们用于发展状态的代码应该如下所示：
function evolve_state() {
randomly pick a source district
randomly pick a non-articulation point, source_point, from source_district
for each neighbour of the articulation point
if the neighbour is in a different district target_district
temporarily remove source_point from source_district and add it to target_district
if any articulation point (other than source point), target_point, in target_district is adjacent to source_district
swap target_point and source_point
return;
restore source_point
}
注意：我以一种随机遍历所有 source_district、source_point、neighbour、target_district 和 target_point 的方式实现了这一点，因为我不确定这会有多稀疏。
如果你准确地实现这个伪代码，你可能需要比我使用更多的迭代来收敛到一个解决方案。
如果您有兴趣，请参阅 evolve_state。
我没有调出的所有函数都是实用函数或绘图函数。
演示
现在进行演示。 :)
（将 Lodash 用于实用函数，将 Mithril 用于 DOM 操作）
如果你想玩这个，使用我的 Plunker 可能更容易：http://plnkr.co/edit/Bho4qhQBKRShXWX8fHmt。
const RED = 'R';
const BLUE = 'B';
const VOTERS_PER_DISTRICT = 10;
const neighbours = [{x: 1, y: 0}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 0, y: -1}];
/* UTILITY FUNCTIONS */
/**
Create a generator that starts at a random point p, 0 <= p < max
The generator will iterate over values p, p+1, ... max, 0, ... p-1
*/
function* cyclic_generator(max) {
let start = _.random(max);
for (let i=0; i<max; i++) {
yield (i + start) % max;
}
}
/**
Return grid[x][y] if x and y are within grid. Otherwise return undefined
*/
function grid_get(grid, x, y) {
if(_.isUndefined(grid[x])) {
return undefined;
}
else {
return grid[x][y];
}
}
/** Generates a 2d array red and blue voters */
function generate_voters() {
return _.times(5, x => _.times(10, () => {return {vote: x > 2 ? RED : BLUE, district_vote: 0xffffff}}))
}
/** Generate an initial state */
function generate_initial_state() {
return _.range(5).map(x => _.range(10).map(y => {return {x, y}}));
}
/**
Randomly swap two squares in the grid between two districts.
The new square to be added must be connected to the district, and the
old square must not break another district in two
*/
function evolve_state(state) {
state = _.cloneDeep(state);
// Create a grid with the district number
let point_to_district = _.range(5).map(x => _.range(10).map(y => -1));
state.forEach((district, i) => district.forEach(({x, y}) => point_to_district[x][y] = i));
// swap a point from source_district to target_district.
// then swap a point from target_district to source_district.
for(let source_district_idx of cyclic_generator(state.length)) {
let source_articulation_points = state[source_district_idx].filter(point => is_swappable(point_to_district, point, source_district_idx));
for(let source_point_idx of cyclic_generator(source_articulation_points.length)) {
let source_point = source_articulation_points[source_point_idx];
for(let neighbour_idx of cyclic_generator(4)) {
let neighbour = neighbours[neighbour_idx];
let target_district_idx = grid_get(point_to_district, source_point.x + neighbour.x, source_point.y + neighbour.y);
if (_.isUndefined(target_district_idx) || target_district_idx == source_district_idx) {
continue;
}
// swap the source point
point_to_district[source_point.x][source_point.y] = target_district_idx;
_.remove(state[source_district_idx], ({x, y}) => x == source_point.x && y == source_point.y);
// we don't add the point the the target array yet because we don't want to swap that point back
// try to find a point in target_district that we can move to source_district
let target_articulation_points = state[target_district_idx].filter(point => is_swappable(point_to_district, point, target_district_idx));
for(let target_point_idx of cyclic_generator(target_articulation_points.length)) {
let target_point = target_articulation_points[target_point_idx];
for(let n of neighbours) {
if(grid_get(point_to_district, target_point.x + n.x, target_point.y + n.y) === source_district_idx) {
// found a point that we can swap!
// console.log('swapping points!', source_point, target_point);
_.remove(state[target_district_idx], ({x, y}) => x == target_point.x && y == target_point.y);
state[target_district_idx].push(source_point);
state[source_district_idx].push(target_point);
return state;
}
}
}
// unswap source point since we were unsuccessful
point_to_district[source_point.x][source_point.y] = source_district_idx;
state[source_district_idx].push(source_point);
}
}
}
throw 'Could not find any states to swap' // this should never happen, since there will always be the option of reversing the previous step
}
/*
Return whether a point can be removed from a district without creating disjoint districts.
In graph theory, points that cannot be removed are articulation points.
For a general algorithm, see:
My version takes advantage of the fact that we're on a grid and that all the districts must be continuous,
so we can consider only the immediate neighbours of a point.
*/
function is_swappable(grid, p, district) {
// if the the point is not even in this district, it makes no sense for this to consider this point at all
if(grid[p.x][p.y] != district) {
return false;
}
// if two opposite edges are part of this district, this is an articulation point
// .x. x is an articulation point
// Exception:
// .x. x is not an articulation point
// ...
if (grid_get(grid, p.x+1, p.y) === district && grid_get(grid, p.x-1, p.y) === district && grid_get(grid, p.x, p.y+1) !== district && grid_get(grid, p.x, p.y-1) !== district) {
return false;
}
if (grid_get(grid, p.x, p.y+1) === district && grid_get(grid, p.x, p.y-1) === district && grid_get(grid, p.x+1, p.y) !== district && grid_get(grid, p.x-1, p.y) !== district) {
return false;
}
// check if any corners are missing:
// .x x is not an articulation point .x x is an articulation point
// .. .
for(let i = 0; i < 4; i++) {
let nx = neighbours[i].x;
let ny = neighbours[i].y;
let nx2 = neighbours[(i+1)%4].x;
let ny2 = neighbours[(i+1)%4].y;
if (grid_get(grid, p.x+nx, p.y+ny) === district && grid_get(grid, p.x+nx2, p.y+ny2) === district && grid_get(grid, p.x+nx+nx2, p.y+ny+ny2) !== district) {
return false;
}
}
return true;
}
/** Count how many districts each party wins */
function get_winners(state, voters) {
let red_wins = 0;
let blue_wins = 0;
let tied = 0;
let wasted_red_votes= 0; // see https://en.wikipedia.org/wiki/Wasted_vote
let wasted_blue_votes = 0;
state.forEach(district => {
let counts = _.countBy(district.map(({x, y}) => voters[x][y].vote))
if ((counts[BLUE] || 0) > (counts[RED] || 0)) {
blue_wins++;
wasted_blue_votes += (counts[BLUE] || 0) - VOTERS_PER_DISTRICT / 2 - 1;
wasted_red_votes += (counts[RED] || 0);
}
else if ((counts[RED] || 0) > (counts[BLUE] || 0)) {
red_wins++;
wasted_red_votes += (counts[RED] || 0) - VOTERS_PER_DISTRICT / 2 - 1;
wasted_blue_votes += (counts[BLUE] || 0);
}
else {
tied++;
}
});
return {red_wins, blue_wins, tied, wasted_red_votes, wasted_blue_votes};
}
/* GUI */
/* Display a grid showing which districts each party won */
function render_districts(state, voters) {
let red_districts = 0;
let blue_districts = 0;
let grey_districts = 0;
// Color each district
state.forEach(district => {
let counts = _.countBy(district.map(({x, y}) => voters[x][y].vote))
let district_color;
if ((counts[BLUE] || 0) > (counts[RED] || 0)) {
district_color = 'blue' + blue_districts++;
}
else if ((counts[RED] || 0) > (counts[BLUE] || 0)) {
district_color = 'red' + red_districts++;
}
else {
district_color = 'grey' + grey_districts++;
}
district.map(({x, y}) => voters[x][y].district_color = district_color);
});
return m('table', [
m('tbody', voters.map(row =>
m('tr', row.map(cell => m('td', {'class': cell.district_color}, cell.vote)))
))
]);
}
/** Score a state with four criteria:
- maximize number of red districts
- minimize number of blue districts
- minimize number of red voters in districts that red wins
- maximize number of blue voters in districts that blue wins
The first two criteria are arbitrarily worth 10x more than the latter two
The latter two are to nudge the final result toward the correct solution
*/
function heuristic(state) {
let {red_wins, blue_wins, tied, wasted_red_votes, wasted_blue_votes} = get_winners(state, voters);
return red_wins - blue_wins - 0.1 * wasted_red_votes + 0.1 * wasted_blue_votes;
}
/**
Optimization routine to find the maximum of prob_fcn.
prob_fcn: function to maximize. should take state as its argument
transition: how to generate another state from the previous state
initialize_state: a function that returns an initial state
iters: number of iterations to run
Stolen from my repo here: https://github.com/c2huc2hu/automated-cryptanalysis/blob/master/part3.js
*/
function anneal(prob_fcn, transition, initialize_state, seeds=1, iters=1000) {
let best_result = initialize_state();
for(let i=0; i<seeds; i++) {
let curr_state = initialize_state();
let curr_cost = prob_fcn(curr_state);
// perform annealing. do a few extra steps with temp=0 to refine the final solution
for(let j=0; j<iters; j++) {
let candidate_state = transition(curr_state);
let candidate_cost = prob_fcn(candidate_state);
temp = 0.8 - j / iters;
if(candidate_cost >= curr_cost || Math.random() < temp) {
curr_state = candidate_state;
curr_cost = candidate_cost;
}
}
if(prob_fcn(curr_state) > prob_fcn(best_result)) {
best_result = curr_state;
}
}
return best_result;
}
let voters = generate_voters();
let state = generate_initial_state();
// main rendering code: this code renders the UI
m.mount(document.getElementById('actions'), {view: function() {
return m('div', [
m('button', {onclick: () => state = generate_initial_state()}, 'Reset'),
m('button', {onclick: () => state = evolve_state(state)}, 'Randomly evolve'), // randomly evolves
m('br'),
m('label', {'for': 'radio-blue'}, 'Gerrymander for blue'),
m('input', {type: 'radio', name: 'heuristic', value: 'blue', id: 'radio-blue'}),
m('label', {'for': 'radio-red'}, 'Gerrymander for red'),
m('input', {type: 'radio', name: 'heuristic', value: 'red', id: 'radio-red'}),
m('br'),
m('label', {'for': 'anneal-steps'}, 'Anneal steps: '),
m('input', {id: 'anneal-steps', type: 'number', value: '500'}),
m('button', {onclick: function() {
let minimize = document.getElementById('radio-red').checked;
let _heuristic = minimize ? heuristic : state => -heuristic(state)
let new_state = anneal(_heuristic, evolve_state, generate_initial_state, 1, parseInt(document.getElementById('anneal-steps').value));
if(_heuristic(new_state) > _heuristic(state)) {
state = new_state;
}
else {
console.log('found no better solutions')
}
}}, 'Anneal!'),
]);
}});
// This renders the grid
m.mount(document.getElementById('grid'), {
view: function() {
return render_districts(state, voters)
}
});
// state = anneal(heuristic, evolve_state, generate_initial_state, 5, 1000);
document.getElementById('radio-red').checked = true;
m.redraw();
/* Layout */
table {
border: solid 1px black;
}
td {
padding: 5px;
border: solid 1px black;
}
button {
margin: 10px;
}
p {
max-width: 500px;
}
/* Colour classes. In hindsight, this wasn't a good idea */
.red0 {
background-color: red;
}
.red1 {
background-color: darkred;
}
.red2 {
background-color: pink;
}
.red3 {
background-color: deeppink;
}
.red4 {
background-color: lightsalmon;
}
.blue0 {
background-color: aqua;
}
.blue1 {
background-color: cadetblue;
}
.blue2 {
background-color: steelblue;
}
.blue3 {
background-color: royalblue;
}
.blue4 {
background-color: midnightblue;
}
.grey0 {
background-color: lightgrey;
}
.grey1 {
background-color: silver;
}
.grey2 {
background-color: darkgray;
}
.grey3 {
background-color: gray;
}
.grey4 {
background-color: dimgray;
}
<!DOCTYPE html>
<html>
<head>
<script data-require="lodash.js@4.17.4" data-semver="4.17.4" src="https://cdn.jsdelivr.net/npm/lodash@4.17.4/lodash.min.js"></script>
<script data-require="mithril@1.0.1" data-semver="1.0.1" src="https://cdnjs.cloudflare.com/ajax/libs/mithril/1.0.1/mithril.js"></script>
<link rel="stylesheet" href="style.css" />
</head>
<body>
<h1>Gerrymandering simulation</h1>
<p>
There are two parties, red and blue (chosen because they contrast well).
Each person will always vote a certain way, and is marked with R or B in the table.
People are divided into districts, shown here as groups of people marked in a single colour.
</p>
<p>
Use the buttons below to divide up districts.
The reset button will restore the initial state.
The randomly-evolve button will swap two people between districts
The anneal button will optimize for your chosen party.
You should limit the number of steps to ~1000 or your browser will appear to hang.
In general, it is sufficient to run a few seeds for 500 iterations.
</p>
<div id="grid"></div>
<div id="actions"></div>
<script src="script.js"></script>
</body>
</html>
我想划分网格。这意味着给定一个带有黄色和红色正方形的 n x m 网格，我想以这样一种方式划分网格，即黄色将成为尽可能多的分区中的主要颜色，如下图所示：
所有分区必须是连续的，相同数量的方块，并且所有方块都将被着色（尽管如果算法可以推广到具有一些未着色的方块的网格，那就太棒了）。
我什至不确定如何解决 'algorithmitizing' 这个问题，过去暴力破解每个可能的分区，这本身就足够困难，而且效率低得令人难以置信。
完成此任务的最佳方法是什么？
tl;dr：使用模拟退火，在选区之间交换选民。 底部的演示可让您执行交换步骤（随机进化）并针对不公平区域进行优化（退火）
常规优化
我们可以将其定义为优化问题，我们试图最大化选区的数量 红色获胜并最小化蓝色获胜的地区数量。
让我们正式化：
function heuristic(state) {
return state.districts_that_red_wins - state.districts_that_blue_wins;
}
其中 state 是选民对选区的分配。
这会起作用，但可以稍微改进一下。 让我们引入 wasted votes 的概念来推动我们的优化朝着正确的方向发展。 我们希望最大化浪费的蓝色选票并最小化浪费的红色选票。 由于每个选区有 10 名选民，因此我武断地将它们加权为一个选区的 1/10。 这给了我们一个函数来最大化：
function heuristic(state) {
let {red_wins, blue_wins, tied, wasted_red_votes, wasted_blue_votes} = get_winners(state, voters);
return red_wins - blue_wins - 0.1 * wasted_red_votes + 0.1 * wasted_blue_votes;
}
您可能想要优化其他内容，例如区的紧凑性。您可以将这些添加到启发式函数中。
模拟退火
让我们选择一个优化算法来优化state。
我们受到一些限制，很难生成符合这些条件的随机地图。
而且我怀疑没有蛮力就不可能找到最佳的区域分配，这是不可能的。
因此，让我们使用一种算法来迭代改进我们的解决方案。
我喜欢 simulated annealing 因为它易于实现和理解，并且通过防止我们陷入早期局部最优而比爬山法表现得更好。
我的温度函数简直就是max(0.8 - iterations/total_iterations, 0)。一开始，20% 的时间我们会选择一个新的状态，当且仅当它更好；其他 80% 无论如何我们都会采用新状态。
这慢慢变得更像爬山，直到我们完成计算预算的 80%，然后我们只有在它提高我们的启发式得分时才改变状态。 80%的选择完全是随意的。
要实现 SA，我们需要一个初始状态（或一种生成它的方法）。为简单起见，我将使用 "Perfect Representation" 作为初始状态，主要是因为我不知道如何生成随机连接的、大小相等的区域。 我们还需要一种对状态进行微小更改的方法。我将在下一节中讨论这个问题。 最后，我们需要一种对状态进行评分的方法。让我们使用上一节中的函数，因为它的计算成本非常低。
如果您有兴趣，请查看 anneal 函数，或者直接阅读维基百科文章。
状态演化
对于这个问题，给定一个状态，我们需要找到另一个不会对启发式得分产生太大影响的相似状态，看看我们是否在朝着正确的方向前进。 我选择从两个不同的区中找到一对点并将它们交换。
我们需要维护一些不变量：
- 保持所有地区连续
- 保持所有区的大小相同
第二个很简单：总是交换点数，从不（永久）从一个地区分配到另一个地区。 第一个比较棘手，我们需要简要介绍一下图论。 连接点（见图）是一个在不平分图形的情况下无法删除的点。 对我们来说，这意味着我们不能在不使地区不连续的情况下删除关节点。 一旦我们有了一个可以删除的点，我们需要确保将它添加到与其相邻的区域中。这很简单。
由于我们在一个网格上，所有的区域必须是连续的，我们可以只考虑一个点的直接邻居来判断它是否是一个关节点。 如果你看不到这个，那也不是特别重要，你可以使用通常在图表上起作用的 algorithm 。 我发现网格版本更容易，因为它不涉及递归。
如果您有兴趣，请参阅 is_swappable 函数。这就是演示中 "Randomly evolve" 按钮的作用。
高层，我们用于发展状态的代码应该如下所示：
function evolve_state() {
randomly pick a source district
randomly pick a non-articulation point, source_point, from source_district
for each neighbour of the articulation point
if the neighbour is in a different district target_district
temporarily remove source_point from source_district and add it to target_district
if any articulation point (other than source point), target_point, in target_district is adjacent to source_district
swap target_point and source_point
return;
restore source_point
}
注意：我以一种随机遍历所有 source_district、source_point、neighbour、target_district 和 target_point 的方式实现了这一点，因为我不确定这会有多稀疏。
如果你准确地实现这个伪代码，你可能需要比我使用更多的迭代来收敛到一个解决方案。
如果您有兴趣，请参阅 evolve_state。
我没有调出的所有函数都是实用函数或绘图函数。
演示
现在进行演示。 :) （将 Lodash 用于实用函数，将 Mithril 用于 DOM 操作）
如果你想玩这个，使用我的 Plunker 可能更容易：http://plnkr.co/edit/Bho4qhQBKRShXWX8fHmt。
const RED = 'R';
const BLUE = 'B';
const VOTERS_PER_DISTRICT = 10;
const neighbours = [{x: 1, y: 0}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 0, y: -1}];
/* UTILITY FUNCTIONS */
/**
Create a generator that starts at a random point p, 0 <= p < max
The generator will iterate over values p, p+1, ... max, 0, ... p-1
*/
function* cyclic_generator(max) {
let start = _.random(max);
for (let i=0; i<max; i++) {
yield (i + start) % max;
}
}
/**
Return grid[x][y] if x and y are within grid. Otherwise return undefined
*/
function grid_get(grid, x, y) {
if(_.isUndefined(grid[x])) {
return undefined;
}
else {
return grid[x][y];
}
}
/** Generates a 2d array red and blue voters */
function generate_voters() {
return _.times(5, x => _.times(10, () => {return {vote: x > 2 ? RED : BLUE, district_vote: 0xffffff}}))
}
/** Generate an initial state */
function generate_initial_state() {
return _.range(5).map(x => _.range(10).map(y => {return {x, y}}));
}
/**
Randomly swap two squares in the grid between two districts.
The new square to be added must be connected to the district, and the
old square must not break another district in two
*/
function evolve_state(state) {
state = _.cloneDeep(state);
// Create a grid with the district number
let point_to_district = _.range(5).map(x => _.range(10).map(y => -1));
state.forEach((district, i) => district.forEach(({x, y}) => point_to_district[x][y] = i));
// swap a point from source_district to target_district.
// then swap a point from target_district to source_district.
for(let source_district_idx of cyclic_generator(state.length)) {
let source_articulation_points = state[source_district_idx].filter(point => is_swappable(point_to_district, point, source_district_idx));
for(let source_point_idx of cyclic_generator(source_articulation_points.length)) {
let source_point = source_articulation_points[source_point_idx];
for(let neighbour_idx of cyclic_generator(4)) {
let neighbour = neighbours[neighbour_idx];
let target_district_idx = grid_get(point_to_district, source_point.x + neighbour.x, source_point.y + neighbour.y);
if (_.isUndefined(target_district_idx) || target_district_idx == source_district_idx) {
continue;
}
// swap the source point
point_to_district[source_point.x][source_point.y] = target_district_idx;
_.remove(state[source_district_idx], ({x, y}) => x == source_point.x && y == source_point.y);
// we don't add the point the the target array yet because we don't want to swap that point back
// try to find a point in target_district that we can move to source_district
let target_articulation_points = state[target_district_idx].filter(point => is_swappable(point_to_district, point, target_district_idx));
for(let target_point_idx of cyclic_generator(target_articulation_points.length)) {
let target_point = target_articulation_points[target_point_idx];
for(let n of neighbours) {
if(grid_get(point_to_district, target_point.x + n.x, target_point.y + n.y) === source_district_idx) {
// found a point that we can swap!
// console.log('swapping points!', source_point, target_point);
_.remove(state[target_district_idx], ({x, y}) => x == target_point.x && y == target_point.y);
state[target_district_idx].push(source_point);
state[source_district_idx].push(target_point);
return state;
}
}
}
// unswap source point since we were unsuccessful
point_to_district[source_point.x][source_point.y] = source_district_idx;
state[source_district_idx].push(source_point);
}
}
}
throw 'Could not find any states to swap' // this should never happen, since there will always be the option of reversing the previous step
}
/*
Return whether a point can be removed from a district without creating disjoint districts.
In graph theory, points that cannot be removed are articulation points.
For a general algorithm, see:
My version takes advantage of the fact that we're on a grid and that all the districts must be continuous,
so we can consider only the immediate neighbours of a point.
*/
function is_swappable(grid, p, district) {
// if the the point is not even in this district, it makes no sense for this to consider this point at all
if(grid[p.x][p.y] != district) {
return false;
}
// if two opposite edges are part of this district, this is an articulation point
// .x. x is an articulation point
// Exception:
// .x. x is not an articulation point
// ...
if (grid_get(grid, p.x+1, p.y) === district && grid_get(grid, p.x-1, p.y) === district && grid_get(grid, p.x, p.y+1) !== district && grid_get(grid, p.x, p.y-1) !== district) {
return false;
}
if (grid_get(grid, p.x, p.y+1) === district && grid_get(grid, p.x, p.y-1) === district && grid_get(grid, p.x+1, p.y) !== district && grid_get(grid, p.x-1, p.y) !== district) {
return false;
}
// check if any corners are missing:
// .x x is not an articulation point .x x is an articulation point
// .. .
for(let i = 0; i < 4; i++) {
let nx = neighbours[i].x;
let ny = neighbours[i].y;
let nx2 = neighbours[(i+1)%4].x;
let ny2 = neighbours[(i+1)%4].y;
if (grid_get(grid, p.x+nx, p.y+ny) === district && grid_get(grid, p.x+nx2, p.y+ny2) === district && grid_get(grid, p.x+nx+nx2, p.y+ny+ny2) !== district) {
return false;
}
}
return true;
}
/** Count how many districts each party wins */
function get_winners(state, voters) {
let red_wins = 0;
let blue_wins = 0;
let tied = 0;
let wasted_red_votes= 0; // see https://en.wikipedia.org/wiki/Wasted_vote
let wasted_blue_votes = 0;
state.forEach(district => {
let counts = _.countBy(district.map(({x, y}) => voters[x][y].vote))
if ((counts[BLUE] || 0) > (counts[RED] || 0)) {
blue_wins++;
wasted_blue_votes += (counts[BLUE] || 0) - VOTERS_PER_DISTRICT / 2 - 1;
wasted_red_votes += (counts[RED] || 0);
}
else if ((counts[RED] || 0) > (counts[BLUE] || 0)) {
red_wins++;
wasted_red_votes += (counts[RED] || 0) - VOTERS_PER_DISTRICT / 2 - 1;
wasted_blue_votes += (counts[BLUE] || 0);
}
else {
tied++;
}
});
return {red_wins, blue_wins, tied, wasted_red_votes, wasted_blue_votes};
}
/* GUI */
/* Display a grid showing which districts each party won */
function render_districts(state, voters) {
let red_districts = 0;
let blue_districts = 0;
let grey_districts = 0;
// Color each district
state.forEach(district => {
let counts = _.countBy(district.map(({x, y}) => voters[x][y].vote))
let district_color;
if ((counts[BLUE] || 0) > (counts[RED] || 0)) {
district_color = 'blue' + blue_districts++;
}
else if ((counts[RED] || 0) > (counts[BLUE] || 0)) {
district_color = 'red' + red_districts++;
}
else {
district_color = 'grey' + grey_districts++;
}
district.map(({x, y}) => voters[x][y].district_color = district_color);
});
return m('table', [
m('tbody', voters.map(row =>
m('tr', row.map(cell => m('td', {'class': cell.district_color}, cell.vote)))
))
]);
}
/** Score a state with four criteria:
- maximize number of red districts
- minimize number of blue districts
- minimize number of red voters in districts that red wins
- maximize number of blue voters in districts that blue wins
The first two criteria are arbitrarily worth 10x more than the latter two
The latter two are to nudge the final result toward the correct solution
*/
function heuristic(state) {
let {red_wins, blue_wins, tied, wasted_red_votes, wasted_blue_votes} = get_winners(state, voters);
return red_wins - blue_wins - 0.1 * wasted_red_votes + 0.1 * wasted_blue_votes;
}
/**
Optimization routine to find the maximum of prob_fcn.
prob_fcn: function to maximize. should take state as its argument
transition: how to generate another state from the previous state
initialize_state: a function that returns an initial state
iters: number of iterations to run
Stolen from my repo here: https://github.com/c2huc2hu/automated-cryptanalysis/blob/master/part3.js
*/
function anneal(prob_fcn, transition, initialize_state, seeds=1, iters=1000) {
let best_result = initialize_state();
for(let i=0; i<seeds; i++) {
let curr_state = initialize_state();
let curr_cost = prob_fcn(curr_state);
// perform annealing. do a few extra steps with temp=0 to refine the final solution
for(let j=0; j<iters; j++) {
let candidate_state = transition(curr_state);
let candidate_cost = prob_fcn(candidate_state);
temp = 0.8 - j / iters;
if(candidate_cost >= curr_cost || Math.random() < temp) {
curr_state = candidate_state;
curr_cost = candidate_cost;
}
}
if(prob_fcn(curr_state) > prob_fcn(best_result)) {
best_result = curr_state;
}
}
return best_result;
}
let voters = generate_voters();
let state = generate_initial_state();
// main rendering code: this code renders the UI
m.mount(document.getElementById('actions'), {view: function() {
return m('div', [
m('button', {onclick: () => state = generate_initial_state()}, 'Reset'),
m('button', {onclick: () => state = evolve_state(state)}, 'Randomly evolve'), // randomly evolves
m('br'),
m('label', {'for': 'radio-blue'}, 'Gerrymander for blue'),
m('input', {type: 'radio', name: 'heuristic', value: 'blue', id: 'radio-blue'}),
m('label', {'for': 'radio-red'}, 'Gerrymander for red'),
m('input', {type: 'radio', name: 'heuristic', value: 'red', id: 'radio-red'}),
m('br'),
m('label', {'for': 'anneal-steps'}, 'Anneal steps: '),
m('input', {id: 'anneal-steps', type: 'number', value: '500'}),
m('button', {onclick: function() {
let minimize = document.getElementById('radio-red').checked;
let _heuristic = minimize ? heuristic : state => -heuristic(state)
let new_state = anneal(_heuristic, evolve_state, generate_initial_state, 1, parseInt(document.getElementById('anneal-steps').value));
if(_heuristic(new_state) > _heuristic(state)) {
state = new_state;
}
else {
console.log('found no better solutions')
}
}}, 'Anneal!'),
]);
}});
// This renders the grid
m.mount(document.getElementById('grid'), {
view: function() {
return render_districts(state, voters)
}
});
// state = anneal(heuristic, evolve_state, generate_initial_state, 5, 1000);
document.getElementById('radio-red').checked = true;
m.redraw();
/* Layout */
table {
border: solid 1px black;
}
td {
padding: 5px;
border: solid 1px black;
}
button {
margin: 10px;
}
p {
max-width: 500px;
}
/* Colour classes. In hindsight, this wasn't a good idea */
.red0 {
background-color: red;
}
.red1 {
background-color: darkred;
}
.red2 {
background-color: pink;
}
.red3 {
background-color: deeppink;
}
.red4 {
background-color: lightsalmon;
}
.blue0 {
background-color: aqua;
}
.blue1 {
background-color: cadetblue;
}
.blue2 {
background-color: steelblue;
}
.blue3 {
background-color: royalblue;
}
.blue4 {
background-color: midnightblue;
}
.grey0 {
background-color: lightgrey;
}
.grey1 {
background-color: silver;
}
.grey2 {
background-color: darkgray;
}
.grey3 {
background-color: gray;
}
.grey4 {
background-color: dimgray;
}
<!DOCTYPE html>
<html>
<head>
<script data-require="lodash.js@4.17.4" data-semver="4.17.4" src="https://cdn.jsdelivr.net/npm/lodash@4.17.4/lodash.min.js"></script>
<script data-require="mithril@1.0.1" data-semver="1.0.1" src="https://cdnjs.cloudflare.com/ajax/libs/mithril/1.0.1/mithril.js"></script>
<link rel="stylesheet" href="style.css" />
</head>
<body>
<h1>Gerrymandering simulation</h1>
<p>
There are two parties, red and blue (chosen because they contrast well).
Each person will always vote a certain way, and is marked with R or B in the table.
People are divided into districts, shown here as groups of people marked in a single colour.
</p>
<p>
Use the buttons below to divide up districts.
The reset button will restore the initial state.
The randomly-evolve button will swap two people between districts
The anneal button will optimize for your chosen party.
You should limit the number of steps to ~1000 or your browser will appear to hang.
In general, it is sufficient to run a few seeds for 500 iterations.
</p>
<div id="grid"></div>
<div id="actions"></div>
<script src="script.js"></script>
</body>
</html>