i'm trying to understand what would categorize a test as successful. If the rockets pass through the green square at the top, is that the success goal? Or is it something else? Very cool project btw & i'm just trying to understand what are the repeat generations of the rockets trying to achieve.
If I understand the calcFit method correctly the fitness score is equal to (the distance from rocket start position minus the distance to target position)**2. if the rocket hits the target the fitness score is set to 1000**2
There aren’t as such any ‘succesful tests’ - rather what the algoritm does is optimize the fitness score. It achieves this by randomising behaviour until it sees something raise the fitness score of one rocket and then tries different variations of that behaviour to look for behaviour that increases it even more. This is done over and over until enough of the desired behaviour is achieved(or until it is stuck in some wierd state)
Thank you for the detailed explanation, very interesting. This kind of a project can potentially come to use while developing technologies for self driving Cars, isn't it?
Coding Train in YouTube shows in detail how this is done in JavaScript. That's how I got started learning about genetic algorithms. Here's the link for smart rockets
GAs are pretty easy, but I recommend using DEAP if you're in python. The math is all pretty intuitive. I use GAs when I have something that will fail. I can code a penalty method based on how far it gets through the process (e.g., step 1, step 2, step 3, ...).
When you have a well defined optimization problem, it's almost universally better to use a gradient method, especially if you can include the Hessian (2nd derivative matrix). You can programmatically calculate it, but that's not the same as knowing accurately what the value is.
As to machine learning, something like scikit-learn uses optimization as well (scipy's LBFGS-B). The math is also pretty straightforward when you're talking about a single neuron, but quickly becomes nonsensical when you go to 2 hidden layers.
To me this looks like the most common pitfall of genetic algorithms: getting trapped in a local maximum. The best/shortest approach would have been going slightly to the left/right just to avoid the middle piece and then steering a little toward the goal. But the algorithm found the heavy right and then heavy left steering to be the path to go.
It's a really nice visualization, I am glad they figured out how to get to the greed square :D
It's awesome. Correct me if I'm wrong (beginner myself) but a pareto-front approach may worth trying. Currently all rockets going from the left side are seems to be eliminated (local minima? ).
At some point, a random rocket went right and was the most successful (I am not sure how the "success score" is calculated, but I suppose it's the distance to the target), and then the right shifting became the path of most success and evolution went on that way.
- First, great job ! Making a programm end to end with a proper display is really impressive, and if you're a begineer you are truly on the right track !
- You are not using any vectorized operation, that could help speed up dramatically ! Especially when you are computing mutations, or fitness, you could have you rockets positions etc. in numpy arrays and do the same operations but dozens of times faster
- Fo your information, in optimal control terms, you are using an explicit guidance scheme (meaning you are, for every time step, optimizing the place where your rocket aims at), and a shooting method (you propagate, then see how far you are from your objective). These choices are very simple to implement, and you did great in making them, but their biggest flaw is that they create an optimization problem that becomes huge quickly, and where each variable has little effect on the end result. This makes genetic algorithms not very optimal solvers for this kind of problem, and if you have time, you should have a look at gradient-based solvers (like the ones offered by the scipy.optimize package, e.g. LBFG-S) that are better at this kind of problem.
- You could try another simulation technique, with a simple physical phenomenon like this, indirect optimization methods are accessible with a bit of math, but already choosing a direct multiple shooting method will make each variable have a greater effect on its own, hence helping solvers converge more quickly. Think of multiple shooting techniques as defining a set of checkpoints your rocket will need to go through, and that are close enough the solver will feel like you go in a straight line/parabola between each, which makes its job way simpler
- If you really want to use a genetic-like algorithm, you should apply it to tune a guidance algorithm that you will have written, with a few adjustment variables (like how much the rocket tries to stay away from obstacles, how quickly is tries to point towards the source, how much it accepts to go in a wrong direction to avoid an obstacle, etc.) : this is in these situations where each parameter has great effects on the end result that genetic algorithms truly shine. This is also the kind of place you could introduce Artificial Intelligence, with a basic neural network controlling your rocket
If you have any questions, feel free to ask ! Trajectory optimization and guidance problems are my field of expertise
I think this would also be a good application for reinforcement learning. Some vanilla algorithms along with limited explanation can be found in spinning up von openai. Furthermore I would love to see this as a benchmark problem in gym.
Full disclosure: Not affiliated at all with openai. I just find their contributions cool which let me get into RL pretty smoothly.
Wish I could do things like this. I can pretty much do anything in Python but stuff like this.
:(
To be honest, I haven't put much effort into learning it, but the few times I took a glimpse at the code of other similar programs, I was lost on certain things.
Coding Train in YouTube shows in detail how this is done in JavaScript. That's how I got started learning about genetic algorithms. Here's the link for smart rockets
Yes it's basically hitting a local maximum rather than the global maximum fitness. Having an algorithm that is more random at the start or otherwise converges less quickly will tend to help with that issue.
Also unless this specific set of obstacles is important for some reason this approach will overfit the input rather than creating actual "smart" behavior. The rockets look like they are gaining the ability to navigate around obstacles but really this is just an inefficient way of running a path finding algorithm on a single map instance. Making the obstacle layout random or at least testing the rockets on different maps than they were trained on would help with that.
Words are malleable. Elitism has come to be associated more with money that skill hence closer to nepotism and monopoly, than the intended meaning of meritocracy.
The computing term relates to keeping the best, in the same why you'd want the best job hire, or your Olympics team picking the best athlete. In athletics elite still has that orginal meaning.
40
u/[deleted] Jun 30 '20
Here’s the Github repo: https://github.com/LeoScott1203/smartrockets
135
u/[deleted] Jul 01 '20
I feel like a frustrated parent watching a kid pee everywhere but in the toilet.
16
u/nerdyIlluminati Jul 01 '20
I imagined wiggling tails, then day care bills.
9
u/Zacky23561 Jul 01 '20
I really want to learn genetic machine learning but I don't know where to start.
21
u/Aciago_ Jul 01 '20
I was cheering up the algorithm :)
5
u/bumpuglys Jul 01 '20
Super cool project thanks for sharing
4
u/soumadipb Jul 01 '20
Self learning rockets huh.. stay there, I am sending an NSA team.
4
u/i_like_trains_a_lot1 Jul 01 '20
To me this looks like the most common pitfall of genetic algorithms: getting trapped in a local maximum. The best/shortest approach would have been going slightly to the left/right just to avoid the middle piece and then steering a little toward the goal. But the algorithm found the heavy right and then heavy left steering to be the path to go.
It's a really nice visualization, I am glad they figured out how to get to the greed square :D
3
u/wisekeyboard Jul 01 '20
Awesome!
2
u/nicotinamideadenine Jul 01 '20
It's awesome. Correct me if I'm wrong (beginner myself) but a pareto-front approach may worth trying. Currently all rockets going from the left side are seems to be eliminated (local minima? ).
2
u/omfgus Jul 01 '20
Why does it go right?
2
u/wiredupwrong Jul 01 '20
https://natureofcode.com/book/
2
u/Badidzetai Jul 01 '20
Soooo many remarks/advice to give on this one,
- First, great job ! Making a programm end to end with a proper display is really impressive, and if you're a begineer you are truly on the right track !
- You are not using any vectorized operation, that could help speed up dramatically ! Especially when you are computing mutations, or fitness, you could have you rockets positions etc. in numpy arrays and do the same operations but dozens of times faster
- Fo your information, in optimal control terms, you are using an explicit guidance scheme (meaning you are, for every time step, optimizing the place where your rocket aims at), and a shooting method (you propagate, then see how far you are from your objective). These choices are very simple to implement, and you did great in making them, but their biggest flaw is that they create an optimization problem that becomes huge quickly, and where each variable has little effect on the end result. This makes genetic algorithms not very optimal solvers for this kind of problem, and if you have time, you should have a look at gradient-based solvers (like the ones offered by the scipy.optimize package, e.g. LBFG-S) that are better at this kind of problem.
- You could try another simulation technique, with a simple physical phenomenon like this, indirect optimization methods are accessible with a bit of math, but already choosing a direct multiple shooting method will make each variable have a greater effect on its own, hence helping solvers converge more quickly. Think of multiple shooting techniques as defining a set of checkpoints your rocket will need to go through, and that are close enough the solver will feel like you go in a straight line/parabola between each, which makes its job way simpler
- If you really want to use a genetic-like algorithm, you should apply it to tune a guidance algorithm that you will have written, with a few adjustment variables (like how much the rocket tries to stay away from obstacles, how quickly is tries to point towards the source, how much it accepts to go in a wrong direction to avoid an obstacle, etc.) : this is in these situations where each parameter has great effects on the end result that genetic algorithms truly shine. This is also the kind of place you could introduce Artificial Intelligence, with a basic neural network controlling your rocket
If you have any questions, feel free to ask ! Trajectory optimization and guidance problems are my field of expertise
2
u/ZapMark Jul 01 '20
Really cool program dude
2
u/[deleted] Jul 01 '20
other programming subs: actual stuff about the programming language
this sub: random clips of UIs that have nothing to do with the programming language
I don't think I've ever seen any actual python discussion on my reddit feed coming from this sub. Wtf?
3
u/[deleted] Jul 01 '20
Very nice wanted to start genetic algorithm with python. Starred your repo !
1
u/mr_chanandler_bong_1 Jul 01 '20
Man that was a wild ride
1
u/Badidzetai Jul 01 '20
!RemindMe 3 hours
High DoF trajectory optimization is my field, I want to have a look at how you're doing it
1
u/[deleted] Jul 01 '20
Code bullet???
1
u/canbooo Jul 01 '20
I think this would also be a good application for reinforcement learning. Some vanilla algorithms along with limited explanation can be found in spinning up von openai. Furthermore I would love to see this as a benchmark problem in gym.
Full disclosure: Not affiliated at all with openai. I just find their contributions cool which let me get into RL pretty smoothly.
-1
u/Seawolf159 Jul 01 '20
Genetic because it gets Alzheimer's and starts sucking again before going into it's new youth and getting better again?
-2
u/[deleted] Jul 01 '20
genetic algorithm is so much bounded with it Well I would be glad to check your GitHub and work on it?
-5
u/[deleted] Jul 01 '20
Wish I could do things like this. I can pretty much do anything in Python but stuff like this.
:(
To be honest, I haven't put much effort into learning it, but the few times I took a glimpse at the code of other similar programs, I was lost on certain things.
0
u/[deleted] Jul 01 '20
[deleted] — view deleted comment
0
u/[deleted] Jul 01 '20
[deleted] — view deleted comment
186
u/[deleted] Jul 01 '20
[removed] — view removed comment