TY - GEN

T1 - Partial neighborhoods of elementary landscapes

AU - Whitley, L. Darrell

AU - Sutton, Andrew M.

PY - 2009

Y1 - 2009

N2 - This paper introduces a new component based model that makes it relatively simple to prove that certain types of landscapes are elementary. We use the model to reconstruct proofs for the Traveling Salesman Problem, Graph Coloring and Min-Cut Graph Partitioning. The same model is then used to efficiently compute the average values over particular partial neighborhoods for these same problems. For Graph Coloring and Min-Cut Graph Partitioning, this computation can be used to focus search on those moves that are most likely to yield an improving move, ignoring moves that cannot yield an improving move. Let x be a candidate solution with objective function value f(x). The mean value of the objective function over the entire landscape is denoted f. Normally in an elementary landscape one can only be sure that a neighborhood includes an improving move (assuming minimization) if f(x) > f. However, by computing the expected value of an appropriate partial neighborhood it is sometimes possible to know that an improving move exists in the partial neighborhood even when f(x) f.

AB - This paper introduces a new component based model that makes it relatively simple to prove that certain types of landscapes are elementary. We use the model to reconstruct proofs for the Traveling Salesman Problem, Graph Coloring and Min-Cut Graph Partitioning. The same model is then used to efficiently compute the average values over particular partial neighborhoods for these same problems. For Graph Coloring and Min-Cut Graph Partitioning, this computation can be used to focus search on those moves that are most likely to yield an improving move, ignoring moves that cannot yield an improving move. Let x be a candidate solution with objective function value f(x). The mean value of the objective function over the entire landscape is denoted f. Normally in an elementary landscape one can only be sure that a neighborhood includes an improving move (assuming minimization) if f(x) > f. However, by computing the expected value of an appropriate partial neighborhood it is sometimes possible to know that an improving move exists in the partial neighborhood even when f(x) f.

KW - Elementary landscapes

KW - Fitness landscapes

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

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

U2 - 10.1145/1569901.1569954

DO - 10.1145/1569901.1569954

M3 - Conference contribution

AN - SCOPUS:72749106337

SN - 9781605583259

T3 - Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

SP - 381

EP - 388

BT - Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

T2 - 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

Y2 - 8 July 2009 through 12 July 2009

ER -