Multimodal Deceptive Functions
Kalyanmoy Deb
Current address: Indian Institute of Technology, Konpur, UP208016, INDIA.
Jeffrey Horn
David E. Goldberg
Illinois Genetic Algorithms Laboratory,
University of Illinois at Urbana-Champaign,
117 Transportation Building, 104 S. Mathews Avenue,
Urbana, IL 61801, USA
Abstract
This paper presents a static analysis of deception in multimodal functions. Deception in a bipolar function of unitation (a function with two global optima and a number of deceptive attractors) is defined, and a set of sufficient conditions relating function values is obtained. A bipolar deceptive function is also constructed from low-order Walsh coefficients. Multimodal functions of bounded deception are formed by concatenating several bipolar deceptive functions. These functions offer a great challenge to global optimization algorithms (including genetic algorithms) because they are deceptive and have a large number of attractors, of which only a few are global optima. These functions also open doors for generalizing the notion of deception, and allow us to better understand the importance of deception in the study of genetic algorithms.
