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.
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!
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 🙌
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
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!
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.
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.
@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!)
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 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.
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
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
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
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.
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.
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
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
This dude gives an authentic coding experience.
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.
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!!!
I like how this guy can't even offend an index of an array
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 🙌
i really love his videos. It makes progamming more fun than studying
this factorial number, we don't have a sense how long it takes. this video really shows the importance of algorithm.
Great stuff! Looking forward to see part II of it!
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.
Thank you. Your lecture has helped me a lot.
Your videos are really helpful and very fun to watch, you are very fun! Thanks for the content
thank you for this great tutorial, i really enjoyed this series
Wow... everything you did seems so complicated! Nice Work!
Thank you!
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.
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
Omg it found the best solution while he wasn't looking! XD
Great! Keep it up!
you are awesome.. you are best programmer I've ever see
Thank you!
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
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!)
Daniel i love you so much .. your recent videos are soo good
I'm so glad to hear!
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!
Sir how to implement multiple traveling salesman problem using NSGA-2 in python.
What I would give, to be able to do the things you are doing, for a living!
haha those horns sound like the intro to jump around
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!
How a genetic algorithm could be applied to the set covering problem (SCP)?
It seemed like the solutions were not only changing order, but changing the location of the dots. What am I missing?
Travelling salesman Problem states that it should start and end at same city...
When is your next video? :D 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'm anxiously looking for implementation of genetic algorithm in timetable scheduling problem
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
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
*deletes order, "next I need to create order..."
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.
Next: Traveling Salesperson with Dynamic Programming
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
/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!
Hi, when picking one why not pick the one with the BEST fitness (like hightest fitness) ?? instead of taking it via random number
TSP is best solved with sat (constraint based) solver AFAIK
Sir , how can i perform a scheduling with genetic algorithm
im your bigger fan
Vytautas I am a bigger fan,
dont lie
Isn't the original name The traveling salesMAN?
How to calculate fitness function without path cost?
you are amazing !
Oh, didn't even notice I was this quick :D
i am your biggest fan.
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
I'm the most big fan
Would in effect never work with a mute mutate function ;)
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.
How about fitness = -d?
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.
انا احب شرح هذا الكائن لكن المشكلة انه يستخدم مكتبة مو مشهورة وتنفع في الرسم بس
java code for flying sidekick traveling salesman problem please
Traveling Salesman problem
Aha?
Watching this in a car, on a laptop with linux.
I'm happy with myself
xD
22:23 mutation
where I can find the whole code? It's much easier for me to follow
Why not just use dijkstra's algorithm
4D travelling salesperson problem, you say? 🤔
But the TSP needs to return back to the city he starts with! Am i right?
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.
swaaaap
17:50 next gen
Woah your coding is messy as hell xD
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
GENERIC not genetic ffs
Are you stupid?
Hasn't the traveling salesman been solved through path of least resistance?
13 factorial is 6,227,020,800 (6 billion, 227 million, 20 thousand, 8 hundred)!
Can you try this problem with Tabu Search?
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
How can I modify this code to add my own points please can anyone help
Please sub this video in English