Linkage identification by fitness difference clustering.
Genetic Algorithms perform crossovers effectively when linkage sets - sets of variables tightly linked to form building blocks - are identified. Several methods have been proposed to detect the linkage sets. Perturbation methods (PMs) investigate fitness differences by perturbations of gene values and Estimation of distribution algorithms (EDAs) estimate the distribution of promising strings. In this paper, we propose a novel approach combining both of them, which detects dependencies of variables by estimating the distribution of strings clustered according to fitness differences. The proposed algorithm, called the Dependency Detection for Distribution Derived from fitness Differences (D(5)), can detect dependencies of a class of functions that are difficult for EDAs, and requires less computational cost than PMs.
Tsuji
Miwako
M
Graduate School of Information Science and Technology, Hokkaido University, North 11, West 5, Sapporo, 060-0811 Japan. m_tsuji@cims.hokudai.ac.jp
Munetomo
Masaharu
M
Akama
Kiyoshi
K
D000465:Algorithms; D005075:Biological Evolution; D016000:Cluster Analysis; D019295:Computational Biology; D008040:Genetic Linkage; D008957:Models, Genetic