3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you have gradients? Do you have any domain knowledge you can apply? On scicomp, there was a question where the function evaluation takes 30 minutes. Take a look there. $\endgroup$
    – Pål GD
    Oct 3, 2018 at 14:24
  • $\begingroup$ What do you know about the function that computes the fitness from this 10-vector? Do you know anything about its structure? Does it have any properties? Does it come from some family? Are all functions equally likely and equally possible? The more information you can give us about what domain knowledge you have, the more likely we can suggest a good solution. $\endgroup$
    – D.W. ♦
    Oct 4, 2018 at 6:45

2 Answers 2

Reset to default
2
$\begingroup$

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:

  1. Construct a function to measure the similarity of two solutions.
  2. Using this function, heuristically group your solutions into 100 clusters.
  3. 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ While I can guess the impact of the values in a solution, and have a lot of domain knowledge that can easily be used to guess the answer - I am trying to prove/disprove the domain knowledge by searching without any knowledge and seeing if the results line up with what we expect. Thank you for your suggestion of using clustering, that is a great idea and not somethnig I had considered. $\endgroup$
    – Steven Waterman
    Oct 3, 2018 at 22:39
1
$\begingroup$

One approach: Evaluate the fitness of a variety of configurations. Train a model to predict the fitness given the 10-vector. (For instance, you might use a neural network, or some other form of nonlinear regression.)

Then, apply any standard optimization method (e.g., gradient descent) to find the input to the model that maximizes its output. That is a reasonable guess at a possible solution to the optimization problem.

Another approach: use local search methods, such as simulated annealing. Or, you can try particle swarm optimization.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.