Providing initial solutions to bboptimize does not appear to register the guesses provided

[wg12385]

The example code provided in the Readme, namely:

myproblem(x) = (x[1] - 3.14)^2 + (x[2] - 7.2)^4
optimum = [3.14, 7.2]
good_guess = [3.0, 7.2]
res1 = bboptimize(myproblem, good_guess; NumDimensions = 2, SearchRange = (-10.0, 10.0));
@assert isapprox(best_fitness(res1), myproblem(optimum); atol = 1e-30)

Returns the correct solution, however if the guesses are registered by the optimiser, it should be possible to reduce the number of function evaluations to a very small number and still achieve a good solution, or even the optimal solution if the optimal solution is provided as a guess. Neither of these seem to work.

This code:

myproblem(x) = (x[1] - 3.14)^2 + (x[2] - 7.2)^4
optimum = [3.14, 7.2]
good_guess = [3.0, 7.2]
res1 = bboptimize(myproblem, good_guess; NumDimensions = 2, MaxSteps = 20, SearchRange = (-10.0, 10.0));
@assert isapprox(best_fitness(res1), myproblem(optimum); atol = 1e-30)

Fails the assertion, and achieves a fitness of between 1 and 5 for me in several tests. (The fitness for the good_guess is about 0.2)
Changing the good_guess to the optimal solution also does not work:

myproblem(x) = (x[1] - 3.14)^2 + (x[2] - 7.2)^4
optimum = [3.14, 7.2]
good_guess = [3.14, 7.2]
res1 = bboptimize(myproblem, good_guess; NumDimensions = 2, MaxSteps = 20, SearchRange = (-10.0, 10.0));
@assert isapprox(best_fitness(res1), myproblem(optimum); atol = 1e-30)

Again the assertion fails, the fitness achieved being somewhere between 1 and 5.

To further test this, i tried removing the initial_guess from the original code, i.e.

myproblem(x) = (x[1] - 3.14)^2 + (x[2] - 7.2)^4
optimum = [3.14, 7.2]
res1 = bboptimize(myproblem, NumDimensions = 2, SearchRange = (-10.0, 10.0));
@assert isapprox(best_fitness(res1), myproblem(optimum); atol = 1e-30)

And this works fine, it passes the assertion, suggesting with this example the optimiser can easily find the optimal solution without the initial guess.

My questions are:

• Have i fundamentally misunderstood something about how the initial guess feature is meant to work here ?
• Is my issue replicated by other people ? (i.e. could this be a local issue for me ?)
• (depending on the above) can this be fixed ? I have an application where the use of initial guesses is quite essential as a large part of the search space will evaluate to zero, so i need to supply an initial point that is known to not be zero, in order for the optimiser to not stall.

[robertfeldt]

Thanks for your examples. I do think there might be some bugs involved, yes, there has been similar but hard-to-reproduce bugs reported before. I'll investigate on my end and see if I can find the culprit.

[dww100]

@robertfeldt have you made any progress with your investigation?

[jarvist]

I had a quick look at this.

I believe the BlackBoxOptim.jl code is working correctly.

Supplying a guess runs set_candidate! for that optimization method. In the case of a population based method (such as the default :adaptive_de_rand_1_bin_radiuslimited), this overwrites one of the population with the guess.
I suppose that is slightly surprising behaviour, but if that guess is genuinely good it should get used for the next population.

You could start filling a certain fraction of the population like this:

res1 = bboptimize(myproblem, [good_guess for i in 1:25]; Method = :adaptive_de_rand_1_bin_radiuslimited, PopulationSize=50, NumDimensions = 2, SearchRange = (-10.0, 10.0), MaxSteps=20); 

But I'm not sure whether that would ever usefully improve convergence. Perhaps you could seed the optimisation with a population sampled from a Gaussian around your initial guess, to increase diversity.

But if you think your guess is good, your function evaluation expensive, and your problem is relatively smooth, it might make most sense to move to one of the direct_search methods which do an iterative line search around each step of the optimisation, starting with the initial guess.

> myproblem(x) = (x[1] - 3.14)^2 + (x[2] - 7.2)^4
> optimum = [3.14, 7.2]
> good_guess = [3.0, 7.2]
> res1 = bboptimize(myproblem, good_guess; Method = :generating_set_search, NumDimensions = 2, SearchRange = (-10.0, 10.0), MaxSteps=10);

