Metaheuristic optimization

Overview

A metaheuristic is a general search procedure that does not need the gradient of the objective and makes few assumptions about its shape. The paper that motivates this page describes nature-inspired metaheuristics as a way to escape local optima, and notes that they offer few guarantees on hard multimodal problems 1904.05226 §I.

The invariant shared by the variants is a population of candidate solutions that is updated until a fixed budget runs out: a fixed number of rounds in the swarm and surrogate GA cards, a cap of 100,000 fitness evaluations in the membrane card 2609.12756 §4.1, a budget of 220 simulator runs in the MARTENS card 2410.19277 §3.1, and six hours of fuzzing in the SimADFuzz card 2412.13802 §5.2.2. In the feature-selection cards the candidate is a subset of features, and in the review's wrapper methods each subset is scored by a classifier 2008.04103 §2.2. In the swarm variant, each round every candidate proposes a new position from its current position and from information about the best candidate so far, and keeps the proposal if it scores better 1904.05226 §IV. The GA variant names a genetic algorithm with population 20 and 100 generations, but its selection, recombination and mutation steps are not stated in the paper 2609.16066 §4.3.

The paper also argues that no single metaheuristic is best on every problem, so a new method is worth proposing when it helps on some problems 1904.05226 §I. Treat that as the reason the design space is wide, not as a ranking.

The second card changes where the cost sits. Its search does not run the simulator for each candidate. It queries a trained neural surrogate, which is cheap, and runs the simulator only on the designs the search returns 2609.16066 §4.3. The two testing cards do the opposite: each candidate is run in the simulator, and the search cost is the simulator's cost 2410.19277 §3.1 2412.13802 §5.1.

The routing card is not a population method. It trains a neural network that builds routing solutions one stop at a time, with several routes grown in parallel rather than a population of candidates that is improved 2608.14156 §3. It is listed here because its comparison baseline is a metaheuristic: Google OR-Tools, including its metaheuristic search, which the card uses as the reference at each size 2608.14156 §5.2 2608.14156 §5.3. Read its results as a trade-off against a metaheuristic, not as a metaheuristic variant.

Variants

Fitness Dependent Optimizer (swarm, weighted step)

Each agent (a "scout") takes a step whose length and direction depend on the ratio of the best candidate's fitness to its own, minus one weight factor wf, plus a random factor drawn from [-1, 1] 1904.05226 §IV [arxiv:1904.05226 eq. 2]. The paper also reuses the last step that improved an agent and tries it again when the new step fails 1904.05226 fig. 3. Card: Fitness Dependent Optimizer: Inspired by the Bee Swarming Reproductive Process.

Reported results are author-reported. On 19 classical functions (10-D, 30 agents, 500 iterations, 30 runs) the authors say the method generally does better on the first six functions and on several composite ones, and worse on some others such as TF7 1904.05226 §V.1 1904.05226 tab. 2. On 10 CEC-2019 functions the text says it outperforms the compared methods except on CEC06 1904.05226 §V.2 1904.05226 tab. 3.

Membrane-split artificial protozoa optimizer (population splitting, roulette guide)

The base is the artificial protozoa optimizer (APO). It moves each candidate with one of four operators: foraging toward a guide, heterotrophic foraging, dormancy and reproduction 2609.12756 §2.1. The membrane variant adds two changes. First, each iteration it measures a volume-based diversity value. When that value falls below a threshold ε, the whole population is one group; otherwise it is split at random into m groups, each updated separately and then merged again 2609.12756 §3.1 2609.12756 alg. 1. The number m is drawn every iteration with m_max = 4 2609.12756 eq. 18. Second, the guide for autotrophic foraging is picked by a roulette wheel over a score that mixes fitness and distance to the best solution 2609.12756 §3.2 2609.12756 eq. 19 2609.12756 eq. 21. Card: MAAPO: an innovative membrane algorithm based on artificial protozoa optimizer for multilevel threshold image segmentation.

Reported results are author-reported. On 30 CEC2017 functions at 10-D, with 51 runs and 13 algorithms, the method has the best average Friedman rank (3.35), ahead of MAQUATRE (3.37) and APO (3.55) 2609.12756 §4.5. Against plain APO it wins 8 functions and loses none 2609.12756 tab. 5. On multilevel thresholding of three RGB images it has the best average rank for Kapur entropy on all three metrics, and for Otsu only on SSIM; for Otsu PSNR PSO ranks better, and for Otsu FSIM DE does 2609.12756 tab. 11 2609.12756 tab. 12. Its average runtime is 1.38 s against 0.81 s for APO on the authors' laptop 2609.12756 tab. 7.

Particle swarm optimization (baseline)

