· 6 years ago · Dec 08, 2019, 02:38 PM
1var map;
2var directionsDisplay = null;
3var directionsService;
4var polylinePath;
5var nodes = [];
6var prevNodes = [];
7var markers = [];
8var durations = [];
9
10
11
12// Initialize google maps
13function initializeMap() {
14 // Map options
15 var opts = {
16 center: new google.maps.LatLng({lat: 33.8547, lng: 35.8623}),
17 zoom: 10,
18 streetViewControl: false,
19 mapTypeControl: false,
20 };
21 map = new google.maps.Map(document.getElementById('map-canvas'), opts);
22 // Create map click event
23
24 // If there are directions being shown, clear them
25 clearDirections();
26
27 let a = JSON.parse(localStorage.getItem('markers'))
28 for (var key in a) {
29 let latitude = parseFloat(a[key]['latitude']);
30 let longitude = parseFloat(a[key]['longitude']);
31 var marker = new google.maps.Marker({ position: { lat: latitude, lng: longitude }, map: map, });
32 markers.push(marker);
33 nodes.push(event.latLng);
34 }
35 $('#destinations-count').html(nodes.length);
36
37}
38
39// Get all durations depending on travel type
40function getDurations(callback) {
41 var service = new google.maps.DistanceMatrixService();
42 service.getDistanceMatrix({
43 origins: nodes,
44 destinations: nodes,
45 travelMode: google.maps.TravelMode[$('#travel-type').val()],
46 avoidHighways: parseInt($('#avoid-highways').val()) > 0 ? true : false,
47 avoidTolls: false,
48 }, function (distanceData) {
49 // Create duration data array
50 var nodeDistanceData;
51 for (originNodeIndex in distanceData.rows) {
52 nodeDistanceData = distanceData.rows[originNodeIndex].elements;
53 durations[originNodeIndex] = [];
54 for (destinationNodeIndex in nodeDistanceData) {
55 if (durations[originNodeIndex][destinationNodeIndex] = nodeDistanceData[destinationNodeIndex].duration == undefined) {
56 alert('Error: couldn\'t get a trip duration from API');
57 return;
58 }
59 durations[originNodeIndex][destinationNodeIndex] = nodeDistanceData[destinationNodeIndex].duration.value;
60 }
61 }
62 if (callback != undefined) {
63 callback();
64 }
65 });
66}
67// Removes markers and temporary paths
68function clearMapMarkers() {
69 for (index in markers) {
70 markers[index].setMap(null);
71 }
72 prevNodes = nodes;
73 nodes = [];
74 if (polylinePath != undefined) {
75 polylinePath.setMap(null);
76 }
77
78 markers = [];
79
80 $('#ga-buttons').show();
81}
82// Removes map directions
83function clearDirections() {
84 // If there are directions being shown, clear them
85 if (directionsDisplay != null) {
86 directionsDisplay.setMap(null);
87 directionsDisplay = null;
88 }
89}
90// Completely clears map
91function clearMap() {
92 clearMapMarkers();
93 clearDirections();
94
95 $('#destinations-count').html('0');
96}
97// Initial Google Maps
98google.maps.event.addDomListener(window, 'load', initializeMap);
99// Create listeners
100$(document).ready(function () {
101 $('#clear-map').click(clearMap);
102 // Start GA
103 $('#find-route').click(function () {
104 if (nodes.length < 2) {
105 if (prevNodes.length >= 2) {
106 nodes = prevNodes;
107 } else {
108 alert('Click on the map to select destination points');
109 return;
110 }
111 }
112 if (directionsDisplay != null) {
113 directionsDisplay.setMap(null);
114 directionsDisplay = null;
115 }
116
117 $('#ga-buttons').hide();
118 // Get route durations
119 getDurations(function () {
120 $('.ga-info').show();
121 // Get config and create initial GA population
122 ga.getConfig();
123 var pop = new ga.population();
124 pop.initialize(nodes.length);
125 var route = pop.getFittest().chromosome;
126 ga.evolvePopulation(pop, function (update) {
127 $('#generations-passed').html(update.generation);
128 $('#best-time').html((update.population.getFittest().getDistance() / 60).toFixed(2) + ' Mins');
129
130 // Get route coordinates
131 var route = update.population.getFittest().chromosome;
132 var routeCoordinates = [];
133 for (index in route) {
134 routeCoordinates[index] = nodes[route[index]];
135 }
136 routeCoordinates[route.length] = nodes[route[0]];
137 // Display temp. route
138 if (polylinePath != undefined) {
139 polylinePath.setMap(null);
140 }
141 polylinePath = new google.maps.Polyline({
142 path: routeCoordinates,
143 strokeColor: "#0066ff",
144 strokeOpacity: 0.75,
145 strokeWeight: 2,
146 });
147 polylinePath.setMap(map);
148 }, function (result) {
149 // Get route
150 route = result.population.getFittest().chromosome;
151 // Add route to map
152 directionsService = new google.maps.DirectionsService();
153 directionsDisplay = new google.maps.DirectionsRenderer();
154 directionsDisplay.setMap(map);
155 var waypts = [];
156 for (var i = 1; i < route.length; i++) {
157 waypts.push({
158 location: nodes[route[i]],
159 stopover: true
160 });
161 }
162
163 // Add final route to map
164 var request = {
165 origin: nodes[route[0]],
166 destination: nodes[route[0]],
167 waypoints: waypts,
168 travelMode: google.maps.TravelMode[$('#travel-type').val()],
169 avoidHighways: parseInt($('#avoid-highways').val()) > 0 ? true : false,
170 avoidTolls: false
171 };
172 directionsService.route(request, function (response, status) {
173 if (status == google.maps.DirectionsStatus.OK) {
174 directionsDisplay.setDirections(response);
175 }
176 clearMapMarkers();
177 });
178 });
179 });
180 });
181});
182// GA code
183var ga = {
184 // Default config
185 "crossoverRate": 0.5,
186 "mutationRate": 0.1,
187 "populationSize": 50,
188 "tournamentSize": 5,
189 "elitism": true,
190 "maxGenerations": 50,
191
192 "tickerSpeed": 60,
193 // Loads config from HTML inputs
194 "getConfig": function () {
195 ga.crossoverRate = parseFloat($('#crossover-rate').val());
196 ga.mutationRate = parseFloat($('#mutation-rate').val());
197 ga.populationSize = parseInt($('#population-size').val()) || 50;
198 ga.elitism = parseInt($('#elitism').val()) || false;
199 ga.maxGenerations = parseInt($('#maxGenerations').val()) || 50;
200 },
201
202 // Evolves given population
203 "evolvePopulation": function (population, generationCallBack, completeCallBack) {
204 // Start evolution
205 var generation = 1;
206 var evolveInterval = setInterval(function () {
207 if (generationCallBack != undefined) {
208 generationCallBack({
209 population: population,
210 generation: generation,
211 });
212 }
213 // Evolve population
214 population = population.crossover();
215 population.mutate();
216 generation++;
217
218 // If max generations passed
219 if (generation > ga.maxGenerations) {
220 // Stop looping
221 clearInterval(evolveInterval);
222
223 if (completeCallBack != undefined) {
224 completeCallBack({
225 population: population,
226 generation: generation,
227 });
228 }
229 }
230 }, ga.tickerSpeed);
231 },
232 // Population class
233 "population": function () {
234 // Holds individuals of population
235 this.individuals = [];
236
237 // Initial population of random individuals with given chromosome length
238 this.initialize = function (chromosomeLength) {
239 this.individuals = [];
240
241 for (var i = 0; i < ga.populationSize; i++) {
242 var newIndividual = new ga.individual(chromosomeLength);
243 newIndividual.initialize();
244 this.individuals.push(newIndividual);
245 }
246 };
247
248 // Mutates current population
249 this.mutate = function () {
250 var fittestIndex = this.getFittestIndex();
251 for (index in this.individuals) {
252 // Don't mutate if this is the elite individual and elitism is enabled
253 if (ga.elitism != true || index != fittestIndex) {
254 this.individuals[index].mutate();
255 }
256 }
257 };
258 // Applies crossover to current population and returns population of offspring
259 this.crossover = function () {
260 // Create offspring population
261 var newPopulation = new ga.population();
262
263 // Find fittest individual
264 var fittestIndex = this.getFittestIndex();
265 for (index in this.individuals) {
266 // Add unchanged into next generation if this is the elite individual and elitism is enabled
267 if (ga.elitism == true && index == fittestIndex) {
268 // Replicate individual
269 var eliteIndividual = new ga.individual(this.individuals[index].chromosomeLength);
270 eliteIndividual.setChromosome(this.individuals[index].chromosome.slice());
271 newPopulation.addIndividual(eliteIndividual);
272 } else {
273 // Select mate
274 var parent = this.tournamentSelection();
275 // Apply crossover
276 this.individuals[index].crossover(parent, newPopulation);
277 }
278 }
279
280 return newPopulation;
281 };
282 // Adds an individual to current population
283 this.addIndividual = function (individual) {
284 this.individuals.push(individual);
285 };
286 // Selects an individual with tournament selection
287 this.tournamentSelection = function () {
288 // Randomly order population
289 for (var i = 0; i < this.individuals.length; i++) {
290 var randomIndex = Math.floor(Math.random() * this.individuals.length);
291 var tempIndividual = this.individuals[randomIndex];
292 this.individuals[randomIndex] = this.individuals[i];
293 this.individuals[i] = tempIndividual;
294 }
295 // Create tournament population and add individuals
296 var tournamentPopulation = new ga.population();
297 for (var i = 0; i < ga.tournamentSize; i++) {
298 tournamentPopulation.addIndividual(this.individuals[i]);
299 }
300 return tournamentPopulation.getFittest();
301 };
302
303 // Return the fittest individual's population index
304 this.getFittestIndex = function () {
305 var fittestIndex = 0;
306 // Loop over population looking for fittest
307 for (var i = 1; i < this.individuals.length; i++) {
308 if (this.individuals[i].calcFitness() > this.individuals[fittestIndex].calcFitness()) {
309 fittestIndex = i;
310 }
311 }
312 return fittestIndex;
313 };
314 // Return fittest individual
315 this.getFittest = function () {
316 return this.individuals[this.getFittestIndex()];
317 };
318 },
319 // Individual class
320 "individual": function (chromosomeLength) {
321 this.chromosomeLength = chromosomeLength;
322 this.fitness = null;
323 this.chromosome = [];
324 // Initialize random individual
325 this.initialize = function () {
326 this.chromosome = [];
327 // Generate random chromosome
328 for (var i = 0; i < this.chromosomeLength; i++) {
329 this.chromosome.push(i);
330 }
331 for (var i = 0; i < this.chromosomeLength; i++) {
332 var randomIndex = Math.floor(Math.random() * this.chromosomeLength);
333 var tempNode = this.chromosome[randomIndex];
334 this.chromosome[randomIndex] = this.chromosome[i];
335 this.chromosome[i] = tempNode;
336 }
337 };
338
339 // Set individual's chromosome
340 this.setChromosome = function (chromosome) {
341 this.chromosome = chromosome;
342 };
343
344 // Mutate individual
345 this.mutate = function () {
346 this.fitness = null;
347
348 // Loop over chromosome making random changes
349 for (index in this.chromosome) {
350 if (ga.mutationRate > Math.random()) {
351 var randomIndex = Math.floor(Math.random() * this.chromosomeLength);
352 var tempNode = this.chromosome[randomIndex];
353 this.chromosome[randomIndex] = this.chromosome[index];
354 this.chromosome[index] = tempNode;
355 }
356 }
357 };
358
359 // Returns individuals route distance
360 this.getDistance = function () {
361 var totalDistance = 0;
362 for (index in this.chromosome) {
363 var startNode = this.chromosome[index];
364 var endNode = this.chromosome[0];
365 if ((parseInt(index) + 1) < this.chromosome.length) {
366 endNode = this.chromosome[(parseInt(index) + 1)];
367 }
368 totalDistance += durations[startNode][endNode];
369 }
370
371 totalDistance += durations[startNode][endNode];
372
373 return totalDistance;
374 };
375 // Calculates individuals fitness value
376 this.calcFitness = function () {
377 if (this.fitness != null) {
378 return this.fitness;
379 }
380
381 var totalDistance = this.getDistance();
382 this.fitness = 1 / totalDistance;
383 return this.fitness;
384 };
385 // Applies crossover to current individual and mate, then adds it's offspring to given population
386 this.crossover = function (individual, offspringPopulation) {
387 var offspringChromosome = [];
388 // Add a random amount of this individual's genetic information to offspring
389 var startPos = Math.floor(this.chromosome.length * Math.random());
390 var endPos = Math.floor(this.chromosome.length * Math.random());
391 var i = startPos;
392 while (i != endPos) {
393 offspringChromosome[i] = individual.chromosome[i];
394 i++
395 if (i >= this.chromosome.length) {
396 i = 0;
397 }
398 }
399 // Add any remaining genetic information from individual's mate
400 for (parentIndex in individual.chromosome) {
401 var node = individual.chromosome[parentIndex];
402 var nodeFound = false;
403 for (offspringIndex in offspringChromosome) {
404 if (offspringChromosome[offspringIndex] == node) {
405 nodeFound = true;
406 break;
407 }
408 }
409 if (nodeFound == false) {
410 for (var offspringIndex = 0; offspringIndex < individual.chromosome.length; offspringIndex++) {
411 if (offspringChromosome[offspringIndex] == undefined) {
412 offspringChromosome[offspringIndex] = node;
413 break;
414 }
415 }
416 }
417 }
418 // Add chromosome to offspring and add offspring to population
419 var offspring = new ga.individual(this.chromosomeLength);
420 offspring.setChromosome(offspringChromosome);
421 offspringPopulation.addIndividual(offspring);
422 };
423 },
424};