Heuristic searching

Chakrabarti, P. P., Ghose, S., and DeSarkar, S. C., Heuristic search through islands. Artif. Intell. 29, 339 (1986). 

Heuristic search procedures can be applied to certain types of combinatorial problems when BB and OA are difficult to apply or converge too slowly. In these problems, it is difficult or impossible to model the problem in terms of a vector of decision variables, which must satisfy bounds on a set of constraint functions, as required by OA. One example is the traveling salesman problem, in which the feasible region is the set of all tours in a graph, that is, closed cycles or paths that visit every node only once. The problem is to find a tour of minimal distance or cost,... 

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. 

Heuristic Search / 10.5.2 Tabu Search / 10.5.3 Simulated Annealing / 10.5.4 Genetic and Evolutionary Algorithms /... 

Virtual screening applications based on superposition or docking usually contain difficult-to-solve optimization problems with a mixed combinatorial and numerical flavor. The combinatorial aspect results from discrete models of conformational flexibility and molecular interactions. The numerical aspect results from describing the relative orientation of two objects, either two superimposed molecules or a ligand with respect to a protein in docking calculations. Problems of this kind are in most cases hard to solve optimally with reasonable compute resources. Sometimes, the combinatorial and the numerical part of such a problem can be separated and independently solved. For example, several virtual screening tools enumerate the conformational space of a molecule in order to address a major combinatorial part of the problem independently (see for example [199]). Alternatively, heuristic search techniques are used to tackle the problem as a whole. Some of them will be covered in this section. 

The following examples illustrate the application of high-throughput screening tools together with heuristic search algorithms in the development of new enhanced catalyst for two fields of industrial interest, olefin epoxidation and the isomerization of light paraffins. 

A Comparison of Heuristic Search Algorithms for Molecular Docking. 

In essence, the selection problem can be viewed as a heuristic search in which each state of the search space represents a particular subset of the virtual library. This section highlights a few common methods of subset selection. 

The refined mesh given above was used in the axial direction the radial mesh used n = 3, y = 0.25,0.5,0.75. It was found possible to use the same mesh throughout in the t-domain, due to the freedom to vary the scaling factor a. This avoided heuristic searching for a new mesh for each new set of parameters. Automatic mesh generation was not felt to be worthwhile, in view of the extra costs involved and the relatively underdeveloped state of the art (24). 

FIGURE 3 Depiction of the heuristic search procedure which employs spectral information to reduce the solution space of structures to one or several solutions. 

SYNCHEM is a self-guided heuristic search program for retrosynthetic analysis of compounds in organic synthesis. 

Recursive dynamic programming (RDP) Another heuristic search procedure based on a branch-and-bound approach has been described in [188]. The approach tries to avoid the restrictions implied by a predefined structural core. Even if the structural core is correctly and completely defined, even the best alignment of the query sequence onto the structure core can be based on information of about half or less of the residues and structural positions of the template structure. Often, structures contain highly conserved loop regions, which if responsible for conserved functions (e.g. ATP binding loops [170]) are also conserved on the sequence level or contain detectable sequence motifs or functional patterns. Such loops can provide important initial hints on similarities and partial alignments exploitable for the assembly of overall alignments. 

D. R. Westhead, D. E. Clark, and C. W. Murray. A comparison of heuristic search algorithms for molecular docking. Journal of Computer-Aided Molecular Design, 11 209-228, 1997. 

---