Skip to content

Learning methods

Solvers that learn a way of building schedules while they solve: temporal-difference agents, a policy gradient, and a genetic-programming hyper-heuristic.

dispatchatlas.solvers.learning

Solvers that learn how to build schedules while they solve.

Each learner starts from scratch on the problem it is given, spends the run's budget on learning, and returns the best schedule it evaluated. What it learns is a way of building schedules, which is itself evaluated as it improves:

  • temporal_difference: q-learning-dispatching and sarsa-dispatching, tabular agents that learn which of four dispatching rules picks the next task in each state of the construction.
  • policy_gradient: reinforce-priority-policy, a softmax policy over linear priorities of task features, trained by the REINFORCE policy gradient.
  • hyper_heuristic: gp-hyper-heuristic, genetic programming of priority-rule expression trees (trees) with a surrogate that chooses which bred rules to evaluate.

All of them use only the standard library and NumPy.

register

register(registry: SolverRegistry) -> None

Add the learning solvers and the genetic-programming hyper-heuristic to registry.

dispatchatlas.solvers.learning.common

Pieces the learning solvers share: due dates, rewards, and policy values.

Improvement dataclass

Improvement(value: float, overrun: float, value_scale: float, time_scale: float)

The reward of a schedule: its improvement over a reference schedule, without units.

The reward of a schedule with objective v, in minimisation form, and total deadline overrun o is (v0 - v) / max(|v0|, 1) + (o0 - o) / max(m0, 1), where v0, o0, and m0 are the objective, overrun, and makespan of the reference. The first term is the relative gain in the objective, the second the overrun removed, counted in reference makespans. The reference itself scores zero.

Attributes:

Name Type Description
value float

Objective of the reference, in minimisation form.

overrun float

Total deadline overrun of the reference.

value_scale float

Divisor of objective differences, max(|v0|, 1).

time_scale float

Divisor of overrun differences, max(m0, 1).

over classmethod

over(reference: Candidate) -> Improvement

Return the reward that measures schedules against an evaluated reference.

__call__

__call__(score: Score) -> float

Return the reward of a schedule with the given score.

horizon

horizon(problem: Problem) -> float

Return the latest release time plus the sum of the shortest task durations.

Running every task in its shortest mode one after another from the last release, ignoring lags and transfers, ends at this time. The learners use it as the due date of tasks that have none.

due_dates

due_dates(problem: Problem) -> list[float]

Return the due date that the learners rank each task by.

A task's due date is the earlier of its soft due date, inherited from its group when it has none (see effective_due_dates()), and its hard deadline. A task with neither gets the problem's horizon(), so that its slack stays finite and large.

policy_value

policy_value(search: Search, latest: Candidate | None) -> float

Return the objective of the latest greedy-policy schedule a learner evaluated.

The learners evaluate the greedy policy of their untrained start first. When that evaluation reached the target and ended the run before returning, the incumbent is that schedule.

Parameters:

Name Type Description Default
search Search

The run.

required
latest Candidate | None

The latest greedy-policy schedule whose evaluation returned.

required

Returns:

Type Description
float

The objective with its natural sign, or NaN when nothing was evaluated.

dispatchatlas.solvers.learning.temporal_difference

Tabular temporal-difference agents that learn which dispatching rule to apply.

Aydin and Oztemel (2000) train an agent that chooses, at each scheduling decision, the priority rule that suits the current state of the shop, and Zhang et al. (2011) learn choices among rule-based actions with SARSA. The agents here learn such a choice on the problem being solved, by tabular temporal-difference control:

  • Construction. An episode builds one schedule a task at a time with the shared Builder. At each step the agent observes a state and chooses a rule, the rule picks the next task among the eligible ones, whose predecessors are all placed, and the builder places it at its earliest start in its earliest-finishing mode. The placement order and modes are then evaluated, which rebuilds the same schedule.
  • Rules (RULES, in action order): shortest processing time, longest processing time, earliest due date, and minimum slack. Durations are the shortest over a task's modes and due dates come from due_dates(). The slack of an eligible task is its due date minus its earliest finish time in the partial schedule minus the longest path after it, so the slack rule reacts to the schedule built so far. Every rule breaks ties by the lowest task index.
  • States (observe()): the fraction of tasks already placed, cut into stage_buckets equal bins, and the number of eligible tasks: one, two, or three or more.
  • Learning. The agent chooses rules epsilon-greedily: a uniformly random rule with probability epsilon, else the rule of largest action value, the first among ties. A decision followed by another earns no reward, and its value moves by learning_rate toward the discounted value of the next state: the largest action value there for Q-learning (Watkins and Dayan 1992), the value of the rule the agent chooses there for SARSA (Rummery and Niranjan 1994; Sutton and Barto 2018). The last decision of an episode moves toward the episode's reward, the Improvement of its schedule over the reference schedule.
  • Budget. Action values start at zero, so the untrained greedy policy applies the first rule in every state. Its schedule is evaluated first and is the reference. The exploration rate falls linearly from exploration to zero as the budget is spent. After an episode that changes the greedy rule of some state, the greedy policy's schedule is evaluated too, unless it equals the last one evaluated. One episode is one iteration.

