Optimization Problem when calculating fitness is expensive
For starters I assume that you can't guess the impact the values of a solution have on its fitness, otherwise you could relax the fitness function to roughly estimate which solutions are promising, and try to find a good solution from there.

However you do know that similar solutions have a similar fitness, so let's work with that. I would suggest something along these lines:


Construct a function to measure the similarity of two solutions.
Using this function, heuristically group your solutions into 100 clusters.
For each cluster, calculate the fitness of the solution closest to its mean.


This will give you the fitness of the 100 most dissimilar solutions, which is a good sample of your search space (it should give you a good idea of the fitness found in most major peaks). As a bonus, you can recursively do this if you want to improve on the best solution found, i.e., divide the best cluster into k clusters and proceed in the same way.