4
$\begingroup$

I have different metaheuristics (Tabu search, Simulated annealing, Iterated local search) solving an optimization problem (a variant of the resource-constrained project scheduling problem). Each metaheuristic is implemented separately in Python.

I want to make an "island model" i.e to run them in parallel with the possibility of handing high-quality solutions to one another i.e keeping track of the best-found solution among all the metaheuristics. If a new higher quality solution using some metaheuristic, every other metaheuristic will then restart from that solution. I am not sure it's the right term

I would be grateful if you could guide me on how to do it. I hope I will not need to re-implement everything from scratch.

Another question: Is there a risk of implementing a "fancy thing" that could be useless? If so, how to figure out in advance if the parallelization will be useful.

P.S: I don't have any knowledge about parallel methods, except for knowing the term "island model" =).

Improve this question
$\endgroup$
3
$\begingroup$

The easiest way is to use the Python multiprocessing module (or similar). You can create a pool of parallel workers, each of which would run a different heuristic. The multiprocessing toolbox also allows you to pass messages between processes, which you can use to communicate information among them (e.g., solution vectors).

In order to do that you would need synchronization points inside your heuristics, i.e., "checkpoints" where each worker requests information from a manager process. If no new information is available in the message it receives, it keeps calculating as normal, and if there's new information it does stuff.

The cleanest design is to have a dedicated process as the manager, and that process will be responsible for all communication between workers. Workers should only be able to communicate with the manager, and not with each other. This design pattern is crucial for good scaling and avoiding deadlocks & bottlenecks.

Be warned though that parallel computing is hard and full of quirks and subtle edge cases, even in Python. Always implement the bare minimum of the functionality you need. Test, test, test, and if it works for you, you're done. Complexity is your greatest enemy here because debugging becomes rapidly intractable in complicated parallel code.

My advice would be to consistently test everything, even syntax that "surely" does what you think it should - in parallel it rarely does, especially in Python.

W.r.t. your second question, yes, definitely. Parallel code is very time consuming, so unless there is a clear need for it, you probably shouldn't do it. Some indicators that it might work for you are:

  • There are numerous independent steps in your algorithm that take roughly the same time.
  • If your tasks differ by too much in execution time you need asynchronous parallel code which is much more complicated.
  • If you have one expensive chunk of calculations and everything else is cheap by comparison, you will not see benefits.
  • The application actually "needs" more speed. If it doesn't you need to make a business case to your boss about why this quality of life feature is something they should be spending money on.

Finally, keep in mind that you can simply run the same Python script multiple times with different inputs as background processes, and the OS will run them in parallel if you have enough cores.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for this detailed answer. I am a little bit confused though. I thought the parallelization has not only a "speed" benefit but also improves the solution quality by making high-quality solutions shareable. Maybe I am missing something here. Is there another way to run the different heuristics at the same time while sharing the best-found solution in such a way that, each time a new higher quality solution is found using some metaheuristic, every other metaheuristic will then restart from that solution? $\endgroup$ – Antarctica Jul 20 '20 at 14:30
  • $\begingroup$ @AmiraZarglayoun It can, if you design it that way. In that case you will need code to pass that information to your workers when it becomes available, and the workers need code to always be expecting such a message. Usually that's done by having a separate thread in a while loop in the worker that keeps pinging the master for updates. Remember, in multiprocessing no process knows what's happening in other processes until you specifically send that information to the relevant process. $\endgroup$ – Nikos Kazazakis Jul 20 '20 at 14:34
  • $\begingroup$ But this is exactly a sort of parallelization. If so, is there another way (i.e, other than parallelization) that can do this? $\endgroup$ – Antarctica Jul 20 '20 at 14:37
  • $\begingroup$ @AmiraZarglayoun Nope. A much simpler way to do that same thing though is by running the same serial scripts many times as background processes and writing to files & a master bash/Python script for synchronization. $\endgroup$ – Nikos Kazazakis Jul 20 '20 at 14:43
  • $\begingroup$ Ok got it. Does it have a name? Ho to google it to look for some code examples? $\endgroup$ – Antarctica Jul 20 '20 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.