# Deceptiveness And Neutrality The Nd Family Of Fitness Landscapes William Beaudoin, S´Ebastien Verel, Philippe Collard, Cathy Escazut

University of Nice-Sophia Antipolis I3S Laboratory Sophia Antipolis, France

## {Beaudoin,Verel,Pc,Escazut}@I3S.Unice.Fr Abstract

When a considerable number of mutations have no effects on fitness values, the fitness landscape is said neutral. In order to study the interplay between neutrality, which exists in many real-world applications, and performances of metaheuristics, it is useful to design landscapes which make it possible to tune precisely neutral degree distribution. Even though many neutral landscape models have already been designed, none of them are general enough to create landscapes with specific neutral degree distributions. We propose three steps to design such landscapes: first using an algorithm we construct a landscape whose distribution roughly fits the target one, then we use a simulated annealing heuristic to bring closer the two distributions and finally we affect fitness values to each neutral network. Then using this new family of fitness landscapes we are able to highlight the interplay between deceptiveness and neutrality.

## Categories And Subject Descriptors

I.2.8 [**Artificial Intelligence**]: Problem Solving, Control Methods, and Search.

## General Terms

Algorithms, performance, design, experimentation.

## Keywords

Fitness landscapes, genetic algorithms, search, benchmark.

## 1. Introduction

The Adaptative Landscape metaphor introduced by S. Wright [1]
has dominated the view of adaptive evolution: an uphill walk of a population on a mountainous fitness landscape in which it can get stuck on suboptimal peaks. Results from molecular evolution has changed this picture: Kimura's model [2] assumes that the overwhelming majority of mutations are either effectively neutral or lethal and in the latter case purged by negative selection. This assumption is called the neutral hypothesis. Under this hypothesis, Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$5.00.

dynamics of populations evolving on such neutral landscapes are different from those on adaptive landscapes: they are characterized by long periods of fitness stasis (population stated on a 'neutral network') punctuated by shorter periods of innovation with rapid fitness increases [3]. In the field of evolutionary computation, neutrality plays an important role in real-world problems: in design of digital circuits [4] [5] [6], in evolutionary robotics [7] [8]. In those problems, neutrality is implicitly embedded in the genotype to phenotype mapping.

## 1.1 Neutrality

We recall a few fundamental concepts about fitness landscapes and neutrality (see [9] for a more detailed treatment). A landscape is a triplet (**S, V, f**) where S is a set of *potential solutions* i.e. a search space, V : S → 2 S, a *neighbourhood* structure, is a function that assigns to every s ∈ S a set of neighbours V (s), and f : S → IR is a fitness function that can be pictured as the "height" of the corresponding potential solutions. The neighbourhood is often defined by an operator like bitflip mutation. A *neutral neighbour* of s is a neighbour with the same fitness f(s). The *neutral* degree of a solution is the number of its neutral neighbours. A
fitness landscape is neutral if there are many solutions with high neutral degree. A *neutral network*, denoted NN, is a connected graph where vertices are solutions with the same fitness value and two vertices are connected if they are neutral neighbours.

## 1.2 Fitness Landscapes With Neutrality

In order to study the relationship between neutrality, dynamics of Evolutionary Algorithms (EA) and search difficulty, some benchmarks of neutral landscapes have been proposed. More often neutrality is either an add-on feature, as in NK-landscapes, or an incidental property, as in Royal-Road functions. In most cases the design acts upon the amount of solutions with the same fitness. RoyalRoad functions [10] are defined on binary strings of length N =
n.k where n is the number of blocks and k the size of one block.

The fitness function corresponds to the number of blocks which are set with k bits value 1 and neutrality increases with k. Numerous landscapes are variant of NK-Landscapes [11]. The fitness function of an NK-landscape is a function f : {0, 1}
N → [0, 1) defined on binary strings with N bits. An 'atom' with fixed epistasis level is represented by a fitness component fi : {0, 1}
K+1 → [0, 1) associated to each bit i. It depends on the value at bit i and also on the values at K other epistatic bits. The fitness f is the average of the values of the N fitness components fi. Several variants of NK-landscapes try to reduce the number of fitness values in order to add some neutrality. In NKp-landscapes [12], fi(x) has a probability p to be equal to 0 ; in NKq-landscapes [13], fi(x) is uniformly distributed in the interval [0, q−1]∩IN; in Technological