Coding Challenge #35.4: Traveling Salesperson with Genetic Algorithm
131.2 هزار بار بازدید -
8 سال پیش
-
In Part 1 of this
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...
p5.js Web Editor Sketches:
🕹️ Part 1: Traveling Salesperson (TSP): https://editor.p5js.org/codingtrain/s...
🕹️ Part 2: Lexicographic Order: https://editor.p5js.org/codingtrain/s...
🕹️ Part 3: TSP with Lexicographic Order: https://editor.p5js.org/codingtrain/s...
🕹️ Part 4: TSP with Genetic Algorithm: https://editor.p5js.org/codingtrain/s...
🕹️ Part 5: TSP with Genetic Algorithm and Crossover: https://editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Part 1: Traveling Salesperson (TSP): Coding Challenge #35.1: Traveling Sal...
📺 Part 2: Lexicographic Order: Coding Challenge #35.2: Lexicographic...
📺 Part 3: TSP with Lexicographic Order: Coding Challenge #35.3: Traveling Sal...
📺 Part 5: TSP with Genetic Algorithm and Crossover: Coding Challenge #35.5: TSP with Gene...
🎥 Previous video: Coding Challenge #34: Diffusion-Limit...
🎥 Next video: Coding Challenge #36: Blobby!
🎥 All videos: Coding Challenges
References:
🌐 Traveling Salesman on Wikipedia: https://en.wikipedia.org/wiki/Travell...
🗨️ Permutation Algorithm Using Lexicographic Ordering: https://www.quora.com/How-would-you-e...
📝 Array on MDN: https://developer.mozilla.org/en/docs...
📝 Array.includes() on MDN: https://developer.mozilla.org/en/docs...
📝 Array.reverse() on MDN: https://developer.mozilla.org/en/docs...
📝 ES6 Sets on MDN: https://developer.mozilla.org/en/docs...
💾 The Nature of Code Part 2: https://github.com/shiffman/NOC-S17-2...
📕 The Nature of Code: http://natureofcode.com/
Videos:
🎥 Improved Pool Selection: 9.8: Genetic Algorithm: Improved Pool...
🎥 Genetic Algorithm Playlist: 9: Genetic Algorithms - The Nature of...
🔴 Live Stream Archive #57: Live Stream #57 - Traveling Salesperson
Related Coding Challenges:
🚂 #29 Smart Rockets in p5.js: Coding Challenge #29: Smart Rockets i...
🚂 #51 A* Pathfinding Algorithm: A* Pathfinding Algorithm (Coding Chal...
🚂 #69 Evolutionary Steering Behaviors: Coding Challenge #69: Evolutionary St...
🚂 #70 Nearest Neighbors Recommendation Engine: Coding Challenge #70: Nearest Neighbo...
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/pas...
🚩 Suggest Topics: https://github.com/CodingTrain/Sugges...
💡 GitHub: https://github.com/CodingTrain
💬 Discord: Discord: discord
💖 Membership: http://youtube.com/thecodingtrain/join
🛒 Store: https://standard.tv/codingtrain
🖋️ Twitter: Twitter: thecodingtrain
📸 Instagram: Instagram: the.coding.train
🎥 Coding Challenges: Coding Challenges
🎥 Intro to Programming: Start learning here!
🔗 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-o...
This description was auto-generated. If you see a problem, please open an issue: https://github.com/CodingTrain/thecod...
#travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js
p5.js Web Editor Sketches:
🕹️ Part 1: Traveling Salesperson (TSP): https://editor.p5js.org/codingtrain/s...
🕹️ Part 2: Lexicographic Order: https://editor.p5js.org/codingtrain/s...
🕹️ Part 3: TSP with Lexicographic Order: https://editor.p5js.org/codingtrain/s...
🕹️ Part 4: TSP with Genetic Algorithm: https://editor.p5js.org/codingtrain/s...
🕹️ Part 5: TSP with Genetic Algorithm and Crossover: https://editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Part 1: Traveling Salesperson (TSP): Coding Challenge #35.1: Traveling Sal...
📺 Part 2: Lexicographic Order: Coding Challenge #35.2: Lexicographic...
📺 Part 3: TSP with Lexicographic Order: Coding Challenge #35.3: Traveling Sal...
📺 Part 5: TSP with Genetic Algorithm and Crossover: Coding Challenge #35.5: TSP with Gene...
🎥 Previous video: Coding Challenge #34: Diffusion-Limit...
🎥 Next video: Coding Challenge #36: Blobby!
🎥 All videos: Coding Challenges
References:
🌐 Traveling Salesman on Wikipedia: https://en.wikipedia.org/wiki/Travell...
🗨️ Permutation Algorithm Using Lexicographic Ordering: https://www.quora.com/How-would-you-e...
📝 Array on MDN: https://developer.mozilla.org/en/docs...
📝 Array.includes() on MDN: https://developer.mozilla.org/en/docs...
📝 Array.reverse() on MDN: https://developer.mozilla.org/en/docs...
📝 ES6 Sets on MDN: https://developer.mozilla.org/en/docs...
💾 The Nature of Code Part 2: https://github.com/shiffman/NOC-S17-2...
📕 The Nature of Code: http://natureofcode.com/
Videos:
🎥 Improved Pool Selection: 9.8: Genetic Algorithm: Improved Pool...
🎥 Genetic Algorithm Playlist: 9: Genetic Algorithms - The Nature of...
🔴 Live Stream Archive #57: Live Stream #57 - Traveling Salesperson
Related Coding Challenges:
🚂 #29 Smart Rockets in p5.js: Coding Challenge #29: Smart Rockets i...
🚂 #51 A* Pathfinding Algorithm: A* Pathfinding Algorithm (Coding Chal...
🚂 #69 Evolutionary Steering Behaviors: Coding Challenge #69: Evolutionary St...
🚂 #70 Nearest Neighbors Recommendation Engine: Coding Challenge #70: Nearest Neighbo...
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/pas...
🚩 Suggest Topics: https://github.com/CodingTrain/Sugges...
💡 GitHub: https://github.com/CodingTrain
💬 Discord: Discord: discord
💖 Membership: http://youtube.com/thecodingtrain/join
🛒 Store: https://standard.tv/codingtrain
🖋️ Twitter: Twitter: thecodingtrain
📸 Instagram: Instagram: the.coding.train
🎥 Coding Challenges: Coding Challenges
🎥 Intro to Programming: Start learning here!
🔗 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-o...
This description was auto-generated. If you see a problem, please open an issue: https://github.com/CodingTrain/thecod...
#travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js
8 سال پیش
در تاریخ 1396/02/11 منتشر شده
است.
131,259
بـار بازدید شده