Random Searches

A random search is, in many ways, the antithesis of a systematic search. A systematic searc explores the energy surface of the molecule in a predictable fashion, whereas it is n(... 

In a systematic search there is a defined endpoint to the procedure, which is reached whe all possible combinations of bond rotations have been considered. In a random search, ther is no natural endpoint one can never be absolutely sure that all of the minimum energ conformations have been found. The usual strategy is to generate conformations until n new structures can be obtained. This usually requires each structure to be generate many times and so the random methods inevitably explore each region of the conformc tional space a large number of times. 

Dmparison of various methods for searching conformational space has been performed cycloheptadecane (C17H34) [Saunders et al. 1990]. The methods compared were the ematic search, random search (both Cartesian and torsional), distance geometry and ecular dynamics. The number of unique minimum energy conformations found with 1 method within 3 kcal/mol of the global minimum after 30 days of computer processing e determined (the study was performed in 1990 on what would now be considered a / slow computer). The results are shown in Table 9.1. 

The energy differences among conforiiiers relative to the ground state are 0.0, 0.85, 1.62, and 3.32 kcal mol . The relative populations of the states, judged by the number of times they were found in a random search or 50 trials, are 0.16, 0.21, 0.15, and 0.08 when degeneracy is taken into account. In the limit of ver y many runs, a Boltzmann distr ibution would lead us to expect a ground state that is much more populous than the output indicates, but this sample is much too small for a statistical law to be valid. 

Once a direction is estabflshed for the next poiat ia the space of the variables of optimization (whether by random search, by systematic evaluation of gradients, or by any other methods of making perturbations), it is possible to take a jump ia the directioa of the improvement much greater than the size of the perturbations. This could speed up the process of finding the optimum and reduce computer time. If such a leap is successful, the next iteration may take a bigger leap and so on, until the improvement stops. Then one could reverse the direction and decrease the size of the step until the optimum is found. 

More or less automatic ways of finding an optimum are described in Appendix 6. The simplest of these by far is the random search method. It can be used for any number of optimization variables. It is extremely inefficient from the viewpoint of the computer but is joyously simple to implement. The following program fragment illustrates the method. 

The random search technique can be applied to constrained or unconstrained optimization problems involving any number of parameters. The solution starts with an initial set of parameters that satisfies the constraints. A small random change is made in each parameter to create a new set of parameters, and the objective function is calculated. If the new set satisfies all the constraints and gives a better value for the objective function, it is accepted and becomes the starting point for another set of random changes. Otherwise, the old parameter set is retained as the starting point for the next attempt. The key to the method is the step that sets the new, trial values for the parameters ... 

The golden section search is the optimization analog of a binary search. It is used for functions of a single variable, F a). It is faster than a random search, but the difference in computing time will be trivial unless the objective function is extremely hard to evaluate. 

Values for kj and kjj are assumed and the above equations are integrated subject to the initial conditions that a = 2, b = 0 at t = 0. The integration gives the model predictions amodel(j) and bmodel(j). The random search technique is used to determine optimal values for the rate constants based on minimization of and S. The following program fragment shows the method used to adjust kj and kjj during the random search. The specific version shown is used to adjust kj based on the minimization of S, and those instructions concerned with the minimization of S appear as comments. 

One of the most reliable direct search methods is the LJ optimization procedure (Luus and Jaakola, 1973). This procedure uses random search points and systematic contraction of the search region. The method is easy to program and handles the problem of multiple optima with high reliability (Wang and Luus, 1977, 1978). A important advantage of the method is its ability to handle multiple nonlinear constraints. 

Belohlav, Z., P. Zamostny, P. Kluson, and J. Volf, "Application of Random-Search Algorithm for Regression Analysis of Catalytic Hydrogenations", CanJ. Chem. Eng., 75, 735-742 (1997). 

Notice how the conversation above reveals that the system has made an attempt to reason logically by finding out what the user considers to be important before it makes any recommendations. This approach is much more productive than a random search in which the interaction might run as follows ... 

Banga et al. [in State of the Art in Global Optimization, C. Floudas and P. Pardalos (eds.), Kluwer, Dordrecht, p. 563 (1996)]. All these methods require only objective function values for unconstrained minimization. Associated with these methods are numerous studies on a wide range of process problems. Moreover, many of these methods include heuristics that prevent premature termination (e.g., directional flexibility in the complex search as well as random restarts and direction generation). To illustrate these methods, Fig. 3-58 illustrates the performance of a pattern search method as well as a random search method on an unconstrained problem. 

FIG. 3-58 Examples of optimization methods without derivatives, (a) Pattern search method. (b) Random search method. O, first phase A, second phase , third phase. 

The most serious problem with MM as a method to predict molecular structure is convergence to a false, rather than the global minimum in the Born-Oppenheimer surface. The mathematical problem is essentially still unsolved, but several conformational searching methods for approaching the global minimum, and based on either systematic or random searches have been developed. These searches work well for small to medium-sized molecules. The most popular of these techniques that simulates excitation to surmount potential barriers, has become known as Molecular Dynamics [112]. 

Various guiding Junctions as criteria to pick the most promising states from W depth-first search, breadth-first search, bounded-width search [21], best-lower-bound search, random search, combined search criteria [22], etc. 

---