subpopulations and parallel processing in ga

Hey everybody, I am having a problem with running ga using subpopulations and I found the same questionn here asked by Fred but not really answered by anyonehttps://de.mathworks.com/matlabcentral/answers/345905-genetic-algorithm-and-parallel-processing

I wonder why there is an option to specify subpopulations in ga if it does not bring any benefit? Is there any possibility to enable parallel processing with subpopulations in ga ?

Many Thanks

Qi

Answer 1

[Walter Roberson]

If you find toolbox/globaloptim/globaloptim/ (which is where ga.m lives) and look inside private/ then there is a migrate.m that only takes effect for non-scalar populations. It is called from galincon() for ga with linear constraints; called by gaunc() for ga with no constraints; by gamultiobjsolve() for gamultiobj. If there are nonlinear constraints then gacon() ends up creating subproblems and calling galincon() or gaunc()

It is possible that there are combinations of conditions under which migrate() does not end up getting called.

migrate() does not invoke any Parallel Computing. What it does is examine cells of population data and move some entries between cells. Then until the next migration phase, each of those populations evolves independently of each other -- but not in separate workers (processes.)

I do not know why the documentation appears to imply that migration does not take place or that the migration options have no effect. It is possible that the documentation is out of date.

Answer 2

[Stephan]

Hi,

we do find the same note as in the question you referred to, in the R2018b documentation here:

"...Subpopulations refer to a form of parallel processing for the genetic algorithm. ga currently does not support this form. In subpopulations, each worker hosts a number of individuals. These individuals are a subpopulation. The worker evolves the subpopulation independently of other workers, except when migration causes some individuals to travel between workers.

Because ga does not currently support this form of parallel processing, there is no benefit to setting PopulationSize to a vector, or to setting the MigrationDirection, MigrationInterval, or MigrationFraction options..."

Maybe TMW plans to introduce this feature in a future release - we can not know and they wont tell us i guess.

For the moment you can only use the following informations / features regarding parallel computation in ga:

"...ga computes the objective function and nonlinear constraint values of the individuals in a population in parallel...Even when running in parallel, ga occasionally calls the fitness and nonlinear constraint functions serially on the host machine. Therefore, ensure that your functions have no assumptions about whether they are evaluated in serial or parallel..."

You find informations related to this topic here:

https://de.mathworks.com/help/gads/how-to-use-parallel-processing.html

https://de.mathworks.com/help/gads/how-solvers-compute-in-parallel.html

This is what you can expect at the moment regarding the parallel computations in ga.

To make it short:

It is said clearly:

"...there is no benefit to setting PopulationSize to a vector, or to setting the MigrationDirection, MigrationInterval, or MigrationFraction options..."

Best regards

Stephan

[Qi Liu]

Hi Stephan:

Thank you for answering my question. But I wonder if there is any possibility to enable this feature by defining my own specifications/ functions in like my custom creation function. Since on one side it is possible to at least generate subpopulations by vectorizing the population size, and on the other side parallel processing is availble in ga.

Best regrards

Qi

[Stephan]

As far as ii understand the documentation the creation function is only responsible for creating the initial population. There are some discussions regarding custom functions here - as far as i have seen it is not a good idea to do so. Just search a bit here - especially Alan Weiss gave interesting answers.

Did you consider to write your function in a way that it is vectorized and use this option for speeding up calculations? Another way to speed up beginning with R2018b is surrogate optimization.

[Qi Liu]

yes, I already considered "Vectorize and Parallel Options". And it works pretty much very good. But I still want to improve my optimization process further. I want to try the feature "Migration". Because I read a book in which the autor proved that a Migration between subpopulations siginificantly improved the optimization result of his problem.

[Stephan]

Normally - after reading the documentation i would say:

I do not recognize a contradiction. The specification of a vector for population size is possible. This leads to subpopulations, which then use migration. The migration behavior is controllable. All these things are described in the documentation and should work accordingly. Only the parallel calculation is not supported. So I do not know why that should not be possible. If the performance with vectorization is satisfactory for you, there should be no problems in this way.

But there is this one statement:

"...there is no benefit to setting PopulationSize to a vector, or to setting the MigrationDirection, MigrationInterval, or MigrationFraction options..."

followed from a descripton how to deal with Migration.

This is confusing for me and instead i ask:

Or do you think that the behavior completely depends on the parallel calculation? Then it would be rather strange to describe the options in the documentation in detail.

Conclusion:

I hope that Alan or Walter reads this thread and adds something enlightening to it.

--> Is there a way to take advantage of Migration using ga currently???

[Qi Liu]

My Conclusion is that the migration in ga in matlab for now is not the "true migration".

This statement (in the doc) "Subpopulations refer to a form of parallel processing for the genetic algorithm. ga currently does not support this form." As far as I understand, "this form" means that ga parallelly processes subpopulations which shoud be evolved truely separately and simultaneously as long as the ga is running and their individuals migrate to each other every now and then (just like asia and europe). And it actually could be called as parallel ga.

I think parallel calculation is supported in ga, but only in the form "parallel calculation of individuals in same population/subpopulation" NOT In the form "parallel calculation of subpopulations".

And my interpretation to the statement "...there is no benefit to setting PopulationSize to a vector, or to setting the MigrationDirection, MigrationInterval, or MigrationFraction options..." is that the subpopulations generated by only setting PopulationSize to a vector are not true subpopulations, since they are not evolved parallely/ simultaneously.

I hope I did not cause more confusion.

[Alan Weiss]

I can confirm that your latest reading of the documentation is correct. I tried to be crystal clear that there is no reason to use subpopulations in ga, it was a feature that was planned but never implemented. So the options are there to support it, but not the software.

Alan Weiss

MATLAB mathematical toolbox documentation

[Qi Liu]

what is the reason that this feature was planned but not implemented?

Is there any possibility to enable this feature by myself?

Many thanks

Qi

[Walter Roberson]

? The appropriate functions already have calls to migrate() in them. I did not see anything obvious that would turn off those calls, so it looks to me as if it is implemented ??

[Alan Weiss]

Implemented, sort of, but not in parallel, which is the main reason to use subpopulations.

Qi Liu, if you want to rewrite the code to perform in parallel, well, the code is there for you to see and modify as you please. But I can tell you that it is unlikely to be a worthwhile investment of your time. In fact, I rarely find it worthwhile to use ga for any reason except nonlinear mixed-integer programming in small dimensions. You would almost always be better off using Optimization Toolbox™ functions for smooth optimization problems, possibly with MultiStart for searching for a global solution, or using patternsearch for nonsmooth problems.

Alan Weiss

MATLAB mathematical toolbox documentation