Additively Decomposable Fitness Functions Abstract

Richard K. Thompson     & Alden H. Wright &

Computer Science Dept.
The University of Montana
Missoula, MT 59812-1008


We define a class of optimization objective functions over discrete domains called additively decomposable functions. An additively decomposable function is a function over several discrete variables that can be written as a sum of component functions, each of which depends on only a small number of those variables. The $N\!K$ fitness landscapes defined by Kauffman are a special case. If the domain variables have a circular ordering, then under the adjacent model, we impose the further restriction that each component function depends on a sequence of adjacent variables in the ordering. Bandwidth-constrained problems and adjacent $N\!K$ landscapes are special cases. We give a polynomial-complexity dynamic programming algorithm to optimize adjacent-model additively decomposable functions, and show that without the adjacency assumption, the optimization problem is NP-complete.