Artificial Immune System (AIS) for Bus Type Allocation

This document outlines the pseudo-algorithm for the Artificial Immune System (AIS) used in BusTypeAllocator to assign bus types (Generator, Load, Connection) to a grid topology. The goal is to minimize the difference between the generated grid’s entropy (\(W\)) and a target entropy (\(W^*\)) derived from reference statistics.

The AIS approach is based on the Clonal Selection Principle from immunology and was proposed for synthetic grid modeling by Elyas and Wang [Elyas and Wang, 2016]. The implementation is ported from the MATLAB SynGrid toolbox (sg_bus_type.m).

Initialization

Input:

  • Graph Topology \(G(V, E)\) with \(N\) nodes and \(M\) edges.

  • Entropy Model Selection (0 or 1).

Setup:

  1. Determine Ratios: Calculate target percentages for Generators (\(P_G\)), Loads (\(P_L\)), and Connections (\(P_C\)) based on network size \(N\).

    • e.g., If \(N < 2000\): \(P_G=23\%, P_L=55\%, P_C=22\%\)

  2. Constraint Identification: Identify non-leaf nodes (degree > 1) as preferred candidates for Connection buses.

Target Entropy Estimation (\(W^*\))

Before optimization, we estimate the “natural” entropy of the specific topology via Monte Carlo simulation.

Procedure:

  1. Initialize empty list samples.

  2. For \(i = 1\) to monte_carlo_iters (e.g., 2000):

    • Generate a random assignment vector \(A\) respecting \(P_G, P_L, P_C\).

    • Calculate Link Ratios (\(R_{links}\)) for the 6 types: GG, LL, CC, GL, GC, LC.

    • Calculate Entropy \(W\) using the entropy function:

      \[W = \text{EntropyFunc}(R_{bus}, R_{links})\]

    • Add \(W\) to samples.

  3. Calculate Mean (\(\mu_W\)) and Standard Deviation (\(\sigma_W\)) of samples.

  4. Calculate Distance Parameter \(d\) based on \(\log(N)\) and reference curves.

  5. Compute Target:

\[W^* = (d \times \sigma_W) + \mu_W\]

  1. Set Convergence Criteria: The convergence threshold \(\epsilon\) is set dynamically based on the Monte Carlo standard deviation and the network size:

    • For small grids (\(N < 50\)): \(\epsilon = \sigma_W / 2\) (entropy model 1) or \(\epsilon = \sigma_W / 10\) (entropy model 0).

    • For larger grids (\(N \geq 50\)): \(\epsilon = \sigma_W / 1000\).

    A smaller \(\epsilon\) demands a closer match to \(W^*\) but requires more optimization iterations.

AIS Optimization Loop

The algorithm mimics the immune system’s Clonal Selection Principle: best antibodies (solutions) proliferate (clone) and undergo affinity maturation (mutation).

Initialization:

  • Generate initial Population of \(K\) random assignments.

Loop (until max_iter or BestError < \(\epsilon\)):

  1. Affinity Evaluation:

    • For each individual \(S\) in Population:

      • Calculate its Entropy \(W_S\).

      • Calculate Error (Affinity):

        \[\text{Error} = |W^* - W_S|\]

    • Sort Population by Error (Ascending).

    • Update BestSolution and BestError.

  2. Convergence Check:

    • If BestError < \(\epsilon\), Break.

  3. Clonal Selection:

    • Select the top 50% of Population (Elite pool).

    • For each individual \(S\) with rank \(r\) in Elite pool:

      • Calculate clone count (Better rank \(\to\) More clones):

        \[N_c = \text{round}\left( \frac{\beta \cdot \text{scale}}{r} \right)\]

      • Create \(N_c\) copies of \(S\).

  4. Hypermutation:

    • For each clone \(C\) derived from parent with rank \(r\):

      • Determine mutation intensity \(M_{rate}\) proportional to rank \(r\). (Worse parents \(\to\) Higher mutation intensity)

      • Perform mutation \(M_{rate}\) times:

        • Select random node \(u\).

        • Flip type of \(u\) to random valid type \(\{Gen, Load, Conn\}\).

    • Collect all mutated clones into ClonePool.

    Note

    Because mutations randomly flip bus types without enforcing the original bus type ratios, the actual G/L/C ratios in mutated solutions may drift from the target ratios. The entropy calculation should therefore use the actual bus type ratios from the assignment vector, not the fixed target ratios. See the implementation notes in bus_type_allocator.py.

  5. Receptor Editing (Diversity Injection):

    • Generate 10% new random solutions (FreshPool) to prevent local optima.

  6. Selection (Next Generation):

    • Define new pool:

      \[\text{CombinedPool} = \text{FreshPool} \cup \text{ClonePool} \cup \text{ElitePool}\]

    • Evaluate Error for all in CombinedPool.

    • Sort and truncate CombinedPool to original size \(K\).

    • Set Population = Truncated Pool.

Final Output

  • Return BestSolution converted to a dictionary {NodeID: BusType}.

[EW16]

Seyyed Hamid Elyas and Zhifang Wang. Improved synthetic power grid modeling with correlated bus type assignments. IEEE Transactions on Power Systems, 32(5):3391–3402, 2016.