Immune Network Algorithm

Artificial Immune Network, aiNet, Optimization Artificial Immune Network, opt-aiNet.

Taxonomy

The Artificial Immune Network algorithm (aiNet) is a Immune Network Algorithm from the field of Artificial Immune Systems. It is related to other Artificial Immune System algorithms such as the Clonal Selection Algorithm, the Negative Selection Algorithm, and the Dendritic Cell Algorithm. The Artificial Immune Network algorithm includes the base version and the extension for optimization problems called the Optimization Artificial Immune Network algorithm (opt-aiNet).

Inspiration

The Artificial Immune Network algorithm is inspired by the Immune Network theory of the acquired immune system. The clonal selection theory of acquired immunity accounts for the adaptive behavior of the immune system including the ongoing selection and proliferation of cells that select-for potentially harmful (and typically foreign) material in the body. A concern of the clonal selection theory is that it presumes that the repertoire of reactive cells remains idle when there are no pathogen to which to respond. Jerne proposed an Immune Network Theory (Idiotypic Networks) where immune cells are not at rest in the absence of pathogen, instead antibody and immune cells recognize and respond to each other [Jerne1974] [Jerne1974a] [Jerne1984].

The Immune Network theory proposes that antibody (both free floating and surface bound) possess idiotopes (surface features) to which the receptors of other antibody can bind. As a result of receptor interactions, the repertoire becomes dynamic, where receptors continually both inhibit and excite each other in complex regulatory networks (chains of receptors). The theory suggests that the clonal selection process may be triggered by the idiotopes of other immune cells and molecules in addition to the surface characteristics of pathogen, and that the maturation process applies both to the receptors themselves and the idiotopes which they expose.

Metaphor

The immune network theory has interesting resource maintenance and signaling information processing properties. The classical clonal selection and negative selection paradigms integrate the accumulative and filtered learning of the acquired immune system, whereas the immune network theory proposes an additional order of complexity between the cells and molecules under selection. In addition to cells that interact directly with pathogen, there are cells that interact with those reactive cells and with pathogen indirectly, in successive layers such that networks of activity for higher-order structures such as internal images of pathogen (promotion), and regulatory networks (so-called anti-idiotopes and anti-anti-idiotopes).

Strategy

The objective of the immune network process is to prepare a repertoire of discrete pattern detectors for a given problem domain, where better performing cells suppress low-affinity (similar) cells in the network. This principle is achieved through an interactive process of exposing the population to external information to which it responds with both a clonal selection response and internal meta-dynamics of intra-population responses that stabilizes the responses of the population to the external stimuli.

Procedure

Algorithm (below) provides a pseudocode listing of the Optimization Artificial Immune Network algorithm (opt-aiNet) for minimizing a cost function.

Heuristics

• aiNet is designed for unsupervised clustering, where as the opt-aiNet extension was designed for pattern recognition and optimization, specifically multi-modal function optimization.
• The amount of mutation of clones is proportionate to the affinity of the parent cell with the cost function (better fitness, lower mutation).
• The addition of random cells each iteration adds a random-restart like capability to the algorithms.
• Suppression based on cell similarity provides a mechanism for reducing redundancy.
• The population size is dynamic, and if it continues to grow it may be an indication of a problem with many local optima or that the affinity threshold may needs to be increased.
• Affinity proportionate mutation is performed using $c' = c + \alpha \times N(1,0)$ where $\alpha = \frac{1}{\beta} \times exp(-f)$, $N$ is a Guassian random number, and $f$ is the fitness of the parent cell, $\beta$ controls the decay of the function and can be set to 100.
• The affinity threshold is problem and representation specific, for example a $AffinityThreshold$ may be set to an arbitrary value such as 0.1 on a continuous function domain, or calculated as a percentage of the size of the problem space.
• The number of random cells inserted may be 40% of the population size.
• The number of clones created for a cell may be small, such as 10.

Code Listing

Listing (below) provides an example of the Optimization Artificial Immune Network (opt-aiNet) implemented in the Ruby Programming Language. The demonstration problem is an instance of a continuous function optimization that seeks $\min f(x)$ where $f=\sum_{i=1}^n x_{i}^2$, $-5.0\leq x_i \leq 5.0$ and $n=2$. The optimal solution for this basin function is $(v_0,\ldots,v_{n-1})=0.0$. The algorithm is an implementation based on the specification by de Castro and Von Zuben [Castro2002c].

def objective_function(vector)
  return vector.inject(0.0) {|sum, x| sum + (x**2.0)}
end

def random_vector(minmax)
  return Array.new(minmax.size) do |i|
    minmax[i][0] + ((minmax[i][1] - minmax[i][0]) * rand())
  end
end

def random_gaussian(mean=0.0, stdev=1.0)
  u1 = u2 = w = 0
  begin
    u1 = 2 * rand() - 1
    u2 = 2 * rand() - 1
    w = u1 * u1 + u2 * u2
  end while w >= 1
  w = Math.sqrt((-2.0 * Math.log(w)) / w)
  return mean + (u2 * w) * stdev
end

