Computing the moments of k-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time

Andrew M. Sutton, L. Darrell Whitley, Adele E. Howe

Research output: Contribution to journalArticle

15 Citations (Scopus)

Abstract

We show that given a k-bounded pseudo-Boolean function f, one can always compute the cth moment of f over regions of arbitrary radius in Hamming space in polynomial time using algebraic information from the adjacency structure (where k and c are constants). This result has implications for evolutionary algorithms and local search algorithms because information about promising regions of the search space can be efficiently retrieved, even if the cardinality of the region is exponential in the problem size. Finally, we use our results to introduce a method of efficiently calculating the expected fitness of mutations for evolutionary algorithms.

Original languageEnglish (US)
Pages (from-to)58-74
Number of pages17
JournalTheoretical Computer Science
Volume425
DOIs
StatePublished - Mar 30 2012

Fingerprint

Pseudo-Boolean Functions
Boolean functions
Evolutionary algorithms
Polynomial time
Radius
Polynomials
Moment
Evolutionary Algorithms
Computing
Arbitrary
Local Search Algorithm
Adjacency
Search Space
Fitness
Cardinality
Mutation

Keywords

  • Elementary landscapes
  • Fitness landscape analysis
  • Local search
  • Pseudo-Boolean functions
  • Walsh analysis

Cite this

Computing the moments of k-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time. / Sutton, Andrew M.; Darrell Whitley, L.; Howe, Adele E.

In: Theoretical Computer Science, Vol. 425, 30.03.2012, p. 58-74.

Research output: Contribution to journalArticle

@article{5e91ef612ee7400091e4590ebadcc6f2,
title = "Computing the moments of k-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time",
abstract = "We show that given a k-bounded pseudo-Boolean function f, one can always compute the cth moment of f over regions of arbitrary radius in Hamming space in polynomial time using algebraic information from the adjacency structure (where k and c are constants). This result has implications for evolutionary algorithms and local search algorithms because information about promising regions of the search space can be efficiently retrieved, even if the cardinality of the region is exponential in the problem size. Finally, we use our results to introduce a method of efficiently calculating the expected fitness of mutations for evolutionary algorithms.",
keywords = "Elementary landscapes, Fitness landscape analysis, Local search, Pseudo-Boolean functions, Walsh analysis",
author = "Sutton, {Andrew M.} and {Darrell Whitley}, L. and Howe, {Adele E.}",
year = "2012",
month = "3",
day = "30",
doi = "10.1016/j.tcs.2011.02.006",
language = "English (US)",
volume = "425",
pages = "58--74",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

TY - JOUR

T1 - Computing the moments of k-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time

AU - Sutton, Andrew M.

AU - Darrell Whitley, L.

AU - Howe, Adele E.

PY - 2012/3/30

Y1 - 2012/3/30

N2 - We show that given a k-bounded pseudo-Boolean function f, one can always compute the cth moment of f over regions of arbitrary radius in Hamming space in polynomial time using algebraic information from the adjacency structure (where k and c are constants). This result has implications for evolutionary algorithms and local search algorithms because information about promising regions of the search space can be efficiently retrieved, even if the cardinality of the region is exponential in the problem size. Finally, we use our results to introduce a method of efficiently calculating the expected fitness of mutations for evolutionary algorithms.

AB - We show that given a k-bounded pseudo-Boolean function f, one can always compute the cth moment of f over regions of arbitrary radius in Hamming space in polynomial time using algebraic information from the adjacency structure (where k and c are constants). This result has implications for evolutionary algorithms and local search algorithms because information about promising regions of the search space can be efficiently retrieved, even if the cardinality of the region is exponential in the problem size. Finally, we use our results to introduce a method of efficiently calculating the expected fitness of mutations for evolutionary algorithms.

KW - Elementary landscapes

KW - Fitness landscape analysis

KW - Local search

KW - Pseudo-Boolean functions

KW - Walsh analysis

UR - http://www.scopus.com/inward/record.url?scp=79956047330&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79956047330&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.02.006

DO - 10.1016/j.tcs.2011.02.006

M3 - Article

AN - SCOPUS:79956047330

VL - 425

SP - 58

EP - 74

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -