Seminar za primenjenu matematiku, 13. mart 2012.

Naredni sastanak Seminara za primenjenu matematiku održaće se u utorak, 13. marta 2012. u 14:15, sobi 301f, MI SANU.

Predavač: Tatjana Jakšić, Matematički institut SANU


Sadržaj: The Bee Colony Optimization (BCO) algorithm is a meta--heuristic that belongs to the class of biologically inspired stochastic swarm optimization methods, based on the foraging habits of bees in nature. BCO operates on a population of solutions, and therefore we expect it to represent a good basis for parallelization. The main contribution of this work is the development of new and more efficient parallelization strategies for BCO. We propose two synchronous and two asynchronous parallelization strategies for a distributed memory multiprocessor architecture under the Message Passing Interface (MPI) communication protocol. The first synchronous strategy involves independent execution of several BCO algorithms, while the second one implements cooperation between these algorithms. The asynchronous strategies are implemented in two ways: with centralized and with non-centralized communication control. The presented experimental results, addressing the problem of static scheduling independent tasks on identical machines, show that our parallel BCO algorithms provide excellent performance. As for the case of independent execution, we obtain significant speedup while preserving the solution quality. Cooperative strategy leads to obtaining better quality solutions within the same amount of wall--clock time, as long as it is applied to a modest number of processors engaged in parallel BCO execution. As this number increases, asynchronous strategies outperform the other ones with respect to both solution quality and running time.

Joint work with T. Davidović, D. Ramljak, M. Šelmić and D. Teodorović

Ostavite vaš komentar:

(nece biti prikazano)