In this work, computationally efficient design optimization of frequency selective surface (FSS)-loaded ultra-wideband Vivaldi antenna via the use of data driven surrogate model is studied. The proposed design methodology consists of a multi-layer FSS structure aimed for performance improvement of the Vivaldi design, which makes the design a multi-objective multidimensional optimization problem. For having a fast and accurate optimization process, a data-driven surrogate model alongside the metaheuristic optimizer honeybee mating optimization (HBMO) had been used. The optimally designed antenna had been prototyped and its performance characteristics had been measured. The obtained experimental results are compared with the simulated results of the proposed method. Results show that the obtained FSS-loaded structure has enhanced directivity compared with the design without FSS structure, without any performance losses in the return loss characteristics. The FSS-loaded Vivaldi antenna operates at 2-12 GHz band with a maximum gain of 10 dBi at 10 GHz which makes the design a good solution for RADAR applications.