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
}))
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.