Performance Tweaks (PLINQ/TPL) to Genetic Algorithm

[codingdna2]

FEATURE REQUEST (Optimization) I've completed a bunch of performance tests on a scheduling algorithm implemented with GeneticSharp. Following are my findings.

I've used PLINQ/TPL to try to improve performance here and there. Following are my results:

• ParallelTaskExecutor.Start, changed loop to Parallel.For, removing the Task.Run RESULT: +2%
• GeneticAlgorithm.Cross, GeneticAlgorithm.Mutate, changed loop to Parallel.ForEach (see PR) and used ConcurrentBag RESULT: +80% +110%

Additional context I didn't like too much the actual implementation of ParallelTaskExecutor due to the need of sizing the min and max threads manually. If I understand well, Parallel class use a default (automatic) partitioner which can be customized if required (maybe even through the external interface?).

Let me know what you think. Kind Regards,

References MSDN Parallel Class MSDN Custom Partitioners for PLINQ and TPL

[codingdna2]

A deeper analysis is probably necessary to distinguish various scenarios (population generation cost, fitness cost, population size, ...) in order to release it as an optimization. Perhaps a way for the user to opt in (as it is now the ParallelTaskExecutor) would be more appropriate.

[giacomelli]

I agree, maybe you could create a whole new class called TplTaskExecutor, then the user can opt to use it or ParallelTaskExecutor or LinearTaskExecutor.

What do you think?

56

[codingdna2]

Most of the improvement was made in the generation/crossover/mutation loops which are in the GeneticAlgorithm, in Task Executor and in the Population.

Task Executor and Population already have their own interface and we can implement a TplTaskExecutor and a TplPopulation.

I guess we need to implement an additional interface like ICoreExecutor (feel free to suggest a better name), where to move cross and mutate methods.

Then as you suggest we can have LinearCoreExecutor and TplCoreExecutor. Thoughts?

[giacomelli]

I agree with the TplTaskExecutor and TplPopulation.

In the case of cross and mutation methods, I think you can use the same pattern that Population class use to perform some generation behaviors. It's represented on IGenerationStrategy (Strategy Pattern) and is implemented in PerformanceGenerationStrategy and TrackingGenerationStrategy classes.

We can define a new interface called IOperatorsStrategy with, initially, two methods:

• IList Cross(IList parents)
• void Mutate(IList chromosomes)

Then add a public writable property to the GenectiAlgorithm class to set what strategy we will use:

• DefaultOperatorsStrategy
• TplOperatorsStrategy

After that, you just need to change the GeneticAlgorithms' Cross e Mutate methods to call the correspondent one on the strategy implementation.

Thoughts?

[giacomelli]

It's in develop branch.