daily pastebin goal
12%
SHARE
TWEET

Untitled

a guest May 16th, 2018 146 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """
  2. Randy Olson's Shortest Route Program modified By Andrew Liesinger to:
  3.    1: Detect waypoints file at runtime - if found use it, otherwise look up distances via google calls (and then save to waypoint file)
  4.    2: Dynamically create and open an HTML file showing the route when a shorter route is found
  5.    3: Make it easier to tinker with the Generation / Population parameters
  6. """
  7. from __future__ import print_function
  8. from itertools import combinations
  9. import googlemaps
  10. import pandas as pd
  11. import numpy as np
  12. import os.path
  13. import random
  14. import webbrowser
  15.  
  16. GOOGLE_MAPS_API_KEY = "AIzaSyCcN9TfZDA9IqyYkMTptWauQ53KTmWxkM4"
  17. waypoints_file = "my-waypoints-dist-dur.tsv"
  18.  
  19. #This is the general filename - as shorter routes are discovered the Population fitness score will be inserted into the filename
  20. #so that interim results are saved for comparision.  The actual filenames using the default below will be:
  21. #Output_<Population Fitness Score>.html
  22. output_file = 'BrianKuoRoadTrip.html'
  23.  
  24. #parameters for the Genetic algoritim
  25. thisRunGenerations=10000
  26. thisRunPopulation_size=1000
  27.  
  28. # ================================================================================
  29. # Family/Friend Constraints
  30. # ================================================================================
  31. # I'll be in Atlanta with my Dad from July 26th - 29th
  32. # I'll be with Allison in Florida between the 15th and the 21st of August
  33. # The best timing for me would probably be mid/late July
  34.  
  35. # So I just checked my calendar. If I'm going to do 3 weekends, it would have to be between the days of July 6th to July 22nd.
  36.  
  37. # ================================================================================
  38. # National Parks - 34 (+ 4?)
  39. # ================================================================================
  40. national_park_waypoints = [
  41.  
  42. "Acadia National Park, Maine, USA", #Acadia National Park
  43. "Cuyahoga Valley National Park, Ohio, USA", #Cuyahoga Valley National Park
  44. "Medora, ND 58645, USA", #Theodore Roosevelt National Park
  45. "Porcupine, SD 57772, USA", #Badlands National Park
  46. "26611 US-385, Hot Springs, SD 57747, USA", #Wind Cave National Park
  47. "Rocky Mountain National Park, Colorado, USA", #Rocky Mountain National Park
  48. "Great Sand Dunes National Park and Preserve, Colorado, USA", #Great Sand Dunes National Park and Preserve
  49. "9800 CO-347, Montrose, CO 81401, USA", #Black Canyon of the Gunnison National Park
  50. "35853 Rd H.5, Mancos, CO 81328, USA", #Mesa Verde National Park
  51. "Canyonlands National Park, Utah, USA", #Canyonlands National Park
  52. "Moab, UT 84532, USA", #Arches National Park
  53. "UT-24, Torrey, UT 84775, USA", #Capitol Reef National Park
  54. "Bryce Canyon National Park, Utah, USA", #Bryce Canyon National Park
  55. "Great Basin National Park, Nevada, USA", #Great Basin National Park
  56. "Grand Teton National Park, Wyoming, USA", #Grand Teton National Park
  57. "30 Yellowstone Ave, West Yellowstone, MT 59758, USA", #Yellowstone National Park
  58. "Glacier National Park, Montana, USA", #Glacier National Park
  59. "North Cascades National Park, Washington, USA", #North Cascades National Park
  60. "Mount Rainier National Park, Washington, USA", #Mount Rainier National Park
  61. "Olympic National Park, 3002 Mt Angeles Rd, Port Angeles, WA 98362, USA", #Olympic National Park
  62. "Crater Lake National Park, Oregon, USA", #Crater Lake National Park
  63. "Redwood National and State Parks, California, USA", #Redwood National and State Parks
  64. "Lassen Volcanic National Park, California, USA", #Lassen Volcanic National Park
  65. "Pinnacles National Park, California 95043, USA", #Pinnacles National Park
  66. "71487 Twentynine Palms Highway, Twentynine Palms, CA 92277, USA", #Joshua Tree National Park
  67. "Furnace Creek, CA 92328, USA", #Death Valley National Park
  68. "Saguaro National Park Rincon Mountain District (West) Visitor Center, 2700 N Kinney Rd, Tucson, AZ 85743, USA", #Saguaro National Park
  69. "Guadalupe Mountains National Park, Salt Flat, TX 79847, USA", #Guadalupe Mountains National Park
  70. "Big Bend National Park, Big Bend National Park, TX, USA", #Big Bend National Park
  71. "Hot Springs National Park, 369 Central Ave, Hot Springs, AR 71901, USA", #Hot Springs National Park
  72. "Mammoth Cave National Park, Kentucky, USA", #Mammoth Cave National Park
  73. "Great Smoky Mountains National Park, United States", #Great Smoky Mountains National Park
  74. "Congaree National Park, 100 National Park Rd, Hopkins, SC 29061, USA", #Congaree National Park
  75. "Shenandoah National Park, Virginia, USA", #Shenandoah National Park
  76.  
  77. ]
  78. # ================================================================================
  79. # 2018 FSGP/ASC
  80. # ================================================================================
  81.  
  82. # http://americansolarchallenge.org/ASC/wp-content/uploads/2017/08/FSGP-2018-Schedule-Calendar-View.pdf
  83.  
  84. #FSGP - Hastings, NE
  85. #July 6, 7, 8, 9 - Scrutineering
  86. #July 10, 11, 12 - Raycing
  87.  
  88. # http://americansolarchallenge.org/ASC/wp-content/uploads/2018/04/ASC-2018-Overview.pdf
  89.  
  90. #ASC - Omaha, NE
  91. #July 13, 14
  92.  
  93. #ASC - Grand Island, NE
  94. #July 14
  95.  
  96. #ASC - Gering, NE
  97. #July 15, 16
  98.  
  99. #ASC - Casper, WY
  100. #July 16
  101.  
  102. #ASC - Lander, WY
  103. #July 17, 18
  104.  
  105. #ASC - Farson, WY
  106. #July 18
  107.  
  108. #ASC - Arco, WY
  109. #July 19
  110.  
  111. #ASC - Craters of the Moon, ID
  112. #July 20
  113.  
  114. #ASC - Mountain Home, ID
  115. #July 20
  116.  
  117. #ASC - Burns, OR
  118. #July 21, 22
  119.  
  120. #ASC - Bend, OR
  121. #July 22
  122.  
  123.  
  124. # ================================================================================
  125. # Other National Park Service Sites
  126. # ================================================================================
  127. other_NPS_waypoints = []
  128.  
  129.  
  130. #                  "Mount Rushmore National Memorial, South Dakota 244, Keystone, SD",
  131. #                  "Lincoln Home National Historic Site Visitor Center, 426 South 7th Street, Springfield, IL",
  132. #                  "Wright Brothers National Memorial Visitor Center, Manteo, NC",
  133. #Manzanar Japanese Internment Camp
  134. #Little Bighorn Battlefield?
  135. #Natural Bridges
  136. #Mount Saint Helens
  137. #First state national historical park?
  138. #White Sands
  139. #Thomas Edison National Historical Park
  140. #Golden Spike National Historic Site
  141. #Lincoln Home National Historic Site
  142. #Minuteman Missile National Historic Site
  143. #Flight 93 national memorial
  144. #Devil's tower
  145. #Mount Rushmore
  146. #Craters of the moon
  147. #Chimney Rock
  148. #antelope Canyon
  149. #Rainbow Bridge
  150.  
  151.  
  152. # ================================================================================
  153. # Potential Points of Interest
  154. # ================================================================================
  155. POI_waypoints = []
  156. #"Pikes Peak, Colorado",
  157. #Crazy horse
  158. #NASA Facilities?
  159. #"Gateway Arch, Washington Avenue, St Louis, MO",
  160. #FIREWATCH LOOKOUT TOWER
  161. #Niagara Falls
  162.  
  163.  
  164. # ================================================================================
  165. # Cities
  166. # ================================================================================
  167. cities_waypoints = [
  168. "Chicago, IL, USA",
  169. "San Fransisco, CA, USA",
  170. "Seattle, WA, USA",
  171. "Toronto, ON, Canada",
  172. "Philadelphia, PA, USA",
  173. "Boston, MA, USA",
  174. "Denver, CO, USA",
  175. "Portland, OR, USA",
  176. "Vancouver, BC, Canada"
  177. ]
  178.  
  179. # Burlington?  
  180. # Providence?  
  181. # Hartford?  
  182. # Augusta?
  183. # Minneapolis?
  184. # Fargo?
  185. # Big Sur
  186. # Sacramento?  
  187. # Los Angeles?
  188. # Dallas?
  189.  
  190. # ================================================================================
  191. # Questionable
  192. # ================================================================================
  193. questionable_waypoints = [
  194. # "9700 SW 328th St, Homestead, FL 33033, USA", #Biscayne National Park
  195. # "40001 State Hwy 9336, Homestead, FL 33034, USA", #Everglades National Park
  196. # "1901 Spinnaker Dr, Ventura, CA 93001, USA", #Channel Islands National Park
  197. # "Voyageurs National Park, 360 MN-11, International Falls, MN 56649, USA" #Voyageurs National Park
  198.  
  199. ]
  200.  
  201.  
  202. all_waypoints = national_park_waypoints + other_NPS_waypoints + POI_waypoints + cities_waypoints + questionable_waypoints
  203.  
  204. def CreateOptimalRouteHtmlFile(optimal_route, distance, display=True):
  205.     optimal_route = list(optimal_route)
  206.     optimal_route += [optimal_route[0]]
  207.  
  208.     Page_1 = """
  209.    <!DOCTYPE html>
  210.    <html lang="en">
  211.      <head>
  212.        <meta charset="utf-8">
  213.        <meta name="viewport" content="initial-scale=1.0, user-scalable=no">
  214.        <meta name="description" content="Randy Olson uses machine learning to find the optimal road trip across the U.S.">
  215.        <meta name="author" content="Randal S. Olson">
  216.        
  217.        <title>The optimal road trip across the U.S. according to machine learning</title>
  218.        <style>
  219.          html, body, #map-canvas {
  220.            height: 100%;
  221.            margin: 0px;
  222.            padding: 0px
  223.          }
  224.          #panel {
  225.            position: absolute;
  226.            top: 5px;
  227.            left: 50%;
  228.            margin-left: -180px;
  229.            z-index: 5;
  230.            background-color: #fff;
  231.            padding: 10px;
  232.            border: 1px solid #999;
  233.          }
  234.        </style>
  235.        <script src="https://maps.googleapis.com/maps/api/js?v=3.exp&signed_in=true"></script>
  236.        <script>
  237.  
  238. """
  239.     Page_2 = """
  240.            var routes_list = []
  241.            //var markerOptions = {icon: "http://maps.gstatic.com/mapfiles/markers2/marker.png"};
  242.            //var markerOptions = {icon: "http://i.imgur.com/fUKnx8P.png"};
  243.            var directionsDisplayOptions = {preserveViewport: true,
  244.            //                                markerOptions: markerOptions,
  245.                                            suppressMarkers: true};
  246.            var directionsService = new google.maps.DirectionsService();
  247.            var map;
  248.  
  249.  
  250.            function initialize() {
  251.              var center = new google.maps.LatLng(39, -96);
  252.              var mapOptions = {
  253.                zoom: 5,
  254.                center: center,
  255.                mapTypeId: google.maps.MapTypeId.ROADMAP
  256.              };
  257.              map = new google.maps.Map(document.getElementById('map-canvas'), mapOptions);
  258.              for (i=0; i<routes_list.length; i++) {
  259.                routes_list[i].setMap(map);
  260.              }
  261.  
  262.            var infowindow = new google.maps.InfoWindow;
  263.            var national_park_link = "http://i.imgur.com/fUKnx8P.png";
  264.            var other_NPS_link = "https://i.imgur.com/kUwSLiA.png";
  265.            var POI_link = "https://i.imgur.com/bNIsBJm.png";
  266.            var cities_link = "https://i.imgur.com/ZKFeMTj.png";
  267.            var question_link = "https://i.imgur.com/dfQZ5dD.png";
  268.  
  269.  
  270.            var locations = [
  271.  
  272. // ================================================================================
  273. // National Parks - 34 (+ 4?)
  274. // ================================================================================
  275.            ['Acadia National Park', 44.353199, -68.274928, national_park_link],
  276.            ['Cuyahoga Valley National Park', 41.282981, -81.571746, national_park_link],
  277.            ['Theodore Roosevelt National Park', 46.916649, -103.524464, national_park_link],
  278.            ['Badlands National Park', 43.235865, -102.326154, national_park_link],
  279.            ['Wind Cave National Park', 43.492139, -103.461198, national_park_link],
  280.            ['Rocky Mountain National Park', 40.335739, -105.666891, national_park_link],
  281.            ['Great Sand Dunes National Park and Preserve', 37.747465, -105.500359, national_park_link],
  282.            ['Black Canyon of the Gunnison National Park', 38.540691, -107.700991, national_park_link],
  283.            ['Mesa Verde National Park', 37.334690, -108.406994, national_park_link],
  284.            ['Canyonlands National Park', 38.310718, -109.855298, national_park_link],
  285.            ['Arches National Park', 38.590752, -109.566939, national_park_link],
  286.            ['Capitol Reef National Park', 38.299454, -111.419043, national_park_link],
  287.            ['Bryce Canyon National Park', 37.622720, -112.191269, national_park_link],
  288.            ['Great Basin National Park', 39.006082, -114.217622, national_park_link],
  289.            ['Grand Teton National Park', 43.791731, -110.683027, national_park_link],
  290.            ['Yellowstone National Park', 44.659798, -111.098267, national_park_link],
  291.            ['Glacier National Park', 48.484216, -113.996058, national_park_link],
  292.            ['North Cascades National Park', 48.999747, -121.061963, national_park_link],
  293.            ['Mount Rainier National Park', 46.737220, -121.831287, national_park_link],
  294.            ['Olympic National Park', 48.101289, -123.425841, national_park_link],
  295.            ['Crater Lake National Park', 42.867356, -122.171270, national_park_link],
  296.            ['Redwood National and State Parks', 41.349842, -124.027042, national_park_link],
  297.            ['Lassen Volcanic National Park', 40.497400, -121.421209, national_park_link],
  298.            ['Pinnacles National Park', 36.490279, -121.182504, national_park_link],
  299.            ['Joshua Tree National Park', 34.134354, -116.103262, national_park_link],
  300.            ['Death Valley National Park', 36.448122, -116.852817, national_park_link],
  301.            ['Saguaro National Park', 32.254429, -111.197227, national_park_link],
  302.            ['Guadalupe Mountains National Park', 31.941920, -104.873669, national_park_link],
  303.            ['Big Bend National Park', 29.126625, -103.243469, national_park_link],
  304.            ['Hot Springs National Park', 34.514589, -93.053847, national_park_link],
  305.            ['Mammoth Cave National Park', 37.185517, -86.101458, national_park_link],
  306.            ['Great Smoky Mountains National Park', 35.557637, -84.009101, national_park_link],
  307.            ['Congaree National Park', 33.792382, -80.768785, national_park_link],
  308.            ['Shenandoah National Park', 38.095057, -78.816753, national_park_link],
  309.  
  310. // ================================================================================
  311. // Other National Park Service Sites
  312. // ================================================================================
  313. //# "Lincoln Home National Historic Site Visitor Center, 426 South 7th Street, Springfield, IL",
  314. //#Manzanar Japanese Internment Camp
  315. //#Natural Bridges
  316. //#First state national historical park?
  317. //#Thomas Edison National Historical Park
  318. //#Lincoln Home National Historic Site
  319. //#Minuteman Missile National Historic Site
  320. //#Craters of the moon
  321. //#Chimney Rock
  322. //#Rainbow Bridge
  323.  
  324.  
  325. ['Mount Rushmore National Memorial', 43.879036, -103.458946, other_NPS_link],
  326. ['Wright Brothers National Memorial', 36.014331, -75.667901, other_NPS_link],
  327. ['Mount Saint Helens', 46.276375, -122.216415, other_NPS_link],
  328. ['White Sands National Monument', 32.781837, -106.329353, other_NPS_link],
  329. ['Golden Spike National Historic Site', 41.617454, -112.550943, other_NPS_link],
  330. ['Flight 93 National Memorial', 40.056539, -78.905805, other_NPS_link],
  331. ['Antelope Canyon', 36.897225, -111.408851, other_NPS_link],
  332. ['Devils Tower National Monument', 44.590225, -104.714607, other_NPS_link],
  333. ['Little Bighorn Battlefield', 45.570121, -107.432388, other_NPS_link],
  334. ['Craters of the Moon National Monument & Preserve', 43.205791, -113.500202, other_NPS_link],
  335.  
  336.  
  337.  
  338. // ================================================================================
  339. // Potential Points of Interest
  340. // ================================================================================
  341. ['Niagara Falls', 43.087956, -79.081180, POI_link],
  342.  
  343. // Bodie, CA?
  344.  
  345.  
  346. // ================================================================================
  347. // Cities
  348. // ================================================================================
  349. ['Chicago, IL', 41.877848, -87.631670, cities_link],
  350. ['San Fransisco, CA', 37.774277, -122.418903, cities_link],
  351. ['Seattle, WA', 47.606001, -122.331966, cities_link],
  352. ['Toronto, ON', 43.652830, -79.386018, cities_link],
  353. ['Philadelphia, PA', 39.951646, -75.166148, cities_link],
  354. ['Boston, MA', 42.358930, -71.059560, cities_link],
  355. ['Denver, CO', 39.736549, -104.991118, cities_link],
  356. ['Portland, OR', 45.521196, -122.677780, cities_link],
  357. ['Vancouver, BC', 49.281396, -123.121168, cities_link],
  358.  
  359.  
  360. // ================================================================================
  361. // Questionable
  362. // ================================================================================
  363.            ['Biscayne National Park', 25.464471, -80.334751, question_link],
  364.            ['Everglades National Park', 25.395347, -80.583131, question_link],
  365.            ['Channel Islands National Park', 34.248528, -119.266543, question_link],
  366.            ['Voyageurs National Park', 48.603372, -93.376871, question_link]
  367.  
  368.  
  369.            ];
  370.  
  371.            for (i = 0; i < locations.length; i++) {  
  372.              marker = new google.maps.Marker({
  373.               position: new google.maps.LatLng(locations[i][1], locations[i][2]),
  374.               map: map,
  375.               icon: locations[i][3]
  376.             });
  377.  
  378.              google.maps.event.addListener(marker, 'click', (function(marker, i) {
  379.               return function() {
  380.                 infowindow.setContent(locations[i][0]);
  381.                 infowindow.open(map, marker);
  382.               }
  383.             })(marker, i));
  384.            }
  385.  
  386.  
  387.            }
  388.  
  389.            function calcRoute(start, end, routes) {
  390.              
  391.              var directionsDisplay = new google.maps.DirectionsRenderer(directionsDisplayOptions);
  392.  
  393.              var waypts = [];
  394.              for (var i = 0; i < routes.length; i++) {
  395.                waypts.push({
  396.                  location:routes[i],
  397.                  stopover:true});
  398.                }
  399.              
  400.  
  401.  
  402.              var request = {
  403.                  origin: start,
  404.                  destination: end,
  405.                  waypoints: waypts,
  406.                  optimizeWaypoints: false,
  407.                  travelMode: google.maps.TravelMode.DRIVING
  408.              };
  409.  
  410.              directionsService.route(request, function(response, status) {
  411.                if (status == google.maps.DirectionsStatus.OK) {
  412.                    directionsDisplay.setDirections(response);      
  413.                }
  414.              });
  415.  
  416.              routes_list.push(directionsDisplay);
  417.            }
  418.  
  419.            function createRoutes(route) {
  420.                // Google's free map API is limited to 10 waypoints so need to break into batches
  421.                route.push(route[0]);
  422.                var subset = 0;
  423.                while (subset < route.length) {
  424.                    var waypointSubset = route.slice(subset, subset + 10);
  425.  
  426.                    var startPoint = waypointSubset[0];
  427.                    var midPoints = waypointSubset.slice(1, waypointSubset.length - 1);
  428.                    var endPoint = waypointSubset[waypointSubset.length - 1];
  429.  
  430.                    calcRoute(startPoint, endPoint, midPoints);
  431.  
  432.                    subset += 9;
  433.                }
  434.            }
  435.  
  436.            // function createMarker(latlng) {
  437.  
  438.            //   var marker = new google.maps.Marker({
  439.            //     position: latlng,
  440.            //     map: map,
  441.            //     icon: "http://i.imgur.com/fUKnx8P.png"
  442.            //   });
  443.            // }
  444.  
  445.  
  446.  
  447.            createRoutes(optimal_route);
  448.  
  449.  
  450.  
  451.  
  452.        // var map = new google.maps.Map(document.getElementById('map'), {
  453.        //   zoom: 4,
  454.        //   center: myLatLng
  455.        // }
  456.  
  457.  
  458.  
  459.  
  460.  
  461.  
  462.  
  463.  
  464.  
  465.            google.maps.event.addDomListener(window, 'load', initialize);
  466.  
  467.        </script>
  468.      </head>
  469.      <body>
  470.        <div id="map-canvas"></div>
  471.      </body>
  472.    </html>
  473.  
  474.    """
  475.  
  476.     localoutput_file = output_file.replace('.html', '_' + str(distance) + '.html')
  477.     with open(localoutput_file, 'w') as fs:
  478.         fs.write(Page_1)
  479.         fs.write("\n\t\t\tnational_park_waypoints = {0}".format(str(national_park_waypoints)))
  480.         fs.write("\n\n\t\t\tother_NPS_waypoints = {0}".format(str(other_NPS_waypoints)))
  481.         fs.write("\n\n\t\t\tPOI_waypoints = {0}".format(str(POI_waypoints)))
  482.         fs.write("\n\n\t\t\tcities_waypoints = {0}\n".format(str(cities_waypoints)))
  483.         fs.write("\n\n\t\t\toptimal_route = {0}\n".format(str(optimal_route)))
  484.  
  485.         fs.write(Page_2)
  486.  
  487.     if display:
  488.         webbrowser.open_new_tab(localoutput_file)
  489.  
  490.  
  491. def compute_fitness(solution):
  492.     """
  493.        This function returns the total distance traveled on the current road trip.
  494.        
  495.        The genetic algorithm will favor road trips that have shorter
  496.        total distances traveled.
  497.    """
  498.    
  499.     solution_fitness = 0.0
  500.    
  501.     for index in range(len(solution)):
  502.         waypoint1 = solution[index - 1]
  503.         waypoint2 = solution[index]
  504.         solution_fitness += waypoint_distances[frozenset([waypoint1, waypoint2])]
  505.        
  506.     return solution_fitness
  507.  
  508. def generate_random_agent():
  509.     """
  510.        Creates a random road trip from the waypoints.
  511.    """
  512.    
  513.     new_random_agent = list(all_waypoints)
  514.     random.shuffle(new_random_agent)
  515.     return tuple(new_random_agent)
  516.  
  517. def mutate_agent(agent_genome, max_mutations=3):
  518.     """
  519.        Applies 1 - `max_mutations` point mutations to the given road trip.
  520.        
  521.        A point mutation swaps the order of two waypoints in the road trip.
  522.    """
  523.    
  524.     agent_genome = list(agent_genome)
  525.     num_mutations = random.randint(1, max_mutations)
  526.    
  527.     for mutation in range(num_mutations):
  528.         swap_index1 = random.randint(0, len(agent_genome) - 1)
  529.         swap_index2 = swap_index1
  530.  
  531.         while swap_index1 == swap_index2:
  532.             swap_index2 = random.randint(0, len(agent_genome) - 1)
  533.  
  534.         agent_genome[swap_index1], agent_genome[swap_index2] = agent_genome[swap_index2], agent_genome[swap_index1]
  535.            
  536.     return tuple(agent_genome)
  537.  
  538. def shuffle_mutation(agent_genome):
  539.     """
  540.        Applies a single shuffle mutation to the given road trip.
  541.        
  542.        A shuffle mutation takes a random sub-section of the road trip
  543.        and moves it to another location in the road trip.
  544.    """
  545.    
  546.     agent_genome = list(agent_genome)
  547.    
  548.     start_index = random.randint(0, len(agent_genome) - 1)
  549.     length = random.randint(2, 20)
  550.    
  551.     genome_subset = agent_genome[start_index:start_index + length]
  552.     agent_genome = agent_genome[:start_index] + agent_genome[start_index + length:]
  553.    
  554.     insert_index = random.randint(0, len(agent_genome) + len(genome_subset) - 1)
  555.     agent_genome = agent_genome[:insert_index] + genome_subset + agent_genome[insert_index:]
  556.    
  557.     return tuple(agent_genome)
  558.  
  559. def generate_random_population(pop_size):
  560.     """
  561.        Generates a list with `pop_size` number of random road trips.
  562.    """
  563.    
  564.     random_population = []
  565.     for agent in range(pop_size):
  566.         random_population.append(generate_random_agent())
  567.     return random_population
  568.    
  569. def run_genetic_algorithm(generations=5000, population_size=100):
  570.     """
  571.        The core of the Genetic Algorithm.
  572.        
  573.        `generations` and `population_size` must be a multiple of 10.
  574.    """
  575.    
  576.     current_best_distance = -1
  577.     population_subset_size = int(population_size / 10.)
  578.     generations_10pct = int(generations / 10.)
  579.    
  580.     # Create a random population of `population_size` number of solutions.
  581.     population = generate_random_population(population_size)
  582.  
  583.     # For `generations` number of repetitions...
  584.     for generation in range(generations):
  585.        
  586.         # Compute the fitness of the entire current population
  587.         population_fitness = {}
  588.  
  589.         for agent_genome in population:
  590.             if agent_genome in population_fitness:
  591.                 continue
  592.  
  593.             population_fitness[agent_genome] = compute_fitness(agent_genome)
  594.  
  595.         # Take the top 10% shortest road trips and produce offspring each from them
  596.         new_population = []
  597.         for rank, agent_genome in enumerate(sorted(population_fitness,
  598.                                                    key=population_fitness.get)[:population_subset_size]):
  599.             if (generation % generations_10pct == 0 or generation == generations - 1) and rank == 0:
  600.                 current_best_genome = agent_genome
  601.                 print("Generation %d best: %d | Unique genomes: %d" % (generation,
  602.                                                                        population_fitness[agent_genome],
  603.                                                                        len(population_fitness)))
  604.                 print(agent_genome)                
  605.                 print("")
  606.  
  607.                 # If this is the first route found, or it is shorter than the best route we know,
  608.                 # create a html output and display it
  609.                 if population_fitness[agent_genome] < current_best_distance or current_best_distance < 0:
  610.                     current_best_distance = population_fitness[agent_genome]
  611.                     CreateOptimalRouteHtmlFile(agent_genome, current_best_distance, False)
  612.                    
  613.  
  614.             # Create 1 exact copy of each of the top road trips
  615.             new_population.append(agent_genome)
  616.  
  617.             # Create 2 offspring with 1-3 point mutations
  618.             for offspring in range(2):
  619.                 new_population.append(mutate_agent(agent_genome, 3))
  620.                
  621.             # Create 7 offspring with a single shuffle mutation
  622.             for offspring in range(7):
  623.                 new_population.append(shuffle_mutation(agent_genome))
  624.  
  625.         # Replace the old population with the new population of offspring
  626.         for i in range(len(population))[::-1]:
  627.             del population[i]
  628.  
  629.         population = new_population
  630.     return current_best_genome
  631.  
  632.  
  633. if __name__ == '__main__':
  634.     # If this file exists, read the data stored in it - if not then collect data by asking google
  635.     print("Begin finding shortest route")
  636.     file_path = waypoints_file
  637.     if os.path.exists(file_path):
  638.         print("Waypoints exist")
  639.         #file exists used saved results
  640.         waypoint_distances = {}
  641.         waypoint_durations = {}
  642.         all_waypoints = set()
  643.  
  644.         waypoint_data = pd.read_csv(file_path, sep="\t")
  645.  
  646.         for i, row in waypoint_data.iterrows():
  647.             waypoint_distances[frozenset([row.waypoint1, row.waypoint2])] = row.distance_m
  648.             waypoint_durations[frozenset([row.waypoint1, row.waypoint2])] = row.duration_s
  649.             all_waypoints.update([row.waypoint1, row.waypoint2])
  650.  
  651.     else:
  652.         # File does not exist - compute results      
  653.         print("Collecting Waypoints")
  654.         waypoint_distances = {}
  655.         waypoint_durations = {}
  656.  
  657.  
  658.         gmaps = googlemaps.Client(GOOGLE_MAPS_API_KEY)
  659.         for (waypoint1, waypoint2) in combinations(all_waypoints, 2):
  660.             try:
  661.                 route = gmaps.distance_matrix(origins=[waypoint1],
  662.                                               destinations=[waypoint2],
  663.                                               mode="driving", # Change to "walking" for walking directions,
  664.                                                               # "bicycling" for biking directions, etc.
  665.                                               language="English",
  666.                                               units="metric")
  667.  
  668.                 # "distance" is in meters
  669.                 distance = route["rows"][0]["elements"][0]["distance"]["value"]
  670.  
  671.                 # "duration" is in seconds
  672.                 duration = route["rows"][0]["elements"][0]["duration"]["value"]
  673.  
  674.                 waypoint_distances[frozenset([waypoint1, waypoint2])] = distance
  675.                 waypoint_durations[frozenset([waypoint1, waypoint2])] = duration
  676.        
  677.             except Exception as e:
  678.                 print("Error with finding the route between %s and %s." % (waypoint1, waypoint2))
  679.        
  680.         print("Saving Waypoints")
  681.         with open(waypoints_file, "w") as out_file:
  682.             out_file.write("\t".join(["waypoint1",
  683.                                       "waypoint2",
  684.                                       "distance_m",
  685.                                       "duration_s"]))
  686.        
  687.             for (waypoint1, waypoint2) in waypoint_distances.keys():
  688.                 out_file.write("\n" +
  689.                                "\t".join([waypoint1,
  690.                                           waypoint2,
  691.                                           str(waypoint_distances[frozenset([waypoint1, waypoint2])]),
  692.                                           str(waypoint_durations[frozenset([waypoint1, waypoint2])])]))
  693.  
  694.     print("Search for optimal route")
  695.     optimal_route = run_genetic_algorithm(generations=thisRunGenerations, population_size=thisRunPopulation_size)
  696.  
  697.     # This is probably redundant now that the files are created in run_genetic_algorithm,
  698.     # but leaving it active to ensure  the final result is not lost
  699.     CreateOptimalRouteHtmlFile(optimal_route, 1, True)
RAW Paste Data
Top