The rules interleave jobs freely, which a permutation problem forbids, so the agents do not accept permutation problems.

RULES module-attribute

RULES: tuple[str, ...] = ('shortest-processing-time', 'longest-processing-time', 'earliest-due-date', 'minimum-slack')

The dispatching rules the agents choose among, in action order.

READY_BUCKETS module-attribute

READY_BUCKETS = 3

Number of eligible-set buckets of a state: one, two, and three or more tasks.

INFOS module-attribute

INFOS: dict[Target, SolverInfo] = {'q-learning': SolverInfo(id='q-learning-dispatching', name='Q-learning dispatching', family='learning', summary='Learns which of four dispatching rules should pick the next task in each coarse state of the construction by one-step Q-learning, bootstrapping from the best action value of the next state, and builds schedules with epsilon-greedy rule choices.', references=('watkins1992qlearning', 'aydin2000dynamic', 'panwalkar1977survey'), supports=_SUPPORTS, parameters=_PARAMETERS), 'sarsa': SolverInfo(id='sarsa-dispatching', name='SARSA dispatching', family='learning', summary='Learns which of four dispatching rules should pick the next task in each coarse state of the construction by SARSA, bootstrapping from the value of the rule chosen in the next state, and builds schedules with epsilon-greedy rule choices.', references=('rummery1994online', 'sutton2018reinforcement', 'aydin2000dynamic', 'zhang2011semiconductor', 'panwalkar1977survey'), supports=_SUPPORTS, parameters=_PARAMETERS)}

Metadata of the two registered agents, by target.

Target

Target = Literal['q-learning', 'sarsa']

The bootstrap target of the value updates.

State

State = tuple[int, int]

A construction state: (stage bucket, eligible-set bucket).

ActionValues

ActionValues(actions: int)

The action values of the visited states, zero until updated.

Parameters:

Name Type Description Default
actions int

Number of actions of every state.

required

row

row(state: State) -> list[float]

Return the live values of state, adding a zero row on its first visit.

get

get(state: State) -> tuple[float, ...]

Return the values of state without adding a row.

update

update(state: State, action: int, target: float, rate: float) -> bool

Move one value toward target by the fraction rate of the difference.

Returns:

Type Description
bool

Whether the greedy action of state changed.

DispatchRules

DispatchRules(problem: Problem)

The rules of RULES, applied to the eligible tasks of a partial schedule.

Parameters:

Name Type Description Default
problem Problem

The problem.

required

choose

choose(rule: int, eligible: Sequence[int], builder: Builder) -> tuple[int, int, float]

Return the task that rule picks among eligible, with its mode and start.

The mode is the task's earliest-finishing mode in the partial schedule of builder, and the start its earliest start in that mode.

Episode dataclass

Episode(schedule: Decoded, decisions: tuple[tuple[State, int], ...], changed: bool = False)

One schedule built by an agent.

Attributes:

Name Type Description
schedule Decoded

The schedule, as the agent's builder placed it.

decisions tuple[tuple[State, int], ...]

The state and the chosen rule of every construction step.

changed bool

Whether a value update during the construction changed the greedy rule of some state.

sequence property

sequence: tuple[int, ...]

Task indices in placement order.

modes property

modes: tuple[int, ...]

Mode index of every task.

starts property

starts: tuple[float, ...]

Start time of every task.

Agent

Agent(problem: Problem, decoder: Decoder, *, target: Target, learning_rate: float, discount: float, stage_buckets: int, check: Callable[[], None] | None = None)

The action values, the rules, and the construction loop of one run.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
decoder Decoder

The decoder of the run, whose builder places the tasks.

required
target Target

