pg.evolution.recombinators.SegmentWise

Accessible via pg.evolution.recombinators.SegmentWise.

class SegmentWise

Bases: pg.evolution.Recombinator

Base for recombinators that interleavingly take segments from parents’ DNA.

A segment-wise recombinator usually involve 2 parents. It cuts both parents’ DNA at K positions, which forms K + 1 segments. Then it takes the K + 1 segments from both parents in an interleaving manner. For example, a two-point crossover that takes places at cutting points 2 and 5 will result in 2 children as follows:

Parent 1:   [1,  2,  | 3,  4,  5,  | 6,  7]
Parent 2:   [10, 20, | 30, 40, 50, | 60, 70]
                     |             |
Child 1:    [1,  2,  | 30, 40, 50, | 6,  7]
Child 2:    [10, 20, | 3,  4,  5,  | 60, 70]

One important aspect of recombination is that the children produced from recombination should be valid. Decisions can be moved around when and only when they are independent from other decisions. In PyGlove, there are multiple interdependent DNA sequences: 1) conditional space, whose DNA is represented by tuples (e.g. (1, 2) means inner-choice 2 is made under outer-choice 1). 2) subchoices of a multi-choice which has sorted and/or distinct constraint. Each interdependent DNA group, like a sub-tree for conditional space, or a list of subchoices for constrained multi-choice will be treated as a single position when the DNA is being cut into segments. For example, DNA([0, 1, [1, 2, 0, 3]]) has length 3 if the multi-choice is sorted or distinct, otherwise its length is 6.

The varitions of segment-wise recombination differ from each other in how they choose the cutting strategies. KPoint randomly choose K cutting points in the DNA sequence, AlternatingPosition cuts the DNA at every position thus forming a list of length-1 segments. Segment lets the user to customize cutting strategies based on a list of applicable decision points.

Methods:

cutting_indices(independent_decision_points, ...)	Implementation of getting the indices of the cutting points.
recombine(parents, global_state, step)	Generate a list of child DNA based on the list of parents given.

abstract cutting_indices(independent_decision_points, global_state, step)

Implementation of getting the indices of the cutting points.

Return type:

List[int]

Parameters:

• independent_decision_points – A list of independent decision points.

• global_state – An optional keyword argument as the global state. Subclass can omit.

• step – An optional keyword argument as the curent step. Subclass can omit.

Returns:

A list of integers as the cutting points.

recombine(parents, global_state, step)

Generate a list of child DNA based on the list of parents given.

User should override this method with optional keyword arguments ‘global_state’ and ‘step’.

The parents DNA contains a metadata field ‘generation’, which is the generation of the parent DNA. If the Recombinator does not assign this field for the new child DNA, the child DNA will have the maximum generation from the parents plus 1.

Return type:

List[pg.DNA]

Parameters:

• parents – Parent trials.

• global_state – An AttributeDict object as the global state container, which is readable/writable during the operation.

• step – Number of examples historically proposed, which can be used for determining a cross over schedule.

Returns:

A list of generated child DNA.