TrapFunktion

TrapFunktion, or trap function, is a class of deceptive fitness landscapes used in the study of optimization and evolutionary computation. It is defined on binary strings and typically built by partitioning a string of length n into non-overlapping blocks of equal length k. The fitness contributed by each block depends on how many ones the block contains, following a predefined trap curve.

The construction yields a conflict between local and global optima. For many blocks with intermediate numbers of ones, the partial fitness is relatively high, which can lure local search methods into suboptimal configurations. Only when all blocks reach a configuration corresponding to the global optimum does the total fitness reach its maximum.

Trap functions are used to investigate the behavior of genetic algorithms and other decomposition-based search methods, including the role of building blocks, epistasis, crossover, and mutation. They provide controlled test cases where problem structure is known and tunable via block size and number of blocks.

Several variants exist, differing in the exact mapping from the number of ones to block fitness and in whether the global optimum is achieved when a block is all ones or all zeros, as well as in the presence of noise or stochastic variants. The simplest and most common form uses the number of ones in a block to assign a block value that makes all-ones configuration the global maximum.

In literature, trap functions are contrasted with unimodal, rugged, and modular landscapes to understand how algorithms cope with deception and with hierarchically organized problems.