Particle swarm optimization

Overview

Particle swarm optimization (PSO) is a gradient-free swarm method. The wiki's three cards use it in different ways. One card builds a variant that drops the velocity term in favour of a fitness-derived step. Another runs PSO as a search over feature subsets 2008.04103 §2.2. The third uses PSO as an off-the-shelf search over hyperparameters [arxiv:1810.03382 §Hyperparameter Tuning].

The variant card treats PSO's velocity-based update as its baseline 1904.05226 §I 1904.05226 §IV. It says that update needs several coefficients tuned by hand, while its own variant needs one [arxiv:1904.05226 §IV]. The variant calls its step "pace". That quantity is not the PSO velocity.

The wiki does not yet hold a PSO-origin paper card. The equations and default coefficients of the baseline PSO are therefore not stated on this page. Every claim about the variant comes from its card 1904.05226 §I 1904.05226 §IV.

Variants

Fitness-dependent step (FDO)

The variant keeps a population of scouts and drops the velocity term. Each scout's step length and direction come from a weight: the absolute value of the ratio of the best scout's fitness to the scout's own fitness, minus a weight factor wf 1904.05226 §IV. A random factor in [-1, 1] sets the sign and the size of the move. The paper says a Lévy flight is used for this factor, but it gives no exponent or scale 1904.05226 §IV. The variant also keeps the last step that improved a scout and tries it again when a new step fails 1904.05226 §IV. Card: Fitness Dependent Optimizer: Inspired by the Bee Swarming Reproductive Process.

The paper calls wf the only parameter to tune. It sets wf to 0 by default and to 1 for two of the test functions 1904.05226 §V.1. The per-function values are not in the authors' code, so expect to tune wf on your own problem 1904.05226 §V.1.

PSO as a feature-selection wrapper

Here PSO searches over subsets of input features. Wrapper methods train a classifier for each candidate subset, so the search is scored by that classifier 2008.04103 §2.2. The survey runs one wrapper per swarm family, so PSO's numbers stand for one method, not for the family [arxiv:2008.04103 §4.3].

On SVM, PSO has the highest wrapper average over six UCI datasets, 89.35 %, with ACO second at 88.85 % 2008.04103 §4.4 fig. 1. On AdaBoost it is first at 88.92 % 2008.04103 §4.4 fig. 3. On Naive Bayes it is second, at 89.08 %, behind COA at 89.24 % 2008.04103 §4.4 fig. 2. These gaps are small and the survey runs no significance test; the Naive Bayes gap falls within the per-dataset standard deviations 2008.04103 §4.4 tab. 4. In the filter setting PSO is second on SVM, at 78.82 %, behind ACO [arxiv:2008.04103 §4.4] fig. 4. The survey gives PSO's mean wrapper run time as 38.4 seconds, the lowest of the six methods in its table 2008.04103 tab. 6. The population size, iteration count and fitness function used for PSO are not stated 2008.04103 §4. Card: Review of Swarm Intelligence-based Feature Selection Methods.

PSO as a hyperparameter search

Here PSO is not the model. It is the procedure that picks a model's hyperparameters from predefined ranges. The paper runs PSO for 50 iterations, and each candidate configuration is scored with 6-fold cross-validated Harrell's C 1810.03382 §Hyperparameter Tuning. The search is run with the Optunity library 1810.03382 §Hyperparameter Tuning. The paper uses the configuration from the final iteration, not the best one seen during the search 1810.03382 §Hyperparameter Tuning. The passage gives neither the swarm size nor the update coefficients. Card: Deep learning cardiac motion analysis for human survival prediction.

The search also sits inside the paper's internal validation. Each bootstrap sample repeats the full training and hyperparameter search 1810.03382 §Internal Validation.

When to use which

Implementation sketch

Language-agnostic pseudocode of the FDO step. The velocity-based PSO update is not written here, because its source is not in the wiki. Minimisation only; the paper's maximisation variant swaps the ratio 1904.05226 §IV.

# One FDO iteration, minimisation  [arxiv:1904.05226 §IV]
def fdo_iteration(positions, paces, f, wf):
    # Best scout of this iteration, taken once before the loop  [§IV]
    best = positions[argmin(f(positions))]
    for i in range(len(positions)):
        # Weight is 0 when the scout's own fitness is zero  [fig. 3]
        if f(positions[i]) == 0:
            weight = 0
        else:
            weight = abs(f(best) / f(positions[i])) - wf  # [eq. 2]
        # Random factor in [-1, 1]  [§IV]
        r = random_uniform(-1, 1)
        # Pace from the position, or from the distance to the best  [eq. 3-5]
        if weight == 0 or weight == 1:
            pace = positions[i] * r
        elif r < 0:
            pace = (positions[i] - best) * weight * -1  # [eq. 4]
        else:
            pace = (positions[i] - best) * weight  # [eq. 5]
        candidate = positions[i] + pace  # [eq. 1]
        if f(candidate) < f(positions[i]):
            positions[i], paces[i] = candidate, pace
        elif paces[i] is not None:
            # Second try with the saved pace  [§IV] [fig. 3]
            candidate = positions[i] + paces[i]
            if f(candidate) < f(positions[i]):
                positions[i] = candidate
    return positions

The signs in equations 4 and 5 are hard to read in the card's source, and the authors' code differs from the paper on several rules. Check the card's "Paper vs code" section before you port anything.

Contradictions

• TF8 result. The paper's text says FDO is poor on TF8 even though it beats PSO there 1904.05226 §V.1. The reported means in the card's table show PSO's TF8 mean as lower than FDO's on this minimisation test 1904.05226 tab. 2. Not resolved here.
• Paper and code. The paper's zero-fitness rule and its pace rule for weight 0 are not what the authors' code does 1904.05226 §IV 1904.05226 §V.1. The card lists these differences. Results from the code do not reproduce the paper's TF14–TF19 numbers 1904.05226 §V.1.
• Search method, paper and code. The paper uses PSO for hyperparameter search 1810.03382 §Hyperparameter Tuning. The card reports that the authors' default configuration uses grid search instead, while the demo script for the network uses PSO 1810.03382 §Paper vs code.
• Wrapper winner by classifier. PSO leads the survey's wrapper averages on SVM and AdaBoost, but COA leads on Naive Bayes 2008.04103 §4.4 fig. 1 fig. 2 fig. 3. The survey does not show that a single method wins across classifiers. Not resolved here.

Papers

• Fitness Dependent Optimizer: Inspired by the Bee Swarming Reproductive Process: a PSO-based variant that replaces the velocity with a fitness-derived step. Author-reported results only.
• Deep learning cardiac motion analysis for human survival prediction: uses PSO as a hyperparameter search for a survival model. Author-reported, single-centre results only.
• Review of Swarm Intelligence-based Feature Selection Methods: a survey of swarm feature selection that runs one PSO wrapper and one filter per family, on six UCI datasets. Author-run results, no code.