Neighborhood search

Caporossi, G., Gutman, I. and Hansen, P. (1999). Variable Neighborhood Search for Extremal Graphs. IV Chemical Trees with Extremal Connectivity Index. Computers Chem., 23, 469-477. 

Hansen, P. and Melot, H. (2003) Variable neighborhood search for extremal graphs. 6. Analyzing bounds for the connectivity index. 

An alternative that has generated much recent research interest is to liberate neighborhood search from the obligation to improve at each step. That is, moves are sometimes adopted that do not improve the objective function (or reduce infeasihUity). Comprehensive books on the topic include Reeves (1993), Aarts and Lenstra (1997), and Glover and Laguna (1998). 

Any of the normal manipulations of neighborhood search can be employed to construct the new solutions, but crossover moves, which interchange parts of solutions in the current population, me the most popular. For example, crossover of parent solutions (0,1,0,0,1,1) and (1,1,0,1,0,1) by cutting after the third component would produce offspring (0,1,0,1,0,1) and (1,1,0,0,1,1). These new solutions would be eviuated and the better ones preserved in the next generation. 

Ishibuchi, H., Yamamoto, N., Murata, T. and Tanaka, H., 1994. Genetic algorithms and neighborhood search algorithms for fuzzy flowshop scheduling problems. Fuzzy Sets and Systems, 67(1), 81-100. 

Gutman, P. Hansen, and H. Melot, Variable neighborhood search for extremal graphs. 10. Comparison of irregularity indices for chemical trees. J. Chem. Inf. Model. 45 (2005) 222-230. 

Rao, R., Mohan, A., Sivasubiamanian, K. (2008). Optimal placement of actuators for active vibration control of seismic excited tall buildings using a multiple start guided neighborhood search (MSGNS) algorithm. Journal of Sound and Vibration, 377(1-2), 133-159. doi 10.1016/j. jsv.2007.08.031... 

Early systematic searches for elementary one-dimensional invertible CA rules turned up none for neighborhood sizes of 2 and 3 [yamaTO] and essentially one case (with eight trivial variants that may be obtained from it by reflection or complementation) out of a total of 2 = 65,536 possibilities for a neighborhood of size four [patt71] ... 

In the left panel of Fig. 1 we present the [Fe/H] distributions for planet host stars (hashed histogram) included in the CORALIE planet-search sample [25], when compared with the same distribution for 900 stars in the whole CORALIE program (open histogram). The knowledge of the uniformly determined metallicity distribution for stars in the solar neighborhood (and included in the CORALIE sample) permits us to determine the percentage of planet host stars per metallicity bin. 

In neighborhood-based heuristic searches, each xeX has an associated neighborhood N(x) that contains all the feasible solutions that the search will explore when the current point is x. Each alternative solution x e N(x) is reached from x by an operation called a move. Consider again the three-job problem based on Table 10.2A. Let the current sequence x be (3, 1, 2), and suppose that we consider only neighboring permutations x that can be reached from x by swapping a pair of jobs in x. This swap neighborhood is shown in Table 10.2B, in which i and j are the indices of the jobs to be swapped. If there are n jobs, then a swap neighborhood contains n(n - l)/2 permutations. 

Key Words Chemical database compound selection library design molecular diversity molecular similarity neighborhood behavior similar property principle similarity searching. 

---