`pygx.algo.evolution`¶

Compositional evolutionary algorithms.

evolution ¶

Compositional evolutionary algorithms.

pygx.algo.evolution builds search algorithms from small, composable operations: selectors choose individuals, mutators perturb them, recombinators combine them, and pipelines connect them with the >> operator.

The top-level Evolution class wires reproduction, population initialization, population updates, and stopping criteria into a single DNAGenerator that plugs into pg.sample, pg.iter, or any other consumer.

Common algorithm constructors are exposed at this level:

hill_climb
neat
nsga2
regularized_evolution

Each takes a Mutator (defaulting to mutators.Uniform()) and returns a ready-to-use Evolution object.

hill_climb ¶

hill_climb(
    mutator: Mutator = Uniform(),
    batch_size: int = 1,
    init_population_size: int = 1,
    seed: int | None = None,
) -> Evolution

Hill-Climbing algorithm, with an extra batched setting.

Batched setting was shown to be effective in https://arxiv.org/pdf/1911.06317.pdf and https://arxiv.org/pdf/2003.01239.pdf, especially in noisy objective settings.

Parameters:

Name	Type	Description	Default
`mutator`	`Mutator`	Mutator to use.	`Uniform()`
`batch_size`	`int`	Number of mutations of the current best.	`1`
`init_population_size`	`int`	Initial population size (randomly generated).	`1`
`seed`	`int \| None`	Random seed.	`None`

Returns:

Type	Description
`Evolution`	An `Evolution` object.

Source code in pygx/algo/evolution/_hill_climb.py

def hill_climb(
    mutator: base.Mutator = mutators.Uniform(),
    batch_size: int = 1,
    init_population_size: int = 1,
    seed: int | None = None,
) -> base.Evolution:
    """Hill-Climbing algorithm, with an extra batched setting.

    Batched setting was shown to be effective in
    https://arxiv.org/pdf/1911.06317.pdf and https://arxiv.org/pdf/2003.01239.pdf,
    especially in noisy objective settings.

    Args:
      mutator: Mutator to use.
      batch_size: Number of mutations of the current best.
      init_population_size: Initial population size (randomly generated).
      seed: Random seed.

    Returns:
      An `Evolution` object.
    """
    return base.Evolution(
        reproduction=(
            selectors.Top(n=1)
            >> (mutator * batch_size)  # pytype: disable=unsupported-operands
        ),
        population_init=(pg.geno.Random(seed=seed), init_population_size),
        population_update=selectors.Top(n=1),
    )

neat ¶

neat(
    mutator: Mutator = Uniform(),
    population_size: int = 100,
    disjoint_coefficient: float = 1.0,
    matching_coefficient: float = 3.0,
    compatibility_threshold: float = 0.4,
    remaining_ratio: float = 0.6,
    seed: int | None = None,
) -> Evolution

NEAT Algorithm.

See http://nn.cs.utexas.edu/downloads/papers/stanley.cec02.pdf for the original paper.

NOTE(daiyip): PyGX supports search spaces that do not change during exploration. Therefore we do not grow the program (e.g. Neural Architecture in the paper) from a minimal program. Also, crossover can take place on any two individuals due to a fixed program structure, which will be implemented later. This algorithm illustrates how speciation is expressed in the compositional evolution framework.

Parameters:

Name	Type	Description	Default
`mutator`	`Mutator`	Mutator to use.	`Uniform()`
`population_size`	`int`	Population size for each generation.	`100`
`disjoint_coefficient`	`float`	Coefficient for DNA disjointness. Used for distance computations.	`1.0`
`matching_coefficient`	`float`	Coefficient for DNA matching. Used for distance computations.	`3.0`
`compatibility_threshold`	`float`	Threshold for max distances between two DNA in the same species.	`0.4`
`remaining_ratio`	`float`	Ratio of best individuals in a species to remain.	`0.6`
`seed`	`int \| None`	Random seed. If None, use the current system time.	`None`

Returns:

Type	Description
`Evolution`	An `Evolution` object that represents the NEAT algorithm.

Source code in pygx/algo/evolution/_neat.py

def neat(
    mutator: base.Mutator = mutators.Uniform(),
    population_size: int = 100,
    disjoint_coefficient: float = 1.0,
    matching_coefficient: float = 3.0,
    compatibility_threshold: float = 0.4,
    remaining_ratio: float = 0.6,
    seed: int | None = None,
) -> base.Evolution:
    """NEAT Algorithm.

    See http://nn.cs.utexas.edu/downloads/papers/stanley.cec02.pdf for the
    original paper.

    NOTE(daiyip): PyGX supports search spaces that do not change during
    exploration. Therefore we do not grow the program (e.g. Neural Architecture
    in the paper) from a minimal program. Also, crossover can take place on any
    two individuals due to a fixed program structure, which will be implemented
    later. This algorithm illustrates how speciation is expressed in the
    compositional evolution framework.

    Args:
      mutator: Mutator to use.
      population_size: Population size for each generation.
      disjoint_coefficient: Coefficient for DNA disjointness. Used for distance
        computations.
      matching_coefficient: Coefficient for DNA matching. Used for distance
        computations.
      compatibility_threshold: Threshold for max distances between two DNA in
        the same species.
      remaining_ratio: Ratio of best individuals in a species to remain.
      seed: Random seed. If None, use the current system time.

    Returns:
      An `Evolution` object that represents the NEAT algorithm.
    """
    # pylint: disable=no-value-for-parameter
    return base.Evolution(
        reproduction=(
            # Get the living species from the population.
            base.GlobalStateGetter(key='living_species')
            # Select species proportional to their scaled average fitness.
            >> selectors.Proportional(
                n=population_size, weights=scaled_average_fitness()
            )
            .for_each(
                # Randomly select 1 member from each species's top performers.
                (lambda x: x.members)
                >> selectors.Top(n=remaining_ratio)
                >> selectors.Random(n=1, seed=seed)
            )
            .flatten()
            >> mutator
        ),
        population_init=(pg.geno.Random(seed=seed), population_size),
        population_update=(
            # Keep only the individuals from the latest generation in the
            # population.
            selectors.Top(n=1, cluster=True, key=base.get_generation_id)
            # Speciate new individuals that are recently added to the population.
            >> speciate(
                distance=compatibility_distance(
                    disjoint_coefficient=disjoint_coefficient,
                    matching_coefficient=matching_coefficient,
                ),
                distance_threshold=compatibility_threshold,
            )
        ),
    )

