Research map / Learning theory and algorithms / Combinatorial and search optimization
Fast Contiguous Somatic Hypermutations for Single-Objective Optimisation and Multi-Objective Optimisation Via Decomposition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Fast CHM, a contiguous somatic hypermutation operator that evaluates intermediate solutions with a power-law probability so it matches standard bit mutation on hillclimbing while keeping CHM's large-jump ability, and proves runtime gains for single- and multi-objective (MOEA/D) problems.
Problem
Contiguous somatic hypermutation (CHM) is slow in hillclimbing phases (e.g., ONEMAX needs Θ(n² log n) vs. O(n log n) for SBM), limiting its use in artificial immune systems and evolutionary optimisation.
Approach
Instead of fixing a contiguous interval length, Fast CHM flips bits sequentially from a random start and evaluates the intermediate string after each flip with a symmetric power-law probability (plus a 1/n floor), returning the best evaluated solution; this makes small-distance evaluations frequent while preserving the chance of evaluating large contiguous jumps.
Key results
- Fast (1+1) BCA optimises ONEMAX in O(n log n) expected evaluations, versus Θ(n² log n) for CHM.
- MOEA/D with Fast CHM finds the whole Pareto front of ONEMINMAX and DEC-OBJ-MOP in O(N n log n), a linear-factor speed-up over MOEA/D with CHM (O(N n² log n)).
- Fast CHM matches CHM's Θ(n²) LEADINGONES and Ω(n²) escape ability, keeping the O(n² log n) to O(n²) speed-up over SBM-type behavior on CLOB-like and MINBLOCKS problems where large contiguous flips are needed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace CHM with Fast CHM | (1+1) BCA · OneMax | expected runtime: O(n2 log n) -> O(n log n) | Helped |
| replace CHM with Fast CHM | (1+1) BCA · Leading Ones | expected runtime: O(n2 log n) -> O(n2) | Helped |
| replace CHM with Fast CHM | (1+1) BCA · CLOB | expected runtime: O(n2 log n) -> O(n2 log n) | No clear effect |
| replace CHM with Fast CHM | (1+1) BCA · Min Blocks | expected runtime: O(n2) -> O(n2) | No clear effect |
| replace CHM with Fast CHM | (1+1) BCA · Vertex Cover (Bn,ϵ inst.) | expected runtime: O(n2 log n) -> O(n2 log n) | No clear effect |
| replace CHM with Fast CHM | (1+1) BCA · Vertex Cover (2 approx) | expected runtime: O(m2 log m) -> O(m log m) | Helped |
| replace CHM with Fast CHM | (1+1) BCA · MaxCut (MC(S,P) inst.) | expected runtime: O(n3) -> O(n3) | No clear effect |
| replace CHM with Fast CHM | MOEA/D · OMM, N = O(1) | expected runtime: O(n2 log n) -> O(n log n) | Helped |
| replace SBM with Fast CHM | MOEA/D · OMM, N = n + 1 | expected runtime: O(n2 log n) -> O(Nn log n), Th.3 | Mixed |
| replace CHM with Fast CHM | MOEA/D · LOTZ, N = O(1) | expected runtime: O(n2 log n) -> O(n2 log n), Cor.1 | No clear effect |
| replace SBM with Fast CHM | MOEA/D · LOTZ, N = n + 1 | expected runtime: O(n3) -> O(Nn2), Th.4 | Mixed |
| replace SBM with Fast CHM | MOEA/D · Dec-obj-MOP, N = n + 1 | expected runtime: O(n2 log n) -> O(Nn log n), Th.5 | Mixed |
Surprising findings
- Fast CHM is asymptotically as fast as SBM on ONEMAX and LEADINGONES-type hillclimbing while retaining CHM's escape ability, despite CHM being a logarithmic or linear factor slower in those phases.
Limitations
- Analysis uses r = 1 for simplicity; practical use requires r slightly below 1 for convergence, which is not analysed.
- Results are theoretical runtime bounds with no empirical experiments reported.
- MOEA/D analysis does not include neighbouring subproblem exchange of solutions, following prior literature.
Experimental setup
Benchmarks: ONEMAX LEADINGONES CLOB MINBLOCKS vertex cover ONEMINMAX LOTZ DEC-OBJ-MOP PLATEAU-MOP
Metrics: expected optimisation time (function evaluations)
Baselines: standard bit mutation (SBM) CHM (1+1) EA MOEA/D with SBM MOEA/D with CHM GSEMO SEMO
Builds on: CHM (Jansen and Zarges 2011) MOEA/D hypermutations with mutation potential
Closest papers by meaning
- Bayesian Optimization of Antibodies Informed by a Generative Model of Evolving Sequences (ICLR 2025 · similarity 0.84)
- Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.83)
- Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations (AAAI 2024 · similarity 0.81)
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.81)
- Differentiable extensions with rounding guarantees for combinatorial optimization over permutations (NeurIPS 2025 · similarity 0.81)
- Ultrafast classical phylogenetic method beats large protein language models on variant effect prediction (NeurIPS 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.