Signal-to-noise, Crosstalk, and Long Range Problem Difficulty in Genetic Algorithms
Hillol Kargupta · 1995
This paper presents a signal-to-noise perspective of the search bias introduced by genetic algorithms. A decision theoretic signal-tonoise framework is used to show that there are two fundamental modes of introducing difficulty through search bias: 1) sending a wrong signal and 2) increasing or decreasing noise depending on the direction of signal. The main purpose of this paper is to identify crosstalk as another possible source of problems, caused by search bias in genetic algorithms. I show that a small modification of the one-max problem can convert it to difficult to solve because of crosstalk. This paper also studies the royal road functions (Forrest and Mitchell, 1994) and demonstrates that crosstalk plays a major role in making R2 harder than R1 to solve. This clearly shows that increasing signal in the right direction alone does not necessarily make a problem easy for GA, unless the noise is also reduced. 1 INTRODUCTION A blackbox optimization problem can be difficult to solv...