An information-theoretic analysis on the interactions of variables in combinatorial optimization problems.
In optimization problems, the contribution of a variable to fitness often depends on the states of other variables. This phenomenon is referred to as epistasis or linkage. In this paper, we show that a new theory of epistasis can be established on the basis of Shannon's information theory. From this, we derive a new epistasis measure called entropic epistasis and some theoretical results. We also provide experimental results verifying the measure and showing how it can be used for designing efficient evolutionary algorithms.
Seo
Dong-Il
DI
School of Computer Science & Engineering, Seoul National University, Sillim-dong, Gwanak-gu, Seoul, 151-744 Korea. diseo@soar.snu.ac.kr
Moon
Byung-Ro
BR
D000465:Algorithms; D005075:Biological Evolution; D019295:Computational Biology; D004843:Epistasis, Genetic; D007257:Information Theory; D008957:Models, Genetic; D015233:Models, Statistical