Starting optimization with optimizer GeneratingSetSearcher(BlackBoxOptim.ConstantDirectionGen)
0.00 secs, 2 evals, 0 steps, fitness=0.019600000

Optimization stopped after 11 steps and 0.00 seconds
Termination reason: Max number of steps (10) reached
Steps per second = 45100.04
Function evals per second = 184500.18
Improvements/step = 0.00000
Total function evaluations = 45

Best candidate found: [3.15625, 7.2]

Fitness: 0.000264062

[robertfeldt]

Thanks @jarvist, yes I also checked and didn't really see a problem with the current implementation. The idea with supplanting one of the existing solutions is that this is mainly intended to be done before the optimization has even started so the candidates of the population should have been randomly selected; thus it doesn't matter if we overwrite one or a few of them. And, as you say, if the guess is good, it (and it's "descendants") should quickly spread in the population giving the intended effect. Given this, I think the current solution is reasonable.

This doesn't help explain why the behavior actually doesn't seem to be the intended one though. I guess one alternative would be to do fitness evaluations when adding solutions rather than (as now) when a set of solutions compete to get back into the population. But this would require more re-design so I'm reluctant. Hmm.

[robertfeldt]

This (the way this is implemented, see my previous post) actually explains the original question by @wg12385, i.e. the time it takes for an initial guess to spread in the population depends on the population size and the number of steps of optimization.

If the population size is large and/or the number of steps is small the initial guess might not have been selected for a tournament which means we don't yet know that it is a good one. It hasn't even been evaluated (yet).

To confirm this theory one can increase the number of steps until the assertion passes and repeat a few times like so:

using BlackBoxOptim, Statistics

myproblem(x) = (x[1] - 3.14)^2 + (x[2] - 7.2)^4
optimum = [3.14, 7.2]
good_guess = [3.0, 7.2]

function stepwise_doubling_opt_steps(startsteps, maxsteps, popsize)
    steps = startsteps
    global myproblem, optimum, good_guess
    while steps < maxsteps
        res = bboptimize(myproblem, good_guess; NumDimensions = 2, MaxSteps = steps, 
            SearchRange = (-10.0, 10.0), PopulationSize = popsize);
        if isapprox(best_fitness(res), myproblem(optimum); atol = 1e-30)
            return steps
        end
        steps *= 2 # We double each time until close to optimum
    end
    return nil
end

Which with a population size of 50, on my machine, gives:

stepsneeded50 = Int[stepwise_doubling_opt_steps(20, Int(1e6), 50) for _ in 1:10];
julia> mean(stepsneeded50)
10240.0

and if we then increase the population size:

stepsneeded500 = Int[stepwise_doubling_opt_steps(20, Int(1e6), 500) for _ in 1:10];
julia> mean(stepsneeded500)
81920.0

so my theory is confirmed. I hope this explains the behavior. I understand if this is not what suits most people, i.e. they might need both a large population and few steps, but really you will not be able to utilise a large population with few steps so at least for now I think the current design is ok.

Thoughts @wg12385 @jarvist or anyone else?

[robertfeldt]

And yes, I agree with @jarvist that if you really think your initial guess is good and the problem is smooth you could move to non-population based algorithms. Alternatively, try reducing the population size or provide multiple initial guess with some variation such as from adding gaussian noise, as proposed by @jarvist. Hope this helps.

[robertfeldt]

Ok, closing this for now. I do think the analyses above explains the behavior. If not, please reopen and describe your situation.

[wg12385]

Sorry for the late reply to this. I wanted to make sure i understood the behaviour and get a good MWE for my situation (though i have failed in the latter). I can reproduce the results you both describe, i.e. if you make the MaxSteps big enough then it does work.

For my specific situation this still leaves me with an issue, because i have an expensive function to evaluate, and a large region of space where it evaluates to 0.0 (the optimum being something negative, it varies). I am struggling to find a version of this example which demonstrates more accurately my issue, and i suspect that the real solution to my problem will be to narrow down my initial search space through other means.

Thank you both

[robertfeldt]

Ah, so you need a large population size to "escape" the non-optimal region but can't use many steps? Hmm, that sounds quite tricky. I would still try with a small population and more steps and adding the initial solution. Or using a non-population optimizer and start it from your initial solution.