In this work, we propose a new method to approximate the cost function of Low-Thrust, Multiple-Gravity-Assist interplanetary trajectories using a Machine Learning surrogate. We identified the computation time required to obtain training data as the main limitation when using Machine Learning methods for this purpose so we present a strategy to build the surrogate with limited training data. We built an Online-Sequential Extreme Learning Machine Multi-Agent System (OS-ELM-MAS) surrogate due to its theoretical good performance when the training data is limited. In addition, we define a method to include the surrogate during the optimization process that can be used with any gradient-free algorithm, and study the effect of several surrogate parameters on the optimization results. Finally, several interplanetary trajectories are optimized with and without the surrogate. Employing the surrogate results in up to 12% lower fuel cost values after a fixed optimization time. The parameters that control the interaction have to be carefully selected to achieve this improvement, and we show that the optimal value of these parameters can be narrowed down based on the characteristics of the transfers.