[SciPy-Dev] Robert Kern's accursed excellent DE implementation

[James Phillips]

If you look in the file _differentialevolution.py, there is a comment

# do the optimisation.

at the top of the per-generation loop.  It is inside this loop that each
generation is processed.  As processing of each generation progresses
within this loop, the population ia modified - that is, mutation is using a
population that changes while the generation is running.

To parallelize this loop, the creation of the trial items (crossover) must
be independent of modifying the changes to the population from which the
new trials are drawn.

So it looks like this loop must be run seriallyin order to modify the
population in-place, and cannot be parallelized to yield identical results
between serial and parallel versions.  Based on my experience, it will have
quite superior performance compared to a version that is made suitable for
parallelization but run serially.

James


On Wed, Mar 25, 2015 at 4:16 AM, James Phillips <zunzun at zunzun.com> wrote:

> I just had a cup of coffee and downloaded the 0.15.1 source, investigating
> now.
>
> James
>
> On Wed, Mar 25, 2015 at 3:50 AM, Andrew Nelson <andyfaff at gmail.com> wrote:
>
>> Scipy 0.15 now has a (serial) DE implementation. I'd be interested to now
>> how the two implementations compare in terms of total number of function
>> evaluations. There are a few papers out there that discuss parallel DE, but
>> I can't remember where they were. I'd be interested to know how easy it is
>> to parallelise function evaluations in scipy. I'm guessing cython and
>> openmp might be a way to go. It's a pity that clang doesn't have openmp.
>> On 25/03/2015 6:00 AM, "James Phillips" <zunzun at zunzun.com> wrote:
>>
>>> I have been using Robert Kern's implementation of the Differential
>>> Evolution (DE) genetic algorithm for a decade, for the purpose of
>>> guessimating initial parameter estimates for curve fitting and surface
>>> fitting in my oprn source pyeq2 fitting library.
>>>
>>> I can't find anything that works better, which gives rise to my current
>>> problem.
>>>
>>> In trying to improve performance of my fitting library, I tried to use
>>> GPU calculations for each generation of the genetic algorithm, I found the
>>> following:
>>>
>>> 1) Robert's 2005 implementation of DE is not parallelizeable, as each
>>> crossover withing a generation can affect the population from which new
>>> items will be created.  That is, within a given generation the population
>>> *changes* as the algorithm runs the generation itself, and it must run
>>> serially in it's present form.
>>>
>>> 2) I can rework the algorithm to be parallelizeable by separating out
>>> "crossover", "breeding" and "evolving" into three separate steps, but
>>> months of testing show that population size and number of generations must
>>> beconsiderably  increased to match the results from Robert's version.  That
>>> is, making the algorithm parallelizable means slowing it down so I can
>>> speed it up!
>>>
>>> I would like to increase performance, but cannot find any way to equal
>>> Robert's results without reducing performance prior to parallelization.
>>>
>>> Any suggestions?
>>>
>>> James
>>>
>>> _______________________________________________
>>> SciPy-Dev mailing list
>>> SciPy-Dev at scipy.org
>>> http://mail.scipy.org/mailman/listinfo/scipy-dev
>>>
>>>
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20150325/6591fb17/attachment.html>