TY - JOUR

T1 - The component model for elementary landscapes and partial neighborhoods

AU - Whitley, Darrell

AU - Sutton, Andrew M.

AU - Ochoa, Gabriela

AU - Chicano, Francisco

N1 - Publisher Copyright:
© 2014 Published by Elsevier B.V.

PY - 2014

Y1 - 2014

N2 - Local search algorithms exploit moves on an adjacency graph of the search space. An "elementary landscape" exists if the objective function f is an eigenfunction of the Laplacian of the graph induced by the neighborhood operator, this allows various statistics about the neighborhood to be computed in closed form. A new component based model makes it relatively simple to prove that certain types of landscapes are elementary. The traveling salesperson problem, weighted graph (vertex) coloring and the minimum graph bisection problem yield elementary landscapes under commonly used local search operators. The component model is then used to efficiently compute the mean objective function value over partial neighborhoods for these same problems. For a traveling salesperson problem over n cities, the 2-opt neighborhood can be decomposed into ⌊ . n/2. -. 1⌋ partial neighborhoods. For graph coloring and the minimum graph bisection problem, partial neighborhoods can be used to focus search on those moves that are capable of producing a solution with a strictly improving objective function value.

AB - Local search algorithms exploit moves on an adjacency graph of the search space. An "elementary landscape" exists if the objective function f is an eigenfunction of the Laplacian of the graph induced by the neighborhood operator, this allows various statistics about the neighborhood to be computed in closed form. A new component based model makes it relatively simple to prove that certain types of landscapes are elementary. The traveling salesperson problem, weighted graph (vertex) coloring and the minimum graph bisection problem yield elementary landscapes under commonly used local search operators. The component model is then used to efficiently compute the mean objective function value over partial neighborhoods for these same problems. For a traveling salesperson problem over n cities, the 2-opt neighborhood can be decomposed into ⌊ . n/2. -. 1⌋ partial neighborhoods. For graph coloring and the minimum graph bisection problem, partial neighborhoods can be used to focus search on those moves that are capable of producing a solution with a strictly improving objective function value.

KW - Elementary landscapes

KW - Fitness landscape analysis

KW - Stochastic local search

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

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

U2 - 10.1016/j.tcs.2014.04.036

DO - 10.1016/j.tcs.2014.04.036

M3 - Article

AN - SCOPUS:84926408926

SN - 0304-3975

VL - 545

SP - 59

EP - 75

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -