Membrane computing

Overview

Membrane computing is a model of computation inspired by cells. A P-system holds objects inside compartments, called membranes, and applies rules that split a membrane into several or merge them back 2609.12756 §2.2. The card that covers this slug uses that idea as a population-management step inside a nature-inspired optimizer, not as a model of biology.

The invariant is that the population of candidate solutions is always recombined into one set after the membranes have searched separately. The split is driven by a diversity value, not by a fixed schedule. Per §3.1 and Algorithm 1, the population is split when that value is at or above a threshold and stays whole below it 2609.12756 §3.1 2609.12756 alg. 1. The paper's plain-language summary describes the trigger the other way round, so this direction should be checked against the paper before implementation.

This page rests on a single card. Every claim below is author-reported and comes from one publication. No second paper in the wiki uses membrane computing yet.

Variants

Membrane-split population in an artificial protozoa optimizer

The base method is the artificial protozoa optimizer. Its candidate solutions forage, go dormant and reproduce 2609.12756 §2.1. The variant adds two changes. A membrane step runs first. It measures a population diversity value, mVOL, which is the population's spread divided by the search-box size, raised to the power 1/dim 2609.12756 eq. 15 2609.12756 eq. 16 2609.12756 eq. 17. If mVOL is below a threshold ε, the population stays in one membrane. Otherwise it is split into m membranes, each updated on its own, and the results are merged back 2609.12756 §3.1. The number of membranes is drawn each iteration between 2 and 4 when m_max is 4 2609.12756 eq. 18.

The second change is in the guide selection. Instead of the usual guide, a roulette wheel picks a candidate with probability proportional to a score that mixes its normalised fitness and its normalised distance to the best candidate 2609.12756 §3.2 2609.12756 eq. 19. The authors name this roulette fitness-distance balance (RFDB) rule 2609.12756 §3.2. Card: MAAPO: an innovative membrane algorithm based on artificial protozoa optimizer for multilevel threshold image segmentation.

Reported results, author-reported, on CEC2017 at 10 dimensions with 51 runs per function 2609.12756 §4.1:

• The variant has the best average Friedman rank over 13 algorithms, 3.35, against 3.37 for MAQUATRE and 3.55 for plain APO 2609.12756 §4.5. The margin over MAQUATRE is within 0.02 2609.12756 §4.5.
• Against plain APO, the variant wins on 8 of 30 functions and loses on none 2609.12756 tab. 5.
• The full variant beats the membrane-only version and the RFDB-only version on 5 functions each, and loses on none 2609.12756 tab. 5. The paper therefore reports that the full combination beats each part on this suite.
• The average runtime is 1.38 s per run, against 0.81 s for plain APO 2609.12756 tab. 7.

The same paper applies the variant to multilevel thresholding of three RGB images, using Otsu and Kapur objectives. The author-reported ranks are mixed: on Kapur it has the best average rank on all three metrics, while on Otsu it is not best on PSNR 2609.12756 tab. 11 2609.12756 tab. 12. See image-thresholding.

When to use which

There is only one variant, so this table compares the membrane approach with the plain method it extends and states what the card does and does not support.

The paper's own parameter sweeps suggest a fixed ε near 0.0001 and m_max = 4 gave the best average ranks in its tests 2609.12756 tab. 3 2609.12756 tab. 4. Those values are tuned on the same benchmark, so they are not general advice.

Implementation sketch

The loop below is the paper's Algorithm 1, condensed. The card does not state how operators are chosen per solution, how the membranes are sized, or which "best" the distance uses, so each of these is a choice the implementer must make and document 2609.12756 §3 2609.12756 alg. 1.

# Random initial population of ps solutions, then evaluate  [§3]
population = sample_uniform(ps, dim, lower, upper)
fitness = evaluate(population)
while evaluations < budget:
    # Diversity value from the spread of the population  [eq. 15]
    mvol = compute_mvol(population, lower, upper)
    if mvol < eps:
        # Stay in one membrane, update all solutions  [alg. 1 lines 4-6]
        membranes = [population]
    else:
        # Split at random into m membranes  [eq. 18] [alg. 1 line 8]
        m = m_min + ceil((m_max - m_min) * rand())
        membranes = random_split(population, m)
    for each membrane in membranes:
        # Guide chosen by roulette over FDB scores  [eq. 19] [§3.2]
        for each solution x_i in membrane:
            x_i = apo_update(x_i, membrane)  # [eq. 21]
    # Merge membranes back into one population  [alg. 1 line 12]
    population = concatenate(membranes)
    fitness = evaluate(population)
    best = best_of(population, fitness)  # [alg. 1 line 14]
return best

Implementation notes from the card:

• The paper computes mVOL from products over dimensions. Working in log space avoids overflow and underflow at higher dimensions. This is our suggestion, not the paper's 2609.12756 eq. 16 2609.12756 eq. 17.
• The score in eq. 19 is not stated to be negated for minimisation, and the roulette needs a non-negative score 2609.12756 §3.2.

Contradictions

None known. Only one card covers this slug, so there are no two papers to compare. Within the paper, the ablation claim (membrane alone and RFDB alone each lose to the full variant) and the Otsu PSNR result (the variant is not best) are both author-reported and are not in conflict with each other.

Papers

• MAAPO: an innovative membrane algorithm based on artificial protozoa optimizer for multilevel threshold image segmentation: introduces a membrane split-and-merge step, driven by a diversity value, and an RFDB guide choice to the artificial protozoa optimizer.