The FDO paper uses PSO as the base for its update style and as a comparison method 1904.05226 §I 1904.05226 §V.1. FDO replaces PSO's velocity term with a fitness-derived step 1904.05226 §I. The PSO page is Particle swarm optimization. The PSO comparison numbers in the FDO paper are taken from another study rather than re-run by the authors 1904.05226 §V.1. In the feature-selection review, PSO is also the strongest wrapper on average for SVM and AdaBoost, but not for Naive Bayes 2008.04103 §4.4.

Genetic algorithm and NSGA-II over a neural surrogate

The compressor-design card runs a genetic algorithm (GA) for single-objective tasks and NSGA-II for multi-objective tasks. Both search a trained neural operator instead of the CFD solver. The GA uses a population of 20 over 100 generations, and NSGA-II a population of 30 over 100 generations 2609.16066 §4.3. Card: Neural-operator surrogate for compressor-cascade flow fields.

The paper reports five single-objective tasks, one per performance parameter. For efficiency, the surrogate predicts 0.871 at the optimum against a reference of 0.854, and CFD gives 0.871 at the same design 2609.16066 tab. 9. Three multi-objective tasks are reported with the highest-efficiency point of each solution set 2609.16066 §4.3 2609.16066 tab. 10. Every optimal design was checked with CFD 2609.16066 §4.3.

The authors state that the surrogate-based optimisation took 121 s, where earlier work needed 1000 CFD runs 2609.16066 §4.3. One CFD run takes about 800 s on the authors' CPU 2609.16066 §2.2. These are author-reported timings; the paper does not state the hardware for the surrogate's prediction time.

Genetic search for failing simulator scenarios (testing)

Here the search looks for inputs that make a system fail, not for the best design. Both cards run every candidate in a simulator and record which ones fail, so the search is bounded by simulator cost rather than by a surrogate.

MARTENS searches a pick-and-place scene in Isaac Sim for failures of a detector 2410.19277 §2.2. A test is a chromosome with an (x, y, r) triple per movable box and a lighting level 2410.19277 §2.2. The fitness is a weighted sum of the largest position error and the largest rotation error across the boxes, with both weights 0.5 2410.19277 eq. 1 2410.19277 §3.1. The search is a single-objective GA with one-point crossover, two mutation operators and a cosine-distance duplicate filter 2410.19277 §2.2. The failing tests then fine-tune the detector 2410.19277 §2.5. Card: In-Simulation Testing of Deep Learning Vision Models in Autonomous Robotic Manipulators.

Author-reported results, against random search with the same budget of 220 evaluations and five runs each: the GA finds about 50% more failing tests in use case 1 and 26% more in use case 2 2410.19277 tab. 2 2410.19277 tab. 3. Its failures are more spread out in features, with a large effect in use case 1 and a medium one in use case 2, but the severity spread does not differ significantly 2410.19277 tab. 4. Fine-tuning on the failing images makes more than 99% of the failing tests pass when re-run 2410.19277 tab. 5 2410.19277 tab. 6. A detector fine-tuned this way reaches mAP 0.948 and 0.892 on the real test splits, against 0.806 and 0.755 for a detector trained on real images only 2410.19277 tab. 8. Those real sets have about 100 images per use case, and no variance across seeds is reported for the real-data models 2410.19277 §3.2.3.

SimADFuzz fuzzes a self-driving stack in CARLA 2412.13802 §4.1. A chromosome holds the ego route, the NPC routes, the pedestrian routes and the weather 2412.13802 §4.2. NSGA-II selects offspring on four objectives: a Transformer score over the simulation trace, a classifier over static road features, the minimum ego distance, and the number of unique violations 2412.13802 §4.2.1. The Transformer is a learned score, not a stand-in for the simulator; each offspring is still simulated 2412.13802 §4.1 2412.13802 §5.1. Mutation removes NPCs that stay still or move away from the ego vehicle, and places new ones 2412.13802 §4.2.3 2412.13802 alg. 1. Card: SimADFuzz: Simulation-Feedback Fuzz Testing for Autonomous Driving Systems.

Author-reported results on InterFuser, Town03, with one shared seed set: 35 unique violations in six hours, against 26 for TM-Fuzzer, 18 for DriveFuzz and 3 for AV-Fuzzer 2412.13802 §5.2.2 2412.13802 fig. 8. In a three-hour ablation the full method finds 24 against 14 [arxiv:2412.13802 §5.2.1] 2412.13802 fig. 7. The authors name one system and one map as a limit on external validity 2412.13802 §5.3.

Wrapper feature selection with swarm methods (review)