The bootstrap target of the value updates.

required
learning_rate float

Step size of the value updates.

required
discount float

Discount of the next state's value.

required
stage_buckets int

Number of progress bins of a state.

required
check Callable[[], None] | None

Called before every construction step. The solver passes check(), which stops a construction that runs past the time limit.

None

Attributes:

Name Type Description
values

The learned action values.

episode

episode(rng: Random, epsilon: float) -> Episode

Build a schedule with epsilon-greedy rule choices, updating values on the way.

At every step the agent draws one uniform number, and a rule index when it explores. The value of the last decision is left for finish(), since the episode's reward is known only once its schedule is evaluated.

greedy

greedy() -> Episode

Build the schedule of the greedy policy, without learning or random draws.

finish

finish(episode: Episode, reward: float) -> bool

Move the value of the episode's last decision toward its reward.

Returns:

Type Description
bool

Whether the greedy rule of that decision's state changed.

TemporalDifferenceDispatching dataclass

TemporalDifferenceDispatching(target: Target = 'q-learning', learning_rate: float = 0.5, discount: float = 0.9, exploration: float = 0.3, stage_buckets: int = 4)

A tabular temporal-difference agent that learns which dispatching rule to apply.

Episodes build schedules in which one of four dispatching rules picks each next task, and the rewards of those schedules teach the agent which rule to apply in each construction state. target selects the registered solver: q-learning-dispatching or sarsa-dispatching. The module docstring gives the details.

Attributes:

Name Type Description
target Target

"q-learning" bootstraps from the largest action value of the next state, "sarsa" from the value of the rule chosen there.

learning_rate float

Step size of the value updates, in (0, 1].

discount float

Discount of the next state's value, in [0, 1].

exploration float

Exploration rate at the start of the run, in [0, 1]. It falls linearly to zero as the budget is spent.

stage_buckets int

Number of equal bins of the placed fraction in a state, at least 1.

info property

info: SolverInfo

Metadata of the solver that target selects.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Learn rule choices within the stop criteria and return the best schedule built.

The result extras hold states, the number of states visited, and policy_value, the objective of the latest greedy-policy schedule evaluated.

observe

observe(placed: int, total: int, eligible: int, stage_buckets: int) -> State

Return the state before a construction step.

Parameters:

Name Type Description Default
placed int

Tasks already placed.

required
total int

Tasks of the problem, at least one.

required
eligible int

Tasks eligible now, at least one.

required
stage_buckets int

Number of equal bins of the placed fraction.

required

Returns:

Type Description
State

