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 RU-vid 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 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.
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
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.
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.
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
