Opened 9 months ago

Closed 6 weeks ago

#2706 closed enhancement (done)

Binary problems should include similarity calculators for population diversity analysis

Reported by: abeham Owned by: abeham
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 (9)

comment:1 Changed 9 months ago by abeham

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

comment:2 Changed 9 months ago by abeham

r14412:

  • 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 9 months ago by abeham

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

comment:4 Changed 2 months 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 2 months ago by jkarder (previous) (diff)

comment:5 Changed 2 months ago by jkarder

  • Description modified (diff)

comment:6 Changed 2 months ago by abeham

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

r15069:

  • 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)

comment:7 Changed 7 weeks ago by jkarder

  • Owner changed from jkarder to abeham

Reviewed r15069 and made further changes, please check.

r15166: QAPSimilarityCalculator now throws an exception if both permutations are of length 0

comment:8 Changed 7 weeks ago by abeham

  • Status changed from reviewing to readytorelease

ok

comment:9 Changed 6 weeks ago by abeham

  • Resolution set to done
  • Status changed from readytorelease to closed

r15217: merged revisions 14412, 14475, 14476, 14659, 14660, 14663, 14779, 14780, 14912, 15050, 15067, 15069, 15079, 15162, 15166, 15172, 15173 to stable

Note: See TracTickets for help on using tickets.