David,how to aviod this defect by evolutionary solver

i have read your new blog of evolutionary solver,so i make a experiment to show the defects,you can see all in my blog here

do you have any idea to avoid this defect when using evolutianry solver？thank you.

Replies to This Discussion

Permalink Reply by David Rutten on October 27, 2013 at 8:19pm

Hi Andrea,

your fitness landscape is not continuous. You artificially inject an incredibly high peak at a single value and nothing in the vicinity of that value suggests that there is a peak nearby. A stochastic solver will never be able to find such solutions unless it gets very very lucky and just happens to stumble upon it.

You've made a one-dimensional phase space with a slider that varies between 0.0 and Pi and has 6 decimal places. This means your slider can take on 3,141,593 different values (1million x Pi).

A brute force search of this range (assuming a single iteration takes 5 milliseconds) would take nearly 4 and a half hours. If you had a two-dimensional phase space with two such sliders, you'd have to brute force your way not just through every possible slider value, but every possible slider permutation. In effect, (1million x Pi)² x 5ms = ~1,500 years. This is why Brute Force search is a very unpopular search algorithm.

Galapagos has logic build in which prevents it from 'stepping' on the same spot twice. In effect, if you let it run long enough it starts to act as a brute force solver, but given the huge number of possible places to step in these examples, I wouldn't want to have to wait for it to find 0.600001

David Rutten

david@mcneel.com

Seattle, WA

Permalink Reply by David Rutten on October 27, 2013 at 8:25pm

To answer your question on how to avoid this problem; you have to come up with a fitness function that is reasonably continuous. It doesn't have to be continuous everywhere, but too many discontinuities or two discontinuities very close together that 'hide' a peak will cause problems.

Sometimes it is not possible to formulate a fitness function that will work. Perhaps your inputs do not allow for a continuous mapping between variables and fitness. In that case you will not be able to use a stochastic solver.

The problem you posted it not a good example because it is not a real problem. It looks specifically designed to be unsolvable.

David Rutten

david@mcneel.com

Seattle, WA

Permalink Reply by Andrea Lu on October 27, 2013 at 8:40pm