Opened 7 months ago

Last modified 13 hours ago

#2706 reviewing enhancement

Binary problems should include similarity calculators for population diversity analysis

Reported by: abeham Owned by: jkarder
Priority: medium Milestone: HeuristicLab 3.3.15
Component: Problems.Binary Version: 3.3.14
Keywords: Cc:

Description (last modified by jkarder)

The binary problems (HIFF, DeceptiveTrap, DeceptiveStepTrap, and 1-max) do not include population diversity analyzers.

The Knapsack problem as the 5th binary problem that we have in the trunk doesn't derive from BinaryProblem and does have such an analyzer, but it includes its own similarity calculator that is actually a similarity calculator on binary vectors in general.

#2730 depends on this ticket.

Change History (6)

comment:1 Changed 7 months ago by abeham

  • Owner set to abeham
  • Status changed from new to accepted

comment:2 Changed 7 months ago by abeham


  • Encodings.BinaryVector:
    • Added HammingSimilarityCalculator
  • Problems.Knapsack:
    • Made KnapsackSimilarityCalculator NonDiscoverable and Obsolete
    • Added HammingSimilarityCalculator to KnapsackProblem and removed NoSimilarityCalculator
  • Problems.Binary:
    • Added HammingSimilarityCalculator and QualitySimilarityCalculator to BinaryProblem
    • Added PopulationSimilarityAnalyzer to BinaryProblem

In my opinion, encoding-specific similarity calculators should be provided and parameterized as part of the encoding. However, the encoding currently only deals with types of IOperator and similarity calculators are not operators. This would be a greater change that we'll have to consider as part of the encodings refactoring.

comment:3 Changed 7 months ago by abeham

  • Owner changed from abeham to jkarder
  • Status changed from accepted to reviewing

comment:4 Changed 8 days ago by jkarder

  • Owner changed from jkarder to abeham
  • Status changed from reviewing to assigned

Reviewed r14412:

  • HammingSimilarityCalculator.CalculateSimilarity
    • double.NaN is returned if both binary vectors are of length 0
    • the exception message says "[...] one or both of the provided scopes is null.", whereas the method does not use scopes at all

#2730 depends on this ticket.

Last edited 7 days ago by jkarder (previous) (diff)

comment:5 Changed 8 days ago by jkarder

  • Description modified (diff)

comment:6 Changed 13 hours ago by abeham

  • Owner changed from abeham to jkarder
  • Status changed from assigned to reviewing


  • Added or updated similarity calculators and population similarity analysis for several problems (BinPacking, LAP, Orienteering, Parameter optimization, PTSP, QAP, TF, TSP, VRP)
  • Made TSPSimilarityCalculator obsolete since it's essentially the same as the one in the permutation plugin
  • Made QAPPopulationDiversityAnalyzer obsolete as it is replaced by the newer PopulationSimilarityAnalyzer
  • Removed genotype specific similarity code in QAPPermutationProximityCalculator (again identical to the permutation plugin)
  • Changed QAPSimilarityCalculator to perform phenotype similarity instead of genotype similarity (has not been previously used)
Note: See TracTickets for help on using tickets.