Genetic Algorithm In Python Super Basic Example
Vložit
- čas přidán 9. 09. 2020
- Genetic Algorithms are a family of evolutionary algorithms which can be implemented in any language (including python) they solve problems which have no clear solution by generating random solutions and picking the best results then applying a crossover and a mutation to the best solutions before starting the process again.
Due to the "evolving" nature of this algorithm, the search space is greatly reduced in comparison to exhaustive search.
To learn more about Genetic Algorithms:
en.wikipedia.org/wiki/Genetic...
Give me money:
/ @thebuilder
Below are affiliate links, I may earn something if you purchase the mentioned product or service linked.
📚 Recommended Books
Fluent Python: amzn.to/3Za7PEN
Tour of C++: amzn.to/3FY0pxW
💵 Get $100 in credits from Vultr with this link
www.vultr.com/?ref=9190242-8H
#python #algorithm - Věda a technologie
Subscribe for more
I found an improvement that made it literally 100 times faster. There, in line 34, when you append all three elements to the same group you're mixing the x, y and z elements. So when you use these elements to create new tupple most of the newGen solutions are mixed, using a good y as x, a good x as z and so on. To fix it, instead of just one group "elements" create three groups ("elements_0", "elements_1" and "elements_2"). Then instead of "elements.append(s[1][0])" type "elements_0.append(s[1][0])", "elements_1.append(s[1][1])" and "elements_2.append(s[1][2])". Finally, when creating the newGen, comand "e1 = random.choice(elemets_0)" and the same for the other two groups. This way you're always taking a good x as x, y as y and z as z, no more scrumble. Congrats for the nice class Top Shelf, the best I could find so far!
I thought the same when I saw the video. The outcome of x, y and z are always around 0.27. This means that if you first solve x in 6*x**3 + 9*x**2 + 90*x = 25 (which is around 0.27), you have an indication where you could start with the initial solutions[ ] array in line 15. If you append that with random.uniform(0,0.3) instead of random.uniform(0,10000), the solution is mostly found within 3 generations, given the accuracy of 999 in line 32.
Tried your solution by the way but it generally takes more generations to find the solution. So I don't see how it's 100x faster.
Information about the slot of the element variable is lost when he lumps it all together in the elements array and samples it without regarding the index of the element. I don't know whether your fix 100x faster, but it's definitely faster in general. Well spotted.
This is a @Jay Karlsen test
Nice idea, instead of finding the solutions after the 800 generation, I found it in the 352 generation with much more fitness rank 👍👍
Slow , steady and perfect video thank you so much !!
Glad it helped!
That was amazing. I just managed to make my first neural network and wanted to learn the NEAT algorithm.
You made it easier for me to understand the application of the genetic algorithm.
Much thanks!
this is so awesome thank you! This really helped distill my understanding of genetic iteration.
thanks sir! the best yet simple explanation for AG ive seen so far... more power!
happy to hear that
Nice Video.
Small tip: you can sort a list in descending order by using the parameter 'reverse' (like: list.sort(reverse=True)) instead of sorting and then reversing the list.
thanks, when I made this I didn't expect it to blow up like it did. I should have scripted it better
@@TheBuilder You can take solace (?) in the fact that this video will be the starting point for part of my PhD thesis work. 😂 Explained well enough that even a complete newbie like me understood what was going on.
I subscribed cause you teach clearly and do not step out of anything. Thank you, sir.
I appreciate that!
This is really great, easy to follow
really great tutorial enjoyed it alot! please keep it up! thank you very much! :) subed!
Thanks for the video, helping me through my AI assignments. A little trick I found is to make the mutation rate adjust depending on fitness, if fitness was exponential, and mutation rate being the inverse (of course capped at 0.02 though) It helps with being super precise
Im honestly surprised so many people found it useful
@@TheBuilder I got given an assignment to make an AI with genetic algorithms as part of my university course. I had absolutely no idea how to make one. This video may have saved me 😄 It is not copied line for line, but just the general thinking behind it was referenced
Hi, thank you for the video. If we want to add constraints in this model how can we do that? Do you have any example code to share about that?
You should try writing constraints that are incorporated into the fitness function, but it probably won't work very well.
Very smooth and clear my boss
Bro, it's great..... Thank you very much. I really appreciate you for this.
I'm a bit confused on why at 12:30 do we scramble all the parameters together into a big list, because aren't a, b and c independent values, like in the correct solution "a" could be 10 and "b" could be 100 so it wouldn't make sense to put them all into the same list because in the next generation the value of "b" from the last generation (let's say 95) could be put in the "a" place (which should be much smaller). Could you explain this if you understood what I meant, thanks
the number of parameters was so small that it would still converge on the result in a couple of seconds so I wasn't thinking about efficiency
Excellent! very informative and understandable.
thanks, if you like i also have a version in C++ which is better structured
Awesome video man! Your good in explainning! The end of the video is so funny :-D
this
Great video! Thank you very much
Glad it helped!
It would great to show the different parts of a GA, variation, fitness, etc.
thank you for your amazing video , I have question about how we can save best result (last ranked solutions ) in a list?
You can make a list for only that solution and save it using the append function
You can make this much much faster by changing the fixed mutation to a time based mutation, i used a 1 - 0.2exp(-i/10), 1 + 0.2exp(-i10). Thank you for this very informative video nonetheless it gives a very clear idea of what genetic algorithms actually are.
Great video! Thanks alot!
i keep getting this error about line 25:"''float' object is not subscriptable".
do you have any idea why?
Thank you! It helped me a ton!
any time
Thank you so much. Great tutorial. I actually learned the best from this tutorial.
Glad it helped!
Thanks, very interesting video!!
glad to hear it
Many thanks for the python code! Very cool
thanks robot bro
hi, thanks for your impressive explaination! Something confuses me is that, I notice that in the array 'element', you just put all the param_x, param_y, param_z into the 'element' array and then randomly choose the new x, y, z value and mutate it. But why? From my perspective, it will cause that the param_x in this iteration will come from the prarm_y in previous iteration, won't it fall into chaos?
you are right, as the complexity of a single solution increases the more random the new solutions become with this example. It would be better to select new components for a specific parameter but I didn't feel like increasing the complexity of the code sorry if that confused anyone
@@TheBuilder thanks for your explaination!
@@TheBuilder I think separating the elements is very essential, otherwise you're actually solving `6*x**3 + 9*x**2 + 90*x = 25`, that's a reason why your best solutions having almost same result.
@@jacrywoo If you use only one of the solution components the algorithm spits out it will give you a much higher error, to restate, the algorithm is not optimized for speed but it will eventually find a solution in the manner genetic algorithms do but if you're generating solutions with hundreds of variables it will significantly slow down the Algorithm to the point of being guess work. I implemented this after reading about them on Wikipedia but I didn't consider to optimize the algorithm due to only using 3 variables
While constraining the random selection of X,Y, and Z does seem like it would improve this algorithm, it still seems to me that there's an inefficiency here. It seems like for the more a complex equation where there would be a large family of possible solutions, that if a given solution is "close", then mixing and matching each variable from separate solutions doesn't make sense to me. Because the X value of a close solution, mixed with a Y value of different close solution, only makes sense when there's 1 solution. Otherwise it seems there's no guarantee, it even seems random in my opinion, whether this mix and match would offer any improvement at all. Sure randomness and brute force will get us there, I'm not denying that, but I feel we can do better.
Hey! I suppose you did this for learning purposes, but all for loops you wrote could be replaced by list comprehensions. Also, the reason why you had to manually add a second convergence interval break was because your approximation rate (or learning rate) was too big for it to converge properly! Really nice video
would be amazing if you could do an implementation of the ES Hyperneat algorithm, but not using the typical google enviroments
Superb video, thank you very much! If I need x to be in a certain range, how could I define that in the code?
Do you mean in the foo function the variable x?
Really Easiest Example
Great video. Thanks :)
My pleasure!
This video is awesome!
glad you found it useful
Thank you
Thanks for the video.
Please, how can one optimize the coefficients of a Logistic Regression Model using a Genetic Algorithm?
using grid search cv for it instead of GA
I am fairly new to GA, and was able to kind of grasp the whole. So the first part is the choice of the fittest solutions (first 100). Then comes the crossover, which is randomly choosing from the pool of fittest solutions (please correct me if I am wrong). Then comes the multiplication by a random probability range, which is where I am confused a little. I would like to know why a multiplication by a random probability is a mutation in this scenario; specifically why do you multiply the chosen elements to obtain a mutation ? In the classical scenario, a mutation would be the swapping of 1 to 0 or 0 to 1 and I would like to know why in this case it represents multiplication.
Its my interpretation of the algorithm. The general algorithm describes the mutation stage: "creating a slightly different solution" which is why I mutate my solutions by a percentage. Following your approach would cause the algorithm to be a lot more random and slower in finding the optimal solution. Please share your sources because you're not the first one to recommend swapping around bits and I want to know why this implementation detail is preferred
@@TheBuilder My sources are videos on CZcams (m.czcams.com/video/nhT56blfRpE/video.html is one of them) where I understood the concept that a given solution is composed of bits of 1 and 0. Therefore, the mutation process is the swapping of a random bit from 1 to 0 or vice versa to obtain a new (better) solution, which is why I asked concerning your method. It seems your method works great though so I guess it’s an approach.
I think you rushed in the explanation too much in the important part, which is at the end when the new contestants mutate from the previous bests. Still it is a really good example and without pedantic, too complex, paraphernalic, stack overflowish code, and I respect that.
valuable feedback thanks
Interesting, thanks!
thanks for the support
1000 LIKES------You are the MAN
Good evening, thank you for this video. I'm trying to reproduce this code to solve a second equation at the same time with 3 unknowns (6 unknowns to be determined) and I'm having a bit of trouble, do you have any advice?
And is it normal that we find approximately a solution where x=y=z? Because I tested with another function with a sine and the program also finds me a solution where the 3 variables are almost identical.
@@thomasjarland8638 First question, you would need to refactor the fitness function to give you a result based on the two functions you're trying to optimize, so if you're trying to optimize two functions just change your fitness function to calculate how fit your solution is for your functions. Second, that isn't a problem as long as you're getting a solution which is close to your answer.
Hey thanks for posting this! I couldn't solve my previous issue; that line just prints scrolling numbers and generations; so I wrote my own code to do that - works just as well, looks even better.
I am able to follow the code through, but I couldn't have written it myself from scratch (yet); the narrator seemed to be blowing it off the top of his head on the fly - I got a long way to go before I am that proficient!
I have adapted it to solve other math problems. You get a different (still correct) answer each time! I suppose there is a way to calculate exactly how many solutions there are to equations like that, or maybe if you are shooting for a "close, good enough" solution, there may be an infinite number, depending on how close you set the break-out. I don't know.
It uses MUTATION, and I found by increasing from 2%->10% it solves much quicker and shorter!
Also, as I study the theory of GA, there is something called "crossover". I know what it is, but I don't see it.
Is that used here? Or am I missing it? (be gentle, I am a newbie with GA).
Great video, helped a ton. Have a question tho. So our professor gave us an assignment to use a GA to find the parameter set of another GA, instead of the user manually typing those parameters, such as mutation probability. For example: GA #1 is processing the equation we gave it, while GA #2 is trying to find the best set of parameters for GA#1 in order for GA#1 find the best solution. Our teacher was previously (and still is) a maths teacher and I find her knowledge in comp sci somewhat lacking(I know, a bad thing to come from a student, but she became a comp sci practically overnight). She calls that process meta-optimization. Is that even a thing? Does that even make sense? Like I tried Googling that stuff, but never found any info of someone actually like putting 2 GA's on top of each other in order to find the best parameters (mutation prob, population, etc). Can you perhaps explain that to me?
Sounds like she wants you to tweak the parameters of the genetic algorithm, run the genetic algorithm and compare the performance to the other runs, I'm not a scientist but tweaking the parameters of the meta optimizing algorithm as the first one runs does not make a lot of sense, I would think you would want to compare the performance after each run found its respective bottom of the function being optimized then use the best parameters, kind of like tweaking a parameters of a normal function except now you're doing it on a genetic algorithm, I didn't study this stuff in school so I can't be to much help with more advanced topics
Thank You!
no problem happy to help
Thanks a lot!
You're welcome!
Hello! Nice tutorial to explain the key/abstract elements of GA. But allow me to mention a couple of points. Someone raised it in the comments (12:30 or thereabouts). I think it is misleading to append the three parameters into one list then selecting at random from that one list. That translates to generating a gene for the 'arms' from a 'gene' for the 'legs' for example. A proper GA code would separate them and randomize around the same gene.
This 'mistake' will cause a faster convergence since it allows the population to try more solutions beyond 1% from the previous population, but also makes it hard to get to the final solution when you are near the correct values, since the mutation could re-start from a completely unrelated, 'far' value.
You are referring to the "elements" list I presume; I wondered about that too. But since x,y,z have no intrinsic difference from each other, scrambling them should work ok; it seems like a type of "crossover" if I understand correctly.
in which part the cross over is happening here?
i recommend watching the C++ version on my channel its better structured
When I get to the line: print(f"=== Gen {i} best solutions === ") I get a "invalid syntax" error, and the cursor is placed between the final ") characters, suggesting the problem is there. Anyone else get this? I am using python 3.5.4 in Fedora Linux.
not enough information to help, I recommend going through the source code to make sure everything is formatted properly, if you open your python repel, define i somewhere and run the code you posted, it works fine so its not that line, as long as i is defined. otherwise I can't help you unless I see your full source code
@@TheBuilder I copied the code exactly as in the video, and checked each step along the way. No problem till I got to this line. Could it be python version? or the IDLE environment? The variable "i" is defined in the function above it ok.
@@FractAlkemist Python is picky with indents, make sure you're indenting your code properly, otherwise I can't come up with anything off the top of my head for why you're having this issue
Hello! I want to use multi-objective genetic algorithm for data imputation. How can I do it? Can you help me with the code?
this is something your teachers would be better suited at helping you with
I did the same thing as you did but didn't get any output. I am always getting error at sort() and reverse().
try attaching a debugger to see what is going wrong
Sir how to implement multiple traveling salesman problem using NSGA-2 in python.
you can try asking your teacher
Am I missing something, why loop 10000 in line 21, when in line 16 you only loop 1000 to make 1000 random solutions?
Can you share the code please?
Hello Sir. What is the name of Mutation operator that u have applied???? that is just multiplying each chromosome by a uniformly distributed no between 0.9 and 1.1 that is 2%????
finally, something I can understand
just keep the components separated, don't mix them into the same list like I did. It doesn't matter when you have few components per solution but with problems with a lot of components it adds up. I have another version of this video in C++ which is better explained.
Wait isn't there a slight inperfection (may be just me not understanding it). We're adding the best x, y, z values in the list 'elements', without specifying which are x, y and z. Then we take random three values into a tuple and add it to newGen and make it them the new solutions. Doesn't this kind of mix x, y and z values together. And from the result we can see that x, y and z are very close to each other.
There's a comment up top that explains how to fix this, haven't tried it myself yet though
It definitely does mix them. On the other hand we have to understand that there are infinite solutions to the formula. In the implementation in the video we are searching for the solution where x, y, and z are close together. Could have been made more clear at the start.
Good stuff
Appreciate it
In line10 you should change the returned value from an arbitrarily large value to 1/ machine epsilon. Your currently selected value is too small, and there is no way for a computer to determine the difference between zero and zero +- anything smaller than machine epsilon.
You're right
can you please share the github link for code?
I deleted the script after making the video unfortunately
@@TheBuilder don't worry I wrote the code by watching your video let me share you colab notebook link
You can host the code on your GitHub and share the link for public
You actually it very well 👍
Can I know how to use GA for optimising an array? Example of given an array of [1, 2, 3, 5, 7, 9] and partition it into two. So my objective is to minimise the difference between these two…
try a greedy algorithm. take the biggest number left in the array and alternate placing it between the two arrays you will create until no numbers remain in the original array
@@TheBuilder what if solely GAs, and I have had partitioned into two..How do I crossover so that I can reach the best solution where both of them will be very close to each other?
@@yongch6407 The best I can think off the top of my head (if it has to be a GA). 1. create N arrays of indexes and which arrays they go (like a key value pair) to 2. calculate the difference between them(fitness), take the best solutions (about 10% of the original solutions) 3. Generate another N solutions by slightly changing the best solutions from the previous run (maybe randomly assigning one element to a different array and index).
what if i want to do this for any variable type function
...i m havung problem in substiting the variables in the funtion.
please give more details
@@TheBuilder suppose I want to find fitness value for n-variable in n-variable function
well i would begin by coming up with a fitness function
@@TheBuilder ahhh...ok..but if i want the function to be given by the user..
How shall I proceed?
what does, this, elements.append(s[1][0]), elements.append(s[1][1]), elements.append(s[1][2]), do?
its a way of taking the components of those solutions and adding them to a master list to create new solutions at random. s[1] gives you the list of the solutions components while s[1][0] gives you the first component of that solution, s[1][1] the second and etc.
@@TheBuilder my bad, thank u so much sir. Really appreciated ur video, hope ull do a video where we generate melody using genetic algorithm, there's a nice video inyt but I'm not sure about understanding each lines of codes
@@TheBuilder where in this video is the, cross over step, and why mutation is done by only 2%,
@@TheBuilder where can i get this code
@@greecemathapamagar7085 Line 40 the script is creating new solutions from the list of old solution components and its a 2% mutation just because, these generic algorithms are not set in stone, you can play around with them to see what works best for you. I don't have the source code on hand anymore sorry to say
Java was my first language and the lack of types in Python is making my head hurt 😂
same, i rewrote this in C++ if you prefer to watch that
I would've like to see it invent algebra lol
Line 29 print (f"=== Gen..........).
The world f not declared. How this is working !?
Thank you
you need to close the string with a quote
one in c++ please...
sure check my recent upload
Can I get the code
check my github
i'am sorry i still don't get it what actually genetic algorithm used for?
if you don't know how to solve a problem, generate a million solutions to said problem then make a function to rank those solutions. Take the best solutions and generate a million solutions from those solutions but with slight modifications until you have something good enough.
It's just sorting and taking the first 100 ?
Did I missed anything ?
The Algorithm works by taking the best N solutions then creating new solutions by using the old solutions, its how we understand evolution theory. We're taking the best solutions from the set of generated solutions then combining those solutions to create new solutions. The computer does not understand the concept of "fitness" "combining" or anything else so we have to come up with our own ideas on how to write out these concepts in code. Fitness is just a simple function for computing a number same with everything else. You understand an algorithm when you realize its very simple.
@@TheBuilder please make a video on how to make an bio eco system , i have seen youtube videos , programmed micro organisms evolving .. please , its very important to me
@@theashmedai007 I see what you mean I have a few computer graphics videos on something like that for example czcams.com/video/jzfORVhTPWI/video.html if you want to use this as a starting example of how to write something like that. I do offer a word of caution, a lot of programmers that try to associate real world qualities of life to computer programs go overboard and try to attribute concepts that are simply not there. Simply you can write a computer program to do anything you want and tell people who aren't so tech oriented that its doing something much more complex.
@@TheBuilder thanks a lot , my brain is kind of hurt , I can't really understand why this universe and life exists , may be this is a way I can calm my brain
@@theashmedai007 Its always good to find meaning where ever you can
Use a list comprehension rather than that for loop.
yea
I just can't understand the need to evaluate the cells as you do. Why bother the if ==0 and the 1/ans ? Instead of just ranking the evaluation the other way around ?
which way would be better?
Because if and is exactly zero you would get an error if you tried to calculate 1/0.
@@Chris-df8qf True that, but it can't ever get to 0 by using random.uniform so that line is just useless
I was thankful about 2048, but it was hard.
Wow, could you make it any slower?
The reason you didn't get a result close to 0 at the end was merely due to the fact that you forgot to subtract 25.
please explain, I didn't follow that
source code>
i lost it years ago
Is this really genetic algorithm. Where is selection, mutation and crossover implemented in this code? This is just generation some random numbers and iterating to get the result.
Line 35 to 47.
@@TheBuilder Ok may be another way of implementing it. But it is better to mutate or cross over it in bit level. It make more sense wrt genetic algorithm since we are mutating the gene of parents.
what do you mean at a bit level? generally optimization algorithms are conceptual until you see your problem. This is true with most algorithms in general. also premature optimization is not wise in education. writing a binary search tree is pointless in high level languages as the native implementation in C or C++ would be much faster but we still do it to teach people the concept.
CAN YOU MAKE A VIDEO ON HOW TO IMPLEMENT THIS ALGORITHM FOR A FULL DATA SCIENCE PROBLEM?. IT WILL BE REALLY HELPFUL IF YOU CAN HELP ME WITH THAT ONE
optimizing for an algebraic equation isn't a full problem?
Great great vídeo, i have a question.
Suppose You have polynomial roots ( -4,-2,-3,-1,4) and You are asked to find the 6 coeffients
How would You do it ?
Small kinda nit-picky suggestion for vids like that: It's really helpful if you'd add an abstract overview of what you're gonna do before you do it. So in this case: What is the general idea of a genetic algorithm. ( So in this case we need a problem, fitness function to evaluate our generation, "genes", mutation etc.. ) Makes listening to you coding more easy.
Also: You might wanna consider editing errors out of the vid. It's really hinders understanding if the viewer tries to understand something which is not correct - also it wastes a lot of time.
Not here to nagg, just some friendly feedback :P. Take it or don't :D.
i recommend watching the C++ version on the channel.
Why didn't you write like this? (I'm not good at ENG)
At first, I thought this is better than your code. Because my code can distinguish x, y, z. but it wasn't better than yours. I wonder why.
(my guess is that: In my code, difference between x, y, z are large. So it is hard to reach to appropriate value. But in your code, x, y and z are almost same. So it's easy to x,y,z to reach to appropriate value.)
elements1 = []
elements2 = []
elements3 = []
for s in bestsolutions:
elements1.append(s[1][0])
elements2.append(s[1][1])
elements3.append(s[1][2])
newGen = []
for _ in range(1000):
e1 = random.choice(elements1) * random.uniform(0.99, 1.01)
e2 = random.choice(elements2) * random.uniform(0.99, 1.01)
e3 = random.choice(elements3) * random.uniform(0.99, 1.01)
here, 'hard' means 'take a long time' and 'easy' means the opposite. :)
this was so confusing
if you want the gist of it, you generate lets say...x solutions then take the best y solutions and mutate them then finally generate another x solutions and keep doing that until your solution is close enough. Its an open ended algorithm so you can implement it anyway you like as long as the basic principle remains Try reading the wikipage on it if its not obvious
Idea great, but this is not how you write python :D
explain
please clap
i clapped 25 times homie no need to thank me
Informative video.Thank you so much for posting! Can you please tell me that is this minimization problem where 0
I feel like the intent behind this video is good, but you should know the basics by hearth before trying to teach genetic algos and stuff. Also, the production quality is.....mediocre at best.
Meanwhile newton's method solves this in two step. Programmers who don't want to learn math and instead just make a random search and give it a fancy biology name are my favorite 😂😂😂😂😂😂😂😂😂😂
Bro, it's great..... Thank you very much. I really appreciate you for this.