4 ms·

None of the animations show a successful parking manoeuvre, because the code is unable, after 40 generations, to produce a car that actually successfully parks

by mrb 5y ago

None of the animations show a successful parking manoeuvre, because the code is unable, after 40 generations, to produce a car that actually successfully parks itself. How long does it take to go through 40, 80, 120 generations?

diskzero 5y ago
Probably longer than most would find acceptable! I did some work with genetic algorithms about twenty years ago and the author mentions some of the optimizations that could be done to improve performance.
timr 5y ago
There's no fixed answer, because "a genetic algorithm" is not one thing -- it's an optimization process, and the details of how you model your problem matter at least as much as (if not more than) the optimization process you use. In this case, the mapping of a complicated multi-step process involving external constraints to a "gene" is going to be a hack, no matter what you do.
- SavantIdiot 5y ago
  Genetic algorithms work well in some circumstances, I recall that multi-band antenna design technology experienced a step-function boost in the 90's due to application of GA principles, which helped the cellphone market boom. (I could be mixing up two IEEE articles in memory.) I think calling it a "hack" misses the nuance: mapping the physical metrics and telemetry into a genome is nontrivial. Plus 40 generations is no where NEAR enough. A GA needs millions (or billions) of generations to avoid local minima/maxima. Especially given the size of the input vector. His vector is what, 2^100 states?
  - timr 5y ago
    GAs are great. Love 'em. Same with monte carlo -- too many people dismiss these approaches and get mired in gradient-based optimization (which is far harder, more expensive, and often doesn't work any better). There should just be a rule that you have to try linear regression before building a neural network, and GA/MCSA before doing gradient optimization. > I think calling it a "hack" misses the nuance: mapping the physical metrics and telemetry into a genome is nontrivial. Well, that's definitely what I was trying to say, so we're agreed. I actually don't think GA a great fit for this problem as parking a car is a time- and circumstance-dependent process, and a fixed gene is...not. But that's a guess.
    - SavantIdiot 5y ago
      > I actually don't think GA a great fit for this problem as parking a car is a time- and circumstance-dependent process, and a fixed gene is...not. But that's a guess. Oh definitely not! :)
    - catillac 5y ago
      Is Monte Carlo approach (versus a gradient based approach) basically trying a bunch of different things until something works, or is it more nuanced than that (perhaps with intelligent optimization of what to try next?)?
      - YeGoblynQueenne 5y ago
        Monte Carlo is basically taking repeated random samples until you get a good approximation of the value you're interested in. Gradient descent is more like what you describe, except you don't try "a bunch of different things" but keep trying the same thing until you have a result you think is good. To give a silly example, Monte Carlo is like trying to guess the surface area of a dartboard by throwing darts at it and counting how many hit it, while gradient descent is like throwing darts at the board until you hit the center (or something you think is the center).
gowld 5y ago
Headline is misleading. It's "Failing to make a Self-Parking Car in 500 lines of code"
- nqzero 5y ago
  maybe they used a genetic algorithm to generate the headline
- cjohansson 5y ago
  Maybe you need to wait 9183718 generations before it suceeds? Like I do a random code generator in 10 lines and say it can solve any problem in the world if you wait long enough
  - a1369209993 5y ago
    > Maybe you need to wait 9183718 generations before it suceeds? Assuming you can actually detect success, that's not really that big of a problem. You can do it in 11 lines by appending: for(i in 1e7){g=do-generation(g);if(worksp(g)) return g} It'll take while, but the claim is that it optimises on lines, not on runtime.

by mrb 5y ago

diskzero 5y ago

Probably longer than most would find acceptable! I did some work with genetic algorithms about twenty years ago and the author mentions some of the optimizations that could be done to improve performance.

timr 5y ago

There's no fixed answer, because "a genetic algorithm" is not one thing -- it's an optimization process, and the details of how you model your problem matter at least as much as (if not more than) the optimization process you use. In this case, the mapping of a complicated multi-step process involving external constraints to a "gene" is going to be a hack, no matter what you do.

SavantIdiot 5y ago
Genetic algorithms work well in some circumstances, I recall that multi-band antenna design technology experienced a step-function boost in the 90's due to application of GA principles, which helped the cellphone market boom. (I could be mixing up two IEEE articles in memory.) I think calling it a "hack" misses the nuance: mapping the physical metrics and telemetry into a genome is nontrivial. Plus 40 generations is no where NEAR enough. A GA needs millions (or billions) of generations to avoid local minima/maxima. Especially given the size of the input vector. His vector is what, 2^100 states?
- timr 5y ago
  GAs are great. Love 'em. Same with monte carlo -- too many people dismiss these approaches and get mired in gradient-based optimization (which is far harder, more expensive, and often doesn't work any better). There should just be a rule that you have to try linear regression before building a neural network, and GA/MCSA before doing gradient optimization. > I think calling it a "hack" misses the nuance: mapping the physical metrics and telemetry into a genome is nontrivial. Well, that's definitely what I was trying to say, so we're agreed. I actually don't think GA a great fit for this problem as parking a car is a time- and circumstance-dependent process, and a fixed gene is...not. But that's a guess.
  - SavantIdiot 5y ago
    > I actually don't think GA a great fit for this problem as parking a car is a time- and circumstance-dependent process, and a fixed gene is...not. But that's a guess. Oh definitely not! :)
  - catillac 5y ago
    Is Monte Carlo approach (versus a gradient based approach) basically trying a bunch of different things until something works, or is it more nuanced than that (perhaps with intelligent optimization of what to try next?)?
    - YeGoblynQueenne 5y ago
      Monte Carlo is basically taking repeated random samples until you get a good approximation of the value you're interested in. Gradient descent is more like what you describe, except you don't try "a bunch of different things" but keep trying the same thing until you have a result you think is good. To give a silly example, Monte Carlo is like trying to guess the surface area of a dartboard by throwing darts at it and counting how many hit it, while gradient descent is like throwing darts at the board until you hit the center (or something you think is the center).

gowld 5y ago

Headline is misleading. It's "Failing to make a Self-Parking Car in 500 lines of code"

nqzero 5y ago
maybe they used a genetic algorithm to generate the headline
cjohansson 5y ago
Maybe you need to wait 9183718 generations before it suceeds? Like I do a random code generator in 10 lines and say it can solve any problem in the world if you wait long enough
- a1369209993 5y ago
  > Maybe you need to wait 9183718 generations before it suceeds? Assuming you can actually detect success, that's not really that big of a problem. You can do it in 11 lines by appending: for(i in 1e7){g=do-generation(g);if(worksp(g)) return g} It'll take while, but the claim is that it optimises on lines, not on runtime.