| # 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 | |
|
|
