In this paper, we optimize the locomotion speed of a micro-bristle robot using three surrogate model optimization methods: Kriging method, Bayesian method, and Deep Neural Network. Moreover, the current most popular optimization algorithm in the micro-robot optimization field, the genetic algorithm, is used as the baseline method for comparison. The four methods’ performances are tested in MATLAB, during which a state-of-art dynamic model is used. Then we 3D print the robot designs obtained from these methods and test these robot designs’ real performances. This is the first time that surrogate model optimization methods are applied on micro-robot design field. The MATLAB optimization results and the robot experimental results show that applying proper surrogate model optimization methods, especially Bayesian method will be able to obtain a satisfying robot design 5-6 times faster than the time spent by genetic algorithm. The paper provides an efficient guidance on micro-robot optimization field.