The adoption of probabilistic models for the best individuals found so far is a powerful approach for evolutionary computation. Increasingly more complex models have been used by estimation of distribution algorithms (EDAs), which often result better effectiveness on finding the global optima for hard optimization problems. Supervised and unsupervised learning of Bayesian networks are very effective options, since those models are able to capture interactions of high order among the variables of a problem. Diversity preservation, through niching techniques, has also shown to be very important to allow the identification of the problem structure as much as for keeping several global optima. Recently, clustering was evaluated as an effective niching technique for EDAs, but the performance of simpler low-order EDAs was not shown to be much improved by clustering, except for some simple multimodal problems. This work proposes and evaluates a combination operator guided by a measure from information theory which allows a clustered low-order EDA to effectively solve a comprehensive range of benchmark optimization problems.
It was already shown that clustering improves the performance of some EDAs for certain classes of problems. For globally multimodal problems, for instance, clustering has revealed a promising approach @cite_1 . Such problems present several global optima or, in other words, several optimal solutions with the same fitness. Those problems may be very tricky for an evolutionary algorithm to solve, since slow convergence to one of the optima (genetic drift) often occurs. The retarded convergence is explained by the combination of solutions coming from different regions of the search space, which often results in poor solutions. The application of clustering in EDAs when solving globally multimodal problems can be described as the separation of the population in subpopulations (one for each cluster), and the subsequent learning of different probabilistic models for each subpopulation. Breeding generally involves no combination among different subpopulations. Clustering improves the performance of the evolutionary algorithm by such an interbreeding avoidance. However, this approach leads to a smaller exploration of the space, since combination from distant regions could be favorable.
@cite_1
2011699475
The problem of multimodal clustering arises whenever the data are gathered with several physically different sensors. Observations from different modalities are not necessarily aligned in the sense there there is no obvious way to associate or compare them in some common space. A solution may consist in considering multiple clustering tasks independently for each modality. The main difficulty with such an approach is to guarantee that the unimodal clusterings are mutually consistent. In this letter, we show that multimodal clustering can be addressed within a novel framework: conjugate mixture models. These models exploit the explicit transformations that are often available between an unobserved parameter space (objects) and each of the observation spaces (sensors). We formulate the problem as a likelihood maximization task and derive the associated conjugate expectation-maximization algorithm. The convergence properties of the proposed algorithm are thoroughly investigated. Several local and global optimization techniques are proposed in order to increase its convergence speed. Two initialization strategies are proposed and compared. A consistent model selection criterion is proposed. The algorithm and its variants are tested and evaluated within the task of 3D localization of several speakers using both auditory and visual data.