A feature subset is the candidate, and a classifier trained on the subset scores it. The review by Rostami, Berahmand and Forouzandeh covers 11 swarm families (PSO, ACO, ABC, DE, GSA, FA, BA, COA, GWO, WOA and SSA) and the feature selection work built on each 2008.04103 §3 [arxiv:2008.04103 tab. 2]. Its own experiment runs one wrapper per family and four filters on six UCI datasets, with SVM, Naive Bayes and AdaBoost, 10 runs each and a random 66/34 train/test split 2008.04103 §4 2008.04103 §4.3. The paper does not state population sizes, iteration counts or stopping rules for any method, so the original method papers are needed to reproduce it 2008.04103 §4. Card: Review of Swarm Intelligence-based Feature Selection Methods.

Author-reported, averaged over the six datasets: PSO has the highest wrapper accuracy on SVM (89.35%) and AdaBoost (88.92%). On Naive Bayes, COA is first (89.24%) and PSO second (89.08%) 2008.04103 §4.4 [arxiv:2008.04103 fig. 1] 2008.04103 fig. 2 2008.04103 fig. 3. The text says PSO does better than the other wrappers in most cases, but the paper gives no significance test, and the gaps are within the per-dataset standard deviations 2008.04103 §4.4 2008.04103 tab. 4. Among filters, ACO has the highest average on SVM (79.52%) against 78.82% for PSO 2008.04103 §4.4.

Cuttlefish feature selection and elephant-herd weight tuning (clinical)

The heart-disease card combines two population searches. A modified cuttlefish algorithm (MCFA) selects features, and an elephant-herd variant (AEHO) sets the weights of a small fully connected network that the paper calls MDCNN 2012.05999 §II-B 2012.05999 §II-C 2012.05999 §II-D. The paper does not state population sizes, generation limits, clan counts or the fitness function for AEHO 2012.05999 §II-D 2012.05999 §II-E. Card: An IoT Framework for Heart Disease Prediction based on MDCNN Classifier.

Author-reported: 98.2% accuracy on the 4000-record Framingham set, against 88.3% for logistic regression and 83.8% for the baseline deep network 2012.05999 tab. 8. These are single results without variance across runs, and the train/test split and the baseline architecture are not stated 2012.05999 §IV-B. Part of the sensor data is generated with pseudo-random numbers 2012.05999 §IV-A.

When to use which

The wiki has eight papers on this page, so the table compares their methods with the constraints they report. It does not rank metaheuristics against each other.

Choose the weight factor per problem. The FDO paper uses wf = 1 for two benchmark functions and wf = 0 elsewhere 1904.05226 §V.1, so a single default is not shown to transfer.

A surrogate in the loop has a cost too. At the optimum, the surrogate can be wrong: for pressure loss, the surrogate predicts 0.115 and CFD gives 0.103, a related error of 11.87% 2609.16066 tab. 9. The paper also says the optimal solutions lie outside the training-sample range 2609.16066 §4.3, so check the chosen designs with the simulator before trusting them.

Implementation sketch

Language-agnostic pseudocode of the swarm variant's core. The zero-fitness rule and the retry step follow the paper's figure 1904.05226 fig. 3. Check the signs in the step equations against the PDF before coding 1904.05226 eq. 4 1904.05226 eq. 5.

# Population search, minimisation  [arxiv:1904.05226 §IV]
def swarm_search(f, n, T, wf, lower, upper):
    # Random start inside the bounds; bounds handling is not stated  [§IV]
    x = random_uniform(lower, upper, shape=(n, dims))
    # Last accepted step per agent, empty at the start  [fig. 3]
    pace = [None] * n
    for t in range(T):
        # Best candidate of this iteration  [§IV]
        best = x[argmin(f(x))]
        for i in range(n):
            # Zero own fitness gives weight 0  [fig. 3]
            w = 0 if f(x[i]) == 0 else abs(f(best) / f(x[i])) - wf  # [eq. 2]
            # Random factor in [-1, 1]; the paper names a Levy flight  [§IV]
            r = random_uniform(-1, 1)
            # Weight 0 or 1 uses the position itself  [eq. 3]
            step = x[i] * r if w in (0, 1) else (x[i] - best) * w * sign(r)
            # Accept the new candidate only if it is better  [eq. 1] [fig. 3]
            cand = x[i] + step
            if f(cand) < f(x[i]):
                x[i], pace[i] = cand, step
            elif pace[i] is not None and f(x[i] + pace[i]) < f(x[i]):
                # Otherwise retry the last accepted step  [fig. 3]
                x[i] = x[i] + pace[i]
    return argmin(f(x))

Where variants differ: the random factor's distribution, bounds handling and the exact sign convention in the step equations. The paper gives no bounds rule §IV, and the Lévy flight has no stated exponent or scale §IV.

