Coding Challenge #35.4: Traveling Salesperson with Genetic Algorithm
ฝัง
- เผยแพร่เมื่อ 15 มิ.ย. 2024
- 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: thecodingtrain.com/challenges...
p5.js Web Editor Sketches:
🕹️ Part 1: Traveling Salesperson (TSP): editor.p5js.org/codingtrain/s...
🕹️ Part 2: Lexicographic Order: editor.p5js.org/codingtrain/s...
🕹️ Part 3: TSP with Lexicographic Order: editor.p5js.org/codingtrain/s...
🕹️ Part 4: TSP with Genetic Algorithm: editor.p5js.org/codingtrain/s...
🕹️ Part 5: TSP with Genetic Algorithm and Crossover: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Part 1: Traveling Salesperson (TSP): • Coding Challenge #35.1...
📺 Part 2: Lexicographic Order: • Coding Challenge #35.2...
📺 Part 3: TSP with Lexicographic Order: • Coding Challenge #35.3...
📺 Part 5: TSP with Genetic Algorithm and Crossover: • Coding Challenge #35.5...
🎥 Previous video: • Coding Challenge #34: ...
🎥 Next video: • Coding Challenge #36: ...
🎥 All videos: • Coding Challenges
References:
🌐 Traveling Salesman on Wikipedia: en.wikipedia.org/wiki/Travell...
🗨️ Permutation Algorithm Using Lexicographic Ordering: www.quora.com/How-would-you-e...
📝 Array on MDN: developer.mozilla.org/en/docs...
📝 Array.includes() on MDN: developer.mozilla.org/en/docs...
📝 Array.reverse() on MDN: developer.mozilla.org/en/docs...
📝 ES6 Sets on MDN: developer.mozilla.org/en/docs...
💾 The Nature of Code Part 2: github.com/shiffman/NOC-S17-2...
📕 The Nature of Code: natureofcode.com/
Videos:
🎥 Improved Pool Selection: • 9.8: Genetic Algorithm...
🎥 Genetic Algorithm Playlist: • 9: Genetic Algorithms ...
🔴 Live Stream Archive #57: • Live Stream #57 - Trav...
Related Coding Challenges:
🚂 #29 Smart Rockets in p5.js: • Coding Challenge #29: ...
🚂 #51 A* Pathfinding Algorithm: • A* Pathfinding Algorit...
🚂 #69 Evolutionary Steering Behaviors: • Coding Challenge #69: ...
🚂 #70 Nearest Neighbors Recommendation Engine: • Coding Challenge #70: ...
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: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: th-cam.com/users/thecodingtrainjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js
![[TH] VCT Pacific Stage 2 - Week 1 Day 1 // DRX vs ZETA | BLD vs TS](http://i.ytimg.com/vi/AWaOqaxN6Y0/mqdefault.jpg)
This man is an alien, the way he teaches is incredible, as soon as video starts the video ends without know that you spent 20 mints, thanks man
Hi I read The Nature of Code a couple of years ago, and I loved it! It was a super fun read and the code was really easy to follow. It was my intro to artificial intelligence and the beginning of my addiction. Now I'm studying computer science and AI in uni and your book is part of the reason why :)
I randomly started watching some of your videos a few days ago and when you mentioned your book I really felt the nostalgia. Your TH-cam channel looks awesome btw and I'm probably gonna binge-watch a bunch of your videos when I have the time! I love you work man. THANK YOU FOR YOUR CONTRIBUTION TO HUMANITY!
Love hearing this, thank you!!!
man. i love how well you explain things, i tried siraj's (don't know how to spell it) videos but it feels like you have to have a phd in math to understand, really looking forward to neural nets 🙌
So glad I found this channel. Even if you're using another language, these videos are incredibly helpful to learn from.
I'm doing a project for a class involving the traveling salesperson problem and was thinking of using ACS or ACO, and it's interesting how similar it is to the genetic algorithm.
Your videos are really helpful and very fun to watch, you are very fun! Thanks for the content
Great stuff! Looking forward to see part II of it!
This dude gives an authentic coding experience.
thank you for this great tutorial, i really enjoyed this series
i really love his videos. It makes progamming more fun than studying
Thank you. Your lecture has helped me a lot.
I like how this guy can't even offend an index of an array
this factorial number, we don't have a sense how long it takes. this video really shows the importance of algorithm.
Wow... everything you did seems so complicated! Nice Work!
Thank you!
Daniel i love you so much .. your recent videos are soo good
I'm so glad to hear!
lol you didnt notice it optimized it behind your back :D 27:49
i LOVE your videos btw, keep doing what you do!
27:56 to be precise
When is your next video? :D Keep it up!
Just a note on the shuffle algorithm you made, it will not produce every possible order. By swapping an even number of times, you only get half of the total permutations. All the orders created will be even permutations, and there is no way for the shuffle to produce an order that is only one, three, or five swaps away. This is the parity theorem of permutations. Helpful information when making a shuffle algorithm! Here's a link to more info on even and odd permutations. www.efgh.com/math/algebra/permutations.htm
27:54 IT UPDATED TO OPTIMAL SOLUTION
I wanted to yell at the screen when he didn't notice that.
Great! Keep it up!
I've got a challenge that I would love to see. I want to see genetic algorithm implemented in a rc car with some sort of distance tracker. so that it can make its way through the obstacle course. i understand it would take a long time. But id still love to see it
I think you need to implement the possibility of switching more than 1 pair of cities per mutation. Otherwise the algorithm can be stuck in a local minimum.
In other words: It can be, that switching any possible single pair of cities leads to a longer distance while switching 2 or more cities would further lower it.
Really like your videos! They are educational and entertaining!
yes, but that will probably be a problem anyway, the traveling salesman problem are well known to be a pretty hard to do with genetic algorithm.
Yeah I would think so too. The number of possible solutions grows with n!. And there will be lots of local optimals.
But intelligent combinations of former generation sequences might make it an efficient algorithm. But this is not an easy problem.
Looking forward to the next part.
i have one idea, about using epigenetic, and using a complete route as a gene.
it will need to have many alternative routes to randomly select between, but cross breading might help removing bad ones.
but think it will be slower then brute force, since it will often remove good routes to.
you are awesome.. you are best programmer I've ever see
Thank you!
What I would give, to be able to do the things you are doing, for a living!
Omg it found the best solution while he wasn't looking! XD
A LSTM or NEAT coding challenge/tutorial/example would be interresting and nice. Also nice videos ;-)
It's coming!
The Coding Train Nice! Always wanted to know more about those two!
I'm anxiously looking for implementation of genetic algorithm in timetable scheduling problem
you are amazing !
Is it calculating at the frame rate?
I mean, is the new distance calculated once per frame and rendered to screen? or is it only rendering the current possibility that is there in the array at the time of rendering? I guess it would be too slow to calculate only once per frame. I suppose it would be better to do the calculation in a separate thread which can continuously crunch the numbers.
Yes, the draw function is called once per frame, so everything inside of it is executed once per frame. That's just how the p5.js library works. You can add custom flags to skip things when something happens (e.g. don't draw the path again if the "bestEver" hasn't changed). That might speed things up a bit. You're right about it being better to do in a seperate thread, however, JavaScript is single thread only.
There are things called "Web Workers" that allow for multithreading in JS but that's a whole different tutorial and there are limitations with that as well, as Web Workers don't have access to things like the document object, the window object etc. I'm not sure how suitable it is in conjunction with p5.js, however, I have to admit that I don't have experience with it either.
Doing this multithreaded would be better in a language that supports parallelization properly.
Just loop the whole thing so it does it multiple times each frame :D
No need for complicated threading and stuff
@GarfieldGaming I think, if we do that on the the same UI thread, it will freeze the canvas.
@GarfieldGaming that would make it choppy and wouldn't really be any faster than doing it once each frame, because you're still calculating everything sequentially.
+Wuzzybrand06 It's capped at 60, that's why it remains at 60 even if it could go faster :D basically it calculates one frame and when it's done it does nothing for the rest of the 1/60th of a second period. I've done this multiple times and it's a neat trick because you can't seem to change the framerate cap :/ (It really does work!)
It seemed like the solutions were not only changing order, but changing the location of the dots. What am I missing?
Hello Sir I am your big fan
Hello Sir I am your big fan
Hello Sir I am your big fan
Hello Sir I am your big fan
Hello Sir I am your big fan
th-cam.com/video/mif77aOd9ns/w-d-xo.html
Hello! I found a quick way to shuffle with order.sort((a, b) => Math.random() > 0.5). But this is not be the best way to do it.
oh, that's clever!
haha those horns sound like the intro to jump around
awesome, good energy, easy to learn only one question where can i find the source code?? fast reply would be appreciated due to my project deadline, All The Bests
In the description
i am your biggest fan.
Can you try this problem with Tabu Search?
TSP is best solved with sat (constraint based) solver AFAIK
Oh, didn't even notice I was this quick :D
How a genetic algorithm could be applied to the set covering problem (SCP)?
Would in effect never work with a mute mutate function ;)
Next: Traveling Salesperson with Dynamic Programming
I'm the most big fan
could you possibly make this with google maps? what if i want to deliver packages to houses as fast as possible.
Great idea! Check out: github.com/cvalenzuela/Mappa
The Coding Train thank you
at 8:52 I assume that you haven't read the text: directly above that piece of code it says: "Here's what the implemententation looks like in Javascript, not that you should use it:". And direct below the code it says: "This is bad, and we can do better." hahaha
Sir how to implement multiple traveling salesman problem using NSGA-2 in python.
*deletes order, "next I need to create order..."
Travelling salesman Problem states that it should start and end at same city...
How to calculate fitness function without path cost?
Sir , how can i perform a scheduling with genetic algorithm
I like your way of doing things
the best programming channel on TH-cam can you please use some ES6 functions and stuff
we want to learn some modern JS
im your bigger fan
Vytautas I am a bigger fan,
dont lie
Hi, when picking one why not pick the one with the BEST fitness (like hightest fitness) ?? instead of taking it via random number
How about fitness = -d?
How can I modify this code to add my own points please can anyone help
13 factorial is 6,227,020,800 (6 billion, 227 million, 20 thousand, 8 hundred)!
can't we do this using Prim's or Kruskal's algorithm of Minimum spanning tree?
this video is about the shortest route that visits all nodes. A tree on the other hand might have branches, which isn't exactly a route you can follow (unless you backtrack, but that wouldn't be short anymore.)
Prim's and Kruskal's would indeed give an minimum spanning TREE, but the Traveling Salesman is looking for the shortest PATH among the vertices. A tree is not necessarily a path
mebamme yeah exactly... I got it
you're talking about Christofide approximate algorithm. once you have the tree, you can traverse it, skipping the backtracks. it provides a pretty good solution relatively quickly.
/20:42 "2-Dimensional space" Why does it have to be 2-dimensional!? The mathematically appropriate way to discribe it is in a 1-dimensional space!
I get this guy is trying to be fun and silly, but I wouldn't mind if he could take it down a notch. Aside from that, it's quality content. He doesn't dive deep into the theory of GAs, but enough to get novice programmers started.
22:23 mutation
Isn't the original name The traveling salesMAN?
Watching this in a car, on a laptop with linux.
I'm happy with myself
xD
java code for flying sidekick traveling salesman problem please
Hasn't the traveling salesman been solved through path of least resistance?
Why not just use dijkstra's algorithm
did university is so important in learning computer sience can i learn alone and how ?
في 90 ثانية - in 90 sec interested too
حسب علمي مستوى الجامعات العربية متدني جدا معظم الخرجين يزعمون انهم تعلموا علوم الحاسب مستقلين عن الجامعة
حسب علمي مستوى الجامعات العربية متدني جدا و معظم الخريجين يزعمون انهم تعلمو علوم الحاسب مستقلين عن الجامعة
Depends on what you want to do with it.
Do you just want to create some personal applications and delve into stuff that is shown here on the channel? No, you probably dont need a university degree. Some things might fly over your head but if you invest enough time and look into the background mathematics or whatever you will be able to do it.
But if you want a solid job in software development you will probably be required to have a degree. Even if you can show a lot of working experience employers will consider people with a degree over you, even if they lack the experience. I think they want this mathematic/algorythmic background in employees.
At least that is the way where I am from.
انا احب شرح هذا الكائن لكن المشكلة انه يستخدم مكتبة مو مشهورة وتنفع في الرسم بس
4D travelling salesperson problem, you say? 🤔
where I can find the whole code? It's much easier for me to follow
Traveling Salesman problem
Aha?
swaaaap
17:50 next gen
For decades there was something similar called the traveling salesman problem. You are being very PC about your computer science. Lol.
You make it out to be a problem.
I watched the stream and I remembered that your algorithm to associate a fitness with a probability really annoyed me so here's mine which I use in my NEAT algorithm and is way more efficient and looks like yours a little:
var fitnesses = [];
function pick() {
// Get the fitness sum
var fitnessSum = 0;
for (var i = 0; i < fitnesses.length; i++)
fitnessSum += fitness[i];
// Pick a random one
var prob = fitnessSum * random();
fitnessSum = 0;
for (var i = 0; i < fitnesses.length; i++) {
fitnessSum += fitness[i];
if (fitnessSum > prob)
return i; // or fitness[i] depending on what you want
}
}
I'm probably going to do a pull request about it soon but it really annoyed me because I had to fight with a guy who didn't understand what I was doing because he was sure that the only way to pick a member depending on the fitness was to use percentages
But the TSP needs to return back to the city he starts with! Am i right?
Woah your coding is messy as hell xD
or you just send multiple salesmen, to every city, one straight line
merge partial best paths
you could display the achieved path length
permutate partial populations
minimize path length
GENERIC not genetic ffs
Are you stupid?
Please sub this video in English