Created
May 23, 2022 15:43
-
-
Save cyrillkuettel/d525acbf52a726394bee7b0103c1096d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Local Search Algorithms\n", | |
| "\n", | |
| "Here, we want to find the shortest path connecting several cities considering the aerial distances. This problem is known as the \"Traveling Sales(man) Problem\".\n", | |
| "\n", | |
| "If we have 15 cities to connect, we have 15! different possibilities. This is already bigger than 10^12. You can easily see that the problem becomes complex very quickly. We will have problems to systematically explore the search space. Therefore, we will use local search algorithms to tackle this problem.\n", | |
| "\n", | |
| "Local search algorithms start with a solution and try to improve the solution by considering the neighbouring states. The best neighbour will be chosen until no better can be found.\n", | |
| "\n", | |
| "\n", | |
| "Implement your local search algorithm of choice (your version of the simulated annealing, hill-climing or genetic algorithm) to find the shortest path connecting a list of cities!\n", | |
| "\n", | |
| "For the **Testat**, you need to find the shortest path between the following cities: \n", | |
| "\n", | |
| "`path = ['Sursee', 'Sion', 'Altdorf', 'Landquart', 'Konolfingen', 'Thun', 'Twann', 'Sargans', 'Lausanne', 'Vevey', 'Locarno', 'Hinwil', 'Bern', 'Liestal', 'Lugano']`\n", | |
| "\n", | |
| "\n", | |
| "For each algorithm, I wrote down some hints and implementation suggestions below. You don't need to implement all algorithms to solve the testat exercise. Try to tweak your algorithm such that a good (or even best) solution is found.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## General hints" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| " You can use the following helper functions to plot visualize your path and to evaluate its cost." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 2, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "import folium\n", | |
| "from typing import List\n", | |
| "\n", | |
| "map_ch = folium.Map(location=[46.8, 8.33],\n", | |
| " zoom_start=8, tiles=\"Stamen TonerBackground\")\n", | |
| "\n", | |
| "\n", | |
| "def create_map(path, sbb, map):\n", | |
| " points = []\n", | |
| " first_city = path[0]\n", | |
| " for city in path:\n", | |
| " points.append([sbb.hubs[city].x, sbb.hubs[city].y])\n", | |
| " folium.Marker([sbb.hubs[city].x, sbb.hubs[city].y], popup=city).add_to(map)\n", | |
| " points.append([sbb.hubs[first_city].x, sbb.hubs[first_city].y]) \n", | |
| " folium.PolyLine(points, color='red').add_to(map)\n", | |
| " return map\n", | |
| "\n", | |
| "def evaluate_path(path, distance_function):\n", | |
| " length = 0\n", | |
| " last_city = \"\"\n", | |
| " for city in path:\n", | |
| " if last_city == \"\":\n", | |
| " first_city = city\n", | |
| " if last_city != \"\":\n", | |
| " length += distance_function(last_city, city) \n", | |
| " last_city = city\n", | |
| " length += distance_function(first_city, last_city) \n", | |
| " return length\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 3, | |
| "outputs": [], | |
| "source": [ | |
| "#path = ['Sursee', 'Sion', 'Altdorf', 'Landquart', 'Konolfingen', 'Thun', 'Twann', 'Sargans', 'Lausanne', 'Vevey', 'Locarno', 'Hinwil', 'Bern', 'Liestal', 'Lugano']\n", | |
| "\n", | |
| "path = ['Lausanne', 'Vevey', 'Sion', 'Thun', 'Konolfingen', 'Bern', 'Twann', 'Liestal', 'Sursee', 'Altdorf', 'Hinwil', 'Sargans', 'Landquart','Lugano', 'Locarno']\n" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 4, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "successfully imported 2787 hubs\n", | |
| "successfully imported 401 train lines\n", | |
| "591.8929170550216\n", | |
| "591.8929170550216\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "from sbb import SBB\n", | |
| "sbb = SBB()\n", | |
| "sbb.import_data('linie-mit-betriebspunkten.json')\n", | |
| "distance_function = sbb.get_distance_between\n", | |
| "\n", | |
| "\n", | |
| "# extremely inefficient O(n^2) algorithm to get maximum distance of any two points\n", | |
| "def get_max_path_in_dataset(path):\n", | |
| " max_path_length = 0\n", | |
| " for city1 in path:\n", | |
| " for city2 in path:\n", | |
| " path_between_two_cities = [city1, city2]\n", | |
| " current = evaluate_path(path_between_two_cities, distance_function)\n", | |
| " if current > max_path_length:\n", | |
| " max_path_length = current\n", | |
| "\n", | |
| " return max_path_length\n", | |
| "\n", | |
| "\n", | |
| "print(get_max_path_in_dataset(path))\n", | |
| "print(evaluate_path(['Lausanne', 'Landquart'], distance_function)) # this is the max path, makes sense visually if you look at the map" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Let's import the data from sbb and viualize our initial path." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 5, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "successfully imported 2787 hubs\n", | |
| "successfully imported 401 train lines\n", | |
| "path cost = 862.7905793414101\n", | |
| "['Lausanne', 'Vevey', 'Sion', 'Thun', 'Konolfingen', 'Bern', 'Twann', 'Liestal', 'Sursee', 'Altdorf', 'Hinwil', 'Sargans', 'Landquart', 'Lugano', 'Locarno']\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "text/plain": "<folium.folium.Map at 0x7fc9d4c83a10>", | |
| "text/html": "<div style=\"width:100%;\"><div style=\"position:relative;width:100%;height:0;padding-bottom:60%;\"><span style=\"color:#565656\">Make this Notebook Trusted to load map: File -> Trust Notebook</span><iframe srcdoc=\"<!DOCTYPE html>\n<head> \n <meta http-equiv="content-type" content="text/html; charset=UTF-8" />\n \n <script>\n L_NO_TOUCH = false;\n L_DISABLE_3D = false;\n </script>\n \n <style>html, body {width: 100%;height: 100%;margin: 0;padding: 0;}</style>\n <style>#map {position:absolute;top:0;bottom:0;right:0;left:0;}</style>\n <script src="https://cdn.jsdelivr.net/npm/leaflet@1.6.0/dist/leaflet.js"></script>\n <script src="https://code.jquery.com/jquery-1.12.4.min.js"></script>\n <script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.min.js"></script>\n <script src="https://cdnjs.cloudflare.com/ajax/libs/Leaflet.awesome-markers/2.0.2/leaflet.awesome-markers.js"></script>\n <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/leaflet@1.6.0/dist/leaflet.css"/>\n <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap.min.css"/>\n <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap-theme.min.css"/>\n <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/font-awesome/4.6.3/css/font-awesome.min.css"/>\n <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/Leaflet.awesome-markers/2.0.2/leaflet.awesome-markers.css"/>\n <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/python-visualization/folium/folium/templates/leaflet.awesome.rotate.min.css"/>\n \n <meta name="viewport" content="width=device-width,\n initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />\n <style>\n #map_9c856fbc980697f5c6f9ad1f4c1ea79e {\n position: relative;\n width: 100.0%;\n height: 100.0%;\n left: 0.0%;\n top: 0.0%;\n }\n </style>\n \n</head>\n<body> \n \n <div class="folium-map" id="map_9c856fbc980697f5c6f9ad1f4c1ea79e" ></div>\n \n</body>\n<script> \n \n var map_9c856fbc980697f5c6f9ad1f4c1ea79e = L.map(\n "map_9c856fbc980697f5c6f9ad1f4c1ea79e",\n {\n center: [46.8, 8.33],\n crs: L.CRS.EPSG3857,\n zoom: 8,\n zoomControl: true,\n preferCanvas: false,\n }\n );\n\n \n\n \n \n var tile_layer_a43a0574783c9c05e44f6b2bebde742e = L.tileLayer(\n "https://stamen-tiles-{s}.a.ssl.fastly.net/toner-background/{z}/{x}/{y}{r}.png",\n {"attribution": "Map tiles by \\u003ca href=\\"http://stamen.com\\"\\u003eStamen Design\\u003c/a\\u003e, under \\u003ca href=\\"http://creativecommons.org/licenses/by/3.0\\"\\u003eCC BY 3.0\\u003c/a\\u003e. Data by \\u003ca href=\\"http://openstreetmap.org\\"\\u003eOpenStreetMap\\u003c/a\\u003e, under \\u003ca href=\\"http://www.openstreetmap.org/copyright\\"\\u003eODbL\\u003c/a\\u003e.", "detectRetina": false, "maxNativeZoom": 18, "maxZoom": 18, "minZoom": 0, "noWrap": false, "opacity": 1, "subdomains": "abc", "tms": false}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var marker_34dfc21bc23b522f1c1f3515818c5f05 = L.marker(\n [46.5167918355, 6.6290923032],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_530dbb9fc811a730de97f84e2c038b96 = L.popup({"maxWidth": "100%"});\n\n \n var html_94f08fc3854fcc5936705e95a9ed4c6d = $(`<div id="html_94f08fc3854fcc5936705e95a9ed4c6d" style="width: 100.0%; height: 100.0%;">Lausanne</div>`)[0];\n popup_530dbb9fc811a730de97f84e2c038b96.setContent(html_94f08fc3854fcc5936705e95a9ed4c6d);\n \n\n marker_34dfc21bc23b522f1c1f3515818c5f05.bindPopup(popup_530dbb9fc811a730de97f84e2c038b96)\n ;\n\n \n \n \n var marker_5e7f6c9b747778ca4e2f3e088ab101d0 = L.marker(\n [46.4630018107, 6.84344559824],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_ac4fb77ed393244c5033de522d4088a9 = L.popup({"maxWidth": "100%"});\n\n \n var html_b8d577cd3525e7f1d0fce1aa6926b9c0 = $(`<div id="html_b8d577cd3525e7f1d0fce1aa6926b9c0" style="width: 100.0%; height: 100.0%;">Vevey</div>`)[0];\n popup_ac4fb77ed393244c5033de522d4088a9.setContent(html_b8d577cd3525e7f1d0fce1aa6926b9c0);\n \n\n marker_5e7f6c9b747778ca4e2f3e088ab101d0.bindPopup(popup_ac4fb77ed393244c5033de522d4088a9)\n ;\n\n \n \n \n var marker_9984ebf3ecb84b6ba01200259152c544 = L.marker(\n [46.2275531964, 7.35919703457],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_49819ce61b2cd56c6cf06e5ab0916ff4 = L.popup({"maxWidth": "100%"});\n\n \n var html_9fcc5355acb892fb2fcf83e59f146321 = $(`<div id="html_9fcc5355acb892fb2fcf83e59f146321" style="width: 100.0%; height: 100.0%;">Sion</div>`)[0];\n popup_49819ce61b2cd56c6cf06e5ab0916ff4.setContent(html_9fcc5355acb892fb2fcf83e59f146321);\n \n\n marker_9984ebf3ecb84b6ba01200259152c544.bindPopup(popup_49819ce61b2cd56c6cf06e5ab0916ff4)\n ;\n\n \n \n \n var marker_da8460e2eec5512bebc42b3a3faba260 = L.marker(\n [46.7548527306, 7.62960582867],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_163df42f72b99d898010f82190509232 = L.popup({"maxWidth": "100%"});\n\n \n var html_9cf5dae5fde9220c3fe2adf14d92cab5 = $(`<div id="html_9cf5dae5fde9220c3fe2adf14d92cab5" style="width: 100.0%; height: 100.0%;">Thun</div>`)[0];\n popup_163df42f72b99d898010f82190509232.setContent(html_9cf5dae5fde9220c3fe2adf14d92cab5);\n \n\n marker_da8460e2eec5512bebc42b3a3faba260.bindPopup(popup_163df42f72b99d898010f82190509232)\n ;\n\n \n \n \n var marker_8223d79ab51eeb044061c3dc8380bbe3 = L.marker(\n [46.8807024189, 7.6213670273],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_7bbc858ec85a08fd0cc03d7fa553c388 = L.popup({"maxWidth": "100%"});\n\n \n var html_72ebc3b45f484f88dc75bee7090bb3ea = $(`<div id="html_72ebc3b45f484f88dc75bee7090bb3ea" style="width: 100.0%; height: 100.0%;">Konolfingen</div>`)[0];\n popup_7bbc858ec85a08fd0cc03d7fa553c388.setContent(html_72ebc3b45f484f88dc75bee7090bb3ea);\n \n\n marker_8223d79ab51eeb044061c3dc8380bbe3.bindPopup(popup_7bbc858ec85a08fd0cc03d7fa553c388)\n ;\n\n \n \n \n var marker_b4e8d707baa3cc65bd1d372bdda50338 = L.marker(\n [46.9488322905, 7.43913088992],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_0d79a73412222a94b400c362b2c49205 = L.popup({"maxWidth": "100%"});\n\n \n var html_07c6fb6e10eee9d2dfdda5df56258761 = $(`<div id="html_07c6fb6e10eee9d2dfdda5df56258761" style="width: 100.0%; height: 100.0%;">Bern</div>`)[0];\n popup_0d79a73412222a94b400c362b2c49205.setContent(html_07c6fb6e10eee9d2dfdda5df56258761);\n \n\n marker_b4e8d707baa3cc65bd1d372bdda50338.bindPopup(popup_0d79a73412222a94b400c362b2c49205)\n ;\n\n \n \n \n var marker_22dc1615d1a605219e32816aab9c3d3a = L.marker(\n [47.0936640656, 7.15649750354],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_142f11cd7891716ebbbf4986874aaac5 = L.popup({"maxWidth": "100%"});\n\n \n var html_066298d36ffc5a0a1fffbbd1ac5672a4 = $(`<div id="html_066298d36ffc5a0a1fffbbd1ac5672a4" style="width: 100.0%; height: 100.0%;">Twann</div>`)[0];\n popup_142f11cd7891716ebbbf4986874aaac5.setContent(html_066298d36ffc5a0a1fffbbd1ac5672a4);\n \n\n marker_22dc1615d1a605219e32816aab9c3d3a.bindPopup(popup_142f11cd7891716ebbbf4986874aaac5)\n ;\n\n \n \n \n var marker_fd99c2169896def7afe452d791d2a885 = L.marker(\n [47.4844611721, 7.7313674807],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_900b58da3833df26bd38a053a99f8d6c = L.popup({"maxWidth": "100%"});\n\n \n var html_4f0648bd5dd08e18b497b3988cf295dc = $(`<div id="html_4f0648bd5dd08e18b497b3988cf295dc" style="width: 100.0%; height: 100.0%;">Liestal</div>`)[0];\n popup_900b58da3833df26bd38a053a99f8d6c.setContent(html_4f0648bd5dd08e18b497b3988cf295dc);\n \n\n marker_fd99c2169896def7afe452d791d2a885.bindPopup(popup_900b58da3833df26bd38a053a99f8d6c)\n ;\n\n \n \n \n var marker_073f0143910324b815ce60e9fe7baca1 = L.marker(\n [47.1707950409, 8.09789386466],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_f0fd314debcd588c6400763c8550a572 = L.popup({"maxWidth": "100%"});\n\n \n var html_2a2546ff45e7eb7bfcbb0894e82e750e = $(`<div id="html_2a2546ff45e7eb7bfcbb0894e82e750e" style="width: 100.0%; height: 100.0%;">Sursee</div>`)[0];\n popup_f0fd314debcd588c6400763c8550a572.setContent(html_2a2546ff45e7eb7bfcbb0894e82e750e);\n \n\n marker_073f0143910324b815ce60e9fe7baca1.bindPopup(popup_f0fd314debcd588c6400763c8550a572)\n ;\n\n \n \n \n var marker_ee5776999d4fcf1aeeeb596a4abf6f77 = L.marker(\n [46.8757387133, 8.63157541744],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_244609bd610c6ae982955baa860a0cbd = L.popup({"maxWidth": "100%"});\n\n \n var html_16d069d660b273442b9780a52764c497 = $(`<div id="html_16d069d660b273442b9780a52764c497" style="width: 100.0%; height: 100.0%;">Altdorf</div>`)[0];\n popup_244609bd610c6ae982955baa860a0cbd.setContent(html_16d069d660b273442b9780a52764c497);\n \n\n marker_ee5776999d4fcf1aeeeb596a4abf6f77.bindPopup(popup_244609bd610c6ae982955baa860a0cbd)\n ;\n\n \n \n \n var marker_9d104a6ec01470500770a546a6bfd5b3 = L.marker(\n [47.3000569504, 8.83971989441],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_af50bb70c33ef1e6491dd7bf15767d4e = L.popup({"maxWidth": "100%"});\n\n \n var html_3cfe8f385e8e8b3f719132fd57c12f99 = $(`<div id="html_3cfe8f385e8e8b3f719132fd57c12f99" style="width: 100.0%; height: 100.0%;">Hinwil</div>`)[0];\n popup_af50bb70c33ef1e6491dd7bf15767d4e.setContent(html_3cfe8f385e8e8b3f719132fd57c12f99);\n \n\n marker_9d104a6ec01470500770a546a6bfd5b3.bindPopup(popup_af50bb70c33ef1e6491dd7bf15767d4e)\n ;\n\n \n \n \n var marker_df6070f562eeb1f6dddcae907fa28cf6 = L.marker(\n [47.0448235144, 9.44626047466],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_ad6e627869776fde5214a94814f931d2 = L.popup({"maxWidth": "100%"});\n\n \n var html_d1b7074e81388151c03c977cf23da407 = $(`<div id="html_d1b7074e81388151c03c977cf23da407" style="width: 100.0%; height: 100.0%;">Sargans</div>`)[0];\n popup_ad6e627869776fde5214a94814f931d2.setContent(html_d1b7074e81388151c03c977cf23da407);\n \n\n marker_df6070f562eeb1f6dddcae907fa28cf6.bindPopup(popup_ad6e627869776fde5214a94814f931d2)\n ;\n\n \n \n \n var marker_686c1be35cec0f685db391a40a6e3465 = L.marker(\n [46.9674404284, 9.55404469208],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_b578fb0cb1c64c46c741e4291acb3f16 = L.popup({"maxWidth": "100%"});\n\n \n var html_b04ceecd65c9122c72912d5b54b37c33 = $(`<div id="html_b04ceecd65c9122c72912d5b54b37c33" style="width: 100.0%; height: 100.0%;">Landquart</div>`)[0];\n popup_b578fb0cb1c64c46c741e4291acb3f16.setContent(html_b04ceecd65c9122c72912d5b54b37c33);\n \n\n marker_686c1be35cec0f685db391a40a6e3465.bindPopup(popup_b578fb0cb1c64c46c741e4291acb3f16)\n ;\n\n \n \n \n var marker_4cb9e8bf6ada69d12341547592fcb242 = L.marker(\n [46.0055005499, 8.94699530851],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_45c40b4b49232d9b51475baa0a3a1ada = L.popup({"maxWidth": "100%"});\n\n \n var html_ee41035fdf35950ed02f0b209809fc5c = $(`<div id="html_ee41035fdf35950ed02f0b209809fc5c" style="width: 100.0%; height: 100.0%;">Lugano</div>`)[0];\n popup_45c40b4b49232d9b51475baa0a3a1ada.setContent(html_ee41035fdf35950ed02f0b209809fc5c);\n \n\n marker_4cb9e8bf6ada69d12341547592fcb242.bindPopup(popup_45c40b4b49232d9b51475baa0a3a1ada)\n ;\n\n \n \n \n var marker_899a2ea2980d8bf9f3bc7d52d58873f4 = L.marker(\n [46.1724201894, 8.80136089926],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_f797c54c98afe8a25f5be53fa722b691 = L.popup({"maxWidth": "100%"});\n\n \n var html_c188cea087bc236e94f65d219133ba3a = $(`<div id="html_c188cea087bc236e94f65d219133ba3a" style="width: 100.0%; height: 100.0%;">Locarno</div>`)[0];\n popup_f797c54c98afe8a25f5be53fa722b691.setContent(html_c188cea087bc236e94f65d219133ba3a);\n \n\n marker_899a2ea2980d8bf9f3bc7d52d58873f4.bindPopup(popup_f797c54c98afe8a25f5be53fa722b691)\n ;\n\n \n \n \n var poly_line_b69a38a6db67751cf6ca9e14439cc67b = L.polyline(\n [[46.5167918355, 6.6290923032], [46.4630018107, 6.84344559824], [46.2275531964, 7.35919703457], [46.7548527306, 7.62960582867], [46.8807024189, 7.6213670273], [46.9488322905, 7.43913088992], [47.0936640656, 7.15649750354], [47.4844611721, 7.7313674807], [47.1707950409, 8.09789386466], [46.8757387133, 8.63157541744], [47.3000569504, 8.83971989441], [47.0448235144, 9.44626047466], [46.9674404284, 9.55404469208], [46.0055005499, 8.94699530851], [46.1724201894, 8.80136089926], [46.5167918355, 6.6290923032]],\n {"bubblingMouseEvents": true, "color": "red", "dashArray": null, "dashOffset": null, "fill": false, "fillColor": "red", "fillOpacity": 0.2, "fillRule": "evenodd", "lineCap": "round", "lineJoin": "round", "noClip": false, "opacity": 1.0, "smoothFactor": 1.0, "stroke": true, "weight": 3}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n</script>\" style=\"position:absolute;width:100%;height:100%;left:0;top:0;border:none !important;\" allowfullscreen webkitallowfullscreen mozallowfullscreen></iframe></div></div>" | |
| }, | |
| "execution_count": 5, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "from sbb import SBB\n", | |
| "\n", | |
| "sbb = SBB()\n", | |
| "sbb.import_data('linie-mit-betriebspunkten.json')\n", | |
| "distance_function = sbb.get_distance_between\n", | |
| "\n", | |
| "print(\"path cost = \" + str(evaluate_path(path, distance_function)))\n", | |
| "\n", | |
| "print(path)\n", | |
| "m = create_map(path, sbb, map_ch)\n", | |
| "m" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "This is defenitly not the best way how to connect the cities. Find the optimal solution with **one** of the follwoing algorithms." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Hill Climbing\n", | |
| "\n", | |
| "Here, we try to minimize the distance of our path. So instead of hill climbing, we will do the opposite. Instead of trying to find the highest hill (maximum), we're looking at the deepest valley (minimum). But that's not a concern, we can easily change the sign to switch from a maximization to a minimization problem.\n", | |
| "\n", | |
| "*Hints:*\n", | |
| "- use the `evaluate_path()` function we have defined earlier\n", | |
| "- make sure to copy lists or sets properly: `current_path = path.copy()`\n", | |
| "- you can convert sets to lists by `list(my_set)`\n", | |
| "- a neighbouring path can be found by switching the position of two cities" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 6, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "import sys\n", | |
| "\n", | |
| "def hill_climbing_TSP(path, distance_function):\n", | |
| " return None\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 7, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "ename": "TypeError", | |
| "evalue": "'NoneType' object is not iterable", | |
| "output_type": "error", | |
| "traceback": [ | |
| "\u001B[0;31m---------------------------------------------------------------------------\u001B[0m", | |
| "\u001B[0;31mTypeError\u001B[0m Traceback (most recent call last)", | |
| "\u001B[0;32m/tmp/ipykernel_37146/57351107.py\u001B[0m in \u001B[0;36m<module>\u001B[0;34m\u001B[0m\n\u001B[1;32m 1\u001B[0m \u001B[0mbest_path\u001B[0m \u001B[0;34m=\u001B[0m \u001B[0mhill_climbing_TSP\u001B[0m\u001B[0;34m(\u001B[0m\u001B[0mpath\u001B[0m\u001B[0;34m,\u001B[0m \u001B[0mdistance_function\u001B[0m\u001B[0;34m)\u001B[0m\u001B[0;34m\u001B[0m\u001B[0;34m\u001B[0m\u001B[0m\n\u001B[0;32m----> 2\u001B[0;31m \u001B[0mprint\u001B[0m\u001B[0;34m(\u001B[0m\u001B[0;34m\"with length \"\u001B[0m \u001B[0;34m+\u001B[0m \u001B[0mstr\u001B[0m\u001B[0;34m(\u001B[0m\u001B[0mevaluate_path\u001B[0m\u001B[0;34m(\u001B[0m\u001B[0mbest_path\u001B[0m\u001B[0;34m,\u001B[0m\u001B[0msbb\u001B[0m\u001B[0;34m)\u001B[0m\u001B[0;34m)\u001B[0m\u001B[0;34m)\u001B[0m\u001B[0;34m\u001B[0m\u001B[0;34m\u001B[0m\u001B[0m\n\u001B[0m", | |
| "\u001B[0;32m/tmp/ipykernel_37146/4090451369.py\u001B[0m in \u001B[0;36mevaluate_path\u001B[0;34m(path, distance_function)\u001B[0m\n\u001B[1;32m 19\u001B[0m \u001B[0mlength\u001B[0m \u001B[0;34m=\u001B[0m \u001B[0;36m0\u001B[0m\u001B[0;34m\u001B[0m\u001B[0;34m\u001B[0m\u001B[0m\n\u001B[1;32m 20\u001B[0m \u001B[0mlast_city\u001B[0m \u001B[0;34m=\u001B[0m \u001B[0;34m\"\"\u001B[0m\u001B[0;34m\u001B[0m\u001B[0;34m\u001B[0m\u001B[0m\n\u001B[0;32m---> 21\u001B[0;31m \u001B[0;32mfor\u001B[0m \u001B[0mcity\u001B[0m \u001B[0;32min\u001B[0m \u001B[0mpath\u001B[0m\u001B[0;34m:\u001B[0m\u001B[0;34m\u001B[0m\u001B[0;34m\u001B[0m\u001B[0m\n\u001B[0m\u001B[1;32m 22\u001B[0m \u001B[0;32mif\u001B[0m \u001B[0mlast_city\u001B[0m \u001B[0;34m==\u001B[0m \u001B[0;34m\"\"\u001B[0m\u001B[0;34m:\u001B[0m\u001B[0;34m\u001B[0m\u001B[0;34m\u001B[0m\u001B[0m\n\u001B[1;32m 23\u001B[0m \u001B[0mfirst_city\u001B[0m \u001B[0;34m=\u001B[0m \u001B[0mcity\u001B[0m\u001B[0;34m\u001B[0m\u001B[0;34m\u001B[0m\u001B[0m\n", | |
| "\u001B[0;31mTypeError\u001B[0m: 'NoneType' object is not iterable" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "best_path = hill_climbing_TSP(path, distance_function)\n", | |
| "print(\"with length \" + str(evaluate_path(best_path,sbb)))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Oh, what happend here? Is this the best we can get?\n", | |
| "- Why is this so? \n", | |
| "- How many steps did we need to get to this solution?\n", | |
| "- Try to improve the hill climbing algorithm with one of the methods you have seen in class?" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Genetic Algorithm \n", | |
| "\n", | |
| "Genetic algorithms (or GA) are inspired by natural evolution and are particularly useful in optimization and search problems with large state spaces.\n", | |
| "\n", | |
| "Given a problem, algorithms in the domain make use of a *population* of solutions (also called *states*), where each solution/state represents a feasible solution. At each iteration (often called *generation*), the population gets updated using methods inspired by biology and evolution, like *crossover*, *mutation* and *natural selection*.\n", | |
| "\n", | |
| "A genetic algorithm works in the following way:\n", | |
| "\n", | |
| "1) Initialize random population.\n", | |
| "\n", | |
| "2) Calculate population fitness.\n", | |
| "\n", | |
| "3) Select individuals for mating.\n", | |
| "\n", | |
| "4) Mate selected individuals to produce new population.\n", | |
| "\n", | |
| " * Random chance to mutate individuals.\n", | |
| "\n", | |
| "5) Repeat from step 2) until an individual is fit enough or the maximum number of iterations was reached.\n", | |
| "\n", | |
| "Below, you can find some helper functions to implement your genetic algorithm.\n", | |
| "\n", | |
| "First, create a dictionnary that maps a letter to a city name." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Our solution will be a path through all the cities. To simplify, we will encode each city with a letter from the alphabet. So your first initial path through the cities will have the code \"ABCDEFGHIJK..\". We can easily convert a letter to a city by `letter2city('A')` or `city2letter('Rotkreuz')`." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 8, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "['Lausanne', 'Vevey', 'Sion', 'Thun', 'Konolfingen', 'Bern', 'Twann', 'Liestal', 'Sursee', 'Altdorf', 'Hinwil', 'Sargans', 'Landquart', 'Lugano', 'Locarno']\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "print(path)" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 9, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "the path has the following code : \n", | |
| "['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']\n", | |
| "['Lausanne', 'Vevey', 'Sion', 'Thun', 'Konolfingen', 'Bern', 'Twann', 'Liestal', 'Sursee', 'Altdorf', 'Hinwil', 'Sargans', 'Landquart', 'Lugano', 'Locarno']\n", | |
| "testing new testpath\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "import string\n", | |
| "\n", | |
| "number_of_cities = len(path)\n", | |
| "letter2city = dict()\n", | |
| "city2letter = dict()\n", | |
| "\n", | |
| "for e in range(number_of_cities):\n", | |
| " letter2city[string.ascii_uppercase[e]] = list(path)[e]\n", | |
| " city2letter[list(path)[e]] = string.ascii_uppercase[e]\n", | |
| "\n", | |
| "# cities to letters\n", | |
| "def path2string(path):\n", | |
| " s = \"\"\n", | |
| " for city in path:\n", | |
| " s+=city2letter[city]\n", | |
| " return list(s)\n", | |
| "\n", | |
| "# letters to cities\n", | |
| "def path2cities(path):\n", | |
| " s = list()\n", | |
| " for letter in path:\n", | |
| " s.append(letter2city[letter])\n", | |
| " return s\n", | |
| "\n", | |
| "path_code = path2string(path)\n", | |
| "print(\"the path has the following code : \")\n", | |
| "print(path_code)\n", | |
| "\n", | |
| "converted_back = path2cities(path_code)\n", | |
| "print(converted_back)\n", | |
| "print(\"testing new testpath\")" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 10, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "B\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "print(city2letter[path[1]])" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Let's inizialize a random population:" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 11, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "import time\n", | |
| "import random\n", | |
| "\n", | |
| "def shuffle_chromosomes(cities):\n", | |
| " \"\"\" the cities is a string like \"ABCDEFGHA\"\n", | |
| " this function is just used once to be called for each individual \"\"\"\n", | |
| " newpopulation = cities.copy()\n", | |
| " # random.seed(time.perf_counter())\n", | |
| " random.shuffle(newpopulation)\n", | |
| " return newpopulation\n", | |
| "\n", | |
| "def init_population(pop_number, cities):\n", | |
| " population = []\n", | |
| " for index in range(pop_number-1):\n", | |
| " population.append(cities)\n", | |
| " population.append(shuffle_chromosomes(cities))\n", | |
| " return population\n", | |
| "\n", | |
| "\n", | |
| "def init_random_population(pop_number, cities):\n", | |
| " \"\"\"Initializes randompopulation for genetic algorithm\n", | |
| " pop_number : Number of individuals in population\n", | |
| " cities : cities in letter code \"\"\"\n", | |
| " population = []\n", | |
| " for index in range(pop_number):\n", | |
| " population.append(shuffle_chromosomes(cities))\n", | |
| " return population\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "We can calculate the fitness of a path using the `evaluate_path` function. Note that shorter paths are considered fitter." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "To map\n", | |
| "[A, B] --> [a, b]\n", | |
| "\n", | |
| "use this formula\n", | |
| "(val - A)*(b-a)/(B-A) + a" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%% md\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 12, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "def fitness(sample: list):\n", | |
| " plain_text_cities = path2cities(sample)\n", | |
| " distance = evaluate_path(plain_text_cities, distance_function)\n", | |
| " \"\"\"\n", | |
| " The GAs are used for maximization problem. Since TSP is a minimization problem one way of defining a \"fitness function\"\n", | |
| " F ( x ) = 1/ f ( x )\n", | |
| " where f (x) is the objective function\n", | |
| " \"\"\"\n", | |
| " return 1/distance\n", | |
| "\n", | |
| "long_path = ['Sursee', 'Sion', 'Altdorf', 'Landquart', 'Konolfingen']\n", | |
| "short_path = ['Sursee', 'Sion']\n", | |
| "long_path_letter = path2string(long_path)\n", | |
| "short_path_letter = path2string(short_path)\n", | |
| "\n", | |
| "\n", | |
| "long_path_fitness = fitness(long_path_letter)\n", | |
| "short_path_fitness= fitness(short_path_letter)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 13, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "['E', 'D', 'A', 'I', 'K', 'L', 'O', 'B', 'M', 'N', 'H', 'J', 'C', 'F', 'G']\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# test shuffle\n", | |
| "test_path = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']\n", | |
| "print(str(shuffle_chromosomes(test_path)))" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Create a function to select two individuals for mating. Fitter individuals are more likely to be selected for reproduction than less fit individuals. Therefore, we have to calculate the weights of each indiviudal that corresponds to the likelyhood of being chosen for reproduction." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 14, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": "0" | |
| }, | |
| "execution_count": 14, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "import numpy.random as npr\n", | |
| "\n", | |
| "# https://stackoverflow.com/questions/10324015/fitness-proportionate-selection-roulette-wheel-selection-in-python\n", | |
| "def select_one_individual_by_weighted_random_choice(population):\n", | |
| " fitness_list_current_individual = [fitness(c) for c in population]\n", | |
| " maximum_value = sum(fitness_list_current_individual)\n", | |
| " # The probabilities associated with each entry\n", | |
| " selection_probs = [f/maximum_value for f in fitness_list_current_individual]\n", | |
| " return npr.choice(len(population), p=selection_probs)\n", | |
| "\n", | |
| "\n", | |
| "def do_roulette_wheel_selection(population, fraction):\n", | |
| " individuals_to_select = len(population) / fraction\n", | |
| " new_population = []\n", | |
| " while len(new_population) <= individuals_to_select:\n", | |
| " index = select_one_individual_by_weighted_random_choice(population)\n", | |
| " selected_individual = population[index]\n", | |
| " new_population.append(selected_individual)\n", | |
| "\n", | |
| " return new_population\n", | |
| "\n", | |
| "\n", | |
| "cities = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']\n", | |
| "pop = init_random_population(2,cities )\n", | |
| "#pop = do_selection(pop, 10)\n", | |
| "select_one_individual_by_weighted_random_choice(pop)" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Now that we can select two individuals, we make them reproduce using crossover and mutation. We need to consider that we want to visit every city exactly once. For example, for the crossover, you can take a random lenght of individual 1 and fill up the remaining cities based on the order of the unvisited cities in individual 2." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 15, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']\n", | |
| "['H', 'F', 'K', 'J', 'I', 'A', 'G', 'N', 'E', 'B', 'M', 'L', 'D', 'C', 'O']\n", | |
| "['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'K', 'J', 'I', 'N', 'M', 'L', 'O']\n", | |
| "['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'K', 'J', 'I', 'N', 'M', 'L', 'O']\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# for now, crossover probability is always 1\n", | |
| "#\n", | |
| "import random\n", | |
| "from random import randrange\n", | |
| "import math\n", | |
| "\n", | |
| "def get_random_index_in_range(begin, end) -> int:\n", | |
| " return random.randrange(begin, end)\n", | |
| "\n", | |
| "def fill_up_remaining_cities_based_on_order(left, parent2):\n", | |
| " right_chromosome = list()\n", | |
| " for city in parent2:\n", | |
| " test_element = city\n", | |
| " if test_element not in left:\n", | |
| " right_chromosome.append(test_element)\n", | |
| " return right_chromosome\n", | |
| " \n", | |
| " \n", | |
| "\n", | |
| "def crossover(parent1, parent2, p_crossover):\n", | |
| " if random.random() < float(p_crossover):\n", | |
| " # create an offspring from the parents x and y\n", | |
| " if len(parent1) != len(parent2):\n", | |
| " raise ValueError('chromosome parents are expected to be of equal length')\n", | |
| " x = parent1.copy()\n", | |
| " y = parent2.copy()\n", | |
| " # crossover_index = get_random_index_in_range(0, len(x))\n", | |
| " crossover_index = math.floor(len(x)/2)\n", | |
| " left_chromosome = x[0:crossover_index]\n", | |
| " right_chromosome = fill_up_remaining_cities_based_on_order(left_chromosome, y)\n", | |
| " child = left_chromosome + right_chromosome\n", | |
| " if len(parent2) != len(child):\n", | |
| " raise ValueError('fatal length of child differs from length of parent')\n", | |
| " return child\n", | |
| " else: # We are not always doing crossover. If we don't do it, just take the parent with max fitness\n", | |
| " fitness1 = fitness(parent1)\n", | |
| " fitness2 = fitness(parent2)\n", | |
| " if fitness1 > fitness2:\n", | |
| " return parent1\n", | |
| " else:\n", | |
| " return parent2\n", | |
| "\n", | |
| "def swap(index1, index2, liste: list ):\n", | |
| " liste[index1], liste[index2] = liste[index2], liste[index1]\n", | |
| " return liste\n", | |
| "\n", | |
| "\n", | |
| "def generate_two_random_indexes(length):\n", | |
| " # print(f\"length = {length}\")\n", | |
| "\n", | |
| " liste = random.sample(range(0, length), 2)\n", | |
| " while liste[0] == liste[1]:\n", | |
| " liste = random.sample(range(0, length), 2)\n", | |
| " return liste[0], liste[1]\n", | |
| "\n", | |
| "def mutate(chromosomes: list, p_mutate):\n", | |
| " # print(f\"len(chromosomes) == {len(chromosomes)}\")\n", | |
| " # switch the location of two cities\n", | |
| " random_generated_ = random.random()\n", | |
| " if random_generated_ < float(p_mutate): # mutate probability\n", | |
| " # print(f\"triggered mutate probability with p_mutate = {p_mutate}\")\n", | |
| " # determine indexes to switch at random:\n", | |
| " rand_swap_index1, rand_swap_index2 = generate_two_random_indexes(len(chromosomes))\n", | |
| " assert rand_swap_index1 != rand_swap_index2\n", | |
| " # print(f\"swapping rand_swap_index1 {rand_swap_index1} with rand_swap_index2 {rand_swap_index2}\")\n", | |
| " chromosomes = swap(rand_swap_index1, rand_swap_index2, chromosomes)\n", | |
| " # else :\n", | |
| " #print(f\" no mutation occured. probability was not in your favour.\"\n", | |
| " # f\" random_generated_ {random_generated_} is not less than p_mutate {p_mutate}\")\n", | |
| " return chromosomes\n", | |
| "\n", | |
| "\n", | |
| "# test your code\n", | |
| "x = path_code\n", | |
| "y = random.sample(path_code, len(path_code))\n", | |
| "xy = crossover(x,y, 0.3)\n", | |
| "print(x)\n", | |
| "print(y)\n", | |
| "print(xy)\n", | |
| "mutate(xy, 0.5)\n", | |
| "print(xy)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 16, | |
| "outputs": [], | |
| "source": [ | |
| "def mate_parents_until_enough_child(selected_individuals, new_population_size, prob) -> list:\n", | |
| " \"\"\" this function performs random selection of parents and generates as many childs as size\n", | |
| " new_population_size. Typically, population size tends to be constant, although there are\n", | |
| " variations of the algorithm where the size evolves over time \"\"\"\n", | |
| "\n", | |
| " population_size = new_population_size\n", | |
| " new_population = list()\n", | |
| " while len(new_population) < population_size:\n", | |
| " random_index_1, random_index_2 = generate_two_random_indexes(len(selected_individuals))\n", | |
| " random_parent_1 = selected_individuals[random_index_1]\n", | |
| " random_parent_2 = selected_individuals[random_index_2]\n", | |
| " assert random_index_1 != random_index_2\n", | |
| " new_individual = crossover(random_parent_1, random_parent_2, prob)\n", | |
| " new_population.append(new_individual)\n", | |
| " return new_population\n", | |
| "\n", | |
| "\n", | |
| "def apply_mutation_on_population(population, MUTATION_PROBABILITY) -> list:\n", | |
| " result = [mutate(p, MUTATION_PROBABILITY) for p in population]\n", | |
| " return result\n" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 17, | |
| "outputs": [], | |
| "source": [ | |
| "def find_best_individual(population):\n", | |
| " min_fitness = float('inf')\n", | |
| " _individual = population[0]\n", | |
| " for individual in population:\n", | |
| " fit = fitness(individual)\n", | |
| " min_fitness = min(fit, min_fitness)\n", | |
| " _individual = individual\n", | |
| " return _individual" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 18, | |
| "outputs": [ | |
| { | |
| "name": "stderr", | |
| "output_type": "stream", | |
| "text": [ | |
| "test_after_roulette_wheel_selection_average_fitness_should_not_be_worse_than_before (__main__.TestMutateAndCrossOverMethods) ... ok\n", | |
| "test_all_fitness_in_specified_range (__main__.TestMutateAndCrossOverMethods) ... skipped 'normalize values over the individual https://www.wikiwand.com/en/Selection_(genetic_algorithm)'\n", | |
| "test_apply_Mutate_on_population (__main__.TestMutateAndCrossOverMethods) ... ok\n", | |
| "test_crossover_always_yields_correct_ouputs (__main__.TestMutateAndCrossOverMethods) ... ok\n", | |
| "test_crossover_should_not_contain_duplicates (__main__.TestMutateAndCrossOverMethods) ... ok\n", | |
| "test_fitness (__main__.TestMutateAndCrossOverMethods) ... FAIL\n", | |
| "test_fitness_function_should_return_higher_values_for_longer_paths (__main__.TestMutateAndCrossOverMethods) ... FAIL\n", | |
| "test_generate_two_random_indexes (__main__.TestMutateAndCrossOverMethods) ... ok\n", | |
| "test_mutate (__main__.TestMutateAndCrossOverMethods) ... ok\n", | |
| "test_python_equal (__main__.TestMutateAndCrossOverMethods) ... ok\n", | |
| "test_rand_range (__main__.TestMutateAndCrossOverMethods) ... ok\n", | |
| "test_random_list_shuffle_is_actually_random (__main__.TestMutateAndCrossOverMethods) ... ok\n", | |
| "test_swap (__main__.TestMutateAndCrossOverMethods) ... " | |
| ] | |
| }, | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "printing random_pop\n", | |
| "[['I', 'J', 'K', 'O', 'D', 'F', 'G', 'B', 'C', 'E', 'L', 'A', 'N', 'M', 'H']]\n", | |
| "printing random_pop modified\n", | |
| "[['I', 'H', 'K', 'O', 'D', 'F', 'G', 'B', 'C', 'E', 'L', 'A', 'N', 'M', 'J']]\n", | |
| "long_path_letter = ['I', 'C', 'J', 'M', 'E']\n", | |
| "short_path_letter = ['I', 'C']\n", | |
| "rand_pop\n", | |
| "[['E', 'H', 'J', 'D', 'C', 'I', 'L', 'B', 'M', 'G', 'A', 'F', 'O', 'K', 'N']]\n", | |
| "result:\n", | |
| "['E', 'H', 'J', 'D', 'C', 'I', 'L', 'B', 'M', 'A', 'G', 'F', 'O', 'K', 'N']\n" | |
| ] | |
| }, | |
| { | |
| "name": "stderr", | |
| "output_type": "stream", | |
| "text": [ | |
| "ok\n", | |
| "\n", | |
| "======================================================================\n", | |
| "FAIL: test_fitness (__main__.TestMutateAndCrossOverMethods)\n", | |
| "----------------------------------------------------------------------\n", | |
| "Traceback (most recent call last):\n", | |
| " File \"/tmp/ipykernel_37146/3173674888.py\", line 80, in test_fitness\n", | |
| " self.assertGreater(fitness(long_path), fitness(short_path))\n", | |
| "AssertionError: 0.002273351429998312 not greater than 0.004173369461019259\n", | |
| "\n", | |
| "======================================================================\n", | |
| "FAIL: test_fitness_function_should_return_higher_values_for_longer_paths (__main__.TestMutateAndCrossOverMethods)\n", | |
| "----------------------------------------------------------------------\n", | |
| "Traceback (most recent call last):\n", | |
| " File \"/tmp/ipykernel_37146/3173674888.py\", line 66, in test_fitness_function_should_return_higher_values_for_longer_paths\n", | |
| " self.assertGreater(long_path_fitness, short_path_fitness)\n", | |
| "AssertionError: 0.0016541063078792438 not greater than 0.004173369461019259\n", | |
| "\n", | |
| "----------------------------------------------------------------------\n", | |
| "Ran 13 tests in 0.059s\n", | |
| "\n", | |
| "FAILED (failures=2, skipped=1)\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "text/plain": "<unittest.main.TestProgram at 0x7fc9d4cd4850>" | |
| }, | |
| "execution_count": 18, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "import copy\n", | |
| "import random\n", | |
| "import unittest\n", | |
| "\n", | |
| "class TestMutateAndCrossOverMethods(unittest.TestCase):\n", | |
| "\n", | |
| " def test_rand_range(self):\n", | |
| " from random import randrange\n", | |
| " for i in range(1000):\n", | |
| " rand_int = randrange(10)\n", | |
| " self.assertTrue(rand_int != 10)\n", | |
| "\n", | |
| " def test_crossover_should_not_contain_duplicates(self):\n", | |
| " cities = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']\n", | |
| "\n", | |
| " sample1 = shuffle_chromosomes(cities)\n", | |
| " sample2 = shuffle_chromosomes(cities)\n", | |
| " self.assertNotEqual(sample2, sample1)\n", | |
| "\n", | |
| " crossover_appplied = crossover(sample1, sample2, 0.3)\n", | |
| " result_as_set = set(crossover_appplied)\n", | |
| " self.assertEqual(len(sample1),len(sample2) )\n", | |
| " self.assertEqual(len(result_as_set), len(sample2) )\n", | |
| "\n", | |
| " def test_crossover_always_yields_correct_ouputs(self):\n", | |
| " cities = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']\n", | |
| " for i in range(1000): # just to get a larger sample\n", | |
| " sample1 = shuffle_chromosomes(cities)\n", | |
| " sample2 = shuffle_chromosomes(cities)\n", | |
| " self.assertNotEqual(sample2, sample1)\n", | |
| " crossover_applied = crossover(sample1, sample2, 0.3)\n", | |
| " result_as_set = set(crossover_applied)\n", | |
| " self.assertEqual(len(sample1),len(sample2) )\n", | |
| " self.assertEqual(len(result_as_set), len(sample2) )\n", | |
| "\n", | |
| "\n", | |
| " def test_after_roulette_wheel_selection_average_fitness_should_not_be_worse_than_before(self):\n", | |
| " # this is not necessarily true. The average fitness should be equalor greater\n", | |
| " cities = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']\n", | |
| " initial_population = init_random_population(100, cities)\n", | |
| " selected_population = do_roulette_wheel_selection(initial_population, 10)\n", | |
| " initial_fitness = sum([fitness(c) for c in initial_population])\n", | |
| " fitness_after_selection = sum([fitness(c) for c in selected_population])\n", | |
| "\n", | |
| "\n", | |
| " # better_fitness_individual1 = ['A', 'B']\n", | |
| " # better_fitness_individual2 = ['A', 'C']\n", | |
| "\n", | |
| " self.assertTrue(len(selected_population), len(initial_population)/10)\n", | |
| " self.assertGreaterEqual(fitness_after_selection/len(selected_population), initial_fitness/len(initial_population))\n", | |
| "\n", | |
| "\n", | |
| " def test_fitness_function_should_return_higher_values_for_longer_paths(self):\n", | |
| " long_path = ['Sursee', 'Sion', 'Altdorf', 'Landquart', 'Konolfingen']\n", | |
| " short_path = ['Sursee', 'Sion']\n", | |
| " long_path_letter = path2string(long_path)\n", | |
| " short_path_letter = path2string(short_path)\n", | |
| "\n", | |
| "\n", | |
| " print(f\"long_path_letter = {long_path_letter}\")\n", | |
| " print(f\"short_path_letter = {short_path_letter}\")\n", | |
| "\n", | |
| " long_path_fitness = fitness(long_path_letter)\n", | |
| " short_path_fitness= fitness(short_path_letter)\n", | |
| "\n", | |
| " self.assertGreater(long_path_fitness, short_path_fitness)\n", | |
| "\n", | |
| " def test_random_list_shuffle_is_actually_random(self):\n", | |
| " my_path = ['Sursee', 'Sion', 'Altdorf', 'Landquart', 'Konolfingen', 'Thun', 'Twann', 'Sargans', 'Lausanne', 'Vevey', 'Locarno', 'Hinwil', 'Bern', 'Liestal']\n", | |
| " random_init_population1 = shuffle_chromosomes(my_path)\n", | |
| " random_init_population2 = shuffle_chromosomes(my_path)\n", | |
| " self.assertNotEqual(random_init_population2, random_init_population1)\n", | |
| "\n", | |
| " def test_fitness(self):\n", | |
| " long_path = path2string(['Lausanne', 'Locarno'])\n", | |
| " short_path = path2string(['Sursee', 'Sion'])\n", | |
| " #print(f\"short_path = {short_path}\")\n", | |
| " #print(f\"long_path = {long_path}\")\n", | |
| "\n", | |
| " self.assertGreater(fitness(long_path), fitness(short_path))\n", | |
| "\n", | |
| " @unittest.skip(\"normalize values over the individual https://www.wikiwand.com/en/Selection_(genetic_algorithm)\")\n", | |
| " def test_all_fitness_in_specified_range(self):\n", | |
| " my_path = ['Sursee', 'Sion', 'Altdorf', 'Landquart', 'Konolfingen', 'Thun', 'Twann', 'Sargans', 'Lausanne', 'Vevey', 'Locarno', 'Hinwil', 'Bern', 'Liestal']\n", | |
| " # loop through every combination, check to see if fitness is in expected range\n", | |
| " for city1 in my_path:\n", | |
| " for city2 in my_path:\n", | |
| " curent_pair = path2string([city1, city2])\n", | |
| " curent_fitness = fitness(curent_pair)\n", | |
| " # fitness should be in range 0 .. 1\n", | |
| " self.assertGreaterEqual(curent_fitness, 0)\n", | |
| " self.assertLessEqual(curent_fitness, 1)\n", | |
| "\n", | |
| "\n", | |
| " def test_apply_Mutate_on_population(self):\n", | |
| " cities = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']\n", | |
| " rand_population = init_random_population(1, cities)\n", | |
| " initial_state = copy.deepcopy(rand_population)\n", | |
| " print(\"printing random_pop\")\n", | |
| " print(rand_population)\n", | |
| " apply_mutation_on_population(rand_population, 1) # function modifies the paramter\n", | |
| " print(\"printing random_pop modified\")\n", | |
| " print(rand_population)\n", | |
| " self.assertNotEqual(initial_state, rand_population)\n", | |
| "\n", | |
| " def test_mutate(self):\n", | |
| " cities = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']\n", | |
| " rand_population = init_random_population(1, cities)\n", | |
| " print(\"rand_pop\")\n", | |
| " print(rand_population)\n", | |
| " result = mutate(rand_population[0], 1) # always mutate just for easy testing\n", | |
| " print(\"result:\")\n", | |
| " print(result)\n", | |
| " check = rand_population == result\n", | |
| " self.assertFalse(check)\n", | |
| " self.assertNotEqual(rand_population, result)\n", | |
| "\n", | |
| " def test_python_equal(self):\n", | |
| " l = ['A', 'B', 'C']\n", | |
| " d = ['C', 'A', 'B']\n", | |
| " self.assertNotEqual(l, d)\n", | |
| "\n", | |
| " def test_swap(self):\n", | |
| " l = ['A', 'B', 'C']\n", | |
| " l = swap(0, 1, l)\n", | |
| " expected = ['B', 'A', 'C']\n", | |
| " self.assertEqual(l, expected)\n", | |
| "\n", | |
| " def test_generate_two_random_indexes(self):\n", | |
| " LENGTH = 10\n", | |
| " p1, p2 = generate_two_random_indexes(LENGTH)\n", | |
| " self.assertLess(p1, LENGTH)\n", | |
| " self.assertLess(p1, LENGTH)\n", | |
| " self.assertNotEqual(p1, p2)\n", | |
| "\n", | |
| "\n", | |
| "unittest.main(argv=[''], verbosity=2, exit=False)\n" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "We have now all the ingredients to create our genetic algorithm:\n", | |
| "\n", | |
| "\n", | |
| "\n", | |
| "1) Initialize random population.\n", | |
| "\n", | |
| "2) Calculate population fitness.\n", | |
| "\n", | |
| "3) Select individuals for mating.\n", | |
| "\n", | |
| "4) Mate selected individuals to produce new population.\n", | |
| "\n", | |
| " * Random chance to mutate individuals.\n", | |
| "\n", | |
| "5) Repeat from step 2) until an individual is fit enough or the maximum number of iterations was reached.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 38, | |
| "outputs": [], | |
| "source": [ | |
| "class Individual:\n", | |
| " def __init__(self, chromosome:list , fit: float):\n", | |
| " self.chromosome: list = chromosome\n", | |
| " self.fit: float = fit\n", | |
| " def __str__(self):\n", | |
| " close_enough = \"{:.7f}\".format(self.fit)\n", | |
| " return \"chromosome = \" + str(self.chromosome) + \"fitness = \" + str(close_enough)\n", | |
| "\n", | |
| " def __hash__(self):\n", | |
| " return hash(('chromosome', tuple(self.chromosome),\n", | |
| " 'fit', self.fit))\n", | |
| " def __eq__(self, other):\n", | |
| " return self.chromosome==other.chromosome\\\n", | |
| " and self.fit==other.fit\n", | |
| "\n", | |
| "\n" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 42, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "chromosome = ['C', 'B', 'A', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']fitness = 0.0012037 Iteration = 0\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 100\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 200\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 300\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 400\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 500\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 600\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 700\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 800\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 900\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1000\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1100\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1200\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1300\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1400\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1500\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1600\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1700\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1800\n", | |
| "chromosome = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'O', 'K', 'L', 'M', 'N', 'J']fitness = 0.0012037 Iteration = 1900\n", | |
| "duplicate_count = 307\n", | |
| "all_items = 2000\n", | |
| "successfully imported 2787 hubs\n", | |
| "successfully imported 401 train lines\n", | |
| "['Lausanne', 'Vevey', 'Sion', 'Thun', 'Konolfingen', 'Bern', 'Twann', 'Liestal', 'Sursee', 'Locarno', 'Hinwil', 'Sargans', 'Landquart', 'Lugano', 'Altdorf']\n", | |
| "path cost = 1043.419739611325\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "\"\"\"\n", | |
| "Genetic Algorithm - Travelling Salesman Problem - Main\n", | |
| "\"\"\"\n", | |
| "\n", | |
| "POPULATION_SIZE = 50\n", | |
| "MUTATION_PROBABILITY = 0.5\n", | |
| "CROSSOVER_PROBABILITY = 0.5\n", | |
| "TOTAL_ITERATIONS = 2000\n", | |
| "current_iterations_count = 0\n", | |
| "\n", | |
| "\n", | |
| "pop = init_population(POPULATION_SIZE, path2string(path))\n", | |
| "\n", | |
| "elites_for_each_generation = []\n", | |
| "\n", | |
| "while current_iterations_count < TOTAL_ITERATIONS:\n", | |
| " selected_individuals = do_roulette_wheel_selection(pop, fraction=10)\n", | |
| " new_population_after_mating = mate_parents_until_enough_child(pop, POPULATION_SIZE, CROSSOVER_PROBABILITY)\n", | |
| " pop = apply_mutation_on_population(new_population_after_mating, MUTATION_PROBABILITY)\n", | |
| "\n", | |
| " individuals = []\n", | |
| " for e in pop:\n", | |
| " individuals.append(Individual(e, fitness(e)))\n", | |
| "\n", | |
| " from operator import attrgetter\n", | |
| " best: Individual = max(individuals, key=attrgetter('fit'))\n", | |
| " elites_for_each_generation.append(best)\n", | |
| "\n", | |
| " if current_iterations_count % 100 == 0:\n", | |
| " best: Individual = max(elites_for_each_generation, key=attrgetter('fit'))\n", | |
| " print(str(best) + \" Iteration = \"+ str(current_iterations_count))\n", | |
| "\n", | |
| " current_iterations_count += 1\n", | |
| "\n", | |
| "non_duplicates = set(elites_for_each_generation)\n", | |
| "all_items = len(elites_for_each_generation)\n", | |
| "duplicate_count = all_items - len(non_duplicates)\n", | |
| "\n", | |
| "print(f\"duplicate_count = {duplicate_count}\")\n", | |
| "print(f\"all_items = {all_items}\")\n", | |
| "\n", | |
| "best: Individual = max(elites_for_each_generation, key=attrgetter('fit'))\n", | |
| "best_path = path2cities(best.chromosome)\n", | |
| "\n", | |
| "from sbb import SBB\n", | |
| "sbb = SBB()\n", | |
| "sbb.import_data('linie-mit-betriebspunkten.json')\n", | |
| "distance_function = sbb.get_distance_between\n", | |
| "\n", | |
| "print(best_path)\n", | |
| "print(\"path cost = \" + str(evaluate_path(best_path, distance_function)))\n", | |
| "\n", | |
| "# key_best_individual = max(elites_for_each_generation, key=elites_for_each_generation.get)\n", | |
| "# best_individual = elites_for_each_generation[key_best_individual]\n", | |
| "# print(f\"best_individual = {best_individual}\")\n" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 24, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/plain": "<folium.folium.Map at 0x7fc9d4c83a10>", | |
| "text/html": "<div style=\"width:100%;\"><div style=\"position:relative;width:100%;height:0;padding-bottom:60%;\"><span style=\"color:#565656\">Make this Notebook Trusted to load map: File -> Trust Notebook</span><iframe srcdoc=\"<!DOCTYPE html>\n<head> \n <meta http-equiv="content-type" content="text/html; charset=UTF-8" />\n \n <script>\n L_NO_TOUCH = false;\n L_DISABLE_3D = false;\n </script>\n \n <style>html, body {width: 100%;height: 100%;margin: 0;padding: 0;}</style>\n <style>#map {position:absolute;top:0;bottom:0;right:0;left:0;}</style>\n <script src="https://cdn.jsdelivr.net/npm/leaflet@1.6.0/dist/leaflet.js"></script>\n <script src="https://code.jquery.com/jquery-1.12.4.min.js"></script>\n <script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.min.js"></script>\n <script src="https://cdnjs.cloudflare.com/ajax/libs/Leaflet.awesome-markers/2.0.2/leaflet.awesome-markers.js"></script>\n <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/leaflet@1.6.0/dist/leaflet.css"/>\n <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap.min.css"/>\n <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap-theme.min.css"/>\n <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/font-awesome/4.6.3/css/font-awesome.min.css"/>\n <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/Leaflet.awesome-markers/2.0.2/leaflet.awesome-markers.css"/>\n <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/python-visualization/folium/folium/templates/leaflet.awesome.rotate.min.css"/>\n \n <meta name="viewport" content="width=device-width,\n initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />\n <style>\n #map_9c856fbc980697f5c6f9ad1f4c1ea79e {\n position: relative;\n width: 100.0%;\n height: 100.0%;\n left: 0.0%;\n top: 0.0%;\n }\n </style>\n \n</head>\n<body> \n \n <div class="folium-map" id="map_9c856fbc980697f5c6f9ad1f4c1ea79e" ></div>\n \n</body>\n<script> \n \n var map_9c856fbc980697f5c6f9ad1f4c1ea79e = L.map(\n "map_9c856fbc980697f5c6f9ad1f4c1ea79e",\n {\n center: [46.8, 8.33],\n crs: L.CRS.EPSG3857,\n zoom: 8,\n zoomControl: true,\n preferCanvas: false,\n }\n );\n\n \n\n \n \n var tile_layer_a43a0574783c9c05e44f6b2bebde742e = L.tileLayer(\n "https://stamen-tiles-{s}.a.ssl.fastly.net/toner-background/{z}/{x}/{y}{r}.png",\n {"attribution": "Map tiles by \\u003ca href=\\"http://stamen.com\\"\\u003eStamen Design\\u003c/a\\u003e, under \\u003ca href=\\"http://creativecommons.org/licenses/by/3.0\\"\\u003eCC BY 3.0\\u003c/a\\u003e. Data by \\u003ca href=\\"http://openstreetmap.org\\"\\u003eOpenStreetMap\\u003c/a\\u003e, under \\u003ca href=\\"http://www.openstreetmap.org/copyright\\"\\u003eODbL\\u003c/a\\u003e.", "detectRetina": false, "maxNativeZoom": 18, "maxZoom": 18, "minZoom": 0, "noWrap": false, "opacity": 1, "subdomains": "abc", "tms": false}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var marker_34dfc21bc23b522f1c1f3515818c5f05 = L.marker(\n [46.5167918355, 6.6290923032],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_530dbb9fc811a730de97f84e2c038b96 = L.popup({"maxWidth": "100%"});\n\n \n var html_94f08fc3854fcc5936705e95a9ed4c6d = $(`<div id="html_94f08fc3854fcc5936705e95a9ed4c6d" style="width: 100.0%; height: 100.0%;">Lausanne</div>`)[0];\n popup_530dbb9fc811a730de97f84e2c038b96.setContent(html_94f08fc3854fcc5936705e95a9ed4c6d);\n \n\n marker_34dfc21bc23b522f1c1f3515818c5f05.bindPopup(popup_530dbb9fc811a730de97f84e2c038b96)\n ;\n\n \n \n \n var marker_5e7f6c9b747778ca4e2f3e088ab101d0 = L.marker(\n [46.4630018107, 6.84344559824],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_ac4fb77ed393244c5033de522d4088a9 = L.popup({"maxWidth": "100%"});\n\n \n var html_b8d577cd3525e7f1d0fce1aa6926b9c0 = $(`<div id="html_b8d577cd3525e7f1d0fce1aa6926b9c0" style="width: 100.0%; height: 100.0%;">Vevey</div>`)[0];\n popup_ac4fb77ed393244c5033de522d4088a9.setContent(html_b8d577cd3525e7f1d0fce1aa6926b9c0);\n \n\n marker_5e7f6c9b747778ca4e2f3e088ab101d0.bindPopup(popup_ac4fb77ed393244c5033de522d4088a9)\n ;\n\n \n \n \n var marker_9984ebf3ecb84b6ba01200259152c544 = L.marker(\n [46.2275531964, 7.35919703457],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_49819ce61b2cd56c6cf06e5ab0916ff4 = L.popup({"maxWidth": "100%"});\n\n \n var html_9fcc5355acb892fb2fcf83e59f146321 = $(`<div id="html_9fcc5355acb892fb2fcf83e59f146321" style="width: 100.0%; height: 100.0%;">Sion</div>`)[0];\n popup_49819ce61b2cd56c6cf06e5ab0916ff4.setContent(html_9fcc5355acb892fb2fcf83e59f146321);\n \n\n marker_9984ebf3ecb84b6ba01200259152c544.bindPopup(popup_49819ce61b2cd56c6cf06e5ab0916ff4)\n ;\n\n \n \n \n var marker_da8460e2eec5512bebc42b3a3faba260 = L.marker(\n [46.7548527306, 7.62960582867],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_163df42f72b99d898010f82190509232 = L.popup({"maxWidth": "100%"});\n\n \n var html_9cf5dae5fde9220c3fe2adf14d92cab5 = $(`<div id="html_9cf5dae5fde9220c3fe2adf14d92cab5" style="width: 100.0%; height: 100.0%;">Thun</div>`)[0];\n popup_163df42f72b99d898010f82190509232.setContent(html_9cf5dae5fde9220c3fe2adf14d92cab5);\n \n\n marker_da8460e2eec5512bebc42b3a3faba260.bindPopup(popup_163df42f72b99d898010f82190509232)\n ;\n\n \n \n \n var marker_8223d79ab51eeb044061c3dc8380bbe3 = L.marker(\n [46.8807024189, 7.6213670273],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_7bbc858ec85a08fd0cc03d7fa553c388 = L.popup({"maxWidth": "100%"});\n\n \n var html_72ebc3b45f484f88dc75bee7090bb3ea = $(`<div id="html_72ebc3b45f484f88dc75bee7090bb3ea" style="width: 100.0%; height: 100.0%;">Konolfingen</div>`)[0];\n popup_7bbc858ec85a08fd0cc03d7fa553c388.setContent(html_72ebc3b45f484f88dc75bee7090bb3ea);\n \n\n marker_8223d79ab51eeb044061c3dc8380bbe3.bindPopup(popup_7bbc858ec85a08fd0cc03d7fa553c388)\n ;\n\n \n \n \n var marker_b4e8d707baa3cc65bd1d372bdda50338 = L.marker(\n [46.9488322905, 7.43913088992],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_0d79a73412222a94b400c362b2c49205 = L.popup({"maxWidth": "100%"});\n\n \n var html_07c6fb6e10eee9d2dfdda5df56258761 = $(`<div id="html_07c6fb6e10eee9d2dfdda5df56258761" style="width: 100.0%; height: 100.0%;">Bern</div>`)[0];\n popup_0d79a73412222a94b400c362b2c49205.setContent(html_07c6fb6e10eee9d2dfdda5df56258761);\n \n\n marker_b4e8d707baa3cc65bd1d372bdda50338.bindPopup(popup_0d79a73412222a94b400c362b2c49205)\n ;\n\n \n \n \n var marker_22dc1615d1a605219e32816aab9c3d3a = L.marker(\n [47.0936640656, 7.15649750354],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_142f11cd7891716ebbbf4986874aaac5 = L.popup({"maxWidth": "100%"});\n\n \n var html_066298d36ffc5a0a1fffbbd1ac5672a4 = $(`<div id="html_066298d36ffc5a0a1fffbbd1ac5672a4" style="width: 100.0%; height: 100.0%;">Twann</div>`)[0];\n popup_142f11cd7891716ebbbf4986874aaac5.setContent(html_066298d36ffc5a0a1fffbbd1ac5672a4);\n \n\n marker_22dc1615d1a605219e32816aab9c3d3a.bindPopup(popup_142f11cd7891716ebbbf4986874aaac5)\n ;\n\n \n \n \n var marker_fd99c2169896def7afe452d791d2a885 = L.marker(\n [47.4844611721, 7.7313674807],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_900b58da3833df26bd38a053a99f8d6c = L.popup({"maxWidth": "100%"});\n\n \n var html_4f0648bd5dd08e18b497b3988cf295dc = $(`<div id="html_4f0648bd5dd08e18b497b3988cf295dc" style="width: 100.0%; height: 100.0%;">Liestal</div>`)[0];\n popup_900b58da3833df26bd38a053a99f8d6c.setContent(html_4f0648bd5dd08e18b497b3988cf295dc);\n \n\n marker_fd99c2169896def7afe452d791d2a885.bindPopup(popup_900b58da3833df26bd38a053a99f8d6c)\n ;\n\n \n \n \n var marker_073f0143910324b815ce60e9fe7baca1 = L.marker(\n [47.1707950409, 8.09789386466],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_f0fd314debcd588c6400763c8550a572 = L.popup({"maxWidth": "100%"});\n\n \n var html_2a2546ff45e7eb7bfcbb0894e82e750e = $(`<div id="html_2a2546ff45e7eb7bfcbb0894e82e750e" style="width: 100.0%; height: 100.0%;">Sursee</div>`)[0];\n popup_f0fd314debcd588c6400763c8550a572.setContent(html_2a2546ff45e7eb7bfcbb0894e82e750e);\n \n\n marker_073f0143910324b815ce60e9fe7baca1.bindPopup(popup_f0fd314debcd588c6400763c8550a572)\n ;\n\n \n \n \n var marker_ee5776999d4fcf1aeeeb596a4abf6f77 = L.marker(\n [46.8757387133, 8.63157541744],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_244609bd610c6ae982955baa860a0cbd = L.popup({"maxWidth": "100%"});\n\n \n var html_16d069d660b273442b9780a52764c497 = $(`<div id="html_16d069d660b273442b9780a52764c497" style="width: 100.0%; height: 100.0%;">Altdorf</div>`)[0];\n popup_244609bd610c6ae982955baa860a0cbd.setContent(html_16d069d660b273442b9780a52764c497);\n \n\n marker_ee5776999d4fcf1aeeeb596a4abf6f77.bindPopup(popup_244609bd610c6ae982955baa860a0cbd)\n ;\n\n \n \n \n var marker_9d104a6ec01470500770a546a6bfd5b3 = L.marker(\n [47.3000569504, 8.83971989441],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_af50bb70c33ef1e6491dd7bf15767d4e = L.popup({"maxWidth": "100%"});\n\n \n var html_3cfe8f385e8e8b3f719132fd57c12f99 = $(`<div id="html_3cfe8f385e8e8b3f719132fd57c12f99" style="width: 100.0%; height: 100.0%;">Hinwil</div>`)[0];\n popup_af50bb70c33ef1e6491dd7bf15767d4e.setContent(html_3cfe8f385e8e8b3f719132fd57c12f99);\n \n\n marker_9d104a6ec01470500770a546a6bfd5b3.bindPopup(popup_af50bb70c33ef1e6491dd7bf15767d4e)\n ;\n\n \n \n \n var marker_df6070f562eeb1f6dddcae907fa28cf6 = L.marker(\n [47.0448235144, 9.44626047466],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_ad6e627869776fde5214a94814f931d2 = L.popup({"maxWidth": "100%"});\n\n \n var html_d1b7074e81388151c03c977cf23da407 = $(`<div id="html_d1b7074e81388151c03c977cf23da407" style="width: 100.0%; height: 100.0%;">Sargans</div>`)[0];\n popup_ad6e627869776fde5214a94814f931d2.setContent(html_d1b7074e81388151c03c977cf23da407);\n \n\n marker_df6070f562eeb1f6dddcae907fa28cf6.bindPopup(popup_ad6e627869776fde5214a94814f931d2)\n ;\n\n \n \n \n var marker_686c1be35cec0f685db391a40a6e3465 = L.marker(\n [46.9674404284, 9.55404469208],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_b578fb0cb1c64c46c741e4291acb3f16 = L.popup({"maxWidth": "100%"});\n\n \n var html_b04ceecd65c9122c72912d5b54b37c33 = $(`<div id="html_b04ceecd65c9122c72912d5b54b37c33" style="width: 100.0%; height: 100.0%;">Landquart</div>`)[0];\n popup_b578fb0cb1c64c46c741e4291acb3f16.setContent(html_b04ceecd65c9122c72912d5b54b37c33);\n \n\n marker_686c1be35cec0f685db391a40a6e3465.bindPopup(popup_b578fb0cb1c64c46c741e4291acb3f16)\n ;\n\n \n \n \n var marker_4cb9e8bf6ada69d12341547592fcb242 = L.marker(\n [46.0055005499, 8.94699530851],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_45c40b4b49232d9b51475baa0a3a1ada = L.popup({"maxWidth": "100%"});\n\n \n var html_ee41035fdf35950ed02f0b209809fc5c = $(`<div id="html_ee41035fdf35950ed02f0b209809fc5c" style="width: 100.0%; height: 100.0%;">Lugano</div>`)[0];\n popup_45c40b4b49232d9b51475baa0a3a1ada.setContent(html_ee41035fdf35950ed02f0b209809fc5c);\n \n\n marker_4cb9e8bf6ada69d12341547592fcb242.bindPopup(popup_45c40b4b49232d9b51475baa0a3a1ada)\n ;\n\n \n \n \n var marker_899a2ea2980d8bf9f3bc7d52d58873f4 = L.marker(\n [46.1724201894, 8.80136089926],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_f797c54c98afe8a25f5be53fa722b691 = L.popup({"maxWidth": "100%"});\n\n \n var html_c188cea087bc236e94f65d219133ba3a = $(`<div id="html_c188cea087bc236e94f65d219133ba3a" style="width: 100.0%; height: 100.0%;">Locarno</div>`)[0];\n popup_f797c54c98afe8a25f5be53fa722b691.setContent(html_c188cea087bc236e94f65d219133ba3a);\n \n\n marker_899a2ea2980d8bf9f3bc7d52d58873f4.bindPopup(popup_f797c54c98afe8a25f5be53fa722b691)\n ;\n\n \n \n \n var poly_line_b69a38a6db67751cf6ca9e14439cc67b = L.polyline(\n [[46.5167918355, 6.6290923032], [46.4630018107, 6.84344559824], [46.2275531964, 7.35919703457], [46.7548527306, 7.62960582867], [46.8807024189, 7.6213670273], [46.9488322905, 7.43913088992], [47.0936640656, 7.15649750354], [47.4844611721, 7.7313674807], [47.1707950409, 8.09789386466], [46.8757387133, 8.63157541744], [47.3000569504, 8.83971989441], [47.0448235144, 9.44626047466], [46.9674404284, 9.55404469208], [46.0055005499, 8.94699530851], [46.1724201894, 8.80136089926], [46.5167918355, 6.6290923032]],\n {"bubblingMouseEvents": true, "color": "red", "dashArray": null, "dashOffset": null, "fill": false, "fillColor": "red", "fillOpacity": 0.2, "fillRule": "evenodd", "lineCap": "round", "lineJoin": "round", "noClip": false, "opacity": 1.0, "smoothFactor": 1.0, "stroke": true, "weight": 3}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var marker_5948cb82cabc621c74bd99ccb5c2ed1c = L.marker(\n [46.5167918355, 6.6290923032],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_5e61d1480f5bb0ee78d37f657e478763 = L.popup({"maxWidth": "100%"});\n\n \n var html_2a2d65db7a030f14e32b0cfd83e975ab = $(`<div id="html_2a2d65db7a030f14e32b0cfd83e975ab" style="width: 100.0%; height: 100.0%;">Lausanne</div>`)[0];\n popup_5e61d1480f5bb0ee78d37f657e478763.setContent(html_2a2d65db7a030f14e32b0cfd83e975ab);\n \n\n marker_5948cb82cabc621c74bd99ccb5c2ed1c.bindPopup(popup_5e61d1480f5bb0ee78d37f657e478763)\n ;\n\n \n \n \n var marker_801093f2e9d3502499211aa4ef1c7e49 = L.marker(\n [47.0448235144, 9.44626047466],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_3c6d0b3e6096d750f68e6829a226dc11 = L.popup({"maxWidth": "100%"});\n\n \n var html_4f9c5ce67b647f6dae0099789eb43763 = $(`<div id="html_4f9c5ce67b647f6dae0099789eb43763" style="width: 100.0%; height: 100.0%;">Sargans</div>`)[0];\n popup_3c6d0b3e6096d750f68e6829a226dc11.setContent(html_4f9c5ce67b647f6dae0099789eb43763);\n \n\n marker_801093f2e9d3502499211aa4ef1c7e49.bindPopup(popup_3c6d0b3e6096d750f68e6829a226dc11)\n ;\n\n \n \n \n var marker_ec303bed7230d9a40766f6276a728c97 = L.marker(\n [46.2275531964, 7.35919703457],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_bd444548edfea6efb1199341e17255f0 = L.popup({"maxWidth": "100%"});\n\n \n var html_bc06fda57a0ee6ac72daffde702b7d0f = $(`<div id="html_bc06fda57a0ee6ac72daffde702b7d0f" style="width: 100.0%; height: 100.0%;">Sion</div>`)[0];\n popup_bd444548edfea6efb1199341e17255f0.setContent(html_bc06fda57a0ee6ac72daffde702b7d0f);\n \n\n marker_ec303bed7230d9a40766f6276a728c97.bindPopup(popup_bd444548edfea6efb1199341e17255f0)\n ;\n\n \n \n \n var marker_2d51912cdab5a3e0a67fe97b8e25ce93 = L.marker(\n [47.1707950409, 8.09789386466],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_24ece83aa0f87fbf7ee46baa9c0d5d7e = L.popup({"maxWidth": "100%"});\n\n \n var html_131f031b588822e2289ba8a2b915687c = $(`<div id="html_131f031b588822e2289ba8a2b915687c" style="width: 100.0%; height: 100.0%;">Sursee</div>`)[0];\n popup_24ece83aa0f87fbf7ee46baa9c0d5d7e.setContent(html_131f031b588822e2289ba8a2b915687c);\n \n\n marker_2d51912cdab5a3e0a67fe97b8e25ce93.bindPopup(popup_24ece83aa0f87fbf7ee46baa9c0d5d7e)\n ;\n\n \n \n \n var marker_e3ac006d6eda56fc55ca2a2873e91034 = L.marker(\n [46.8807024189, 7.6213670273],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_abf738443bc664898148d9703f85f641 = L.popup({"maxWidth": "100%"});\n\n \n var html_305c182c7b4337d34d55e9f662d7a965 = $(`<div id="html_305c182c7b4337d34d55e9f662d7a965" style="width: 100.0%; height: 100.0%;">Konolfingen</div>`)[0];\n popup_abf738443bc664898148d9703f85f641.setContent(html_305c182c7b4337d34d55e9f662d7a965);\n \n\n marker_e3ac006d6eda56fc55ca2a2873e91034.bindPopup(popup_abf738443bc664898148d9703f85f641)\n ;\n\n \n \n \n var marker_bfa51c8820eb887370eb267eb4f4bab3 = L.marker(\n [46.9488322905, 7.43913088992],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_82e8c6d290d8b61c3d7100d5a08f83f5 = L.popup({"maxWidth": "100%"});\n\n \n var html_8fc99c68e2ae374651345401492b9da2 = $(`<div id="html_8fc99c68e2ae374651345401492b9da2" style="width: 100.0%; height: 100.0%;">Bern</div>`)[0];\n popup_82e8c6d290d8b61c3d7100d5a08f83f5.setContent(html_8fc99c68e2ae374651345401492b9da2);\n \n\n marker_bfa51c8820eb887370eb267eb4f4bab3.bindPopup(popup_82e8c6d290d8b61c3d7100d5a08f83f5)\n ;\n\n \n \n \n var marker_65e5e62bda095b340caff65aabf6ec81 = L.marker(\n [47.0936640656, 7.15649750354],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_b00f2c2685056cf859345a23a0de4135 = L.popup({"maxWidth": "100%"});\n\n \n var html_ba5876b712533869aa386c2670409ae6 = $(`<div id="html_ba5876b712533869aa386c2670409ae6" style="width: 100.0%; height: 100.0%;">Twann</div>`)[0];\n popup_b00f2c2685056cf859345a23a0de4135.setContent(html_ba5876b712533869aa386c2670409ae6);\n \n\n marker_65e5e62bda095b340caff65aabf6ec81.bindPopup(popup_b00f2c2685056cf859345a23a0de4135)\n ;\n\n \n \n \n var marker_1c52ac7289176ddb86c0551a79d81b43 = L.marker(\n [47.4844611721, 7.7313674807],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_ec092957e424dce85e7d235686f2812f = L.popup({"maxWidth": "100%"});\n\n \n var html_3180a5c2977a5a2c40117e434764d90f = $(`<div id="html_3180a5c2977a5a2c40117e434764d90f" style="width: 100.0%; height: 100.0%;">Liestal</div>`)[0];\n popup_ec092957e424dce85e7d235686f2812f.setContent(html_3180a5c2977a5a2c40117e434764d90f);\n \n\n marker_1c52ac7289176ddb86c0551a79d81b43.bindPopup(popup_ec092957e424dce85e7d235686f2812f)\n ;\n\n \n \n \n var marker_45d010ce6aec4d5f8cb5024e530ec62e = L.marker(\n [46.7548527306, 7.62960582867],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_db0575291910e4631c3ec266e046a0a7 = L.popup({"maxWidth": "100%"});\n\n \n var html_866d811e2805006eeedd48d3fc16a43c = $(`<div id="html_866d811e2805006eeedd48d3fc16a43c" style="width: 100.0%; height: 100.0%;">Thun</div>`)[0];\n popup_db0575291910e4631c3ec266e046a0a7.setContent(html_866d811e2805006eeedd48d3fc16a43c);\n \n\n marker_45d010ce6aec4d5f8cb5024e530ec62e.bindPopup(popup_db0575291910e4631c3ec266e046a0a7)\n ;\n\n \n \n \n var marker_9e6ebfc69b83aed9d8dc64c3f41b23e8 = L.marker(\n [46.8757387133, 8.63157541744],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_cbfa2de5fec7619202d67a3552c1e91d = L.popup({"maxWidth": "100%"});\n\n \n var html_9f72584dc22e46d5fc16ece84ecaa2e2 = $(`<div id="html_9f72584dc22e46d5fc16ece84ecaa2e2" style="width: 100.0%; height: 100.0%;">Altdorf</div>`)[0];\n popup_cbfa2de5fec7619202d67a3552c1e91d.setContent(html_9f72584dc22e46d5fc16ece84ecaa2e2);\n \n\n marker_9e6ebfc69b83aed9d8dc64c3f41b23e8.bindPopup(popup_cbfa2de5fec7619202d67a3552c1e91d)\n ;\n\n \n \n \n var marker_e18e391eb3d5c868b74aa61f7ab5ffd0 = L.marker(\n [47.3000569504, 8.83971989441],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_6832a49f8e9a322893a9c53934c331f2 = L.popup({"maxWidth": "100%"});\n\n \n var html_9335d4188a99d1957a5164790b2fb77a = $(`<div id="html_9335d4188a99d1957a5164790b2fb77a" style="width: 100.0%; height: 100.0%;">Hinwil</div>`)[0];\n popup_6832a49f8e9a322893a9c53934c331f2.setContent(html_9335d4188a99d1957a5164790b2fb77a);\n \n\n marker_e18e391eb3d5c868b74aa61f7ab5ffd0.bindPopup(popup_6832a49f8e9a322893a9c53934c331f2)\n ;\n\n \n \n \n var marker_6485a86c8e325152b529fbf32c6d841a = L.marker(\n [46.4630018107, 6.84344559824],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_cdecff9d4f4759adc62fd79394a9600c = L.popup({"maxWidth": "100%"});\n\n \n var html_894a53987bb776bf97e190aea558ffd1 = $(`<div id="html_894a53987bb776bf97e190aea558ffd1" style="width: 100.0%; height: 100.0%;">Vevey</div>`)[0];\n popup_cdecff9d4f4759adc62fd79394a9600c.setContent(html_894a53987bb776bf97e190aea558ffd1);\n \n\n marker_6485a86c8e325152b529fbf32c6d841a.bindPopup(popup_cdecff9d4f4759adc62fd79394a9600c)\n ;\n\n \n \n \n var marker_17a64cdec3112db6429e649cc9a759da = L.marker(\n [46.9674404284, 9.55404469208],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_78180bb48727ffb985b6a6421231b898 = L.popup({"maxWidth": "100%"});\n\n \n var html_98458b2d0a897b2401d05f900b2852ee = $(`<div id="html_98458b2d0a897b2401d05f900b2852ee" style="width: 100.0%; height: 100.0%;">Landquart</div>`)[0];\n popup_78180bb48727ffb985b6a6421231b898.setContent(html_98458b2d0a897b2401d05f900b2852ee);\n \n\n marker_17a64cdec3112db6429e649cc9a759da.bindPopup(popup_78180bb48727ffb985b6a6421231b898)\n ;\n\n \n \n \n var marker_ac1bd12f87abd65a1c6153eb1d0b6952 = L.marker(\n [46.0055005499, 8.94699530851],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_f14c2c84163ab26968f0758f5ff3cfbc = L.popup({"maxWidth": "100%"});\n\n \n var html_a2e3ff7b3baed122cca03e38321045f5 = $(`<div id="html_a2e3ff7b3baed122cca03e38321045f5" style="width: 100.0%; height: 100.0%;">Lugano</div>`)[0];\n popup_f14c2c84163ab26968f0758f5ff3cfbc.setContent(html_a2e3ff7b3baed122cca03e38321045f5);\n \n\n marker_ac1bd12f87abd65a1c6153eb1d0b6952.bindPopup(popup_f14c2c84163ab26968f0758f5ff3cfbc)\n ;\n\n \n \n \n var marker_3e4f362ac4249334d6552e06a9a166b0 = L.marker(\n [46.1724201894, 8.80136089926],\n {}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n \n var popup_bfd9b905ad31a16b761f8c32dc1ab39e = L.popup({"maxWidth": "100%"});\n\n \n var html_dfa878945c66740206a5ae2d5ee39396 = $(`<div id="html_dfa878945c66740206a5ae2d5ee39396" style="width: 100.0%; height: 100.0%;">Locarno</div>`)[0];\n popup_bfd9b905ad31a16b761f8c32dc1ab39e.setContent(html_dfa878945c66740206a5ae2d5ee39396);\n \n\n marker_3e4f362ac4249334d6552e06a9a166b0.bindPopup(popup_bfd9b905ad31a16b761f8c32dc1ab39e)\n ;\n\n \n \n \n var poly_line_736a7fc55b38daa4365f6c430a2023eb = L.polyline(\n [[46.5167918355, 6.6290923032], [47.0448235144, 9.44626047466], [46.2275531964, 7.35919703457], [47.1707950409, 8.09789386466], [46.8807024189, 7.6213670273], [46.9488322905, 7.43913088992], [47.0936640656, 7.15649750354], [47.4844611721, 7.7313674807], [46.7548527306, 7.62960582867], [46.8757387133, 8.63157541744], [47.3000569504, 8.83971989441], [46.4630018107, 6.84344559824], [46.9674404284, 9.55404469208], [46.0055005499, 8.94699530851], [46.1724201894, 8.80136089926], [46.5167918355, 6.6290923032]],\n {"bubblingMouseEvents": true, "color": "red", "dashArray": null, "dashOffset": null, "fill": false, "fillColor": "red", "fillOpacity": 0.2, "fillRule": "evenodd", "lineCap": "round", "lineJoin": "round", "noClip": false, "opacity": 1.0, "smoothFactor": 1.0, "stroke": true, "weight": 3}\n ).addTo(map_9c856fbc980697f5c6f9ad1f4c1ea79e);\n \n</script>\" style=\"position:absolute;width:100%;height:100%;left:0;top:0;border:none !important;\" allowfullscreen webkitallowfullscreen mozallowfullscreen></iframe></div></div>" | |
| }, | |
| "execution_count": 24, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "\n", | |
| "\n", | |
| "\n", | |
| "\n", | |
| "\n", | |
| "m = create_map(best_path, sbb, map_ch)\n", | |
| "m" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 147, | |
| "outputs": [], | |
| "source": [ | |
| "\n" | |
| ], | |
| "metadata": { | |
| "collapsed": false, | |
| "pycharm": { | |
| "name": "#%%\n" | |
| } | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Simulated Annealing\n", | |
| "\n", | |
| "\n", | |
| "Simulated Annealing is quite similar to Hill Climbing, \n", | |
| "but instead of picking the _best_ move every iteration, it picks a _random_ move. \n", | |
| "If this random move brings us closer to the global optimum, it will be accepted, \n", | |
| "but if it doesn't, the algorithm may accept or reject the move based on a probability dictated by the _temperature_. \n", | |
| "When the *temperature* is high, the algorithm is more likely to accept a random move even if it is bad.\n", | |
| "At low temperatures, only good moves are accepted, with the occasional exception.\n", | |
| "This allows exploration of the state space and prevents the algorithm from getting stuck at a local optimum.\n", | |
| "\n", | |
| "The temperature is gradually decreased over the course of the iteration.\n", | |
| "This is done by a scheduling routine:\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 72, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "import math\n", | |
| "\n", | |
| "\n", | |
| "def exp_schedule(t, k=300, lam=0.0001, limit=20000):\n", | |
| " \"\"\"One possible schedule function for simulated annealing\"\"\"\n", | |
| " return (k * math.exp(-lam * t) if t < limit else 0)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "With this, try to implement the simulated annealing algorithm:" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 202, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "def simulated_annealing_TSP(path, distance_function):\n", | |
| " return" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 202, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [] | |
| } | |
| ], | |
| "metadata": { | |
| "kernelspec": { | |
| "name": "python3", | |
| "language": "python", | |
| "display_name": "Python 3 (ipykernel)" | |
| }, | |
| "language_info": { | |
| "codemirror_mode": { | |
| "name": "ipython", | |
| "version": 3 | |
| }, | |
| "file_extension": ".py", | |
| "mimetype": "text/x-python", | |
| "name": "python", | |
| "nbconvert_exporter": "python", | |
| "pygments_lexer": "ipython3", | |
| "version": "3.7.3" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 2 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment