Crowding with Restricted Tournament Selection #

Name #

Crowding with Restricted Tournament Selection (RTS)

Taxonomy #

Crowding with Restricted Tournament Selection is a niching technique in Evolutionary Computation, a subfield of Computational Intelligence and Biologically Inspired Computation. It is closely related to other diversity preservation techniques like Fitness Sharing, Clearing, and Deterministic Crowding.

• Computational Intelligence
  • Biologically Inspired Computation
    • Evolutionary Computation
      • Evolutionary Algorithms
        • Genetic Algorithms
          • Niching Methods
            • Crowding
              • Crowding with Restricted Tournament Selection

Strategy #

Crowding with Restricted Tournament Selection aims to maintain population diversity and prevent premature convergence in genetic algorithms by promoting competition between similar individuals. This is achieved through a modified selection process that restricts tournament selection to a subset of the population based on genotypic or phenotypic similarity.

The core idea behind RTS is to create a local neighborhood for each individual in the population, consisting of its most similar members. Selection pressure is then applied within these neighborhoods, encouraging the formation and preservation of distinct niches throughout the search process.

Similarity Measure #

To determine the local neighborhood for each individual, a similarity measure is employed. This measure quantifies the genotypic or phenotypic distance between individuals, allowing the algorithm to identify the most similar members of the population. Common similarity measures include Euclidean distance, Hamming distance, and domain-specific metrics tailored to the problem at hand.

Restricted Tournament Selection #

Once the local neighborhoods are established, the selection process proceeds through a series of restricted tournaments. For each individual in the population, a small subset of its nearest neighbors is randomly chosen to participate in the tournament. The winner of this localized tournament, typically the individual with the highest fitness, is then selected for reproduction.

By restricting competition to similar individuals, RTS promotes the preservation of diverse solutions across the search space. This localized selection pressure allows distinct niches to evolve independently, preventing any single niche from dominating the population and leading to premature convergence.

Procedure #

1. Initialize the population with a set of randomly generated individuals.
2. Evaluate the fitness of each individual in the population.
3. For each generation:
   1. Create an empty offspring population.
   2. For each individual in the current population:
      1. Calculate the similarity between the individual and all other members of the population using a chosen similarity measure.
      2. Identify the K most similar individuals to form the local neighborhood.
      3. Randomly select N individuals from the local neighborhood to participate in a restricted tournament.
      4. Choose the individual with the highest fitness from the restricted tournament as the winner.
      5. Apply genetic operators (crossover and mutation) to the winner to create an offspring.
      6. Add the offspring to the new population.
   3. Replace the current population with the offspring population.
   4. Evaluate the fitness of each individual in the new population.
4. Repeat step 3 until a termination criterion is met (e.g., maximum number of generations or satisfactory fitness level).

Parameters #

• Population Size: The number of individuals in the population.
• K: The size of the local neighborhood for each individual.
• N: The number of individuals participating in each restricted tournament.
• Crossover Rate: The probability of applying the crossover operator to selected individuals.
• Mutation Rate: The probability of applying the mutation operator to the offspring.

Considerations #

Advantages #

• Promotes and maintains diversity within the population, preventing premature convergence.
• Allows the formation and preservation of distinct niches, enabling the exploration of multiple optima simultaneously.
• Increases the chances of finding global optima in multimodal search spaces.

Disadvantages #

• Increased computational complexity due to the need to calculate similarities between individuals.
• The performance of the algorithm depends on the choice of an appropriate similarity measure, which may require domain knowledge or experimentation.
• The size of the local neighborhood (K) and the number of individuals in each restricted tournament (N) need to be carefully tuned for optimal performance.

Heuristics #

Similarity Measure Selection #

• Choose a similarity measure that captures the relevant features or characteristics of the problem domain.
• For genotypic similarity, consider measures like Hamming distance for binary representations or Euclidean distance for real-valued representations.
• For phenotypic similarity, use domain-specific metrics that quantify the behavioral or functional similarity of individuals.

Parameter Tuning #

• Population Size:
  • Choose a population size that balances diversity and computational efficiency.
  • Larger populations can maintain more diversity but may require more computational resources.
• Local Neighborhood Size (K):
  • Set K to a value that captures the local structure of the search space.
  • Larger values of K result in more diverse neighborhoods but may dilute selection pressure.
• Restricted Tournament Size (N):
  • Choose N to be smaller than K to maintain localized competition.
  • Larger values of N increase selection pressure within each neighborhood.
• Crossover and Mutation Rates:
  • Adjust the crossover and mutation rates based on the problem characteristics and desired balance between exploration and exploitation.
  • Higher crossover rates promote the exchange of genetic material between individuals, while higher mutation rates introduce new genetic variants.

Balancing Exploration and Exploitation #

• Monitoring Population Diversity:
  • Regularly assess the diversity of the population using metrics like genotypic or phenotypic distance.
  • If diversity falls below a certain threshold, consider increasing the mutation rate or adjusting the local neighborhood size to encourage exploration.
• Adaptive Parameter Control:
  • Implement adaptive mechanisms to dynamically adjust parameters like the mutation rate or local neighborhood size based on the progress of the search.
  • Increase exploration when the population becomes too homogeneous or when the fitness improvement stagnates.

Hybridization and Extensions #

• Combine RTS with other diversity preservation techniques, such as fitness sharing or clearing, to further enhance population diversity.
• Incorporate local search or memetic algorithms to refine the solutions within each niche.
• Extend RTS to multi-objective optimization by considering Pareto dominance and niching in the objective space.