3e:null 3f:["$","title",null,{"children":"Ant Colony Optimization | Andrew's Workspace | Observable"}] 45:Tbea,results = { const pheremone = Array.from(Array(n), () => Array.from(Array(n), () => 0)); const ant = Array.from(Array(m), () => new Object({ tour_length: 0.0, tour: Array(n), visited: Array(n) })); function decision_rule(t, k, i) { let prob = new Array(n); let c = ant[k].tour[i-1]; let sum_prob = 0.0; for (let j = 0; j < n; j++) { prob[j] = (Math.pow(pheremone[c][j],alpha))*Math.pow(1.0/dist[c][j],beta); if (ant[k].visited[j]) prob[j] = 0.0; // Don't pick same city twice else sum_prob += prob[j]; } if (sum_prob == 0.0) { let j, j0 = -1; for (j = 0; j < n; j++) { if (!ant[k].visited[j]) { j0 = j; break; } } for (; j < n; j++) { if (!ant[k].visited[j] && dist[c][j] < dist[c][j0]) j0 = j; } ant[k].tour[i] = j0; ant[k].visited[j0] = true; } else { // Select randomly using weights let r = Math.random()*sum_prob; let j = 0; let p = prob[0]; while (p < r) { j++; p += prob[j]; } ant[k].tour[i] = j; ant[k].visited[j] = true; } } function tourlen(tour) { let len = 0.0; for (let i = 0; i+1 < n; i++) { len += dist[tour[i]][tour[i+1]]; } return len + dist[tour[n-1]][tour[0]]; } function construct_solutions(t) { // Randomly assign each ant to an initial city for (let k = 0; k < m; k++) { let r = Math.floor(Math.random()*n); ant[k].tour[0] = r; for (let i = 0; i < n; i++) ant[k].visited[i] = false; ant[k].visited[r] = true; } // Construct tours for each ant for (let step = 1; step < n; step++) { for (let k = 0; k < m; k++) { decision_rule(t, k, step); } } // Calculate distance travelled for (let k = 0; k < m; k++) { ant[k].tour_length = tourlen(ant[k].tour); } } function update_pheremone(t) { // Evaporate pheremone for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) { pheremone[i][j] *= (1 - rho); } // Deposit pheremone for each ant k for (let k = 0; k < m; k++) { let delT = 1.0/ant[k].tour_length; for (let i = 0; i < n; i++) { let j = ant[k].tour[i]; let l = ant[k].tour[(i+1)%n]; pheremone[j][l] += delT; pheremone[l][j] = pheremone[j][l]; } } } const results = []; for (let t = 0; t < 300; t++) { construct_solutions(t); update_pheremone(t); results.push({x: t, y: ant[0].tour_length, pheremone: structuredClone(pheremone), tour: ant[0].tour.slice() }); } return results; }46:[] 43:{"id":"95a0ca977e161ef1","slug":null,"title":"Ant Colony Optimization","thumbnail":"4b58e43e5cac8bc960c8dfde5daa683048270d73773be39d87136ae9608427b4","access_level":"public","create_time":"$D2023-11-23T16:00:40.666Z","update_time":"$D2024-12-24T17:50:08.308Z","view_time":null,"first_public_time":"$D2023-12-18T21:17:10.026Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace","avatar_url":"https://avatars-next.observableusercontent.com/b1bbfc156d3f54c3b6f6e1de0d7484c30b7661fb82d534963c2f721cd9b269b2","tier":"starter_2024","bio":"","following":false},"version":233,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"a304072c6a1ecaa7","login":"bottledspace","name":"Andrew","avatar_url":"https://avatars-next.observableusercontent.com/d15f3341dde29a23f8e8e86e2402a48080aa207acbd0f307d1b8f32970715453","tier":null,"bio":"","following":false}],"members":[{"type":"team","id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace","avatar_url":"https://avatars-next.observableusercontent.com/b1bbfc156d3f54c3b6f6e1de0d7484c30b7661fb82d534963c2f721cd9b269b2","tier":"starter_2024","role":"editor"},{"type":"individual","id":"a304072c6a1ecaa7","login":"bottledspace","name":"Andrew","avatar_url":"https://avatars-next.observableusercontent.com/d15f3341dde29a23f8e8e86e2402a48080aa207acbd0f307d1b8f32970715453","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"f4aee92b58c0361a","slug":"travelling-salesperson-problem","title":"Travelling Salesperson Problem","owner":{"id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace"}},"type":"notebook","body":{"titling":"auto","title":"Ant Colony Optimization","cells":[{"id":0,"value":"# Ant Colony Optimization","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":198,"value":"viewof n = Inputs.range([100, 100], {step: 1, label: \"Number of Cities\"}); ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":213,"value":"R = d3.randomLcg(1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":200,"value":"x = Array.from(Array(n), () => R()*300);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":202,"value":"y = Array.from(Array(n), () => R()*300);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"// Now we compute distances between them (symmetric)\ndist = Array.from(Array(n), (_, i) => Array.from(Array(n), (_, j) => \n Math.hypot(x[i]-x[j], y[i]-y[j])\n));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"viewof alpha = Inputs.range([0,10], {label: \"Alpha\"});","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"viewof beta = Inputs.range([0,10], {label: \"Beta\"});","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"viewof rho = Inputs.range([0.0,1.0], {label: \"Rho\"});","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"viewof m = Inputs.range([1,100], {step:1, label: \"Number of Ants\"})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"$45","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"Plot.plot({\n marks: [\n Plot.lineY(results, { x: \"x\", y: \"y\"}),\n Plot.ruleX(results, Plot.pointerX({x: \"x\", py: \"y\", stroke: \"red\"})),\n Plot.dot(results, Plot.pointerX({x: \"x\", y: \"y\", fill: \"red\"})),\n ]})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"viewof t = Inputs.range([1, results.length-1], {step: 1, label: \"Iteration\"})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":225,"value":"results[299].y","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n svg.append(\"g\")\n .attr(\"fill\", \"#000\")\n .attr(\"stroke\", \"#fff\")\n .selectAll(\"circle\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"circle\")\n .attr(\"r\", 3)\n .attr(\"cx\", d => x[d])\n .attr(\"cy\", d => y[d]);\n svg.append(\"g\")\n .attr(\"stroke\", \"#000\")\n .selectAll(\"line\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"line\")\n .attr(\"x1\", d => x[results[t].tour[d]])\n .attr(\"y1\", d => y[results[t].tour[d]])\n .attr(\"x2\", d => x[results[t].tour[(d+1)%n]])\n .attr(\"y2\", d => y[results[t].tour[(d+1)%n]]);\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n \n const pal = d3.scaleLinear()\n .range([\"white\", \"#69b3a2\"])\n .domain([0,0.001]);\n\n for (let i = 0; i < n; i++)\n for (let j = 0; j < n; j++) {\n svg.append(\"rect\")\n .attr(\"x\", 300*i/n )\n .attr(\"y\", 300*j/n )\n .attr(\"width\", 300/n )\n .attr(\"height\", 300/n )\n .style(\"fill\", pal(results[t].pheremone[i][j]) );\n }\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W46","stdlib":"1"}} 44:"$43:body"