We introduce a computational method for global optimization of structure and ordering in atomic systems. The method relies on interpolation between chemical elements, which is incorporated in a machine learning structural fingerprint. The method is based on Bayesian optimization with Gaussian processes and is applied to the global optimization of Au-Cu bulk systems, Cu-Ni surfaces with CO adsorption, and Cu-Ni clusters. The method consistently identifies low-energy structures, which are likely to be the global minima of the energy. For the investigated systems with 23-66 atoms, the number of required energy and force calculations is in the range 3-75.