Add function to calculate BOHB behavior

[JarnoRFB]

This should be useful to calculate how many runs will be generated based on the hyperparameters of BOHB.

[codecov-io]

Codecov Report

Merging #43 into master will increase coverage by 0.42%. The diff coverage is 100%.

@@            Coverage Diff             @@
##           master      #43      +/-   ##
==========================================
+ Coverage    64.9%   65.33%   +0.42%     
==========================================
  Files          28       28              
  Lines        1852     1872      +20     
==========================================
+ Hits         1202     1223      +21     
+ Misses        650      649       -1

[JarnoRFB]

Maybe I can combine this PR with another question. I first started by writing a naive implementation of the pseudocode from the paper

The function ended up looking like this

from math import log, floor, ceil
from itertools import cycle, islice

def predict_bobh_run(b_min, b_max, η, n_iterations):
    s_max = floor(log(b_max / b_min, η))

    n_runs = 0
    n_configurations = []
    initial_budgets = []
    
    for s in islice(cycle(range(s_max, -1, -1)), n_iterations):
        n = ceil(((s_max + 1) / (s + 1)) * (η ** s))
        n_configurations.append(n)
        n_runs += n
        initial_budget = (η ** -s) * b_max
        initial_budgets.append(initial_budget)
        budget = initial_budget
        while budget <= b_max:
            n = max(floor(n / η), 1)
            n_runs += n
            budget *= η
    
    print('Running BOBH with these parameters will proceed as follows:')
    print(f'{n_iterations} iterations of SuccessiveHalving will be executed.')
    print(f'The iterations will start with the a number of configurations as {n_configurations}.')
    print(f'With the initial budgets as {initial_budgets}.')
    print(f'A total of {sum(n_configurations)} unique configurations will be sampled')
    print(f'A total of {n_runs} runs will be executed.')

Yet I could not get this to match with the actual behavior of BOHB, so I ended up copying the the relevant lines from the original source code.

For the example from the test the output from the naive implementation is

Running BOBH with these parameters will proceed as follows:
  5 iterations of SuccessiveHalving will be executed.
  The iterations will start with the a number of configurations as [9, 5, 3, 9, 5].
  With the initial budgets as [1.0, 3.0, 9, 1.0, 3.0].
  A total of 31 unique configurations will be sampled
  A total of 46 runs will be executed.

While the function from the PR, that matches the behavior of BOHB outputs

Running BOBH with these parameters will proceed as follows:
  5 iterations of SuccessiveHalving will be executed.
  The iterations will start with a number of configurations as [9, 3, 3, 9, 3].
  With the initial budgets as [1.0, 3.0, 9, 1.0, 3.0].
  A total of 27 unique configurations will be sampled
  A total of 37 runs will be executed.

Any ideas why there exists this difference?