.. _sprout_conditions:

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.

.. code-block:: python

    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.

.. code-block:: python

    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

.. code-block:: python

    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`

.. code-block:: python

    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.