``(min(placed * stage_buckets // total, stage_buckets - 1),

State

min(eligible - 1, READY_BUCKETS - 1))``.

greedy_action

greedy_action(values: Sequence[float]) -> int

Return the action of largest value, the lowest index among ties.

td_target

td_target(target: Target, values: Sequence[float], action: int, discount: float) -> float

Return the discounted value that a zero-reward transition moves toward.

Parameters:

Name Type Description Default
target Target

"q-learning" uses the largest action value of the next state, whatever the agent does there. "sarsa" uses the value of the action the agent takes there.

required
values Sequence[float]

Action values of the next state.

required
action int

The action the agent takes in the next state.

required
discount float

Discount factor.

required

Returns:

Type Description
float

discount * max(values) or discount * values[action].

register

register(registry: SolverRegistry) -> None

Add q-learning-dispatching and sarsa-dispatching to registry.

dispatchatlas.solvers.learning.policy_gradient

A linear softmax priority policy trained with REINFORCE.

Instead of applying a fixed priority rule, this solver learns one. A task's priority is a weighted sum of five features, and the policy builds a task order by drawing, at each step, one eligible task (all its predecessors already drawn) with probability given by the softmax of the eligible tasks' priorities divided by temperature. The weights are trained with the REINFORCE estimator of Williams (1992):

  1. Features (task_features()): a constant 1, the shortest duration over the task's modes, the release time, the slack, and the number of direct successors. The slack is the due date from due_dates() minus the release time minus the shortest duration; tasks without a due date use the problem's horizon, the latest release plus the sum of the shortest durations. Every column except the constant is divided by its largest absolute value over the tasks, so the weights are comparable. The constant shifts every priority by the same amount, so it changes neither the probabilities nor the greedy order, and its gradient is zero.
  2. Rollout. An episode draws one order with one uniform number per step (inverse-transform sampling) and sums, over the steps, the gradient of the log-probability of each choice with respect to the weights, (phi(chosen) - E[phi]) / temperature, where E[phi] is the mean feature vector of the eligible tasks under the policy.
  3. Update. The order is evaluated. Its reward is the Improvement of its schedule over the reference schedule, and the weights move by learning_rate * (reward - baseline) times the summed gradient. The baseline is the mean reward of the earlier episodes, zero before the first, the reinforcement comparison that Williams (1992) discusses.
  4. Greedy policy. The greedy policy takes the eligible task of highest priority, the lowest index on ties. With the initial all-zero weights it yields the problem's topological order, whose schedule is evaluated first and is the reference. After every update the greedy order is evaluated when it differs from the last one evaluated.

Orders are evaluated as they are drawn: the schedule builder places each task at its earliest start in its earliest-finishing mode, and in a permutation problem it keeps each job's tasks together, jobs in the order they first appear. One episode is one iteration.

FEATURES module-attribute

FEATURES: tuple[str, ...] = ('bias', 'duration', 'release', 'slack', 'successors')

Names of the policy's features, in weight order.

LinearPolicy

LinearPolicy(problem: Problem, temperature: float)

A softmax policy over eligible tasks with linear priorities.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
temperature float

Divisor of the priorities inside the softmax.

required

Attributes:

Name Type Description
features

Feature vector of every task, from task_features().

weights

One weight per feature, initially zero.

priorities

priorities() -> list[float]

Return the priority of every task, its weighted feature sum rounded once.

rollout

rollout(rng: Random, check: Callable[[], None] | None = None) -> tuple[list[int], list[float]]

Draw a precedence-feasible order and the gradient of its log-probability.

Parameters:

Name Type Description Default
rng Random

Source of the one uniform number drawn per step.

required
check Callable[[], None] | None

Called before every step, to stop at the time limit.

None

Returns:

Type Description
list[int]

The order and, per weight, the sum over the steps of

list[float]

(phi(chosen) - E[phi]) / temperature.

greedy

greedy() -> list[int]

Return the order of the greedy policy: highest priority first, lowest index on ties.

step

step(gradient: Sequence[float], scale: float) -> None

Add scale times gradient to the weights.

ReinforcePriorityPolicy dataclass

ReinforcePriorityPolicy(learning_rate: float = 0.2, temperature: float = 1.0)

A linear priority rule learned by the REINFORCE policy gradient (Williams 1992).

The policy draws task orders from a softmax over linear priorities of five task features, and each schedule's reward moves the weights along the gradient of the drawn order's log-probability. The module docstring gives the details.

Attributes:

Name Type Description
learning_rate float

Step size of the weight updates, positive.

temperature float

Divisor of the priorities inside the softmax, positive. Larger values make the draws more uniform.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Train the policy within the stop criteria and return the best schedule built.

The result extras hold policy_value, the objective of the latest greedy-policy schedule evaluated, and the final weights, as weight_<feature>.

task_features

task_features(problem: Problem) -> list[tuple[float, ...]]

Return the feature vector of every task, in the order of FEATURES.

Every column except the constant is divided by its largest absolute value over the tasks. A column of zeros stays zero.

softmax

softmax(scores: Sequence[float]) -> list[float]

Return the softmax of scores, computed after subtracting the largest one.

sample

sample(probabilities: Sequence[float], rng: Random) -> int

Return an index drawn with the given probabilities, from one uniform number.

The first index whose cumulative probability exceeds the uniform draw is returned, the last one when rounding leaves the total below the draw.

dispatchatlas.solvers.learning.hyper_heuristic

A genetic-programming hyper-heuristic that evolves priority rules.

A hyper-heuristic searches a space of heuristics instead of a space of schedules (Burke et al. 2013). This one evolves priority rules, the expression trees of trees, by genetic programming (Koza 1992), and scores each rule by the schedule it builds on the problem:

  • Decoding. A rule gives every task a priority; a priority that is not a number counts as minus infinity. The list schedule takes, at each step, the eligible task of highest priority (pick()): priorities within TIE_TOLERANCE of the highest tie, and ties go to the shortest task, then the lowest index. The schedule builder places each task at its earliest start in its earliest-finishing mode. Every rule applied to the problem is one evaluation.
  • Initialisation. population rules by ramped half-and-half.
  • Breeding. A generation breeds offspring_multiplier * population children, each from winners of tournaments of tournament_size members: subtree crossover of two winners with probability crossover_rate, subtree mutation of one with probability mutation_rate, otherwise a copy of one. A child deeper than max_depth is replaced by a new ramped half-and-half tree.
  • Surrogate screening (Hildebrandt and Branke 2015). A rule's phenotypic characterisation lists its decision in each of situations decision situations: sets of 2 to situation_size tasks, drawn uniformly once at the start of the run. The decision is the rank, by shortest duration then lowest index, of the task that the rule picks in the situation. Rules with equal characterisations count as equivalent, so a child whose characterisation occurs in the population or in an earlier child is dropped. The others are ranked by their estimated score, the mean score of the neighbours members of the current population whose characterisations are nearest in Euclidean distance, and evaluated in that order until, together with the elites best members carried over unchanged, they fill the next population. New random rules fill any remaining places. Zhang et al. (2021) screen offspring of scheduling rules with this surrogate as well.

One generation is one iteration. The result extras hold the rule of the best schedule as text.

TIE_TOLERANCE module-attribute

TIE_TOLERANCE = 1e-09

Priorities this close to the highest one count as ties.

Rule dataclass

Rule(tree: Tree, priorities: tuple[float, ...], characterisation: tuple[int, ...])

A rule with its priorities and phenotypic characterisation.

Attributes:

Name Type Description
tree Tree

The expression tree.

priorities tuple[float, ...]

Priority of every task.

characterisation tuple[int, ...]

Rank decisions in the run's decision situations.

Member dataclass

Member(rule: Rule, score: Score)

An evaluated rule of the population.

Attributes:

Name Type Description
rule Rule

The rule.

score Score

Score of the schedule it builds.

GpHyperHeuristic dataclass

GpHyperHeuristic(population: int = 24, max_depth: int = 6, crossover_rate: float = 0.8, mutation_rate: float = 0.15, tournament_size: int = 5, elites: int = 2, offspring_multiplier: int = 2, neighbours: int = 1, situations: int = 12, situation_size: int = 7)

Genetic programming of priority rules with surrogate screening of the offspring.

A population of priority-rule trees evolves by tournament selection, subtree crossover, and subtree mutation. Every generation breeds a surplus of children, and a nearest-neighbour surrogate over the rules' decisions in sample situations chooses which of them to evaluate. The module docstring gives the details.

Attributes:

Name Type Description
population int

Rules per generation, at least 1.

max_depth int

Largest depth of a bred tree, at least the largest initial depth, 3.

crossover_rate float

Probability that a child is a subtree crossover.

mutation_rate float

Probability that a child is a subtree mutation. With crossover_rate it sums to at most 1; the rest is copying.

tournament_size int

Members drawn, with replacement, per tournament.

elites int

Best members carried into the next generation, fewer than population.

offspring_multiplier int

Children bred per generation, as a multiple of population.

neighbours int

Nearest population members whose mean score estimates a child's score.

situations int

Decision situations of the phenotypic characterisation.

situation_size int

Largest number of tasks in a decision situation, at least 2.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Evolve rules within the stop criteria and return the best schedule built.

The result extras hold rule, the rule of the best schedule as text.

pick

pick(candidates: Sequence[int], priorities: Sequence[float], durations: Sequence[float]) -> int

Return the candidate of highest priority.

Candidates within TIE_TOLERANCE of the highest priority tie, and ties go to the shortest duration, then the lowest index.

list_order

list_order(problem: Problem, priorities: Sequence[float], durations: Sequence[float]) -> list[int]

Return the list-scheduling order of a rule's priorities.

At each step the eligible task (all its predecessors already listed) that pick() chooses comes next.

decision_situations

decision_situations(tasks: int, count: int, largest: int, rng: Random) -> list[tuple[int, ...]]

Draw the decision situations of the phenotypic characterisation.

Each situation is a sorted set of distinct tasks whose size is drawn uniformly from 2 to min(largest, tasks). A single-task problem has only the situation made of its task.

Parameters:

Name Type Description Default
tasks int

Number of tasks of the problem.

required
count int

Number of situations.

required
largest int

Largest number of tasks in a situation, at least 2.

required
rng Random

Random generator.

required

characterise

characterise(priorities: Sequence[float], situations: Sequence[tuple[int, ...]], durations: Sequence[float]) -> tuple[int, ...]

Return the phenotypic characterisation of a rule given by its priorities.

Entry i is the rank, by shortest duration then lowest index, of the task that pick() chooses in situation i.

dispatchatlas.solvers.learning.trees

Priority rules as expression trees: the primitive set and the variation operators.

A rule is an expression tree whose leaves are terminals, attributes of a task, and whose inner nodes are binary functions. Evaluated on a task, it gives the task's priority. The function set, including the protected division, follows the task-scheduling rules that Zaki et al. (2024) evolve, as do the duration and successor-count terminals:

  • DUR: the shortest duration over the task's modes.
  • SUCC: the number of the task's direct successors.
  • REL: the task's release time.
  • SLACK: the due date from due_dates() minus the release time minus the shortest duration.
  • DEPTH: the number of dependencies on the longest chain of dependencies that ends at the task (task_depths()).
  • ADD, SUB, MUL, MAX, MIN, and DIV, the protected division, whose value is 1 wherever the divisor is 0.

Trees are evaluated on every task at once, over NumPy columns. The operators are those of Koza (1992): ramped half-and-half initialisation, subtree crossover, and subtree mutation. Nodes are addressed by their pre-order index.

TERMINALS module-attribute

TERMINALS: tuple[str, ...] = ('DUR', 'SUCC', 'REL', 'SLACK', 'DEPTH')

Terminal names, in the order random draws index them.

FUNCTIONS module-attribute

FUNCTIONS: tuple[str, ...] = ('ADD', 'SUB', 'MUL', 'DIV', 'MAX', 'MIN')

Function names, in the order random draws index them.

INITIAL_DEPTHS module-attribute

INITIAL_DEPTHS: tuple[int, ...] = (2, 3)

Depths of the trees that ramped half-and-half draws from.

GROW_TERMINAL_RATE module-attribute

GROW_TERMINAL_RATE = 0.3

Probability that the grow method ends a branch above the depth limit.

OPERATIONS module-attribute

OPERATIONS: Mapping[str, Callable[[Column, Column], Column]] = MappingProxyType({'ADD': np.add, 'SUB': np.subtract, 'MUL': np.multiply, 'DIV': protected_division, 'MAX': lambda first, second: np.where(first >= second, first, second), 'MIN': lambda first, second: np.where(first <= second, first, second)})

The element-wise operation of every function.

Tree

Tree = str | tuple[str, Tree, Tree]

A terminal name, or a function name with its two argument trees.

Column

Column = NDArray[float64]

One value per task.

protected_division

protected_division(numerator: Column, divisor: Column) -> Column

Divide element-wise, giving 1 wherever the divisor is 0.

task_depths

task_depths(problem: Problem) -> list[int]

Return, per task, the number of dependencies on the longest chain ending at it.

One pass over the tasks in topological order relaxes every dependency, so each task's depth is one more than the largest depth of its predecessors, and zero without predecessors.

terminal_columns

terminal_columns(problem: Problem) -> dict[str, Column]

Return the value of every terminal for every task, keyed by terminal name.

evaluate

evaluate(tree: Tree, columns: Mapping[str, Column]) -> Column

Return the value of tree for every task, from the terminal columns.

Overflow gives infinities and undefined operations give NaN, without warnings.

grow

grow(limit: int, full: bool, rng: Random) -> Tree

Return a random tree of depth at most limit.

With full, every branch reaches limit. Otherwise a branch above the limit ends in a terminal with probability GROW_TERMINAL_RATE. Terminals and functions are drawn uniformly.

ramped_half_and_half

ramped_half_and_half(rng: Random) -> Tree

Return a tree of a depth drawn from INITIAL_DEPTHS, full or grown with equal odds.

size

size(tree: Tree) -> int

Return the number of nodes of tree.

depth

depth(tree: Tree) -> int

Return the depth of tree; a single terminal has depth 1.

subtree

subtree(tree: Tree, position: int) -> Tree

Return the subtree rooted at the node of pre-order index position.

replace

replace(tree: Tree, position: int, replacement: Tree) -> Tree

Return a copy of tree with the subtree at pre-order index position replaced.

crossover

crossover(parent: Tree, donor: Tree, rng: Random) -> Tree

Return parent with a random subtree replaced by a random subtree of donor.

mutate

mutate(tree: Tree, rng: Random) -> Tree

Return tree with a random subtree replaced by a new grown tree.

The new tree has at most the smallest depth of INITIAL_DEPTHS.

text

text(tree: Tree) -> str

Return a compact text form such as ADD(DUR,DIV(SLACK,DEPTH)).