A New DSM Clustering Algorithm for Linkage Groups Identification

摘要

Linkage learning has been considered as an influential factor in success of genetic and evolutionary algorithms for solving difficult optimization problems. In this paper, a deterministic model named Dependency Structure Matrix (DSM) is used for explicitly decomposing the problem. DSM captures pair-wise dependencies of the problem that must be turned into higher order interactions while solving complex problems. One way to obtain these higher order interactions (linkage groups) is clustering the DSM. A new DSM clustering algorithm is proposed in this paper which is able to identify all the linkage groups from a less accurate DSM leading to a reduction in the number of fitness calls required for identifying the linkage groups. The proposed technique is tested on several benchmark problems and it is shown that it can accurately identify all the linkage groups by O(n~(1.7)) fitness evaluations, where n is problem size.