with increasing system size is exponential and can not be reduced to polynomial without using some sort of approximations. In terms of the configuration space, these exponentially increasing solution candidates correspond to local extrema which are similar to the desired global extremum in a topological manner and consequently there is no way to decide if an extremum is a local or a global one other than to search for better solutions. A famous example of the NP complexity problems is a combinatorial problem known as the traveling salesman problem (TSP) [4], which searches for the shortest path for a salesman whose objective is visiting a certain number of cities and eventually returning to the starting city. As the number of cities increases linearly, the number of possible paths increases exponentially and therefore, our unfortunate salesman starts having trouble in estimating the shortest path for his travel. Another well known problem of the NP complexity class is from chemical physics about finding the most stable structure of nanoparticles composed of certain number and types of atoms or molecules [5; 6]. Even though this important problem of chemical physics does not resemble TSP at a first glance, a deeper analysis shows that these two problems are indeed very similar combinatorial problems if the solution space of the nanoparticle problem is constructed as being composed of stable isomers only. The number of stable isomers of the nanoparticle increases exponentially just like the possible paths in TSP as the system size increases and an exact solution becomes intractable even for moderate sized nanoparticles [7].  
Because of the exponential scaling property of computation time with the system size, these kind of problems can only be solved approximately in a reasonable amount of time by the search algorithms seeking configuration space extensively to find the desired solution. Monte Carlo methods, simulated annealing, basin-hoping and genetic algorithms (GAs) are examples of such search methods used in various branches of science and engineering [8; 9]. The common stochastic nature of these methods is an advantage for the optimization problems with higher dimensional configuration spaces. Monte Carlo methods use the random walk concept as the search technique and jump over local minima by thermal fluctuations. Simulated annealing tries to find the global minimum by decreasing thermal fluctuations with passing time. The main theme of basin-hoping is a potential energy surface (PES) transformation to reduce the configuration space to the space of local minima. This transformed PES is then searched by Monte Carlo methods. GAs use principles of natural evolution to make a search in the configuration space and they gained importance because of their wide applicability and success for the global optimization problems.  
This article reviews application of GAs to the geometry optimization problem of nanoparticles by mentioning past and recent developments on the GAs specific for this problem of chemical physics with some illustrating examples from the literature. Methodology of GA optimization is explained in Section 2 together with some historical remarks. Information about the geometry optimization problem of nanoparticles and usage of GAs in this field is given in section 3 and two GA applications of the current authors to the geometry optimization of atomic clusters using a single parent Lamarckian GA implementation, are presented in section 4 together with some discussion about the relative power of single parent GAs for the geometry optimization problem.