Upper Bounds on the Time and Space Complexity of Optimizing Additively Separable Functions

Matthew J. Streeter
Carnegie Mellon University
Pittsburgh, PA 15213

Abstract

We present upper bounds on the time and space complexity of finding the global optimum of additively separable functions, a class of functions that has been studied extensively in the evolutionary computation literature. The algorithm presented uses efficient linkage discovery in conjunction with local search. Using our algorithm, the global optimum of an order-k additively separable function defined on strings of length l can be found using O(l*ln(l)*2^k) function evaluations, a bound which is lower than all those that have previously been reported.

This page contains supporting materials for the paper "Upper Bounds on the Time and Space Complexity of Optimizing Additively Separable Functions", presented at GECCO 2004.

A copy of the paper can be found here.

Proofs omitted from the paper to save space can be found here.

A Java implementation of the algorithm presented in the paper is available here.