def clone(parent)
  v = Array.new(parent[:vector].size) {|i| parent[:vector][i]}
  return {:vector=>v}
end

def mutation_rate(beta, normalized_cost)
  return (1.0/beta) * Math.exp(-normalized_cost)
end

def mutate(beta, child, normalized_cost)
  child[:vector].each_with_index do |v, i|
    alpha = mutation_rate(beta, normalized_cost)
    child[:vector][i] = v + alpha * random_gaussian()
  end
end

def clone_cell(beta, num_clones, parent)
  clones = Array.new(num_clones) {clone(parent)}
  clones.each {|clone| mutate(beta, clone, parent[:norm_cost])}
  clones.each{|c| c[:cost] = objective_function(c[:vector])}
  clones.sort!{|x,y| x[:cost] <=> y[:cost]}
  return clones.first
end

def calculate_normalized_cost(pop)
  pop.sort!{|x,y| x[:cost]<=>y[:cost]}
  range = pop.last[:cost] - pop.first[:cost]
  if range == 0.0
    pop.each {|p| p[:norm_cost] = 1.0}
  else
    pop.each {|p| p[:norm_cost] = 1.0-(p[:cost]/range)}
  end
end

def average_cost(pop)
  sum = pop.inject(0.0){|sum,x| sum + x[:cost]}
  return sum / pop.size.to_f
end

def distance(c1, c2)
  sum = 0.0
  c1.each_index {|i| sum += (c1[i]-c2[i])**2.0}
  return Math.sqrt(sum)
end

def get_neighborhood(cell, pop, aff_thresh)
  neighbors = []
  pop.each do |p|
    neighbors << p if distance(p[:vector], cell[:vector]) < aff_thresh
  end
  return neighbors
end

def affinity_supress(population, aff_thresh)
  pop = []
  population.each do |cell|
    neighbors = get_neighborhood(cell, population, aff_thresh)
    neighbors.sort!{|x,y| x[:cost] <=> y[:cost]}
    pop << cell if neighbors.empty? or cell.equal?(neighbors.first)
  end
  return pop
end

def search(search_space, max_gens, pop_size, num_clones, beta, num_rand, aff_thresh)
  pop = Array.new(pop_size) {|i| {:vector=>random_vector(search_space)} }
  pop.each{|c| c[:cost] = objective_function(c[:vector])}
  best = nil
  max_gens.times do |gen|
    pop.each{|c| c[:cost] = objective_function(c[:vector])}
    calculate_normalized_cost(pop)
    pop.sort!{|x,y| x[:cost] <=> y[:cost]}
    best = pop.first if best.nil? or pop.first[:cost] < best[:cost]
    avgCost, progeny = average_cost(pop), nil
    begin
      progeny=Array.new(pop.size){|i| clone_cell(beta, num_clones, pop[i])}
    end until average_cost(progeny) < avgCost
    pop = affinity_supress(progeny, aff_thresh)
    num_rand.times {pop << {:vector=>random_vector(search_space)}}
    puts " > gen #{gen+1}, popSize=#{pop.size}, fitness=#{best[:cost]}"
  end
  return best
end

if __FILE__ == $0
  # problem configuration
  problem_size = 2
  search_space = Array.new(problem_size) {|i| [-5, +5]}
  # algorithm configuration
  max_gens = 150
  pop_size = 20
  num_clones = 10
  beta = 100
  num_rand = 2
  aff_thresh = (search_space[0][1]-search_space[0][0])*0.05
  # execute the algorithm
  best = search(search_space, max_gens, pop_size, num_clones, beta, num_rand, aff_thresh)
  puts "done! Solution: f=#{best[:cost]}, s=#{best[:vector].inspect}"
end

References

Primary Sources

Early works, such as Farmer et al. [Farmer1986] suggested at the exploitation of the information processing properties of network theory for machine learning. A seminal network theory based algorithm was proposed by Timmis et al. for clustering problems called the Artificial Immune Network (AIN) [Timmis2000] that was later extended and renamed the Resource Limited Artificial Immune System [Timmis2001] and Artificial Immune Network (AINE) [Knight2001]. The Artificial Immune Network (aiNet) algorithm was proposed by de Castro and Von Zuben that extended the principles of the Artificial Immune Network (AIN) and the Clonal Selection Algorithm (CLONALG) and was applied to clustering [Castro2000a]. The aiNet algorithm was further extended to optimization domains and renamed opt-aiNet [Castro2002c].

Learn More

The authors de Castro and Von Zuben provide a detailed presentation of the aiNet algorithm as a book chapter that includes immunological theory, a description of the algorithm, and demonstration application to clustering problem instances [Castro2001]. Timmis and Edmonds provide a careful examination of the opt-aiNet algorithm and propose some modifications and augmentations to improve its applicability and performance for multimodal function optimization problem domains [Timmis2004]. The authors de Franca, Von Zuben, and de Castro proposed an extension to opt-aiNet that provided a number of enhancements and adapted its capability for for dynamic function optimization problems called dopt-aiNet [Franca2005].

Bibliography

Please Note: This content was automatically generated from the book content and may contain minor differences.