The surface of a material often undergoes dramatic structure evolution under a chemical environment, which, in turn, helps determine the different properties of the material. Here, we develop a general-purpose method for the automated search of optimal surface phases (ASOPs) in the grand canonical ensemble, which is facilitated by the stochastic surface walking (SSW) global optimization based on global neural network (G-NN) potential. The ASOP simulation starts by enumerating a series of composition grids, then utilizes SSW-NN to explore the configuration and composition spaces of surface phases, and relies on the Monte Carlo scheme to focus on energetically favorable compositions. The method is applied to silver surface oxide formation under the catalytic ethene epoxidation conditions. The known phases of surface oxides on Ag(111) are reproduced, and new phases on Ag(100) are revealed, which exhibit novel structure features that could be critical for understanding ethene epoxidation. Our results demonstrate that the ASOP method provides an automated and efficient way for probing complex surface structures that are beneficial for designing new functional materials under working conditions.