Clonalg

CLONALG #

Name #

CLONALG, Clonal Selection Algorithm

Taxonomy #

The Clonal Selection Algorithm (CLONALG) is a biologically inspired computational technique that falls under the umbrella of Artificial Immune Systems (AIS) and Computational Intelligence. It is closely related to other immune-inspired algorithms such as Negative Selection and Immune Network Theory.

  • Computational Intelligence
    • Biologically Inspired Computation
      • Artificial Immune Systems (AIS)
        • Clonal Selection Algorithm (CLONALG)
        • Negative Selection
        • Immune Network Theory

Strategy #

CLONALG is inspired by the clonal selection principle of the adaptive immune system, where B-cells that best recognize an antigen are selected for cloning and hypermutation to produce high-affinity antibodies. In the computational model, antibodies represent candidate solutions, and the antigen represents the problem to be solved or optimized.

The algorithm starts by initializing a population of candidate solutions (antibodies) and evaluating their fitness (affinity) based on the problem-specific objective function. The best solutions are then selected for cloning, with the number of clones proportional to their fitness. These clones undergo hypermutation, where the mutation rate is inversely proportional to the fitness of the parent antibody. This allows for a balance between exploration and exploitation, as high-affinity solutions are mutated less to fine-tune them, while low-affinity solutions are mutated more to explore the search space.

After hypermutation, the clones are evaluated, and the best ones are selected to replace the worst individuals in the original population. This process is repeated for a fixed number of iterations or until a stopping criterion is met. The result is a population of high-affinity antibodies that represent good solutions to the problem.

CLONALG also includes a mechanism for maintaining diversity in the population by introducing new randomly generated antibodies at each iteration, replacing a portion of the worst individuals. This helps prevent premature convergence and allows the algorithm to explore different regions of the search space.

Procedure #

Data Structures:

  • Antibody: Represents a candidate solution to the problem
  • Population: A collection of antibodies
  • Clone: A copy of an antibody that undergoes hypermutation

Parameters:

  • Population Size: The number of antibodies in the population
  • Clone Size: The maximum number of clones generated for each selected antibody
  • Mutation Rate: The rate at which clones are mutated (typically inversely proportional to fitness)
  • Replacement Ratio: The proportion of the population replaced by new random antibodies at each iteration
  • Max Iterations: The maximum number of iterations before termination

Steps:

  1. Initialize a population of antibodies randomly
  2. Evaluate the fitness (affinity) of each antibody
  3. Repeat until stopping criteria are met:
    1. Select the best antibodies based on their fitness
    2. For each selected antibody:
      1. Generate clones proportional to its fitness
      2. Hypermutate the clones, with mutation rate inversely proportional to fitness
      3. Evaluate the fitness of the clones
      4. Select the best clone to replace the parent antibody
    3. Replace a portion of the worst antibodies with new random antibodies
    4. Evaluate the fitness of the new antibodies
  4. Return the best antibody found as the solution

Considerations #

Advantages:

  • Effective at exploring and exploiting the search space due to the balance between cloning and hypermutation
  • Maintains diversity in the population, reducing the risk of premature convergence
  • Inherently parallel, making it suitable for distributed and multi-objective optimization problems

Disadvantages:

  • Requires careful tuning of parameters, such as population size, clone size, and mutation rate, for optimal performance
  • May be computationally expensive due to the cloning and hypermutation processes
  • The algorithm’s performance is dependent on the choice of the affinity function, which may be problem-specific and require domain knowledge

Heuristics #

Parameter Selection:

  • Population Size: Typically ranges from 10 to 100, depending on the complexity of the problem. Larger populations can explore more of the search space but may be computationally expensive.
  • Clone Size: Usually proportional to the population size and the affinity of the parent antibody. Higher affinity antibodies should generate more clones for fine-tuning.
  • Mutation Rate: Inversely proportional to the affinity of the parent antibody. High-affinity antibodies should have a lower mutation rate to exploit their good characteristics, while low-affinity antibodies should have a higher mutation rate to explore the search space.
  • Replacement Ratio: Typically ranges from 10% to 30% of the population size. Higher ratios can introduce more diversity but may slow down convergence.

Affinity Function Design:

  • The affinity function should accurately measure the quality of a candidate solution with respect to the problem objectives.
  • For multi-objective problems, consider using Pareto dominance or aggregation techniques to combine multiple objectives into a single affinity value.
  • Normalize the affinity values to ensure a fair comparison between antibodies.

Diversity Maintenance:

  • Introduce new random antibodies at each iteration to maintain diversity and prevent premature convergence.
  • Consider using a diversity measure, such as the Hamming distance or Euclidean distance, to ensure that the new antibodies are sufficiently different from the existing ones.
  • Adjust the replacement ratio based on the diversity of the population. If the diversity is low, increase the ratio to introduce more new antibodies.

Stopping Criteria:

  • Set a maximum number of iterations based on the problem complexity and available computational resources.
  • Monitor the progress of the best affinity value and stop if it does not improve for a certain number of iterations (e.g., 10% of the maximum iterations).
  • For problems with known optimal solutions, stop when the best affinity reaches a predefined threshold or is within a certain tolerance of the optimal value.