title: Linkage identification by fitness difference clustering.
abstract: 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.
authors.affiliation: Graduate School of Information Science and Technology, Hokkaido University, North 11, West 5, Sapporo, 060-0811 Japan. m_tsuji@cims.hokudai.ac.jp
authors.forename: Miwako
authors.initials: M
authors.lastname: Tsuji
authors.forename: Masaharu
authors.initials: M
authors.lastname: Munetomo
authors.forename: Kiyoshi
authors.initials: K
authors.lastname: Akama
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D016000:Cluster Analysis; D019295:Computational Biology; D008040:Genetic Linkage; D008957:Models, Genetic