Characterization of neighborhood behaviours in a multi-neighborhood local search algorithm
We consider a multi-neighborhood local search algorithm with a large number of possible neighborhoods. Each neighborhood is accompanied by a weight value which represents the probability of being chosen at each iteration. These weights are fixed before the algorithm runs, and are considered as parameters of the algorithm. Given a set of instances, off-line tuning of the algorithm's parameters can be done by automated algorithm configuration tools (e.g., SMAC). However, the large number of neighborhoods can make the tuning expensive and difficult even when the number of parameters has been reduced by some intuition. In this work, we propose a systematic method to characterize each neighborhood's behaviours, representing them as a feature vector, and using cluster analysis to form similar groups of neighborhoods. The novelty of our characterization method is the ability of reflecting changes of behaviours according to hardness of different solution quality regions. We show that using neighborhood clusters instead of individual neighborhoods helps to reduce the parameter configuration space without misleading the search of the tuning procedure. Moreover, this method is problem-independent and potentially can be applied in similar contexts.
Code (0)
등록된 구현이 없습니다.
Tasks
SMACSMAC+Similar Papers 제목 키워드 기반
Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
Propagating similarity information along the data manifold requires careful selection of local neighborhood. Selecting a "good" neighborhood in an unsupervised setting, given an affinity graph, has been a difficult task.…
Learning Conditional Averages
We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in standard PAC learning. However, instead…
Recommendation SystemsSCoNE: Spherical Consistent Neighborhoods Ensemble for Effective and Efficient Multi-View Anomaly Detection
The core problem in multi-view anomaly detection is to represent local neighborhoods of normal instances consistently across all views. Recent approaches consider a representation of local neighborhood in each view indep…
Anomaly DetectionNode Embedding using Mutual Information and Self-Supervision based Bi-level Aggregation
Graph Neural Networks (GNNs) learn low dimensional representations of nodes by aggregating information from their neighborhood in graphs. However, traditional GNNs suffer from two fundamental shortcomings due to their lo…
Node ClusteringLearning From Graph Neighborhoods Using LSTMs
Many prediction problems can be phrased as inferences over local neighborhoods of graphs. The graph represents the interaction between entities, and the neighborhood of each entity contains information that allows the in…