A genetic algorithm coupled to electronic structure calculations is developed for searching the global minimum in the ab initio potential energy landscape of alloy clusters. The convergence criterion for the energy gradient in local optimization is progressively reduced over the generations in order to require less energy evaluations. A case studied is the Na-K alloy with MP2/ECP energies, where it is demonstrated that the algorithm is efficient in obtaining global minima. Particular analysis of a 2D-3D-2D transition in the 6-atoms case is studied in detail for the first time. Completely new structures are unveiled for larger alloy clusters. (C) 2015 Elsevier B.V. All rights reserved.