Linkage Tree Genetic Algorithm

Linkage-Tree Genetic Algorithm #

Name #

Linkage-Tree Genetic Algorithm (LTGA), Linkage Tree Genetic Algorithm, LTGA

Taxonomy #

The Linkage-Tree Genetic Algorithm is a type of Genetic Algorithm, a population-based metaheuristic optimization technique inspired by the principles of natural selection and genetics, which belongs to the broader field of Evolutionary Computation, a subfield of Computational Intelligence.

  • Computational Intelligence
    • Evolutionary Computation
      • Evolutionary Algorithms
        • Genetic Algorithms
          • Linkage-Tree Genetic Algorithm

Strategy #

Problem Decomposition #

The Linkage-Tree Genetic Algorithm addresses the challenge of efficiently identifying and exploiting the linkage (dependencies) between problem variables during the optimization process. It achieves this by constructing a hierarchical model of the linkage structure, represented as a tree, which guides the variation operators (crossover and mutation) to respect the identified dependencies and preserve promising partial solutions.

Linkage Learning #

The linkage tree is constructed using a bottom-up approach, starting with each variable as a leaf node and iteratively merging the most dependent pair of nodes until a single root node is formed. The dependency between variables is measured using a linkage function, such as mutual information or the chi-square statistic, which quantifies the strength of the relationship between variables based on their co-occurrence in the population.

Variation Operators #

Once the linkage tree is constructed, the LTGA applies specialized variation operators that respect the identified dependencies. The crossover operator, known as the Gene-Pool Optimal Mixing (GPOM) operator, selects a subset of nodes from the linkage tree and creates offspring by mixing the genetic material of the selected nodes from two parent solutions. The mutation operator introduces random changes to the offspring, ensuring the exploration of new solutions.

Population Update #

The LTGA employs a steady-state population update strategy, where a portion of the population is replaced by the newly generated offspring in each generation. The selection of individuals for replacement is based on their fitness values, with less fit individuals having a higher probability of being replaced. This process allows the population to gradually improve over generations while maintaining diversity.

Procedure #

Data Structures:

  • Population: A set of candidate solutions, each represented as a fixed-length vector of decision variables.
  • Linkage Tree: A hierarchical structure that captures the dependencies between variables, with leaf nodes representing individual variables and internal nodes representing groups of dependent variables.

Parameters:

  • Population Size: The number of candidate solutions in the population.
  • Offspring Size: The number of offspring generated in each generation.
  • Linkage Function: The method used to measure the dependency between variables (e.g., mutual information, chi-square statistic).
  • Mixing Operator: The operator used to create offspring by mixing the genetic material of selected nodes from the linkage tree (e.g., Gene-Pool Optimal Mixing).
  • Mutation Rate: The probability of applying mutation to each variable in the offspring.
  • Termination Criteria: The conditions under which the algorithm stops (e.g., maximum number of generations, convergence threshold).

Procedure:

  1. Initialize the population with random candidate solutions.
  2. Evaluate the fitness of each candidate solution in the population.
  3. While the termination criteria are not met, repeat steps 4-9.
  4. Construct the linkage tree using the selected linkage function.
    1. Start with each variable as a leaf node.
    2. Iteratively merge the most dependent pair of nodes until a single root node is formed.
  5. Generate offspring using the mixing operator.
    1. Select a subset of nodes from the linkage tree.
    2. Create offspring by mixing the genetic material of the selected nodes from two parent solutions.
  6. Apply mutation to the offspring based on the mutation rate.
  7. Evaluate the fitness of the offspring.
  8. Update the population by replacing less fit individuals with the offspring.
  9. If the termination criteria are met, return the best solution found; otherwise, go to step 4.

Considerations #

Advantages:

  • Effective at identifying and exploiting the linkage between problem variables, leading to more efficient optimization.
  • Preserves promising partial solutions by respecting the identified dependencies during variation operations.
  • Suitable for a wide range of optimization problems, including those with complex variable interactions.

Disadvantages:

  • Constructing the linkage tree can be computationally expensive, especially for high-dimensional problems.
  • The performance of the algorithm depends on the choice of the linkage function and the accuracy of the linkage learning process.
  • The algorithm may require problem-specific knowledge to select appropriate parameter values and linkage functions.

Heuristics #

Population Size and Offspring Size #

  • The population size should be large enough to maintain diversity and explore the search space effectively, typically ranging from 50 to 1000 individuals, depending on the problem complexity.
  • The offspring size should be a fraction of the population size, often between 10% and 50%, to balance exploration and exploitation.

Linkage Function Selection #

  • Mutual information and the chi-square statistic are commonly used linkage functions that capture the non-linear dependencies between variables.
  • The choice of the linkage function should be based on the characteristics of the problem and the types of variable interactions expected.

Mixing Operator Configuration #

  • The Gene-Pool Optimal Mixing (GPOM) operator is a popular choice for the LTGA, as it effectively mixes the genetic material of promising partial solutions.
  • The number of nodes selected for mixing should be a balance between preserving good building blocks and introducing sufficient diversity, typically ranging from 10% to 50% of the linkage tree nodes.

Mutation Rate #

  • The mutation rate should be set low enough to preserve the good solutions found by the algorithm but high enough to introduce diversity and prevent premature convergence.
  • A mutation rate between 1/N and 1/√N, where N is the problem size (number of variables), is often a good starting point.

Termination Criteria #

  • The maximum number of generations should be set based on the available computational resources and the desired solution quality, typically ranging from 100 to 10,000 generations.
  • Convergence can be detected when the best fitness value or the population diversity does not improve significantly over a fixed number of generations (e.g., 50-100 generations).