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.

StackExchange Computer Science Q#98088, answer score: 2