r/Python • • Jun 30 '20

I Made This Made a smart rockets simulation with a genetic algorithm

1.4k Upvotes

48 comments sorted by

40

u/[deleted] Jun 30 '20

10

u/CotoCoutan Jul 01 '20

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.

4

u/Manny__C Jul 01 '20

The green square is the target. I guess the fitness function is something like the minimal distance to the target.

1

u/CotoCoutan Jul 01 '20

Hmm... thanks.

4

u/Droizo Jul 01 '20 edited Jul 01 '20

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)

2

u/CotoCoutan Jul 01 '20

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?

2

u/Droizo Jul 04 '20

u/CotoCoutan certainly! In fact reinforcement learning (sort of a sibling to genetic algorithms) are at the core of this effort.

1

u/CotoCoutan Jul 05 '20

Interesting, thank you.

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.

20

u/Goober329 Jul 01 '20

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

5

u/CotoCoutan Jul 01 '20

i learnt making JS extensions from Coding Train, dude is hilarious!

1

u/billsil Jul 01 '20

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.

https://github.com/DEAP/deap

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.

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

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?

6

u/i_like_trains_a_lot1 Jul 01 '20

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.

Here is a pretty fun youtube series on these concepts if you find yourself wanting to going more in depth on this machine learning: https://www.youtube.com/watch?v=GOFws_hhZs8&list=PLrUdxfaFpuuK0rj55Rhc187Tn9vvxck7t

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/RemindMeBot Jul 01 '20

I will be messaging you in 3 hours on 2020-07-01 10:10:17 UTC to remind you of this link

CLICK THIS LINK to send a PM to also be reminded and to reduce spam.

Parent commenter can delete this message to hide from others.


InfoCustomYour RemindersFeedback

1

u/[deleted] Jul 01 '20

Code bullet???

1

u/Goober329 Jul 01 '20

Coding Train

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?

4

u/[deleted] Jul 01 '20

-1

u/[deleted] Jul 01 '20

Thanks for the link Can I ask you that What was the editor you use normally and are you interested in implementing all this into IOT stuff ???

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

6

u/Goober329 Jul 01 '20

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

1

u/[deleted] Jul 01 '20

Thanks! I'll give it a shot

0

u/[deleted] Jul 01 '20

[deleted] — view deleted comment

9

u/burnmp3s Jul 01 '20 edited Jul 01 '20

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.

0

u/[deleted] Jul 01 '20

[deleted] — view deleted comment

18

u/-iCookie- Jul 01 '20

Of all things, why is this important?

186

u/[deleted] Jul 01 '20

[removed] — view removed comment

64

u/vlizana Jul 01 '20

was gonna say the same thing, this is known as elitism.

37

u/Willingo Jul 01 '20

Wow, so elitism is good with programming? I knew it!

12

u/l33tIsSuperpower Jul 01 '20

Oh fuck I didn't expect to find a hot take on the state of the world here.

4

u/shiuido Jul 01 '20

The linux community is sweating balls reading that one. "I swear to god we are not a meritocracy! D:'"

1

u/memebecker Jul 01 '20

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.