Speed test: Genetic Algo vs Brute Force

Discussion in 'Automated Trading' started by psheridan050, Jun 17, 2008.

  1. I was wondering if it is possible to measure how much faster a genetic algorithm is compared to something like brute force optimization. Is there a ratio or approximate ratio of one compared to the other in terms of speed? Going along with this same type of thinking, is there a way to get an idea of how fast a computer processor can crunch these types of numbers? For example, take a fast computer with an Intel QX9650 3.0 GHz and 8 Gb of memory running Microsoft Vista and optimizing a strategy that contains 70,200,000 combinations of inputs. Is there a math formula that would help compare the two types of optimization techniques? I realize that there probably isn’t a way to get an exact figure, but an approximation would be helpful.
     
  2. you could try to find a relationship empirically. Start with a small data set,
    calculate the number of permutations of the dataset and the time it took to converge to an acceptable sample distribution of the statistic you are optimizing (could take all possible permutations as benchmark, but that would probably take way too long). Then run a GA optimization on the same data set. Measure the time it took to settle to a solution (note that GA may not be optimal as it may be in local min, whereas large permutation gives better feel for optimal min).

    Keep increasing the data set size, and plot a graph of the size of the data set vs. time to run complete (or statisically acceptable) permutations, overlaid with avg. time to GA convergence for the data set.

    Should give you an empirical feel.
    You could get the slope of the two results and take a ratio.

    My guess would be a log relationship, as the GA algorithm cuts down time dramatically as the sample size becomes larger.

    Hitting the sack... but there's a paper on this if you can get it--

    http://www.sciencedirect.com/scienc...serid=10&md5=1413008b8433c1aa91d6172954b598fb
     
  3. Corey

    Corey

    Well, it really depends on the fitness function. But considering genetic algorithms are essentially <a href="http://en.wikipedia.org/wiki/Randomized_algorithm">Randomized Algorithms</a>, to an extent, I am sure you could formulate a proof as to exactly how much faster you will approach an answer than a brute-force method...
     
  4. Hi psheridan050,

    MultiCharts has a built-in genetic optimizer, so I have asked the developers to have a look at the code and give you the results.

    MultiCharts supports two GA optimization methods: simple and incremental.


    Simple GA:
    Input combinations: 70200000

    Population size: 1286

    Generation count: 1286

    Strategy recalculations: 826898

    Incremental GA:
    Input combinations: 70200000

    Population size: 407

    Generation count: 40648

    Strategies recalculations: 81703



    I can't guarantee, though, that the above results are 100% accurate. It'll be easier for you to check it MultiCharts yourself.
     
  5. Yes.

    Along with the fitness...

    It depends. If you are confident with a single fitness or trying to work around a single fitness... then it would be fine.

    If you are out for a rather different approach, GA or others will not be as quite as suitable.
     
  6. chvid

    chvid

    It depends on the fitness landscape.

    Genetic algorithms works because the algorithm has elements of hill-climbing in it.

    So for it to work the fitness landscape has to have "hills" in it.

    For complete general problems genetic algorithms are not faster than random search.
     
  7. It looks like from your posts, the speed of a genetic algo can vary. So what about Brute Force? Is there a way to calculate the amount of time it would take for a test to complete with the chip and memory given above?
     
  8. Yes.

    But you never know until you've ran some optimizations...
    And, of course, by the time you put it live, the topology has shifted.