Optimization Problem when calculating fitness is expensive I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, I am only able to calculate the fitness of 100 solutions per run. Each solution is represented by vector in ten dimensions with real values [0..1], such that two similar vectors represent similar solutions and should have similar fitness.

Obviously I have no expectation of finding a solution that is anywhere near optimal, but is there a preferred method for AI search when you're only able to test the fitness of very few solutions? I get the feeling that I'm missing one or two keywords that would point my search in the right direction.

I'm considering calculus-based search as one option, as it's better to find a local maxima than just randomly search the space and not find any good solutions whatsoever.
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.