New Epistasis Measures for Detecting Independently Optimizable Partitions of Variables

Dong-Il Seo, Sung-Soon Choi, and Byung-Ro Moon

Abstract. An optimization problem is often represented with a set of variables, and the interaction between the variables is referred to as epistasis. In this paper, we propose two new measures of epistasis: internal epistasis and external epistasis. Then we show that they can quantify the decomposability of a problem, which has a theoretical meaning about how strongly the problem is independently optimizable with a partition of variables. We present examples of the problem decomposition and the results of experiments that support the consistency of the measures.

LNCS 3103, p. 150 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004