## 1 Introduction
However, in a large number of instances, just identifying the global minimum without any prior information about the cost function landscape is already a highly nontrivial task that typically requires an enormous computational effort. This is due to the large size of the state space--prohibiting an exhaustive search via testing every microstate--and due to the complexity of the barrier structure, which makes straightforward steepest descent gradient-based minimizations (for continuous landscapes) or random downhill walks ineffective. Although some improvement is achieved by combining such greedy downhill algorithms with a systematic (nearly exhaustive) grid-like selection of starting points for the local minimization [9], this combination is still not very efficient in identifying the global minimum of the system, due to the enormous size of the state space and the large number of local minima present. Moreover, many of these minima would be rediscovered many times, thus resulting in a massive oversampling of the landscape's minima. As a consequence, researchers in many fields have developed a plethora of global optimization algorithms, many of which are variations of some \"classical\" ones, such as genetic algorithms (GA) [10], simulated annealing (SA) [11], or branch-and-bound algorithms (BB) [12]. Among these are the bounce algorithm [13], the great-deluge algorithm [14], threshold accepting [15], particle swarm optimization [16], the tabu algorithm [17], thermal cycling [18], and evolutionary algorithms [19; 20; 21], just to name a few--for an overview, we refer to the literature [1; 22; 23; 24]. Many of these methods are inspired by physical processes, e.g., molecular dynamics simulations [25; 26] or thermal cycling [18], and by biology, e.g., the evolutionary [19] or genetic algorithms [10; 27], while others are based on general energy landscape considerations as, e.g., the great-deluge [14] or the tabu [17] algorithms. These basic--in principle generally applicable--algorithms are often specially adapted to certain classes of systems and energy landscapes, e.g., for the prediction of the conformers of molecules, such as the rotamers of chain-like molecules such as proteins or polysaccharides. Since one usually restricts the structure generation to molecules with a given bond network, only limited changes in the bond lengths are allowed, and the main degrees of freedom that are varied during the search are the bond angles and dihedral (torsion) angles. Ideally, one would compute the energy on the ab initio level. However, because of the high computational expense of quantum mechanical calculations, one commonly employs empirical molecular modeling potentials instead, possibly adding penalty terms that restrict the bond lengths and angles to certain \"allowed\" ranges which are physically and chemically sensible--according to experimental data and/or results from ab initio calculations. Such limits can be either implemented as parts of the energy function or via the moveclass, i.e., no new test configuration is allowed that violates these constraints. Moveclasses with such constraints on the allowed configurations are sometimes called \"rule-based conformation generators\" [24]; they are employed in the context of molecular structure prediction by, e.g., the OMEGA [28] method; for a review of these and other approaches, we refer to the literature [24]. Trying to find the optimal combination of computational speed, quality of the candidates--both regarding their energy and the accuracy of the parameters of the physical structure obtained--, and diversity of the solutions in the set of generated candidates, is a great challenge for systems that exhibit complex multi-minima landscapes.