Astron. Astrophys. 320, 553-567 (1997)

Appendix: calculation of the structure and bond energy of clusters

The stable equilibrium configuration of a cluster with N atoms is determined by the local minima of the potential in the -dimensional space of the positions of its individual atoms ( labels the atoms, their cartesian coordinates). The ground state of the cluster corresponds to the absolute minimum of the potential. The basic problem then is to determine the absolute minimum of the cluster potential and all other deep local potential minima with comparable depth to that of the ground state.

As is well known, such an optimization problem with a large number of variables cannot be solved directly by analytical methods and the task of solving the problem by numerical methods becomes extremely difficult and time consuming if the surfaces have a complicated geometric structure. Up to now, no general method is known which allows one

1. to find definitely all local extrema of an optimization problem and
2. to decide whether the real optimum is contained within the set of extrema found by the applied method.

Numerous methods, however, have been developed which allow one to find in a certain sense a best result, which means that for test cases with a known absolute minimum the algorithm always finds this minimum or at least a local minimum not much different from the absolute one.

One method, which has been applied in the past successfully to several difficult optimization problems like that of the travelling salesman is the "evolution strategy" developed by Rechenberg (1973 , 1989). We apply this method to determine the possible equilibrium configurations of ionic clusters.

The special variant of the method used in our computation is the (1,10)-evolution strategy (Rechenberg 1973 , 1989), which proceeds in the following manner: Starting from an initial vector in the variable space (called parent) and an initial step length , ten new vectors (), called offsprings, are generated by adding to the parent new vectors . The vectors are unit vectors with components which are normally distributed random numbers with variance . The numbers are the individual step length's, generated from by multiplying this by logarithmic normally distributed random numbers with where the are normally distributed such that the numbers and are distributed with the same probability. k determines the width of the distribution of step length's. Numerical experience shows to be a reasonable choice for most problems (Rechenberg 1973).

The best offspring, i.e. that offspring whose quality function is nearest to the optimum, is declared as the new parent of the next generation and its step length is declared as the new step length of the next generation. In our case the quality function is the cluster potential and the best offspring is that which results in the lowest potential energy.

The basic idea of the whole method is to approach the optimum by an intelligent trial and error strategy, in which the experience with respect to the optimum step sizes is left from generation to generation in the "evolution" process. Since the step length itself is varied by a random process, from time to time "mutations" of the step lengths occur if a big sidestep improves the quality. This prevents the process from being trapped into a deep local isolated minimum. Its numerical efficiency stems from the fact that only the quality function has to be evaluated a few times in each generation. Its derivatives are not required and the method is well suited for treating even unpleasant quality functions, even those with discontinuities.

The search for the absolute minimum is stopped if the step lengths drops below some prescribed (small) limit because this indicates that further "mutations" do not improve the result (cf. Fig. 6 for an example). All local deep minima encountered during the search are stored because these are required for determining the isomers. Details with respect to the application of the evolution strategy to the calculation of cluster structures are described in Köhler (1988 , 1989).

Fig. 6. Example for the minimum search of the cluster potential for the MgO cluster using the evolution strategy. The difference (left scale) is the energy difference between some cluster configuration tried during the otimising process and its final value. The nearly horizontal part after 600 generations is due to the machine accuracy. The stepsize (right scale) are the steplengths in units of the ionic radii.

© European Southern Observatory (ESO) 1997

Online publication: June 30, 1998
helpdesk.link@springer.de