Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
08/09/11 11:01:08 (13 years ago)
Author:
mkommend
Message:

#1479: Updated grammar editor branch.

Location:
branches/GP.Grammar.Editor/HeuristicLab.Problems.QuadraticAssignment/3.3
Files:
6 edited
1 copied

Legend:

Unmodified
Added
Removed
  • branches/GP.Grammar.Editor/HeuristicLab.Problems.QuadraticAssignment/3.3/Analyzers/QAPAlleleFrequencyAnalyzer.cs

    r6377 r6647  
    2020#endregion
    2121
     22using System.Collections.Generic;
    2223using HeuristicLab.Analysis;
    2324using HeuristicLab.Common;
     
    5657
    5758    protected override Allele[] CalculateAlleles(Permutation solution) {
    58       Allele[] alleles = new Allele[solution.Length];
     59      Allele[] alleles = new Allele[solution.Length * solution.Length];
     60      Dictionary<string, int> allelesDict = new Dictionary<string, int>();
    5961      DoubleMatrix weights = WeightsParameter.ActualValue;
    6062      DoubleMatrix distances = DistancesParameter.ActualValue;
    61       int source, target;
    6263      double impact;
    6364
    64       for (int i = 0; i < solution.Length; i++) {
    65         source = i;
    66         target = solution[i];
    67         impact = 0;
    68         for (int j = 0; j < solution.Length; j++)
    69           impact += weights[source, j] * distances[target, solution[j]];
    70         alleles[i] = new Allele(source.ToString() + "->" + target.ToString(), impact);
     65      for (int x = 0; x < solution.Length; x++) {
     66        for (int y = 0; y < solution.Length; y++) {
     67          string allele = weights[x, y].ToString() + ">" + distances[solution[x], solution[y]].ToString();
     68          int repetition = 1;
     69          if (allelesDict.ContainsKey(allele)) repetition += allelesDict[allele];
     70          allelesDict[allele] = repetition;
     71          impact = weights[x, y] * distances[solution[x], solution[y]];
     72          alleles[x * solution.Length + y] = new Allele(allele + "/" + repetition, impact);
     73        }
    7174      }
    7275
  • branches/GP.Grammar.Editor/HeuristicLab.Problems.QuadraticAssignment/3.3/Analyzers/QAPPopulationDiversityAnalyzer.cs

    r6377 r6647  
    2323using HeuristicLab.Common;
    2424using HeuristicLab.Core;
     25using HeuristicLab.Data;
    2526using HeuristicLab.Encodings.PermutationEncoding;
     27using HeuristicLab.Parameters;
    2628using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2729
     
    3335  [StorableClass]
    3436  public sealed class QAPPopulationDiversityAnalyzer : PopulationDiversityAnalyzer<Permutation> {
     37    public IValueParameter<BoolValue> UsePhenotypeSimilarityParameter {
     38      get { return (IValueParameter<BoolValue>)Parameters["UsePhenotypeSimilarity"]; }
     39    }
     40    public ILookupParameter<DoubleMatrix> WeightsParameter {
     41      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
     42    }
     43    public ILookupParameter<DoubleMatrix> DistancesParameter {
     44      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
     45    }
     46
    3547    [StorableConstructor]
    3648    private QAPPopulationDiversityAnalyzer(bool deserializing) : base(deserializing) { }
    3749    private QAPPopulationDiversityAnalyzer(QAPPopulationDiversityAnalyzer original, Cloner cloner) : base(original, cloner) { }
    38     public QAPPopulationDiversityAnalyzer() : base() { }
     50    public QAPPopulationDiversityAnalyzer()
     51      : base() {
     52      Parameters.Add(new ValueParameter<BoolValue>("UsePhenotypeSimilarity", "True if the similarity should be measured a level closer to the phenotype (the number of similar assignments of individual weights to distances). Set to false if the number of equal assignments (facility to location) should be counted.", new BoolValue(false)));
     53      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));
     54      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));
     55    }
    3956
    4057    public override IDeepCloneable Clone(Cloner cloner) {
     
    4259    }
    4360
     61    [StorableHook(HookType.AfterDeserialization)]
     62    private void AfterDeserialization() {
     63      // BackwardsCompatibility3.3
     64      #region Backwards compatible code, remove with 3.4
     65      if (!Parameters.ContainsKey("UsePhenotypeSimilarity"))
     66        Parameters.Add(new ValueParameter<BoolValue>("UsePhenotypeSimilarity", "True if the similarity should be measured a level closer to the phenotype (the number of similar assignments of individual weights to distances). Set to false if the number of equal assignments (facility to location) should be counted.", new BoolValue(false)));
     67      if (!Parameters.ContainsKey("Weights"))
     68        Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));
     69      if (!Parameters.ContainsKey("Distances"))
     70        Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));
     71      #endregion
     72    }
     73
    4474    protected override double[,] CalculateSimilarities(Permutation[] solutions) {
     75      DoubleMatrix weights = WeightsParameter.ActualValue, distances = DistancesParameter.ActualValue;
     76      bool phenotypeSimilarity = UsePhenotypeSimilarityParameter.Value.Value;
    4577      int count = solutions.Length;
    4678      double[,] similarities = new double[count, count];
     
    4981        similarities[i, i] = 1;
    5082        for (int j = i + 1; j < count; j++) {
    51           similarities[i, j] = CalculateSimilarity(solutions[i], solutions[j]);
     83          if (phenotypeSimilarity)
     84            similarities[i, j] = QAPPermutationProximityCalculator.CalculatePhenotypeSimilarity(solutions[i], solutions[j], weights, distances);
     85          else similarities[i, j] = QAPPermutationProximityCalculator.CalculateGenotypeSimilarity(solutions[i], solutions[j]);
    5286          similarities[j, i] = similarities[i, j];
    5387        }
     
    5589      return similarities;
    5690    }
    57 
    58     private double CalculateSimilarity(Permutation assignment1, Permutation assignment2) {
    59       int identicalAssignments = 0;
    60       for (int i = 0; i < assignment1.Length; i++) {
    61         if (assignment1[i] == assignment2[i])
    62           identicalAssignments++;
    63       }
    64       return ((double)identicalAssignments) / assignment1.Length;
    65     }
    6691  }
    6792}
  • branches/GP.Grammar.Editor/HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPSwap2MoveEvaluator.cs

    r5933 r6647  
    4949    }
    5050
     51    /// <summary>
     52    /// Calculates the quality of the move <paramref name="move"/> by evaluating the changes.
     53    /// The runtime complexity of this method is O(N) with N being the size of the permutation.
     54    /// </summary>
     55    /// <param name="assignment">The current permutation.</param>
     56    /// <param name="move">The move that is to be evaluated if it was applied to the current permutation.</param>
     57    /// <param name="weights">The weights matrix.</param>
     58    /// <param name="distances">The distances matrix.</param>
     59    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
    5160    public static double Apply(Permutation assignment, Swap2Move move, DoubleMatrix weights, DoubleMatrix distances) {
    5261      if (move.Index1 == move.Index2) return 0;
     
    7382    }
    7483
     84    /// <summary>
     85    /// Is able to compute the move qualities faster O(1) in some cases if it knows the quality of
     86    /// performing the move <paramref name="move"/> previously. In other cases it performs a
     87    /// standard move quality calculation with runtime complexity O(N).
     88    /// </summary>
     89    /// <remarks>
     90    /// The number of cases that the calculation can be performed faster grows with N^2
     91    /// while the number of cases which require a larger recalculation grows linearly with N.
     92    /// Larger problem instances thus benefit from this faster method to a larger degree.
     93    /// </remarks>
     94    /// <param name="assignment">The current permutation.</param>
     95    /// <param name="move">The current move that is to be evaluated.</param>
     96    /// <param name="previousQuality">The quality of that move as evaluated for the previous permutation.</param>
     97    /// <param name="weights">The weigths matrix.</param>
     98    /// <param name="distances">The distances matrix.</param>
     99    /// <param name="lastMove">The move that was applied to transform the permutation from the previous to the current one.</param>
     100    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
     101    public static double Apply(Permutation assignment, Swap2Move move, double previousQuality,
     102      DoubleMatrix weights, DoubleMatrix distances, Swap2Move lastMove) {
     103      bool overlapsLastMove = move.Index1 == lastMove.Index1
     104                           || move.Index2 == lastMove.Index1
     105                           || move.Index1 == lastMove.Index2
     106                           || move.Index2 == lastMove.Index2;
     107
     108      if (!overlapsLastMove) {
     109        int r = lastMove.Index1, u = move.Index1, s = lastMove.Index2, v = move.Index2;
     110        int pR = assignment[lastMove.Index1], pU = assignment[move.Index1], pS = assignment[lastMove.Index2], pV = assignment[move.Index2];
     111
     112        return previousQuality
     113          + (weights[r, u] - weights[r, v] + weights[s, v] - weights[s, u])
     114            * (distances[pS, pU] - distances[pS, pV] + distances[pR, pV] - distances[pR, pU])
     115          + (weights[u, r] - weights[v, r] + weights[v, s] - weights[u, s])
     116            * (distances[pU, pS] - distances[pV, pS] + distances[pV, pR] - distances[pU, pR]);
     117      } else {
     118        return Apply(assignment, move, weights, distances);
     119      }
     120    }
     121
    75122    public override IOperation Apply() {
    76123      Swap2Move move = Swap2MoveParameter.ActualValue;
  • branches/GP.Grammar.Editor/HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj

    r6377 r6647  
    124124    <Compile Include="Parsers\QAPLIBParser.cs" />
    125125    <Compile Include="QAPAssignment.cs" />
     126    <Compile Include="QAPPermutationProximityCalculator.cs" />
    126127    <Compile Include="QuadraticAssignmentProblem.cs" />
    127128    <EmbeddedResource Include="Data\bur26a.dat" />
  • branches/GP.Grammar.Editor/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

    r6618 r6647  
    385385        Distances = new DoubleMatrix(parser.Distances);
    386386        Weights = new DoubleMatrix(parser.Weights);
    387         Name = "Quadratic Assignment Problem (loaded instance " + instance + ")";
    388         Description = "Loaded embedded problem data of instance " + instance + ".";
     387        Name = instance;
     388        Description = "Loaded embedded QAPLIB problem data of instance " + instance + ".";
    389389        OnReset();
    390390      }
  • branches/GP.Grammar.Editor/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPMoveEvaluatorTest.cs

    r5933 r6647  
    6060      for (int i = 0; i < ProblemSize - 1; i++) {
    6161        for (int j = i + 1; j < ProblemSize; j++) {
    62           symmetricDistances[i, j] = random.Next(ProblemSize);
     62          symmetricDistances[i, j] = random.Next(ProblemSize * 100);
    6363          symmetricDistances[j, i] = symmetricDistances[i, j];
    64           symmetricWeights[i, j] = random.Next(ProblemSize);
     64          symmetricWeights[i, j] = random.Next(ProblemSize * 100);
    6565          symmetricWeights[j, i] = symmetricWeights[i, j];
    66           asymmetricDistances[i, j] = random.Next(ProblemSize);
    67           asymmetricDistances[j, i] = random.Next(ProblemSize);
    68           asymmetricWeights[i, j] = random.Next(ProblemSize);
    69           asymmetricWeights[j, i] = random.Next(ProblemSize);
    70           nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize);
    71           nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize);
    72           nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize);
    73           nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize);
     66          asymmetricDistances[i, j] = random.Next(ProblemSize * 100);
     67          asymmetricDistances[j, i] = random.Next(ProblemSize * 100);
     68          asymmetricWeights[i, j] = random.Next(ProblemSize * 100);
     69          asymmetricWeights[j, i] = random.Next(ProblemSize * 100);
     70          nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize * 100);
     71          nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize * 100);
     72          nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize * 100);
     73          nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize * 100);
    7474        }
    75         nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize);
    76         nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize);
     75        nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize * 100);
     76        nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize * 100);
    7777      }
    7878      int index = random.Next(ProblemSize);
    7979      if (nonZeroDiagonalDistances[index, index] == 0)
    80         nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize);
     80        nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize * 100);
    8181      index = random.Next(ProblemSize);
    8282      if (nonZeroDiagonalWeights[index, index] == 0)
    83         nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize);
     83        nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize * 100);
    8484      assignment = new Permutation(PermutationTypes.Absolute, ProblemSize, random);
     85    }
     86
     87    [TestMethod]
     88    public void Swap2MoveEvaluatorFastEvaluationTest() {
     89
     90      for (int i = 0; i < 500; i++) {
     91        Swap2Move lastMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
     92        Permutation prevAssignment = (Permutation)assignment.Clone();
     93        Swap2Manipulator.Apply(assignment, lastMove.Index1, lastMove.Index2);
     94        Permutation nextAssignment = (Permutation)assignment.Clone();
     95        Swap2Move currentMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
     96        Swap2Manipulator.Apply(nextAssignment, currentMove.Index1, currentMove.Index2);
     97
     98        double moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, symmetricWeights, symmetricDistances);
     99        double moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
     100                moveBefore, symmetricWeights, symmetricDistances, lastMove);
     101        double before = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
     102        double after = QAPEvaluator.Apply(nextAssignment, symmetricWeights, symmetricDistances);
     103
     104        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on symmetric matrices: " + Environment.NewLine
     105          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
     106
     107        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, asymmetricWeights, asymmetricDistances);
     108        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
     109                moveBefore, asymmetricWeights, asymmetricDistances, lastMove);
     110        before = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     111        after = QAPEvaluator.Apply(nextAssignment, asymmetricWeights, asymmetricDistances);
     112
     113        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on asymmetric matrices: " + Environment.NewLine
     114          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
     115
     116        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     117        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
     118                moveBefore, nonZeroDiagonalWeights, nonZeroDiagonalDistances, lastMove);
     119        before = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     120        after = QAPEvaluator.Apply(nextAssignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     121
     122        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on non-zero diagonal matrices: " + Environment.NewLine
     123          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
     124      }
    85125    }
    86126
Note: See TracChangeset for help on using the changeset viewer.