For the surrogate pattern, the same kind of loop runs with f replaced by the surrogate's prediction, and the simulator checks only the returned designs 2609.16066 §4.3. The GA's selection, recombination and mutation operators are not stated, so the implementer has to choose them 2609.16066 §4.3.

For the simulation-testing loop, the shared core is: run each candidate in the simulator, record pass or fail, drop near-duplicates, breed, and stop at a budget 2410.19277 §2.2 2412.13802 §5.1. Neither card states every operator. MARTENS does not give its parent-selection rule, its replacement scheme or the number of generations, and its cut-point range is not given 2410.19277 §2.2. SimADFuzz's stopping rule is the time budget alone 2412.13802 §5.2.

For the membrane variant, each iteration first computes the diversity value 2609.12756 eq. 15. Below ε the population is updated as one group; otherwise it is split into m random groups, each updated, and then merged 2609.12756 alg. 1. The card's pitfalls list open points to settle before coding: whether each solution gets one APO operator or all four per iteration 2609.12756 alg. 1 2609.12756 §2.1; whether the pool fraction pf is used at all 2609.12756 eq. 11; and which "best" the distance term measures 2609.12756 §3.2. The paper does not state these.

Contradictions

None between the cards on the same claim. Their results measure different things: benchmark functions in the FDO card, a compressor-design task in the second, benchmark suites plus image thresholding in the membrane card, and failures found in simulators in the two testing cards, a routing construction task in the routing card, and classifier accuracy on feature subsets in the two feature-selection cards. Their numbers are therefore not comparable. The review's and the heart-disease card's feature-selection results are on different data and classifiers, so neither confirms the other. The heart-disease card's own tables also disagree on feature counts 2012.05999 tab. 3 2012.05999 tab. 7. The routing card's early-solution gains also differ by size: about up to 3% at 50 customers 2608.14156 §5.1, 15 to 200 percent at 100 and 200 2608.14156 §5.2, and about 50% at 400 and 1000 2608.14156 §5.3. The paper gives these in the text and plots rather than in a table. Within the FDO card, the PSO, GA and DA classical numbers come from another study, not from the authors' runs 1904.05226 §V.1, so those comparisons mix sources. The compressor card compares its optimisation only with the authors' earlier work, not with other metaheuristics 2609.16066 §4.3. The membrane card's ranking margin over MAQUATRE is 0.02 2609.12756 §4.5, and the card's own win-loss counts against MAQUATRE are even at 10 and 10 2609.12756 §4.5.

Inside the testing cards, the printed numbers do not always add up. In the MARTENS tables, the row sums do not match the printed totals, so the gains over random search are the card's reading of the counts 2410.19277 tab. 2 2410.19277 tab. 3. In SimADFuzz, the text gives a margin of 27 over DriveFuzz, but its six-hour table gives 18 for DriveFuzz, which implies 17 2412.13802 §5.2.2 2412.13802 §7. Check the source before quoting either margin.

Papers

• Fitness Dependent Optimizer: Inspired by the Bee Swarming Reproductive Process: a swarm method whose step is scaled by a fitness-derived weight, with a random factor and a reused step after success; author-reported benchmark results.
• MAAPO: an innovative membrane algorithm based on artificial protozoa optimizer for multilevel threshold image segmentation: APO with membrane-style splitting and merging of the population, and a roulette fitness-distance rule for the guide; author-reported CEC2017 and thresholding results.
• Neural-operator surrogate for compressor-cascade flow fields: GA and NSGA-II run over a trained neural operator for compressor-blade design; author-reported optima, each checked with CFD.
• In-Simulation Testing of Deep Learning Vision Models in Autonomous Robotic Manipulators: a single-objective GA searches a simulated pick-and-place scene for detector failures, then fine-tunes the detector on them; author-reported gains over random search and on real images.
• SimADFuzz: Simulation-Feedback Fuzz Testing for Autonomous Driving Systems: NSGA-II genetic fuzzer for self-driving systems in CARLA, with a Transformer score over the simulation trace; author-reported violation counts against three fuzzers on one system.
• Attention-based RL for pickup-and-delivery routing with time windows: an attention-based reinforcement-learning route builder with a pickup-order mask and a soft penalty; OR-Tools, including its metaheuristic search, is the baseline. Author-reported results only.
• Review of Swarm Intelligence-based Feature Selection Methods: a survey of 11 swarm families for feature selection, with one wrapper and one filter per family run on six UCI datasets; author-run averages, no significance test.
• An IoT Framework for Heart Disease Prediction based on MDCNN Classifier: cuttlefish-based feature selection and elephant-herd tuning of a small network for heart-disease classification; author-reported accuracy, with key settings not stated.