Published
Edited
Sep 23, 2020
6 stars
function neighborOf(seatNumber) {
// Corners
if (seatNumber === 0) return [1, 12, 13];
if (seatNumber === 11) return [10, 22, 23];
if (seatNumber === 12) return [0, 1, 13];
if (seatNumber === 23) return [10, 11, 22];
// First row (except corners)
if (seatNumber < 12) {
return [
seatNumber - 1,
seatNumber + 1,
seatNumber + 11,
seatNumber + 12,
seatNumber + 13
];
}
// Second row (except corners)
if (seatNumber >= 12) {
return [
seatNumber - 1,
seatNumber + 1,
seatNumber - 11,
seatNumber - 12,
seatNumber - 13,
];
}
}
// Example
[...Array(24)].map((d, i) => neighborOf(i))
function cost(permutation) {
let cost = 0;
permutation.forEach((i, p) => {
const neighborsFirst = neighborOf(p);
const neighborsSecond = neighborOf(i).map(n => permutation[n]);
const numNeighbors = neighborsFirst.length +
neighborsSecond.filter(n => !neighborsFirst.includes(n)).length;
// Rule 2
if (numNeighbors === 7) cost += 5; // (A)
if (numNeighbors < 7) cost += 10; // (B)
// Rule 1
const maxPossibleNeighbors = neighborsFirst.length + neighborsSecond.length;
if (numNeighbors < maxPossibleNeighbors){
cost += maxPossibleNeighbors - numNeighbors;
}
});
return cost;
}
// Swap randomly selected two elements in the given array
function randomSwap(permutation) {
const index1 = Math.floor(Math.random() * permutation.length);
const index2 = Math.floor(Math.random() * permutation.length);
const swapped = [...permutation];
swapped[index1] = permutation[index2];
swapped[index2] = permutation[index1]
return swapped;
}
// Calculate the acceptance probability for given cost change
function acceptanceProbability(oldCost, newCost, temperature) {
return (newCost < oldCost) ? 1 : Math.exp((oldCost - newCost) / temperature);
}
result = {
// Initial permutation and cost
let permutation = d3.shuffle([...Array(24)].map((d, i) => i));
let oldCost = cost(permutation);
let best = permutation;
let bestCost = oldCost;
const temperatures = [];
const history = [];
let T = t_init; // Initial temperature
while (T > t_min) {
for (let i = 0; i< 50; i++) {
// Random update
const newPermutation =randomSwap(permutation);
const newCost = cost(newPermutation);
// Log best
if (newCost < bestCost) {
best = newPermutation;
bestCost = newCost;
}
// Probabilistic acceptance
const prob = acceptanceProbability(oldCost, newCost, T);
if (Math.random() < prob) { // Accept
permutation = newPermutation;
oldCost = newCost;
}
}
T = T * alpha; // Decrease temperature
// Save history
temperatures.push(T);
history.push(bestCost);
}
return {
best: best,
history: history,
temperatures: temperatures
};
}
result.best
// Cost = 0: every participant can communicate with at least 8 unique participants
cost(result.best)
// Format data
data = result.history.map((h, i) => ({
cost: h,
temperature: result.temperatures[i],
loop: i
}))
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
