Optimizing Expensive Functions
According to the two papers (Limited Evaluation Evolutionary Algorithm (LEEA) and Limited Evaluation Cooperative Co-evolutionary Differential Evolution Algorithm (LECCDE)) you can approximate the result of the evolutionary algorithms by applying the algorithm not on the whole dataset but on mini-batches like in SGD (Stochastic Gradient Descent). This significantly reduces computation time (about 25 times in LECCDE paper for an ANN on MNIST dataset).

According to Prellberg 2018 Limited Evaluation Evolutionary Optimization the training times of LE algorithms is still 10 times longer than the Adam variation of stochastic gradient descent. In your case it is not possible to calculate gradients.

The following changes to the evolutionary algorithm are proposed in the first paper (LEEA):


Use mini-batching while ensuring the diversity of the expected outputs.



  Ideal mini-batch size in LEEA was determined experimentally to be 2. ...To apply the idea of diversity in minibatches, the output range is divided into two equally sized sections, and examples selected so that each mini-batch contains
  one example for both sections of the range. A new mini-batch is randomly generated at the beginning of each generation.



Use ancestor fitness for evaluation. 



  f'=(f_p1 + f_p2)/2*(1-d) + f.
  
  Where f' is the individual's modified fitness. f is the fitness of the
  individual against the current mini-batch. f_pn is the fitness of
  parent n. d is a constant decay value.


The second paper (LECCDE) points to the following speed-up using Limited Evaluation algorithms:

LECCDE vs CCDE for different datasets:

Dataset    Parameters   Speedup             Accuracy
WBC        1652          1.10 times faster  1.2% worse
ESR        9052          2.05 times faster  0.3% worse
HAR        28406         4.00 times faster  0.2% worse
MNIST      47710        25.3  times faster  unknown