2c:null 2d:["$","title",null,{"children":"Seat optimization by simulated annealing algorithm | sw1227 | Observable"}] 32:T4d0,md`### 3.2. Cost function In order to do optimization, we need a **cost function** of shuffling. As I mentioned earlier, a shuffling is represented as a permutation of [0, 1, ..., 23]. Cost function receives a permutation and returns the "badness" of shuffling. There are many possibilities of cost function. In our case the following cost worked fine, but this is just a heuristic, tricky example. #### Cost definition - Total cost is sum of the costs of each participant. - Cost of **a participant** is defined like the following: - **Rule 1: **If he/she is adjacent to the same person thorough first and second half, then +1 for each adjacency. - **Rule 2: **If "the number of neighbors in the first half" + "the number of first-time adjacency in the second half" is less than 8, then add the following cost: - (A) If it's equal to 7, then cost += 5 - (B) If it's less than 7, then cost += 10 - (Note 1): "the number of neighbors in the first half" is either 3(corner) or 5(else). - (Note 2): Why 8? If someone sit at a corner in first or second half, then total number of first-time adjacency for the guy is 8 or less. So 8 is inevitable and acceptable, but we want to avoid less communication than that. `33:T882,chart = { const height = 400; const margin = ({top: 20, right: 35, bottom: 30, left: 30}); const svg = d3.create("svg") .attr("viewBox", [0, 0, width, height]); // Scale const x = d3.scaleLinear() .domain(d3.extent(data, d => d.loop)) .range([margin.left, width - margin.right]); // y1: cost, y2: temperature const y1 = d3.scaleLinear() .domain([0, d3.max(data, d => d.cost)]).nice() .range([height - margin.bottom, margin.top]); const y2 = d3.scaleLinear() .domain([0, d3.max(data, d => d.temperature)]).nice() .range([height - margin.bottom, margin.top]); // Axis const xAxis = g => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(x).ticks(width / 80).tickSizeOuter(0)); svg.append("g") .call(xAxis); const yAxis1 = g => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y1)) .call(g => g.select(".domain").remove()) .call(g => g.select(".tick:last-of-type text").clone() .attr("x", 3) .attr("text-anchor", "start") .attr("font-weight", "bold") .attr("color", "steelblue") .text("Cost")); svg.append("g") .call(yAxis1); const yAxis2 = g => g .attr("transform", `translate(${width - margin.right},0)`) .call(d3.axisRight(y2)) .call(g => g.select(".domain").remove()) .call(g => g.select(".tick:last-of-type text").clone() .attr("x", -3) .attr("text-anchor", "end") .attr("font-weight", "bold") .attr("color", "salmon") .text("Temperature")); svg.append("g") .call(yAxis2); // Line chart (cost) const line1 = d3.line() .x(d => x(d.loop)) .y(d => y1(d.cost)); svg.append("path") .datum(data) .attr("fill", "none") .attr("stroke", "steelblue") .attr("stroke-width", 2) .attr("d", line1); // Line chart (temperature) const line2 = d3.line() .x(d => x(d.loop)) .y(d => y2(d.temperature)); svg.append("path") .datum(data) .attr("fill", "none") .attr("stroke", "salmon") .attr("stroke-width", 2) .attr("d", line2); return svg.node(); }34:[{"id":"06d90462f2b940a0723f88887d2d0874f8b6069e26eaaf464b43f40375fc1c87940e3673804a1e579810816362a3751b4cf6f719dcd59e1abc9c397bd4f644d4","href":"https://static.observableusercontent.com/files/06d90462f2b940a0723f88887d2d0874f8b6069e26eaaf464b43f40375fc1c87940e3673804a1e579810816362a3751b4cf6f719dcd59e1abc9c397bd4f644d4","name":"seats-simulatedAnnealing.jpg","type":"image/jpeg","lastModified":1600872304742.164,"size":6293},{"id":"812301aff997b01ada959f4e55d44a6e4035456dcc5812c9ca5fb3743617100fd71679c653e446adce41a93f0c9ddb9ec0aaaa864e1b6f879e9ecd63cc8d4783","href":"https://static.observableusercontent.com/files/812301aff997b01ada959f4e55d44a6e4035456dcc5812c9ca5fb3743617100fd71679c653e446adce41a93f0c9ddb9ec0aaaa864e1b6f879e9ecd63cc8d4783","name":"seats-simulatedAnnealing-1.jpg","type":"image/jpeg","lastModified":1600872290138.998,"size":5448}] 30:{"id":"d74ac97d669319b7","slug":"seat-optimization-by-simulated-annealing-algorithm","title":"Seat optimization by simulated annealing algorithm","thumbnail":"a30166b7724aaf5fc12ff5ee9a3d63e738126779684770c65b7329fb51b7dae9","access_level":"public","create_time":"$D2020-09-13T12:21:31.115Z","update_time":"$D2020-09-23T14:48:20.851Z","view_time":null,"first_public_time":"$D2020-09-23T14:40:49.161Z","fork":false,"stars":6,"starred":false,"owner":{"type":"team","id":"06475ae5027cde36","login":"sw1227","name":"sw1227","avatar_url":"https://avatars-next.observableusercontent.com/3e09ff2c49317e618eedc394f3b33dbb5c952acf0d9654683424e681e7857f8c","tier":"starter_2024"},"version":491,"publish_version":491,"role":null,"authored":false,"authors":[{"type":"individual","id":"4a648b0bd17e2c08","login":"sw1227","name":"sw1227","avatar_url":"https://avatars-next.observableusercontent.com/3e09ff2c49317e618eedc394f3b33dbb5c952acf0d9654683424e681e7857f8c","tier":null}],"members":[{"type":"individual","id":"4a648b0bd17e2c08","login":"sw1227","name":"sw1227","avatar_url":"https://avatars-next.observableusercontent.com/3e09ff2c49317e618eedc394f3b33dbb5c952acf0d9654683424e681e7857f8c","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"bf0b144b80365709","slug":"simulation","title":"Simulation","owner":{"id":"06475ae5027cde36","login":"sw1227","name":"sw1227"}},"type":"notebook","body":{"title":"Seat optimization by simulated annealing algorithm","cells":[{"id":0,"value":"md`# Seat optimization by simulated annealing algorithm\nThis is how I helped my colleague to create an **optimal seat shuffling** for get-together party, which his wife hosted.\n\nShe wanted to know **the way to shuffle the seats** in the intermediate break, in which every participants **can sit side by side with as many people as possible** through first and second half.\n\nI used simulated annealing algorithm to solve the optimization problem.\n\n**ref:**\n- [Wedding Seat Optimization using Simulated Annealing](http://linanqiu.github.io/2018/03/05/Wedding-Seat-Optimization/)\n- [The Simulated Annealing Algorithm](http://katrinaeg.com/simulated-annealing.html)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"md`## 1. Problem setting\n- There are 24 participants.\n- There are ${tex`12 \\times 2 = 24`} seats. I numbered the seats like the following diagram.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"FileAttachment(\"seats-simulatedAnnealing-1.jpg\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"md`\n- **Seats are shuffled** in the intermediate break: participants sit at different seats in the first and second half of the party.\n- Participants can communicate with the adjacent people in each half. \"Adjacent\" means **horizontal, vertical, and diagonal**.\n - e.g.) Participant at seat 1 can communicate with the people at seat 0, 2, 12, 13, and 14.\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":195,"value":"FileAttachment(\"seats-simulatedAnnealing.jpg\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":198,"value":"md`\n- The host want to **maximize the sum of new communication** by using a good shuffling method.\n - i.e.) Each participant should be adjacent to different participant through first and second half.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"md`## 2. Approach\n- Seat shuffling can be represented as the permutation of the following seat numbers.\n - e.g.) [13, 20, 10, 6, 4, ..., 3] (length = 24)\n - The above example can be interpreted that participant at seat 13 in first half is allocated seat 0 in second half, and so on.\n - More precisely, if ${tex`j`} -th element of permutation is number ${tex`i`}, the participant who sit at seat ${tex`i`} in first half should sit at seat ${tex`j`} in second half.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"FileAttachment(\"seats-simulatedAnnealing-1.jpg\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"md`\n- Brute force approach needs ${tex`24! \\simeq 6.2 \\times 10^{23}`}, which is nearly equal to Avogadro constant.\n- Think of the problem as optimization problem. We define a **cost of shuffling** that represents the badness of shuffling, then use simulated annealing algorithm to minimize that.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"md`## 3. Implementation\n\n### 3.1. Adjacency function\nFirst, let's implement a adjacency function, which returns a list of adjacent seat numbers given a seat number.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"function neighborOf(seatNumber) {\n // Corners\n if (seatNumber === 0) return [1, 12, 13];\n if (seatNumber === 11) return [10, 22, 23];\n if (seatNumber === 12) return [0, 1, 13];\n if (seatNumber === 23) return [10, 11, 22];\n // First row (except corners)\n if (seatNumber < 12) {\n return [\n seatNumber - 1,\n seatNumber + 1,\n seatNumber + 11,\n seatNumber + 12,\n seatNumber + 13\n ];\n }\n // Second row (except corners)\n if (seatNumber >= 12) {\n return [\n seatNumber - 1,\n seatNumber + 1,\n seatNumber - 11,\n seatNumber - 12,\n seatNumber - 13,\n ];\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":175,"value":"// Example\n[...Array(24)].map((d, i) => neighborOf(i))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":174,"value":"function cost(permutation) {\n let cost = 0;\n permutation.forEach((i, p) => {\n const neighborsFirst = neighborOf(p);\n const neighborsSecond = neighborOf(i).map(n => permutation[n]);\n const numNeighbors = neighborsFirst.length +\n neighborsSecond.filter(n => !neighborsFirst.includes(n)).length;\n \n // Rule 2\n if (numNeighbors === 7) cost += 5; // (A)\n if (numNeighbors < 7) cost += 10; // (B)\n\n // Rule 1\n const maxPossibleNeighbors = neighborsFirst.length + neighborsSecond.length;\n if (numNeighbors < maxPossibleNeighbors){\n cost += maxPossibleNeighbors - numNeighbors;\n }\n });\n\n return cost;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"md`### 3.3. Simulated annealing\nSimulated annealing algorithm starts with a random solution and gradually improves it.\n\nYou can see the detail of simulated annealing at [The Simulated Annealing Algorithm](http://katrinaeg.com/simulated-annealing.html). My JavaScript implementation is based on the Python implementation there.\n\nFirst, we need a random swap function for gradual improvement.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":239,"value":"// Swap randomly selected two elements in the given array\nfunction randomSwap(permutation) {\n const index1 = Math.floor(Math.random() * permutation.length);\n const index2 = Math.floor(Math.random() * permutation.length);\n const swapped = [...permutation];\n swapped[index1] = permutation[index2];\n swapped[index2] = permutation[index1]\n return swapped;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":268,"value":"md`\nRandom update to the solution may or may not be accepted, based on its cost value.\n\n- If cost improves, or ${tex`c_{new} < c_{old}`}, accept the update.\n- If ${tex`c_{new} > c_{old}`}, maybe accept the update. Acceptance probability is:\n - ${tex`P_{accept} = e^{\\frac{c_{old} - c_{new}}{T}}`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"// Calculate the acceptance probability for given cost change\nfunction acceptanceProbability(oldCost, newCost, temperature) {\n return (newCost < oldCost) ? 1 : Math.exp((oldCost - newCost) / temperature);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":277,"value":"md`\nNow let's execute simulated annealing.\n\nSome parameter values are provided by the sliders in the next section.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":281,"value":"result = {\n // Initial permutation and cost\n let permutation = d3.shuffle([...Array(24)].map((d, i) => i));\n let oldCost = cost(permutation);\n \n let best = permutation;\n let bestCost = oldCost;\n \n const temperatures = [];\n const history = [];\n \n let T = t_init; // Initial temperature\n\n while (T > t_min) {\n for (let i = 0; i< 50; i++) {\n // Random update\n const newPermutation =randomSwap(permutation);\n const newCost = cost(newPermutation);\n // Log best\n if (newCost < bestCost) {\n best = newPermutation;\n bestCost = newCost;\n }\n // Probabilistic acceptance\n const prob = acceptanceProbability(oldCost, newCost, T);\n if (Math.random() < prob) { // Accept\n permutation = newPermutation;\n oldCost = newCost;\n }\n }\n T = T * alpha; // Decrease temperature\n\n // Save history\n temperatures.push(T);\n history.push(bestCost);\n }\n\n return {\n best: best,\n history: history,\n temperatures: temperatures\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":429,"value":"md`\nNow we've got the best perumutation. Let's check the result and its cost.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":430,"value":"result.best","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":340,"value":"// Cost = 0: every participant can communicate with at least 8 unique participants\ncost(result.best)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":392,"value":"md`### 3.4. Visualizing Result`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"// Format data\ndata = result.history.map((h, i) => ({\n cost: h,\n temperature: result.temperatures[i],\n loop: i\n}))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":436,"value":"viewof alpha = {\n const form = html`\n`;\n form.i.oninput = () => form.o.value = `Alpha = ${form.value = form.i.valueAsNumber}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":441,"value":"viewof t_init = {\n const form = html`\n`;\n form.i.oninput = () => form.o.value = `Initial temperature = ${form.value = form.i.valueAsNumber}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":444,"value":"viewof t_min = {\n const form = html`\n`;\n form.i.oninput = () => form.o.value = `Minimum temperature = ${form.value = form.i.valueAsNumber}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":343,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":285,"value":"d3 = require(\"d3@6\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 31:"$30:body"