Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2011.02.006 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Elementary landscapes,cth moment,Fitness landscape analysis,local search algorithm,Hamming sphere,evolutionary algorithm,Local search,Hamming space,arbitrary radius,Pseudo-Boolean functions,algebraic information,search space,k-bounded pseudo-Boolean function,polynomial time,expected fitness,Walsh analysis,adjacency structure | Journal | 425, |
ISSN | Citations | PageRank |
Theoretical Computer Science | 15 | 0.97 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew M. Sutton | 1 | 256 | 21.19 |
| L. Darrell Whitley | 2 | 6631 | 968.30 |
| Adele E. Howe | 3 | 561 | 65.70 |