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.
Speed test: Genetic Algo vs Brute Force
- Thread starter psheridan050
- Start date
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
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
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...
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.
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.
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?
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.
https://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf as i read it claims there is no difference over the entire space of optimization problems.