Surface-structure search with variable composition and periodicity via machine learning and evolutionary algorithms:...

First-principles structure prediction is essential for discovering functional materials; however, surface structure searches remain challenging because most search algorithms assume fixed in-plane periodicity and composition. Here we develop a global search framework that treats both two-dimensional superlattice periodicity and stoichiometry as dynamic variables, enabling the direct identification of the most stable surface structures across competing supercell shapes and compositions. The proposed method integrates an evolutionary algorithm with surface-specific variation operators and symmetry-enriched initialization, and accelerates screening via Bayesian optimization using atomic cluster expansion descriptors. Case studies on FCC Pt(111) and diamond Ge(100) surfaces yield oxygen-induced surface structures consistent with experimental observations, and the same framework identifies Sn alloying motifs on FCC Au(111) that agree with reported surface-structure trends. Overall, the framework delivers accurate structure prediction with substantially fewer high-cost first-principles evaluations and provides a general route to exploring complex materials landscapes - such as heterogeneous catalysis, electronics, and spintronics - in which coupled structural and compositional degrees of freedom govern functionality.