Multiple-deme parallel estimation of distribution algorithms: Basic framework and application

Abstract

This paper presents a basic framework that facilitates the development of new multiple-deme parallel estimation of distribution algorithms (PEDAs). The aim is to carry over the migration effect that arises in multiple-deme parallel genetic algorithms (PGAs) into probability distribution of EDAs. The idea is to employ two kinds of probability vector (PV): one each for resident and immigrant candidates. The distribution of crossbred individuals (that virtually exist on both kinds of PV) is then utilized by a new type of crossover, the PV-wise crossover. A multiple-deme parallel population-based incremental learning ((PBIL)-B-2) scheme is proposed as an application. The (PBIL)-B-2 scheme closely follows the proposed framework that includes a new learning strategy (i.e., PV update rule). Experimental results show that (PBIL)-B-2 generally exhibits solutions that compare favourably with those computed by an existing PGA with multiple demes, thereby supporting the validity of the proposed framework for designing multiple-deme PEDAs.