Population-based quasi-Bayesian algorithm for high-dimensional sequential problems and hierarchization of it for distributed computing environments

The merging particle filter (MPF) is a population-based quasi-Bayesian algorithm for solving sequential Bayesian problems. The MPF algorithm at each time step consists of three procedures: evaluation of fitness to observation, selection of samples in the population, and merging among multiple samples. The MPF has a certain similarity to evolutionary algorithms except that it is based on Bayesian approach and it provides a posterior probability density function rather than a optimum value. Population-based algorithms including the MPF is easy to implement on parallel computing systems. However, when we implement the MPF in a parallel computing system, much communication occurs between processing elements (PEs) and it could spoil the computational efficiency. In order to reduce the communication between PEs, we propose a bi-level hierarchical algorithm in which the MPF is locally performed in each PE and and communication between different PEs are treated separately. Although this hierarchical algorithm is similar to the island model in the genetic algorithm, it is derived on the basis of the Bayesian framework. We also confirm the efficiency of the proposed algorithm by an experiment of state estimation with a simple one-dimensional system model.