Negative Correlation Learning in Estimation of Distribution Algorithms for Combinatorial Optimization 

Warin Wattanapornprom, and Prabhas Chongstitvatana

SUMMARY This article introduces the Coincidence Algorithm (COIN) to solve several multimodal puzzles. COIN is an algorithm in the class of Estimation of Distribution Algorithms (EDAs) that makes use of probabilistic models to generate solutions. The model of COIN is a joint probability table of adjacent events (coincidence) derived from the population of candidate solutions. A unique characteristic of COIN is the ability to learn from the negative sample. Various experiments show that learning from the negative examples helps to prevent premature convergence, promotes diversity and preserves the good building blocks.

keywords: combinatorial optimization, estimation of distribution algorithms, negative correlation learning, multimodal

in review: IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences