title
Coding Challenge #35.4: Traveling Salesperson with Genetic Algorithm

description
In Part 1 of this multi-part coding challenge, I introduce the classic computer science problem of the Traveling Salesperson (TSP) and discuss the pitfalls with a brute force solution. In Part 2, I discuss Lexicographic Ordering and demonstrate one algorithm to iterate over all the permutations of an array. In Part 3, I apply this algorithm to a brute-force solution of the TSP problem. Every single route permutation is checked one by one. In Part 4, I attempt to create a solution to the TSP problem with a genetic algorithm, and then I add a “crossover” algorithm in Part 5. Code: https://thecodingtrain.com/challenges/35-traveling-salesperson p5.js Web Editor Sketches: 🕹️ Part 1: Traveling Salesperson (TSP): https://editor.p5js.org/codingtrain/sketches/FCNAHaCqf 🕹️ Part 2: Lexicographic Order: https://editor.p5js.org/codingtrain/sketches/iYxi30gbl 🕹️ Part 3: TSP with Lexicographic Order: https://editor.p5js.org/codingtrain/sketches/bWPIkEv9s 🕹️ Part 4: TSP with Genetic Algorithm: https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9 🕹️ Part 5: TSP with Genetic Algorithm and Crossover: https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9 Other Parts of this Challenge: 📺 Part 1: Traveling Salesperson (TSP): https://youtu.be/BAejnwN4Ccw 📺 Part 2: Lexicographic Order: https://youtu.be/goUlyp4rwiU 📺 Part 3: TSP with Lexicographic Order: https://youtu.be/9Xy-LMAfglE 📺 Part 5: TSP with Genetic Algorithm and Crossover: https://youtu.be/hnxn6DtLYcY 🎥 Previous video: https://youtu.be/Cl_Gjj80gPE?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH 🎥 Next video: https://youtu.be/rX5p-QRP6R4?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH 🎥 All videos: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH References: 🌐 Traveling Salesman on Wikipedia: https://en.wikipedia.org/wiki/Travelling_salesman_problem 🗨️ Permutation Algorithm Using Lexicographic Ordering: https://www.quora.com/How-would-you-explain-an-algorithm-that-generates-permutations-using-lexicographic-ordering 📝 Array on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array 📝 Array.includes() on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/includes 📝 Array.reverse() on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/reverse 📝 ES6 Sets on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Set 💾 The Nature of Code Part 2: https://github.com/shiffman/NOC-S17-2-Intelligence-Learning 📕 The Nature of Code: http://natureofcode.com/ Videos: 🎥 Improved Pool Selection: https://www.youtube.com/watch?v=ETphJASzYes&list=PLRqwX-V7Uu6YJ3XfHhT2Mm4Y5I99nrIKX&index=23 🎥 Genetic Algorithm Playlist: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6bJM3VgzjNV5YxVxUwzALHV 🔴 Live Stream Archive #57: https://youtu.be/r_SpBy9fQuo Related Coding Challenges: 🚂 #29 Smart Rockets in p5.js: https://youtu.be/bGz7mv2vD6g 🚂 #51 A* Pathfinding Algorithm: https://youtu.be/aKYlikFAV4k 🚂 #69 Evolutionary Steering Behaviors: https://youtu.be/flxOkx0yLrY 🚂 #70 Nearest Neighbors Recommendation Engine: https://youtu.be/N8Fabn1om2k Timestamps: 00:00 Introducing Part 4 01:56 Code! Creating a population of orders 05:25 Shuffling the arrays of orders 09:45 Giving each order in the population a fitness score 11:17 Storing the order with the best fitness 13:17 Creating a new file for the Genetic Algorithm 14:08 Generating the next generation based on the best orders 18:59 Picking an order using pool selection based on their fitness 22:02 Mutating the picked orders 26:02 Debugging the code 27:12 Yay! This is working! 27:26 How to make the algorithm better? Editing by Mathieu Blanchette Animations by Jason Heglund Music from Epidemic Sound 🚂 Website: http://thecodingtrain.com/ 👾 Share Your Creation! https://thecodingtrain.com/guides/passenger-showcase-guide 🚩 Suggest Topics: https://github.com/CodingTrain/Suggestion-Box 💡 GitHub: https://github.com/CodingTrain 💬 Discord: https://discord.gg/hPuGy2g 💖 Membership: http://youtube.com/thecodingtrain/join 🛒 Store: https://standard.tv/codingtrain 🖋️ Twitter: https://twitter.com/thecodingtrain 📸 Instagram: https://www.instagram.com/the.coding.train/ 🎥 Coding Challenges: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH 🎥 Intro to Programming: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6Zy51Q-x9tMWIv9cueOFTFA 🔗 p5.js: https://p5js.org 🔗 p5.js Web Editor: https://editor.p5js.org/ 🔗 Processing: https://processing.org 📄 Code of Conduct: https://github.com/CodingTrain/Code-of-Conduct This description was auto-generated. If you see a problem, please open an issue: https://github.com/CodingTrain/thecodingtrain.com/issues/new #travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js

