The Theory Benchmark

Task: controlling number of flips in RLS on LeadingOnes

Cost: number of iterations until solution

Number of hyperparameters to control: one float

State Information: user specified, highly flexible

Noise Level: fairly large

Instance space: different instantiations of LeadingOnes

This benchmark is considered one of our highly controllable ones as there is ground truth available. It is also, however, built on top of the RLS algorithm, so not an artificial benchmark. At each step, the DAC controller chooses how many solution bits to flip. We want to optimize how many algorithm steps are taken, so the number of iterations is the reward.

While this is not an easy to solve benchmark, it is cheap to run and interfaces a real EA. Thus it may be a good entry point for harder EA-based benchmarks and also a good benchmark for analyzing controller behavior.

The Theory benchmark was constructed by Biedenkapp et al. for the paper `”Theory-Inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration” <https://arxiv.org/pdf/2202.03259.pdf>`_ at GECCO 2022

Theory Benchmark.

class dacbench.benchmarks.theory_benchmark.TheoryBenchmark(config=None)

Bases: AbstractBenchmark

Benchmark with various settings for (1+(lbd, lbd))-GA and RLS.

create_observation_space_from_description(obs_description, env_class=<class 'dacbench.envs.theory.TheoryEnvDiscrete'>)

Create a gym observation space (Box only) based on a string containing observation variable names, e.g. “n, f(x), k, k_{t-1}”.

Returns:

A gym.spaces.Box observation space.

get_environment(test_env=False)

Return an environment with current configuration.

Parameters:

test_env –

whether the enviroment is used for train an agent or for testing if test_env=False:

cutoff time for an episode is set to 0.8*n^2 (n: problem size) if an action is out of range, stop the episode immediately and return a large negative reward (see envs/theory.py for more details)

otherwise: benchmark’s original cutoff time is used,

and out-of-range action will be clipped to nearest valid value and the episode will continue.

read_instance_set()

Read instance set from file we look at the current directory first, if the file doesn’t exist, we look in <DACBench>/dacbench/instance_sets/theory/.

Theory Environment.

class dacbench.envs.theory.BinaryProblem(n, rng=None)

Bases: object

An abstract class for an individual in binary representation.

combine(xprime, locs_xprime)

Combine (crossover) self and xprime by taking xprime’s bits at locs_xprime and self’s bits at other positions.

Parameters:

• xprime (1d boolean array) – the individual to crossover with

• locs_x (1d boolean/integer array) – positions where we keep current bits of self

• locs_xprime (: 1d boolean/integer array) – positions where we change to xprime’s bits

• Returns

• ------- – the new individual after the crossover

crossover(xprime, p, n_childs, include_xprime=True, count_different_inds_only=True, rng=None)

Crossover operation in population.

Crossover operator: for each bit, taking value from x with probability p and from self with probability 1-p

Parameters:

• xprime – the individual to crossover with

• p (float) – probability in [0,1]

• n_childs (int) – number of child individuals

• include_xprime (bool) – whether to inculde x

• count_different_inds_only (bool) – whether to only count different individuals

• rng – random number generator

eval()

Evaluate fitness.

flip(locs)

Flip the bits at position indicated by locs.

Parameters:

• locs (1d-array) – positions where bits are flipped

• Returns

• ------- – the new individual after the flip

get_fitness_after_crossover(xprime, locs_x, locs_xprime)

Calculate fitness of the child aftering being crossovered with xprime.

Parameters:

• xprime (1d boolean array) – the individual to crossover with

• locs_x (1d boolean/integer array) – positions where we keep current bits of self

• locs_xprime (: 1d boolean/integer array) – positions where we change to xprime’s bits

• Returns

• ------- – fitness of the new individual after crossover

get_fitness_after_flipping(locs)

Calculate the change in fitness after flipping the bits at positions locs.

Parameters:

• locs (1d-array) – positions where bits are flipped

• Returns

• ------- – objective after flipping

get_optimal()

Get optimum.

initialise_with_fixed_number_of_bits(k, rng=None)

Init with given number of bits.

is_optimal()

Get is_optimal flag.

mutate(p, n_childs, rng=None)

Draw l ~ binomial(n, p), l>0.

Generate n_childs children by flipping exactly l bits

Returns:

the best child (maximum fitness), its fitness and number of evaluations used

mutate_rls(length, rng=None)

Generate a child by flipping exactly l bits.

Returns:

child, its fitness

class dacbench.envs.theory.LeadingOne(n, rng=None, initObj=None)

Bases: BinaryProblem

An individual for LeadingOne problem.

The aim is to maximise the number of leading (and consecutive) 1 bits in the string

eval()

Evaluate fitness.

get_fitness_after_crossover(xprime, locs_x, locs_xprime)

Return fitness after crossover.

get_fitness_after_flipping(locs)

Return fitness after flipping.

get_optimal()

Return optimum.

is_optimal()

Return is_optimal flag.

class dacbench.envs.theory.TheoryEnv(config, test_env=False)

Bases: AbstractEnv

Environment for RLS with step size.

Current assumption: we only consider (1+1)-RLS, so there’s only one parameter to tune (r)

close() → bool

Close Env.

No additional cleanup necessary

Returns:

bool: Closing confirmation

static get_obs_domain_from_name(var_name)

Get default lower and upperbound of a observation variable based on its name.

The observation space will then be created

Returns:

Two int values, e.g., 1, np.inf

get_state()

Return state.

reset(seed=None, options=None)

Resets env.

Returns:

numpy.array: Environment state

step(action)

Execute environment step.

Parameters:

• action (Box) – action to execute

• Returns

• --------

• np.array (state, reward, terminated, truncated, info)

• float (state, reward, terminated, truncated, info)

• bool (state, reward, terminated, truncated, info)

• bool

• dict (state, reward, terminated, truncated, info)

class dacbench.envs.theory.TheoryEnvDiscrete(config, test_env=False)

Bases: TheoryEnv

RLS environment where the choices of r is discretised.

step(action)

Take step.

previous

The ToySGD Benchmark

next

The CMA-ES Benchmark