Neighborhood Preserving Codes for Assigning Point Labels: Applications to Stochastic Search
Venue
Procedia Computer Science: 2013 International Conference on Computational Science, Elsevier, pp. 956-965
Publication Year
2013
Authors
Shumeet Baluja, Michele Covell
BibTeX
Abstract
Selecting a good representation of a solution-space is vital to solving any search
and optimization problem. In particular, once regions of high performance are
found, having the property that small changes in the candidate solution correspond
to searching nearby neighborhoods provides the ability to perform effective local
optimization. To achieve this, it is common for stochastic search algorithms, such
as stochastic hillclimbing, evolutionary algorithms (including genetic algorithms),
and simulated annealing, to employ Gray Codes for encoding ordinal points or
discretized real numbers. In this paper, we present a novel method to label similar
and/or close points within arbitrary graphs with small Hamming distances. The
resultant point labels can be seen as an approximate high-dimensional variant of
Gray Codes with standard Gray Codes as a subset of the labels found here. The
labeling procedure is applicable to any task in which the solution requires the
search algorithm to select a small subset of items out of many. Such tasks include
vertex selection in graphs, knapsack-constrained item selection, bin packing,
prototype selection for machine learning, and numerous scheduling problems, to name
a few.
