Interaction-Detection Metric with Differential Mutual Complement for Dependency Structure Matrix Genetic Algorithm

Dependency structure matrix genetic algorithm (DSMGA), one of estimation of distribution algo-rithms (EDAs), adopts model-building mechanisms via dependency structure matrix clustering tech-niques. Previous researches have shown that DSMGA can effectively solve nearly decomposable prob-lems. DSMGA utilizes an entropy-based metric to detect the interactions among genes. The efficiency of DSMGA and other model-building GAs greatly depend on their interaction-detection metrics. This paper investigates several commonly used metrics, and proposes a new interaction-detection metric which aims at what GAs really need. The proposed metric, namely the differential mutual complement, is based on both the disruption and reproduction effects of the crossover operator on significant schemata. Empirical results show that DSMGA with the proposed metric performs better than the other existing metrics on the aspects of population size and sensitivity to threshold. This new metric is shown to perform well on DSMGA and could be expected to work with other EDAs.