Sprouting Mechanisms

Introduction

Sprouting mechanisms are a key component of the Hierarchic Memetic Strategy (HMS) algorithm. They determine when and where to create new demes (populations) at lower levels of the HMS tree. Effective sprouting is crucial for balancing exploration and exploitation in the search process.

The sprouting process enables HMS to focus computational resources on promising regions of the search space. When a deme at a higher level identifies a potentially valuable area, it “sprouts” a new child deme to conduct a more refined search in that region.

Available Sprouting Mechanisms

pyHMS provides several built-in sprouting mechanisms:

Nearest Better Clustering (NBC)

The NBC sprouting mechanism identifies promising points by analyzing the distance relationships between solutions in the fitness landscape. It is particularly effective for multimodal problems.

from pyhms import get_NBC_sprout
sprout_condition = get_NBC_sprout(
    level_limit=4,          # Maximum tree level depth
    gen_dist_factor=3.0,    # Generation distance factor
    trunc_factor=0.7,       # Truncation factor
    fil_dist_factor=3.0     # Filter distance factor
)

Simple Sprouting

A simpler alternative that relies on the best individual in each deme.

from pyhms import get_simple_sprout
sprout_condition = get_simple_sprout(
    far_enough=2.0,         # Minimum distance between sprouts
    level_limit=4           # Maximum tree level depth
)

Components of Sprouting Mechanisms

A sprouting mechanism in pyHMS is composed of three main components:

  1. Candidates Generator: Identifies potential solutions for sprouting

  2. Deme-Level Filters: Filter candidates at the deme level

  3. Tree-Level Filters: Apply global filters across the entire tree

from pyhms.sprout.sprout_mechanisms import SproutMechanism
from pyhms.sprout.sprout_generators import BestPerDeme
from pyhms.sprout.sprout_filters import FarEnough, LevelLimit

# Create a custom sprouting mechanism
sprout_mechanism = SproutMechanism(
    candidates_generator=BestPerDeme(),
    deme_filter_chain=[FarEnough(min_distance=2.0)],
    tree_filter_chain=[LevelLimit(limit=4)]
)

Candidates Generators

Candidates generators identify potential solutions for sprouting:

  • BestPerDeme: Selects the best individual from each deme

  • NBC_Generator: Uses Nearest Better Clustering to identify multiple candidates

Deme-Level Filters

These filters operate on candidates from individual demes:

  • FarEnough: Ensures candidates are sufficiently distant from existing demes

  • NBC_FarEnough: Similar to FarEnough but uses NBC

  • MahalanobisFarEnough: Uses Mahalanobis distance for filtering

  • DemeLimit: Limits the number of candidates per deme

Tree-Level Filters

These filters operate globally across the entire tree:

  • LevelLimit: Ensures each level doesn’t exceed a maximum number of demes

  • SkipSameSprout: Prevents sprouting at locations where demes already exist

Data Structures

pyHMS uses specialized data structures to store sprouting information:

  • DemeFeatures: Contains numerical information about the deme state

  • DemeCandidates: Stores candidate solutions and their associated features

Customizing Sprouting

For advanced users, pyHMS allows customization of sprouting mechanisms by implementing:

  1. Custom generators by extending SproutCandidatesGenerator

  2. Custom deme-level filters by extending DemeLevelCandidatesFilter

  3. Custom tree-level filters by extending TreeLevelCandidatesFilter

from pyhms.sprout.sprout_generators import SproutCandidatesGenerator
from pyhms.sprout.sprout_candidates import DemeCandidates, DemeFeatures

# Example of a custom generator
class CustomGenerator(SproutCandidatesGenerator):
    def __call__(self, tree) -> dict[AbstractDeme, DemeCandidates]:
        # Your custom logic here
        return candidates

Creating Your Own Sprouting Mechanism

To create a custom sprouting mechanism:

  1. Choose or implement a candidates generator

  2. Select or create appropriate deme-level filters

  3. Select or create appropriate tree-level filters

  4. Combine them using the SproutMechanism class

This modular approach allows for flexible experimentation with different sprouting strategies.