Published
Edited
Sep 23, 2020
6 stars
Seat optimization by simulated annealing algorithm
Simple Genetic AlgorithmSIR simulation of infection (WebGL)
Also listed in…
Math
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
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,
];
}
}
Insert cell
// Example
[...Array(24)].map((d, i) => neighborOf(i))
Insert cell
Insert cell
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;
}
Insert cell
Insert cell
// 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;
}
Insert cell
Insert cell
// Calculate the acceptance probability for given cost change
function acceptanceProbability(oldCost, newCost, temperature) {
return (newCost < oldCost) ? 1 : Math.exp((oldCost - newCost) / temperature);
}
Insert cell
Insert cell
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
};
}
Insert cell
Insert cell
result.best
Insert cell
// Cost = 0: every participant can communicate with at least 8 unique participants
cost(result.best)
Insert cell
Insert cell
// Format data
data = result.history.map((h, i) => ({
cost: h,
temperature: result.temperatures[i],
loop: i
}))
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell

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.
Learn more