Literature Review

Recently there has been considerable interest in employing GAs for solving cluster optimization problems [1,8,9,10,11,12]. Judson [13] has shown that GAs outperform the traditional Monte Carlo based simulated annealing method. Zeiri [14] reports that GAs are superior to simulated annealing in predicting the geometry of Ar_nH₂. GAs were successful in predicting the optimal structure for C₆₀ [15] atom and simulated annealing failed for the same case. In the above study the authors used a geometric crossover to create new individuals. Hartke [11] used a simple GA to predict the structure of Si₄ and Si₁₀ on a semi-empirical potential. Gregurick et al. proposed a hybrid GA, in which they combined a binary coded GA and a conjugate gradient local search. They reported significant improvement in the performance when compared a GA without local search method. Niesse and Mayne [1] modified this hybrid GA by encoding real values instead of binary. Iwamatsu [10] used a Nelder-Mead simplex [16] instead of a conjugate gradient technique to predict the cluster structure of Si_n (n = 3-15).

In most of the studies on cluster optimization with GA, researchers have used operators like proportionate selection, single point crossover, etc. Proportionate selection has various drawbacks, the scaling problem being the foremost. Single point crossover is known to disrupt good building blocks and thereby increase the convergence time as well as population size required. It has been shown in recent works [17,18,19] that ensuring effective building block (BB) mixing is an integral part of efficient GA design. These studies also showed that this could be achieved through a tight linkage of the set of alleles belonging to a BB. Based upon this concept many novel competent GA designs have been proposed which can be broadly classified into three groups; (1) Perturbation techniques like fast messy GA (FMGA) [20], gene expression messy GA (GEMGA) [21], Linkage identification by nonlinearity check/Linkage identification by detection GA (LINC/LIMD GA) [22], (2) Linkage adaptation techniques like linkage learning GA (LLGA) [23], and (3) Probabilistic model based techniques like extended compact GA (ECGA) [7] and Bayesian optimization algorithm (BOA) [24]. Sastry and Goldberg [25] successfully applied ECGA for optimizing a binary fluid power cycle formulated as a nonlinear constrained problem. They also reported semi-empirical relations for the convergence time and the population size required.