# AHD-CMA — Algorithm reference

Mathematical exposition of the released AHD-CMA. See
`Research_Proposal_AHD-CMA_LoRA_ViT.md` for the original scientific
specification and `docs/spec_deviations.md` for every place the
implementation diverges from that spec.

---

## 1. Problem setting

Given a fitness function `f : [lb, ub]^d -> R` (we minimise) and a
budget of `T` generations with population `N`, find
`x* in argmin f(x)`.

For the LoRA-tuning use case the search space is the 11-dimensional
mixed encoding from the proposal's §14 appendix; see
`src/ahdcma/search_space/encoder.py`.

## 2. Initialization (chaotic Tent map)

The Tent map on `[0, 1]` is

    T_mu(z) = z / mu                 if z < mu
              (1 - z) / (1 - mu)     otherwise

For `mu = 0.499` the orbit is uniformly ergodic. We iterate per
dimension to draw `N` quasi-uniform samples and rescale to the
problem box. See `src/ahdcma/search_space/tent_map.py`.

We use `mu = 0.499` (not `0.5`) because exact `0.5` collapses to a
fixed point for any binary-fraction `z_0`.

## 3. CMA-ES (via pycma)

CMA-ES is wrapped from the `cma` package. The wrapper calls
`ask` -> evaluate -> `tell` exactly once per generation; bounds are
provided to pycma's `BoundaryHandler` and we `clip` once more before
fitness evaluation for robustness. See
`src/ahdcma/algorithms/cmaes_wrapper.py`.

## 4. Dhole Optimization Algorithm (DOA)

Per Ghasemi et al. (Cluster Computing 2025), reproduced in Khlie et
al. (ETASR 15(3), 2025):

* **Phase 1 — exploration / "attack toward prey":**

      X_mean = mean(X_t)
      P      = X_best + r * (X_mean - X_worst),    r ~ U(0, 1)
      x_i^P1 = x_i + r * (P - I * x_i),    I ∈ {1, 2}, r ~ U(0, 1)

  Greedy elitist replacement: keep `x_i^P1` only if `f(x_i^P1) <= f(x_i)`.

* **Phase 2 — exploitation / "chase":**

      x_i^P2 = x_i + (1 - 2 r) * (ub - lb) / t,   r ~ U(0, 1)

  Greedy elitist replacement.

The two phases run sequentially every iteration. DOA has only `N`
and `T` as free parameters. See `src/ahdcma/algorithms/doa.py`.

## 5. Controller (probe-then-lock + stagnation bursts)

The proposal originally used an entropy + ruggedness rule. The Phase 5
acceptance test on CEC-2022 dim=10 showed that lag-1 random-walk
autocorrelation does not separate smooth-from-rugged on the
CEC-2022 search box, and the entropy threshold collapsed every run
into EXPLORE mode. Replaced with:

1. **Probe phase**: first `stag_window` generations always run
   pure CMA-ES (mode = exploit, k_top = N).
2. **Lock-in test** at the end of probe:
   - if best fitness halved (or bigger absolute drop), or
   - if it is already below `1e-6`,
   set `cma_locked = True` for the rest of the run.
3. **Stagnation burst** (only if not locked): when the best-fitness
   improvement over the last `stag_window` generations is below
   `1e-4` of the running best (or `stag_eps`), burst into HYBRID
   mode for `hybrid_burst` generations. EXPLORE promotion is
   disabled by default (`explore_burst = 0`).
4. **Elitism**: the global best individual is always preserved, so
   a hybrid burst that produces only worse samples cannot lose
   ground.

Mode definitions:

* `exploit` — k_top = N, pure CMA-ES.
* `hybrid`  — k_top = round(0.3 N), CMA-ES on top, DOA on the rest.
* `explore` — k_top = 0, pure DOA (rarely used).

Entropy and ruggedness signals are still computed and recorded in
History so the paper's diagnostic figures work.

See `src/ahdcma/algorithms/ahd_cma.py` and the controller modules in
`src/ahdcma/controller/`.

## 6. Convergence sketch

Per Solis & Wets (1981) generalised convergence:

* **Decreasing best**: elitism guarantees `f(x_t^*) >= f(x_{t+1}^*)`.
* **Positive sampling probability**: the chaotic Tent init plus DOA's
  Phase-2 perturbation hit every measurable subset with non-zero
  probability.

Together these imply almost-sure convergence to the global optimum
under mild regularity on `f`.

## 7. Hyperparameters (defaults)

See `configs/algo/ahdcma.yaml` for the canonical config. Key knobs:

| key                                  | default | role                            |
|--------------------------------------|---------|---------------------------------|
| `population_size`                    | 20      | N                               |
| `max_generations`                    | 50      | T                               |
| `init.tent_iterations`               | 100     | Tent-map burn-in                |
| `cmaes.initial_sigma`                | 0.4     | initial CMA-ES step size        |
| `stagnation.window`                  | 8       | probe length / stagnation window|
| `stagnation.eps`                     | 1e-8    | absolute improvement floor      |
| `stagnation.hybrid_burst`            | 3       | length of hybrid burst          |
| `stagnation.explore_burst`           | 0       | length of explore burst         |
| `controller.entropy_bins`            | 10      | diagnostic only                 |
| `controller.ruggedness_walk_length`  | 10      | diagnostic only                 |