The Theory Benchmark
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
- class dacbench.benchmarks.theory_benchmark.TheoryBenchmark(config=None)
Bases:
AbstractBenchmarkBenchmark with various settings for (1+(lbd, lbd))-GA and RLS
- create_observation_space_from_description(obs_description, env_class=<class 'dacbench.envs.theory.RLSEnvDiscrete'>)
Create a gym observation space (Box only) based on a string containing observation variable names, e.g. “n, f(x), k, k_{t-1}” Return:
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/
- class dacbench.envs.theory.BinaryProblem(n, rng=Generator(PCG64) at 0x7F03439146D8)
Bases:
objectAn 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=Generator(PCG64) at 0x7F02E3D2E6D8)
- Crossover operator:
for each bit, taking value from x with probability p and from self with probability 1-p
- Arguments:
x: the individual to crossover with p (float): in [0,1]
- 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
- 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
objective after flipping
- mutate(p, n_childs, rng=Generator(PCG64) at 0x7F02E3D2E4F8)
Draw l ~ binomial(n, p), l>0 Generate n_childs children by flipping exactly l bits Return: the best child (maximum fitness), its fitness and number of evaluations used
- mutate_rls(l, rng=Generator(PCG64) at 0x7F02E3D2E5E8)
generate a child by flipping exactly l bits Return: child, its fitness
- class dacbench.envs.theory.LeadingOne(n, rng=Generator(PCG64) at 0x7F02E3D2E7C8, initObj=None)
Bases:
BinaryProblemAn individual for LeadingOne problem The aim is to maximise the number of leading (and consecutive) 1 bits in the string
- 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
- 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
objective after flipping
- class dacbench.envs.theory.RLSEnv(config, test_env=False)
Bases:
AbstractEnvEnvironment 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
Closing confirmation
- Return type
bool
- get_obs_domain_from_name()
Get default lower and upperbound of a observation variable based on its name. The observation space will then be created Return:
Two int values, e.g., 1, np.inf
- reset()
Resets env
- Returns
Environment state
- Return type
numpy.array
- step(action)
Execute environment step
- Parameters
action (Box) – action to execute
- Returns
state, reward, done, info
np.array, float, bool, dict