Fitness Sharing

Fitness Sharing #

Name #

Fitness Sharing, Shared Fitness, Fitness Sharing Scheme

Taxonomy #

Fitness Sharing is a niching technique used in Evolutionary Algorithms, a subfield of Computational Intelligence and Biologically Inspired Computation. It is closely related to other niching methods such as Crowding and Speciation. Fitness Sharing belongs to the following hierarchy:

  • Computational Intelligence
    • Biologically Inspired Computation
      • Evolutionary Computation
        • Evolutionary Algorithms
          • Genetic Algorithms
            • Niching Methods
              • Fitness Sharing

Strategy #

Fitness Sharing is a technique designed to maintain population diversity and prevent premature convergence in Genetic Algorithms. It achieves this by reducing the fitness of individuals that are similar to each other, effectively forcing the population to spread out and explore different regions of the search space.

The core idea behind Fitness Sharing is that individuals in a population are competing for limited resources. If multiple individuals occupy the same niche (i.e., are similar to each other), they must share the resources available in that niche. This sharing of resources is simulated by dividing an individual’s fitness by a measure of how many individuals are similar to it.

Similarity Measure #

To determine the similarity between individuals, a distance metric is defined. This metric could be based on genotypic similarity (e.g., Hamming distance for binary representations) or phenotypic similarity (e.g., Euclidean distance in the solution space). A threshold value, known as the sharing radius, is used to determine whether two individuals are considered similar enough to share fitness.

Shared Fitness #

Once the similarity between individuals has been determined, the shared fitness of each individual is calculated. This is done by dividing the individual’s raw fitness by a sharing factor, which is the sum of the similarity values between the individual and all other individuals in the population that fall within the sharing radius.

By reducing the fitness of similar individuals, Fitness Sharing encourages the population to maintain diversity and explore different regions of the search space. This can help prevent the population from converging prematurely on suboptimal solutions and improve the algorithm’s ability to locate multiple optima in multimodal optimization problems.

Procedure #

  1. Initialize the population
    1. Generate a population of individuals
    2. Evaluate the fitness of each individual
  2. While termination condition not met:
    1. For each individual i in the population:
      1. Calculate the sharing factor:
        1. Set sharing_factor = 0
        2. For each individual j in the population (j != i):
          1. Calculate the distance d between individuals i and j
          2. If d < sharing_radius:
            1. Calculate the sharing function value: sh = 1 - (d / sharing_radius)^alpha
            2. sharing_factor += sh
      2. Calculate the shared fitness of individual i: shared_fitness[i] = raw_fitness[i] / sharing_factor
    2. Perform selection based on shared fitness values
    3. Apply genetic operators (crossover and mutation) to create a new population
    4. Evaluate the fitness of each individual in the new population
  3. Return the best solution found

Data Structures:

  • Population: An array of individuals
  • Individual: Represents a candidate solution, typically encoded as a string (e.g., binary, real-valued) or a more complex data structure
  • Fitness: A numeric value indicating the quality of an individual

Typical Parameters:

  • Population Size: The number of individuals in the population
  • Sharing Radius: The threshold distance for determining whether individuals share fitness
  • Alpha: A scaling factor for the sharing function (typically set to 1)
  • Selection Method: The method used to select individuals for reproduction (e.g., tournament selection, roulette wheel selection)
  • Crossover Rate: The probability of applying the crossover operator
  • Mutation Rate: The probability of applying the mutation operator

Considerations #

Advantages: #

  • Promotes population diversity, helping to avoid premature convergence
  • Enables the discovery and maintenance of multiple optima in multimodal optimization problems
  • Can be easily incorporated into existing Genetic Algorithm implementations

Disadvantages: #

  • Increases computational complexity due to the need to calculate pairwise distances between individuals
  • Requires the definition of an appropriate distance metric and sharing radius, which may be problem-dependent
  • May slow down convergence in some cases, as it prevents the population from rapidly focusing on the most promising regions of the search space

Heuristics #

Choosing the Sharing Radius #

  • The sharing radius should be large enough to encourage diversity but not so large that it prevents convergence.
  • A good starting point is to set the sharing radius to a fraction (e.g., 10%) of the maximum possible distance between individuals.
  • Experiment with different values and adjust based on the specific problem and desired balance between exploration and exploitation.

Adapting the Sharing Radius #

  • Consider reducing the sharing radius over time to allow for more focused search in later generations.
  • Dynamically adjust the sharing radius based on population diversity metrics (e.g., average pairwise distance) to maintain a desired level of diversity.

Combining with Other Techniques #

  • Fitness Sharing can be used in conjunction with other diversity preservation techniques, such as Crowding or Speciation, for enhanced performance.
  • Incorporate local search methods (e.g., hill climbing) to refine solutions discovered by the Genetic Algorithm with Fitness Sharing.

Handling Computational Complexity #

  • To reduce the computational overhead of calculating pairwise distances, consider using data structures like KD-trees or applying clustering techniques to group similar individuals.
  • Parallelize the distance calculations and fitness sharing computations to take advantage of multi-core processors or distributed computing resources.

Parameter Tuning #

  • Experiment with different values for the population size, crossover rate, and mutation rate to find a good balance between exploration and exploitation.
  • Use parameter tuning techniques, such as grid search or evolutionary parameter optimization, to automatically find effective parameter settings for a given problem.

Monitoring and Analysis #

  • Track population diversity metrics (e.g., average pairwise distance, number of distinct solutions) over generations to assess the effectiveness of Fitness Sharing.
  • Visualize the population’s distribution in the search space to gain insights into the algorithm’s exploration and convergence behavior.
  • Compare the performance of Fitness Sharing with other diversity preservation techniques and standard Genetic Algorithms to evaluate its impact on the specific problem at hand.