detail
{'title': 'Coding Challenge #35.4: Traveling Salesperson with Genetic Algorithm', 'heatmap': [{'end': 708.246, 'start': 632.515, 'weight': 0.722}, {'end': 1059.027, 'start': 1011.096, 'weight': 0.969}, {'end': 1340.403, 'start': 1282.907, 'weight': 0.884}, {'end': 1653.77, 'start': 1628.012, 'weight': 0.817}], 'summary': 'Explores the use of genetic algorithm to improve efficiency in solving the traveling salesperson problem, covering topics such as population creation, shuffle function implementation in p5.js, genetic algorithm implementation in javascript, and the analysis of performance for different population sizes and city numbers, emphasizing the need for further improvements and future plans.', 'chapters': [{'end': 110.568, 'segs': [{'end': 55.673, 'src': 'embed', 'start': 17.858, 'weight': 0, 'content': [{'end': 25.162, 'text': "But just quickly, just in case you don't, what the traveling salesperson problem is is you create a set of points, cities, in a two-dimensional space.", 'start': 17.858, 'duration': 7.304}, {'end': 25.922, 'text': 'It could be three-dimensional.', 'start': 25.182, 'duration': 0.74}, {'end': 27.443, 'text': 'It could be four-dimensional.', 'start': 25.942, 'duration': 1.501}, {'end': 28.904, 'text': 'But in this case, two-dimensional.', 'start': 27.463, 'duration': 1.441}, {'end': 37.909, 'text': 'And you try to find what is a path that connects every possible city, starting from any city, ending with any cities, that is the shortest path.', 'start': 29.404, 'duration': 8.505}, {'end': 42.79, 'text': 'What is the easiest way to visit every single city and get to every single one?', 'start': 38.169, 'duration': 4.621}, {'end': 44.31, 'text': "What's the shortest path through all the cities?", 'start': 42.83, 'duration': 1.48}, {'end': 50.552, 'text': 'OK, so this particular program, which I did in the previous coding challenge, is looking at every single possibility.', 'start': 44.45, 'duration': 6.102}, {'end': 55.673, 'text': "And even just with one, two, three, four, five, six, seven cities, it's taking quite a while to check every possible city.", 'start': 50.572, 'duration': 5.101}], 'summary': 'Traveling salesperson problem: finding shortest path through cities, takes time to check all possibilities.', 'duration': 37.815, 'max_score': 17.858, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c17858.jpg'}, {'end': 101.203, 'src': 'embed', 'start': 75.878, 'weight': 2, 'content': [{'end': 81.624, 'text': "So is there a way we could do better? So the strategy I'm going to look at here is using a genetic algorithm.", 'start': 75.878, 'duration': 5.746}, {'end': 87.37, 'text': 'These are the traveling salesperson previous videos that I would recommend you take a look at.', 'start': 82.945, 'duration': 4.425}, {'end': 94.076, 'text': "And if you haven't seen or looked at any of, don't know what a genetic algorithm is, then I would recommend this particular playlist.", 'start': 87.67, 'duration': 6.406}, {'end': 99.441, 'text': "So this video that I'm making is not on this list right now because, but it will be in the future.", 'start': 94.116, 'duration': 5.325}, {'end': 101.203, 'text': 'When you are watching it, it will be there.', 'start': 99.621, 'duration': 1.582}], 'summary': 'Using a genetic algorithm to improve strategy for the traveling salesperson. related videos available for further information.', 'duration': 25.325, 'max_score': 75.878, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c75878.jpg'}], 'start': 1.459, 'title': 'Genetic algorithm for traveling salesperson', 'summary': 'Discusses the inefficiency of the exhaustive search method for the traveling salesperson problem and introduces genetic algorithm as a potential improvement, providing insights into its efficiency and effectiveness.', 'chapters': [{'end': 110.568, 'start': 1.459, 'title': 'Genetic algorithm for traveling salesperson', 'summary': 'Discusses the traveling salesperson problem and introduces the concept of a genetic algorithm as an alternative solution to the exhaustive search method, highlighting the inefficiency of the former and the potential improvement offered by the latter.', 'duration': 109.109, 'highlights': ['The traveling salesperson problem involves finding the shortest path that connects every possible city in a set, presenting challenges in computational complexity, with 10 factorial possibilities for 10 cities and exponential increases with additional cities.', 'The current approach of checking every possible city for the shortest path is inefficient, especially as the number of cities increases, as evident from the significant time taken for just a few cities.', 'The introduction of a genetic algorithm is proposed as a strategy to improve the efficiency of finding the shortest path, with references to previous videos for additional context and understanding.']}], 'duration': 109.109, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1459.jpg', 'highlights': ['The traveling salesperson problem has 10 factorial possibilities for 10 cities.', 'Checking every possible city for the shortest path is inefficient, especially with increasing cities.', 'Genetic algorithm is proposed to improve the efficiency of finding the shortest path.']}, {'end': 449.653, 'segs': [{'end': 136.857, 'src': 'embed', 'start': 110.588, 'weight': 0, 'content': [{'end': 114.81, 'text': "So if you don't know what a genetic algorithm is, I recommend maybe you check out some of these videos first and then come back.", 'start': 110.588, 'duration': 4.222}, {'end': 117.591, 'text': "But I'm just going to start programming this straight away.", 'start': 114.99, 'duration': 2.601}, {'end': 124.073, 'text': 'So the idea of the genetic algorithm is What I want to have is a population.', 'start': 117.911, 'duration': 6.162}, {'end': 125.153, 'text': "So right now I'm checking.", 'start': 124.113, 'duration': 1.04}, {'end': 128.633, 'text': 'I have this idea of an order, which is an order through all the cities.', 'start': 125.173, 'duration': 3.46}, {'end': 132.556, 'text': "So I'm just going to use the code I had from the previous coding challenge and just start from there.", 'start': 129.193, 'duration': 3.363}, {'end': 135.277, 'text': 'And hopefully this is going to work.', 'start': 132.576, 'duration': 2.701}, {'end': 136.857, 'text': "There's a bunch of stuff I'll be able to get rid of.", 'start': 135.597, 'duration': 1.26}], 'summary': 'Starting genetic algorithm programming to optimize city order.', 'duration': 26.269, 'max_score': 110.588, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c110588.jpg'}, {'end': 385.463, 'src': 'embed', 'start': 344.311, 'weight': 1, 'content': [{'end': 345.752, 'text': "But anyway, I'm just going to write my own function.", 'start': 344.311, 'duration': 1.441}, {'end': 347.674, 'text': "So I'm going to go down here to the very bottom.", 'start': 346.033, 'duration': 1.641}, {'end': 351.297, 'text': "This is something from the previous example that I don't need anymore.", 'start': 348.835, 'duration': 2.462}, {'end': 354.56, 'text': "I'm looking for the swap function.", 'start': 353.119, 'duration': 1.441}, {'end': 356.82, 'text': 'Where is the swap? Here it is.', 'start': 355.68, 'duration': 1.14}, {'end': 359.782, 'text': "So what I'm, I'm going to make use of this swap function.", 'start': 357.281, 'duration': 2.501}, {'end': 363.423, 'text': 'So my shuffle function is going to receive an array.', 'start': 360.142, 'duration': 3.281}, {'end': 366.945, 'text': "And why don't we give it like a number? Shuffle 10 times.", 'start': 363.963, 'duration': 2.982}, {'end': 368.625, 'text': 'So like shuffle the deck 10 times.', 'start': 367.085, 'duration': 1.54}, {'end': 370.146, 'text': "So I'm going to say for, oops.", 'start': 369.025, 'duration': 1.121}, {'end': 372.387, 'text': 'And so this is num.', 'start': 370.766, 'duration': 1.621}, {'end': 385.463, 'text': "For var i equals zero, i is less than num, i plus plus, var, So let's use n.", 'start': 372.987, 'duration': 12.476}], 'summary': 'Creating a shuffle function to shuffle an array 10 times', 'duration': 41.152, 'max_score': 344.311, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c344311.jpg'}, {'end': 428.275, 'src': 'embed', 'start': 397.875, 'weight': 2, 'content': [{'end': 405.662, 'text': "And then I'll just say, this is like index one, or index a, is a random index into the array.", 'start': 397.875, 'duration': 7.787}, {'end': 421.211, 'text': 'And index b, is another random index into the array, and then all I need to do is say swap array index, index A, index B.', 'start': 405.682, 'duration': 15.529}, {'end': 428.275, 'text': 'So the idea is that I shuffle by saying 10 times swap 10 spots in the array, or 100 times, or 1,000 times.', 'start': 421.211, 'duration': 7.064}], 'summary': 'Shuffling array by swapping indexes, up to 1000 times.', 'duration': 30.4, 'max_score': 397.875, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c397875.jpg'}], 'start': 110.588, 'title': 'Genetic algorithm population creation', 'summary': 'Introduces the concept of a genetic algorithm for creating a population of random configurations for traveling through cities, emphasizing the creation of a shuffled order and the use of a swap function for shuffling.', 'chapters': [{'end': 449.653, 'start': 110.588, 'title': 'Genetic algorithm population creation', 'summary': 'Introduces the concept of a genetic algorithm to create a population of random configurations for traveling through cities, emphasizing the creation of a shuffled order and the use of a swap function for shuffling.', 'duration': 339.065, 'highlights': ['The concept of the population for a genetic algorithm is introduced, emphasizing the need for a population of random configurations for traveling through cities. Population creation for genetic algorithm, random configurations for city traversal', 'The process of creating a shuffled order for the population is detailed, involving the use of a swap function to shuffle the array. Creation of shuffled order, use of swap function for shuffling', 'The implementation of a shuffle function to randomize the order of elements in the population is explained, demonstrating the use of a loop to swap array elements multiple times for shuffling. Implementation of shuffle function, use of loop for multiple element swaps']}], 'duration': 339.065, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c110588.jpg', 'highlights': ['Population creation for genetic algorithm, random configurations for city traversal', 'Creation of shuffled order, use of swap function for shuffling', 'Implementation of shuffle function, use of loop for multiple element swaps']}, {'end': 792.777, 'segs': [{'end': 512.989, 'src': 'embed', 'start': 480.724, 'weight': 2, 'content': [{'end': 482.705, 'text': 'I have to say shuffle a certain number of times.', 'start': 480.724, 'duration': 1.981}, {'end': 484.245, 'text': 'So shuffle 100 times.', 'start': 482.945, 'duration': 1.3}, {'end': 485.685, 'text': "Let's try this again.", 'start': 484.985, 'duration': 0.7}, {'end': 489.026, 'text': "And let's look at it now.", 'start': 487.845, 'duration': 1.181}, {'end': 492.086, 'text': 'There we go, so you can see these shuffled into random orders.', 'start': 489.546, 'duration': 2.54}, {'end': 495.067, 'text': 'So now I have a whole bunch of random orders, perfect.', 'start': 492.386, 'duration': 2.681}, {'end': 505.524, 'text': "Okay Now, what do I want to do here? First I want to go look up, what's this shuffle function? Shuffle p5.js reference.", 'start': 495.627, 'duration': 9.897}, {'end': 508.469, 'text': 'Because maybe this does what we want it to do.', 'start': 506.726, 'duration': 1.743}, {'end': 512.989, 'text': 'Oh yeah, array functions, shuffle.', 'start': 511.229, 'duration': 1.76}], 'summary': 'Shuffled array 100 times, explored p5.js reference for shuffle function.', 'duration': 32.265, 'max_score': 480.724, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c480724.jpg'}, {'end': 585.787, 'src': 'embed', 'start': 554.925, 'weight': 0, 'content': [{'end': 559.79, 'text': 'Why are they not shuffled? Well I have a feeling that what it does is it makes a new copy of the array.', 'start': 554.925, 'duration': 4.865}, {'end': 563.995, 'text': 'So actually what I want to do here is just say shuffle order.', 'start': 560.331, 'duration': 3.664}, {'end': 567.08, 'text': "So I'm using the p5 shuffle function.", 'start': 565.199, 'duration': 1.881}, {'end': 572.922, 'text': 'I want to just take that array order, shuffle it into a new array, and put that in the population.', 'start': 567.5, 'duration': 5.422}, {'end': 577.824, 'text': 'Perfect And now if we look at this, we can see there we go.', 'start': 573.262, 'duration': 4.562}, {'end': 579.805, 'text': 'So both are good ways of doing it.', 'start': 578.244, 'duration': 1.561}, {'end': 585.787, 'text': "Now I'm at the point where I have an array, and I have a population of orders, and I've shuffled them.", 'start': 580.065, 'duration': 5.722}], 'summary': 'Using p5 shuffle function to shuffle array order for creating a population.', 'duration': 30.862, 'max_score': 554.925, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c554925.jpg'}, {'end': 708.246, 'src': 'heatmap', 'start': 632.515, 'weight': 0.722, 'content': [{'end': 634.156, 'text': 'first I need to say what is that distance?', 'start': 632.515, 'duration': 1.641}, {'end': 635.957, 'text': "The distance is, and don't?", 'start': 634.636, 'duration': 1.321}, {'end': 637.237, 'text': 'I have a calc?', 'start': 635.957, 'duration': 1.28}, {'end': 640.98, 'text': 'from my previous example, I have this calcDistance function.', 'start': 637.237, 'duration': 3.743}, {'end': 642.649, 'text': 'which is right here.', 'start': 641.889, 'duration': 0.76}, {'end': 649.092, 'text': 'So this calculate distance function already calculates the distance of an array of points in a given order.', 'start': 642.97, 'duration': 6.122}, {'end': 649.813, 'text': "So that's perfect.", 'start': 649.212, 'duration': 0.601}, {'end': 651.233, 'text': "I don't have to add that code again.", 'start': 649.873, 'duration': 1.36}, {'end': 653.134, 'text': 'I already have that from the previous coding challenge.', 'start': 651.273, 'duration': 1.861}, {'end': 654.355, 'text': "That's really nice.", 'start': 653.594, 'duration': 0.761}, {'end': 665.16, 'text': "So I'm going to say d equals calc distance cities in the particular order of the population.", 'start': 655.135, 'duration': 10.025}, {'end': 669.317, 'text': "And then I'm going to say fitness index, i equals that distance.", 'start': 666.616, 'duration': 2.701}, {'end': 675.678, 'text': "Now that's not exactly right, because I'm going to have to do some mapping to the fitness, because a smaller distance is a higher fitness.", 'start': 669.397, 'duration': 6.281}, {'end': 677.158, 'text': "But let's just leave that for right now.", 'start': 675.698, 'duration': 1.46}, {'end': 681.499, 'text': "And let's also, we have this idea of the best ever record distance.", 'start': 677.558, 'duration': 3.941}, {'end': 684.6, 'text': "So I'm going to start with the record distance as infinity.", 'start': 681.859, 'duration': 2.741}, {'end': 691.341, 'text': "And while I'm doing that, I'm going to say if distance is less than record distance,", 'start': 685.5, 'duration': 5.841}, {'end': 701.422, 'text': 'Record distance equals that distance and best ever equals population index i that particular order.', 'start': 693.056, 'duration': 8.366}, {'end': 702.823, 'text': 'Okay, great.', 'start': 702.062, 'duration': 0.761}, {'end': 708.246, 'text': "So now, I'm going to take out this.", 'start': 703.963, 'duration': 4.283}], 'summary': 'The code calculates the distance of an array of points in a given order and determines the best ever record distance.', 'duration': 75.731, 'max_score': 632.515, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c632515.jpg'}], 'start': 452.435, 'title': 'Implementing shuffle function in p5.js', 'summary': 'Covers creating a shuffle function in p5.js, comparing it with p5.js shuffle function, implementing fitness scoring for a population of orders, with a reference to the fisher-yates shuffle algorithm.', 'chapters': [{'end': 792.777, 'start': 452.435, 'title': 'Implementing shuffle function in p5.js', 'summary': 'Covers the process of creating a shuffle function in p5.js, comparing it with the p5.js shuffle function, and implementing fitness scoring for a population of orders, with a reference to the fisher-yates shuffle algorithm.', 'duration': 340.342, 'highlights': ['The chapter discusses the process of creating a shuffle function in p5.js and compares it with the p5.js shuffle function, ultimately implementing fitness scoring for a population of orders.', 'The transcript provides insights into the process of creating a shuffle function in p5.js and the comparison with the p5.js shuffle function, along with implementing fitness scoring for a population of orders.', 'It also mentions the reference to the Fisher-Yates shuffle algorithm in the context of implementing the shuffle function in p5.js.']}], 'duration': 340.342, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c452435.jpg', 'highlights': ['The chapter covers creating a shuffle function in p5.js and comparing it with the p5.js shuffle function, while implementing fitness scoring for a population of orders.', 'Insights into the process of creating a shuffle function in p5.js and comparing it with the p5.js shuffle function are provided, along with implementing fitness scoring for a population of orders.', 'Reference to the Fisher-Yates shuffle algorithm is mentioned in the context of implementing the shuffle function in p5.js.']}, {'end': 1334.561, 'segs': [{'end': 822.221, 'src': 'embed', 'start': 792.777, 'weight': 0, 'content': [{'end': 795.438, 'text': 'you can see it got something better than just a random order.', 'start': 792.777, 'duration': 2.661}, {'end': 796.978, 'text': 'But this is clearly not the best order.', 'start': 795.458, 'duration': 1.52}, {'end': 802.841, 'text': "OK. so one thing I want to do right now, just because I'm seeing things starting to get.", 'start': 797.559, 'duration': 5.282}, {'end': 807.143, 'text': "as I already have all this code and I'm adding new code, I'm going to create a new JavaScript file.", 'start': 802.841, 'duration': 4.302}, {'end': 810.584, 'text': "I'm just going to call it ga for genetic algorithm dot js.", 'start': 807.483, 'duration': 3.101}, {'end': 816.227, 'text': "And then I'm going to add a reference to it in my index.html file.", 'start': 811.305, 'duration': 4.922}, {'end': 822.221, 'text': 'And what I want to do is I want to take some of the stuff.', 'start': 817.597, 'duration': 4.624}], 'summary': 'Creating a new javascript file for genetic algorithm implementation.', 'duration': 29.444, 'max_score': 792.777, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c792777.jpg'}, {'end': 860.007, 'src': 'embed', 'start': 835.427, 'weight': 1, 'content': [{'end': 846.13, 'text': 'But I want to have this other JavaScript file where I can start putting functions that are particularly relevant to the genetic algorithm itself there.', 'start': 835.427, 'duration': 10.703}, {'end': 849.451, 'text': 'So all I have so far.', 'start': 846.93, 'duration': 2.521}, {'end': 854.172, 'text': 'I know I just said this, but I got to recap this for myself is I create a whole bunch of random orders.', 'start': 849.451, 'duration': 4.721}, {'end': 857.526, 'text': 'I try all of them out and I pick the best one.', 'start': 855.685, 'duration': 1.841}, {'end': 860.007, 'text': 'So for the genetic algorithm to work.', 'start': 858.227, 'duration': 1.78}], 'summary': 'Developing a javascript file for genetic algorithm with random order creation and selection of the best one.', 'duration': 24.58, 'max_score': 835.427, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c835427.jpg'}, {'end': 993.185, 'src': 'embed', 'start': 971.991, 'weight': 3, 'content': [{'end': 981.877, 'text': "What I want to do is and I'm going to mention another video that I made recently is I want all of those fitness values not to be just some arbitrary value that's higher or lower,", 'start': 971.991, 'duration': 9.886}, {'end': 989.342, 'text': 'but I want them to map to a probability between 0% and 100%, and I want all of them to add up to 100%.', 'start': 981.877, 'duration': 7.465}, {'end': 993.185, 'text': 'So the way that I do that is I first need to calculate a sum.', 'start': 989.342, 'duration': 3.843}], 'summary': 'Convert fitness values to probabilities, totaling 100%.', 'duration': 21.194, 'max_score': 971.991, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c971991.jpg'}, {'end': 1059.027, 'src': 'heatmap', 'start': 1011.096, 'weight': 0.969, 'content': [{'end': 1014.577, 'text': "because that's really the array that I'm working with, although fitness and population are going to have the same length.", 'start': 1011.096, 'duration': 3.481}, {'end': 1022.72, 'text': "I'm going to then go through it again and say fitness index i equals fitness index i divided by sum.", 'start': 1015.517, 'duration': 7.203}, {'end': 1026.222, 'text': 'So this is the process of normalizing all those fitness values.', 'start': 1023.101, 'duration': 3.121}, {'end': 1032.709, 'text': "Okay, so if I go back to the sketch, this is something I'm going to do every frame.", 'start': 1027.765, 'duration': 4.944}, {'end': 1035.311, 'text': 'So now I really have my genetic algorithm.', 'start': 1032.97, 'duration': 2.341}, {'end': 1042.917, 'text': 'The first thing I need to do is calculate fitness, then I need to normalize fitness.', 'start': 1036.693, 'duration': 6.224}, {'end': 1051.666, 'text': "Okay, so once we've done that, I've calculated fitness, I've normalized fitness, now it's time to make the next generation.", 'start': 1043.699, 'duration': 7.967}, {'end': 1059.027, 'text': "And you know, I suppose I could draw the best before I make the next generation, but I'm not going to worry about order too much here right now,", 'start': 1053.103, 'duration': 5.924}], 'summary': 'Creating a genetic algorithm to calculate and normalize fitness values for the next generation.', 'duration': 47.931, 'max_score': 1011.096, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1011096.jpg'}, {'end': 1042.917, 'src': 'embed', 'start': 1015.517, 'weight': 2, 'content': [{'end': 1022.72, 'text': "I'm going to then go through it again and say fitness index i equals fitness index i divided by sum.", 'start': 1015.517, 'duration': 7.203}, {'end': 1026.222, 'text': 'So this is the process of normalizing all those fitness values.', 'start': 1023.101, 'duration': 3.121}, {'end': 1032.709, 'text': "Okay, so if I go back to the sketch, this is something I'm going to do every frame.", 'start': 1027.765, 'duration': 4.944}, {'end': 1035.311, 'text': 'So now I really have my genetic algorithm.', 'start': 1032.97, 'duration': 2.341}, {'end': 1042.917, 'text': 'The first thing I need to do is calculate fitness, then I need to normalize fitness.', 'start': 1036.693, 'duration': 6.224}], 'summary': 'Process of normalizing fitness values for genetic algorithm.', 'duration': 27.4, 'max_score': 1015.517, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1015517.jpg'}, {'end': 1095.344, 'src': 'embed', 'start': 1063.35, 'weight': 5, 'content': [{'end': 1069.734, 'text': "So how do I make the next generation? Okay, let's go back to here, and I'm going to write that function.", 'start': 1063.35, 'duration': 6.384}, {'end': 1072.917, 'text': 'Next generation.', 'start': 1070.595, 'duration': 2.322}, {'end': 1075.238, 'text': "So I'm going to make another array.", 'start': 1073.837, 'duration': 1.401}, {'end': 1077.179, 'text': "I'm going to call it new population.", 'start': 1075.258, 'duration': 1.921}, {'end': 1084.46, 'text': 'And what I want to do is I want to, create something like this.', 'start': 1079.241, 'duration': 5.219}, {'end': 1095.344, 'text': 'I want to say, for every, I want to say, for every member of the existing population, make a new member of the new population.', 'start': 1084.52, 'duration': 10.824}], 'summary': 'Creating a new generation by iterating through existing population and making new members.', 'duration': 31.994, 'max_score': 1063.35, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1063350.jpg'}, {'end': 1194.133, 'src': 'embed', 'start': 1172.256, 'weight': 4, 'content': [{'end': 1181.004, 'text': 'How do I pick one member of the old population according to its fitness value? The things with a higher fitness, I want to pick more often.', 'start': 1172.256, 'duration': 8.748}, {'end': 1183.706, 'text': 'The things with a lower fitness, I want to pick less often.', 'start': 1181.224, 'duration': 2.482}, {'end': 1187.93, 'text': "I want to just copy the ones that were good and not copy the ones that weren't so good.", 'start': 1184.026, 'duration': 3.904}, {'end': 1194.133, 'text': "Okay, so how do I do that? So I've already normal map, I've already calculated fitness and normalized it.", 'start': 1188.47, 'duration': 5.663}], 'summary': 'Select members based on fitness value to copy good ones more often and bad ones less often.', 'duration': 21.877, 'max_score': 1172.256, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1172256.jpg'}], 'start': 792.777, 'title': 'Genetic algorithm implementation and process', 'summary': 'Discusses implementing a genetic algorithm in javascript, creating separate files for algorithm functions, and outlines the process of calculating fitness values, normalizing them to probabilities, and creating the next generation with a focus on pool selection.', 'chapters': [{'end': 955.91, 'start': 792.777, 'title': 'Genetic algorithm implementation', 'summary': 'Discusses the implementation of a genetic algorithm in javascript, including creating a separate file for relevant algorithm functions, such as calculating fitness and generating new orders based on the best ones.', 'duration': 163.133, 'highlights': ['Creating a new JavaScript file for genetic algorithm functions The speaker mentions creating a new JavaScript file called ga.js to contain functions relevant to the genetic algorithm.', 'Separating relevant functions for the genetic algorithm into a separate file The chapter emphasizes the need to move certain functions, such as calculating fitness, into a separate JavaScript file to focus on genetic algorithm-specific operations.', 'Adjusting fitness calculation for genetic algorithm The speaker discusses modifying fitness calculation by inverting the distance value to ensure a higher distance corresponds to a lower fitness value, achieved through the formula 1 divided by d.']}, {'end': 1334.561, 'start': 955.93, 'title': 'Genetic algorithm process', 'summary': 'Outlines the process of calculating fitness values, normalizing them to probabilities, and creating the next generation in a genetic algorithm, with a particular focus on the process of pool selection.', 'duration': 378.631, 'highlights': ['The process of normalizing fitness values is crucial, ensuring they map to a probability between 0% and 100% and add up to 100% in total. The fitness values are normalized to map to a probability between 0% and 100%, ensuring that they add up to 100% in total.', 'The step of pool selection involves picking one member of the old population based on its fitness value, prioritizing those with higher fitness and avoiding those with lower fitness. Pool selection involves picking one member of the old population based on its fitness value, prioritizing those with higher fitness and avoiding those with lower fitness.', "The function 'next generation' is introduced to create a new population by picking members from the existing population based on their fitness values. The 'next generation' function creates a new population by picking members from the existing population based on their fitness values."]}], 'duration': 541.784, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c792777.jpg', 'highlights': ['Creating a new JavaScript file for genetic algorithm functions', 'Separating relevant functions for the genetic algorithm into a separate file', 'Adjusting fitness calculation for genetic algorithm', 'The process of normalizing fitness values is crucial, ensuring they map to a probability between 0% and 100% and add up to 100% in total', 'The step of pool selection involves picking one member of the old population based on its fitness value, prioritizing those with higher fitness and avoiding those with lower fitness', "The function 'next generation' is introduced to create a new population by picking members from the existing population based on their fitness values"]}, {'end': 1795.021, 'segs': [{'end': 1364.538, 'src': 'embed', 'start': 1334.982, 'weight': 0, 'content': [{'end': 1340.403, 'text': "So this is where I'm going to add a function, and I'm going to call it mutate.", 'start': 1334.982, 'duration': 5.421}, {'end': 1345.944, 'text': "So in next generation, I'm now also going to say mutate order.", 'start': 1341.723, 'duration': 4.221}, {'end': 1356.313, 'text': "So now I need to write sorry, Yeah, mutate, oh, and also I didn't.", 'start': 1347.364, 'duration': 8.949}, {'end': 1360.756, 'text': 'I also have to actually put it in the population, in the new population, which I forgot to do.', 'start': 1356.313, 'duration': 4.443}, {'end': 1364.538, 'text': "So let's make sure things are still working when I do that.", 'start': 1362.277, 'duration': 2.261}], 'summary': 'Adding a mutate function for next generation in the population.', 'duration': 29.556, 'max_score': 1334.982, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1334982.jpg'}, {'end': 1423.653, 'src': 'embed', 'start': 1395.27, 'weight': 1, 'content': [{'end': 1402.577, 'text': "How am I going to do that? So I'm going to write a function called mutate, and it's going to take an order.", 'start': 1395.27, 'duration': 7.307}, {'end': 1407.121, 'text': "And what I'm going to do is, now we have to think, and a mutation rate.", 'start': 1403.878, 'duration': 3.243}, {'end': 1411.851, 'text': "So let's think about this.", 'start': 1410.831, 'duration': 1.02}, {'end': 1423.653, 'text': 'Mutation, so how do I mutate an order? Well, one way to do it would actually just to be to take two random elements and swap them.', 'start': 1412.631, 'duration': 11.022}], 'summary': 'Creating a function to mutate an order by swapping two random elements.', 'duration': 28.383, 'max_score': 1395.27, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1395270.jpg'}, {'end': 1659.552, 'src': 'heatmap', 'start': 1628.012, 'weight': 0.817, 'content': [{'end': 1631.493, 'text': "And I've got some console log in here that I probably want to get rid of, or maybe I don't.", 'start': 1628.012, 'duration': 3.481}, {'end': 1633.775, 'text': "Let's try refreshing it and see what happens.", 'start': 1631.513, 'duration': 2.262}, {'end': 1634.535, 'text': 'Ah, yes.', 'start': 1634.235, 'duration': 0.3}, {'end': 1636.296, 'text': "So it's getting better over time.", 'start': 1634.855, 'duration': 1.441}, {'end': 1637.556, 'text': 'Ah, this is working.', 'start': 1636.316, 'duration': 1.24}, {'end': 1638.397, 'text': 'Look at that.', 'start': 1637.937, 'duration': 0.46}, {'end': 1639.177, 'text': 'How wonderful.', 'start': 1638.517, 'duration': 0.66}, {'end': 1639.917, 'text': 'OK, yay.', 'start': 1639.477, 'duration': 0.44}, {'end': 1653.77, 'text': "All right, so now, what have I done? Have I really solved the traveling salesperson problem? I don't think so.", 'start': 1644.54, 'duration': 9.23}, {'end': 1659.552, 'text': 'So first of all, is this the optimal order? Looks pretty good, but kind of hard to say.', 'start': 1653.89, 'duration': 5.662}], 'summary': 'Testing and improving a solution for the traveling salesperson problem, but the optimal order is uncertain.', 'duration': 31.54, 'max_score': 1628.012, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1628012.jpg'}, {'end': 1696.199, 'src': 'embed', 'start': 1664.193, 'weight': 6, 'content': [{'end': 1665.094, 'text': "Wouldn't that be less?", 'start': 1664.193, 'duration': 0.901}, {'end': 1666.894, 'text': "but I know it's hard for me to eyeball it,", 'start': 1665.094, 'duration': 1.8}, {'end': 1672.955, 'text': 'but only way for us to check for sure would be to also have the brute force solution going and have it check every possibility,', 'start': 1666.894, 'duration': 6.061}, {'end': 1677.436, 'text': 'which I would love for somebody to contribute to this to add that functionality back in.', 'start': 1672.955, 'duration': 4.481}, {'end': 1679.597, 'text': "But let's just go to total cities equals five.", 'start': 1677.796, 'duration': 1.801}, {'end': 1685.658, 'text': "And we can see that very, and let's make the population size, let's make that a variable.", 'start': 1681.877, 'duration': 3.781}, {'end': 1692.878, 'text': "And let's just make that 10 right now.", 'start': 1690.317, 'duration': 2.561}, {'end': 1696.199, 'text': "And so I'm going to put that here.", 'start': 1694.259, 'duration': 1.94}], 'summary': 'Seeking contribution to add brute force solution for checking every possibility in a program with 5 cities and a population size of 10.', 'duration': 32.006, 'max_score': 1664.193, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1664193.jpg'}, {'end': 1763.078, 'src': 'embed', 'start': 1717.008, 'weight': 2, 'content': [{'end': 1728.874, 'text': "Sorry What did I have it at? Total, even now with 10 cities, you're going to see it's doing really, really terribly.", 'start': 1717.008, 'duration': 11.866}, {'end': 1731.134, 'text': 'But I only gave it a population of 10.', 'start': 1728.974, 'duration': 2.16}, {'end': 1732.515, 'text': "So let's give it a population of 300.", 'start': 1731.134, 'duration': 1.381}, {'end': 1737.436, 'text': "And you could see with 10, I don't know, maybe that's is that a good order?", 'start': 1732.515, 'duration': 4.921}, {'end': 1742.277, 'text': 'No, you could clearly see that you could get a much shorter order by going up those three and then across.', 'start': 1737.536, 'duration': 4.741}, {'end': 1743.277, 'text': "You can't.", 'start': 1742.937, 'duration': 0.34}, {'end': 1745.612, 'text': 'My hand is, oh, there, it figured it out.', 'start': 1744.232, 'duration': 1.38}, {'end': 1746.573, 'text': 'So look at this.', 'start': 1745.832, 'duration': 0.741}, {'end': 1749.173, 'text': "Ah, maybe there's some optimization here that could be done.", 'start': 1747.113, 'duration': 2.06}, {'end': 1749.634, 'text': "I don't know.", 'start': 1749.253, 'duration': 0.381}, {'end': 1751.154, 'text': 'So you can see that this is working.', 'start': 1749.954, 'duration': 1.2}, {'end': 1752.875, 'text': "And I didn't even do crossover.", 'start': 1751.454, 'duration': 1.421}, {'end': 1757.156, 'text': "All I'm doing is mutating, swapping some points in ones that did well.", 'start': 1753.215, 'duration': 3.941}, {'end': 1760.697, 'text': "I didn't even make the fitness function an exponential function.", 'start': 1757.216, 'duration': 3.481}, {'end': 1763.078, 'text': "So there's a lot of improvements we can make on this.", 'start': 1761.057, 'duration': 2.021}], 'summary': 'City optimization algorithm working with population 10, suggests potential for further improvements.', 'duration': 46.07, 'max_score': 1717.008, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1717008.jpg'}, {'end': 1795.021, 'src': 'embed', 'start': 1781.028, 'weight': 3, 'content': [{'end': 1787.774, 'text': "So what I'm going to do in the next video is I'm going to try to add some things to improve this, and namely do crossover between two orders,", 'start': 1781.028, 'duration': 6.746}, {'end': 1790.176, 'text': "which will not be so obvious how to do that I don't think.", 'start': 1787.774, 'duration': 2.402}, {'end': 1793.659, 'text': "I'll have to think about that in between when I hit stop recording and recording.", 'start': 1790.577, 'duration': 3.082}, {'end': 1795.021, 'text': 'OK, see you in the next video.', 'start': 1793.88, 'duration': 1.141}], 'summary': 'The next video will attempt to improve by adding crossovers between two orders.', 'duration': 13.993, 'max_score': 1781.028, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1781028.jpg'}], 'start': 1334.982, 'title': 'Implementing mutation in genetic algorithm and solving the traveling salesperson problem', 'summary': 'Discusses the implementation of a mutation function in a genetic algorithm to introduce subtle changes, and the progress made in solving the traveling salesperson problem with analysis of performance for different population sizes and city numbers, emphasizing the need for further improvements and the plan for the next steps.', 'chapters': [{'end': 1634.535, 'start': 1334.982, 'title': 'Implementing mutation in genetic algorithm', 'summary': "Discusses the implementation of a mutation function, which involves swapping two random elements in an order to introduce subtle changes, with the aim of improving the genetic algorithm's performance.", 'duration': 299.553, 'highlights': ["The importance of adding a mutation function to introduce subtle changes and improve the genetic algorithm's performance. ", 'The process of implementing the mutation function by swapping two random elements in an order. ', 'The troubleshooting process involving checking and uncommenting the mutate function to ensure its proper execution. ']}, {'end': 1795.021, 'start': 1634.855, 'title': 'Solving the traveling salesperson problem', 'summary': 'Discusses the progress made in solving the traveling salesperson problem using a genetic algorithm, with analysis of its performance for different population sizes and city numbers, highlighting the need for further improvements and the plan for the next steps.', 'duration': 160.166, 'highlights': ["The algorithm's performance is evaluated for different population sizes and city numbers, demonstrating its effectiveness for small numbers but poor performance for larger city numbers with a population size of 10, while showing potential for optimization. (e.g. population size of 300)", 'The need for improvements is emphasized, including the intention to introduce crossover between two orders in the genetic algorithm to enhance its efficiency and effectiveness.', "The speaker plans to enhance the algorithm by incorporating crossover between two orders and drawing the current population's best order in the next video, indicating a focus on refining the genetic algorithm's functionality and performance.", 'The current approach involves mutating and swapping points in the orders, with the speaker identifying the need to make the fitness function an exponential function and considering additional optimization opportunities.', 'The speaker highlights the need for someone to contribute to adding functionality for the brute force solution to check every possibility in the algorithm, expressing a desire for further development of the genetic algorithm.']}], 'duration': 460.039, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/M3KTWnTrU_c/pics/M3KTWnTrU_c1334982.jpg', 'highlights': ["The importance of adding a mutation function to improve genetic algorithm's performance.", 'The process of implementing the mutation function by swapping two random elements.', "The algorithm's performance is evaluated for different population sizes and city numbers, demonstrating effectiveness for small numbers but poor performance for larger city numbers.", 'The need for improvements is emphasized, including the intention to introduce crossover between two orders in the genetic algorithm.', "The speaker plans to enhance the algorithm by incorporating crossover between two orders and drawing the current population's best order in the next video.", 'The current approach involves mutating and swapping points in the orders, with the speaker identifying the need to make the fitness function an exponential function and considering additional optimization opportunities.', 'The speaker highlights the need for someone to contribute to adding functionality for the brute force solution to check every possibility in the algorithm.']}], 'highlights': ['Genetic algorithm proposed to improve efficiency of finding shortest path', 'Population creation for genetic algorithm, random configurations for city traversal', 'Creation of shuffled order, use of swap function for shuffling', 'Implementation of shuffle function, use of loop for multiple element swaps', 'Insights into creating a shuffle function in p5.js and comparing it with p5.js shuffle function', 'Reference to Fisher-Yates shuffle algorithm in context of implementing shuffle function in p5.js', 'Creating a new JavaScript file for genetic algorithm functions', 'Separating relevant functions for genetic algorithm into a separate file', 'Adjusting fitness calculation for genetic algorithm, normalizing fitness values', "Introduction of 'next generation' function to create new population based on fitness values", "Importance of adding mutation function to improve genetic algorithm's performance", "Evaluation of algorithm's performance for different population sizes and city numbers", 'Emphasis on need for improvements, including introducing crossover between two orders', "Plan to enhance algorithm by incorporating crossover between two orders and drawing current population's best order", 'Identification of need to make fitness function an exponential function and considering additional optimization opportunities', 'Highlighting need for contribution to adding functionality for brute force solution in the algorithm']}