I've written a genetic algorithm and in an attempt to optimize its performance, I decided to parallelize the fitness testing for individuals. To see what kind of change this made in my algorithm, I redid a test run I had done before the parallelization where I tested the GA's performance for growing population sizes.

The parallel version of the GA actually took roughly 50% longer than the original version. I realize that sometimes the overhead of the parallelization can actually take more time than it saves, but I doubt that that should apply in this situation - my fitness test is finding the global minimum of a Sheckel's Foxholes function ( <http://extreme.adorio-research.org/download/mvf/html/node51.html> ), and my population sizes range from 10 to 1000. I would expect that in parallelizing 1000 executions of sheckel's foxholes the time saved would greatly outweigh the overhead of parallelization.

So my question is: why would the parallelization have slowed down the algorithm (and so significantly)?

For the record, I'm coding in Java and I'm parallelizing using a CountDownLatch that waits for all threads (fitness tests) to execute before continuing on.