nsga2 ¶

nsga2(
    mutator: Mutator = Uniform(),
    population_size: int = 100,
    seed: int | None = None,
) -> Evolution

NSGA-II: A multi-objective evolutionary search algorithm.

For reference and for citations, please use: https://ieeexplore.ieee.org/document/996017

Parameters:

Name	Type	Description	Default
`mutator`	`Mutator`	Mutator to use.	`Uniform()`
`population_size`	`int`	Population size, which will be used as both batch size for proposing new individuals and tourament size for finding the elites among recently added populations.	`100`
`seed`	`int \| None`	Random seed for initializing the population. If None, the system time will be used.	`None`

Returns:

Type	Description
`Evolution`	An `Evolution` object.

Source code in pygx/algo/evolution/_nsga2.py

def nsga2(
    mutator: base.Mutator = mutators.Uniform(),
    population_size: int = 100,
    seed: int | None = None,
) -> base.Evolution:
    """NSGA-II: A multi-objective evolutionary search algorithm.

    For reference and for citations, please use:
    https://ieeexplore.ieee.org/document/996017

    Args:
      mutator: Mutator to use.
      population_size: Population size, which will be used as both batch size for
        proposing new individuals and tourament size for finding the elites among
        recently added populations.
      seed: Random seed for initializing the population. If None, the system time
        will be used.

    Returns:
      An `Evolution` object.
    """
    # pylint: disable=no-value-for-parameter
    return base.Evolution(
        # Reproduction is to simply select the next elite and mutate it.
        reproduction=next_elite() >> mutator,
        population_init=(pg.geno.Random(seed=seed), population_size * 2),
        population_update=(
            # Take previous elites and unprocessed population as input to compute
            # the new elites.
            base.GlobalStateGetter(key='elites', default=[]) + base.Identity()
            # Apply non-dominated sorting, which returns a list of frontiers.
            # Each frontier is a list of DNA.
            # NOTE(daiyip): We converts the functor into a Lambda operation here
            # in order to call `for_each`.
            >> base.Lambda(fn=nondominated_sort())
            .for_each(
                # Apply crowding distance sort on each frontier, and flatten
                # their output into a single list.
                crowding_distance_sort()
            )
            .flatten()
            # Choose the first N (N=population_size) individuals as elites.
            # Reset the next cursor.
            >> (
                selectors.First(n=population_size)
                .as_global_state('elites')
                .set_global_state('elite_cursor', 0)
            )
            # We update the elites only when unprocessed population reaches the
            # population limit.
        ).if_true(lambda x: len(x) >= population_size),
        multi_objective=True,
    )

regularized_evolution ¶

regularized_evolution(
    mutator: Mutator = Uniform(),
    population_size: int = 100,
    tournament_size: int = 10,
    seed: int | None = None,
) -> Evolution

Regularized Evolution algorithm.

https://www.aaai.org/ojs/index.php/AAAI/article/view/4405.

Parameters:

Name	Type	Description	Default
`mutator`	`Mutator`	Mutator to use.	`Uniform()`
`population_size`	`int`	Population size. Must be larger than tournament size.	`100`
`tournament_size`	`int`	Tournament size.	`10`
`seed`	`int \| None`	Random seed. If None, the current system time is used as seed.	`None`

Returns:

Type	Description
`Evolution`	An `Evolution` object.

Source code in pygx/algo/evolution/_regularized_evolution.py

def regularized_evolution(
    mutator: base.Mutator = mutators.Uniform(),
    population_size: int = 100,
    tournament_size: int = 10,
    seed: int | None = None,
) -> base.Evolution:
    """Regularized Evolution algorithm.

    https://www.aaai.org/ojs/index.php/AAAI/article/view/4405.

    Args:
      mutator: Mutator to use.
      population_size: Population size. Must be larger than tournament size.
      tournament_size: Tournament size.
      seed: Random seed. If None, the current system time is used as seed.

    Returns:
      An `Evolution` object.
    """
    if tournament_size < 2:
        raise ValueError(
            f'`tournament_size` must be no less than 2. '
            f'Encountered: {tournament_size}'
        )
    if population_size < tournament_size:
        raise ValueError(
            f'The value of `population_size` ({population_size}) must be no '
            f'less than the value of `tournament_size` ({tournament_size}).'
        )
    return base.Evolution(
        reproduction=(
            selectors.Random(n=tournament_size, seed=seed)
            >> selectors.Top(n=1)
            >> mutator
        ),
        population_init=(pg.geno.Random(seed=seed), population_size),
        population_update=selectors.Last(n=population_size),
    )

options: show_root_heading: false show_root_toc_entry: false members_order: source heading_level: 2

pygx.algo.evolution¶

evolution ¶

hill_climb ¶

neat ¶

nsga2 ¶

regularized_evolution ¶

`pygx.algo.evolution`¶