Changeset 8910


Ignore:
Timestamp:
11/14/12 11:19:36 (9 years ago)
Author:
abeham
Message:

#1841:

  • Corrected best known solutions in new taillard and microarray instances
  • Improved computation of an average fitness in the QAP
Location:
trunk/sources
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Problems.Instances.QAPLIB/3.3/QAPLIBInstanceProvider.cs

    r8909 r8910  
    3232    #region Reversed instances
    3333    // These instances specified their best known solution in the wrong order
    34     private static HashSet<string> reversedSolutions = new HashSet<string>(new string[] {
    35       "bur26a",
    36       "bur26b",
    37       "bur26c",
    38       "bur26d",
    39       "bur26e",
    40       "bur26f",
    41       "bur26g",
    42       "bur26h",
    43       "chr12a",
    44       "chr12b",
    45       "chr12c",
    46       "chr15a",
    47       "chr15b",
    48       "chr15c",
    49       "chr18a",
    50       "chr18b",
    51       "chr20a",
    52       "chr20b",
    53       "chr20c",
    54       "chr22a",
    55       "chr22b",
    56       "chr25a",
    57       "esc16a",
    58       "esc16b",
    59       "esc16c",
    60       "esc16d",
    61       "esc16e",
    62       "esc16g",
    63       "esc16h",
    64       "esc16i",
    65       "esc16j",
    66       "esc32a",
    67       "esc32b",
    68       "esc32c",
    69       "esc32d",
    70       "esc32e",
    71       "esc32f",
    72       "esc32g",
    73       "esc32h",
    74       "had12",
    75       "had14",
    76       "had16",
    77       "had18",
    78       "had20",
    79       "kra32",
    80       "lipa20a",
    81       "lipa30a",
    82       "lipa40a",
    83       "lipa50a",
    84       "lipa60a",
    85       "lipa70a",
    86       "lipa80a",
    87       "lipa90a",
    88       "nug12",
    89       "nug14",
    90       "nug15",
    91       "nug16a",
    92       "nug16b",
    93       "nug17",
    94       "nug18",
    95       "nug20",
    96       "nug21",
    97       "nug22",
    98       "nug24",
    99       "nug25",
    100       "nug27",
    101       "nug28",
    102       "rou12",
    103       "rou15",
    104       "rou20",
    105       "scr12",
    106       "scr15",
    107       "scr20",
    108       "sko100a",
    109       "sko100b",
    110       "sko100c",
    111       "sko100d",
    112       "sko100e",
    113       "sko100f",
    114       "sko49",
    115       "sko81",
    116       "sko90",
    117       "ste36a",
    118       "ste36b",
    119       "tai100a",
    120       "tai100b",
    121       "tai12a",
    122       "tai12b",
    123       "tai150b",
    124       "tai15a",
    125       "tai15b",
    126       "tai17a",
    127       "tai20a",
    128       "tai20b",
    129       "tai256c",
    130       "tai25a",
    131       "tai25b",
    132       "tai30a",
    133       "tai30b",
    134       "tai35a",
    135       "tai35b",
    136       "tai40a",
    137       "tai40b",
    138       "tai50a",
    139       "tai50b",
    140       "tai60a",
    141       "tai60b",
    142       "tai64c",
    143       "tai80a",
    144       "tai80b",
    145       "wil100"
    146     });
     34    protected virtual HashSet<string> ReversedSolutions {
     35      get {
     36            return new HashSet<string>(new string[] {
     37              "bur26a",
     38              "bur26b",
     39              "bur26c",
     40              "bur26d",
     41              "bur26e",
     42              "bur26f",
     43              "bur26g",
     44              "bur26h",
     45              "chr12a",
     46              "chr12b",
     47              "chr12c",
     48              "chr15a",
     49              "chr15b",
     50              "chr15c",
     51              "chr18a",
     52              "chr18b",
     53              "chr20a",
     54              "chr20b",
     55              "chr20c",
     56              "chr22a",
     57              "chr22b",
     58              "chr25a",
     59              "esc16a",
     60              "esc16b",
     61              "esc16c",
     62              "esc16d",
     63              "esc16e",
     64              "esc16g",
     65              "esc16h",
     66              "esc16i",
     67              "esc16j",
     68              "esc32a",
     69              "esc32b",
     70              "esc32c",
     71              "esc32d",
     72              "esc32e",
     73              "esc32f",
     74              "esc32g",
     75              "esc32h",
     76              "had12",
     77              "had14",
     78              "had16",
     79              "had18",
     80              "had20",
     81              "kra32",
     82              "lipa20a",
     83              "lipa30a",
     84              "lipa40a",
     85              "lipa50a",
     86              "lipa60a",
     87              "lipa70a",
     88              "lipa80a",
     89              "lipa90a",
     90              "nug12",
     91              "nug14",
     92              "nug15",
     93              "nug16a",
     94              "nug16b",
     95              "nug17",
     96              "nug18",
     97              "nug20",
     98              "nug21",
     99              "nug22",
     100              "nug24",
     101              "nug25",
     102              "nug27",
     103              "nug28",
     104              "rou12",
     105              "rou15",
     106              "rou20",
     107              "scr12",
     108              "scr15",
     109              "scr20",
     110              "sko100a",
     111              "sko100b",
     112              "sko100c",
     113              "sko100d",
     114              "sko100e",
     115              "sko100f",
     116              "sko49",
     117              "sko81",
     118              "sko90",
     119              "ste36a",
     120              "ste36b",
     121              "tai100a",
     122              "tai100b",
     123              "tai12a",
     124              "tai12b",
     125              "tai150b",
     126              "tai15a",
     127              "tai15b",
     128              "tai17a",
     129              "tai20a",
     130              "tai20b",
     131              "tai256c",
     132              "tai25a",
     133              "tai25b",
     134              "tai30a",
     135              "tai30b",
     136              "tai35a",
     137              "tai35b",
     138              "tai40a",
     139              "tai40b",
     140              "tai50a",
     141              "tai50b",
     142              "tai60a",
     143              "tai60b",
     144              "tai64c",
     145              "tai80a",
     146              "tai80b",
     147              "wil100"
     148        });
     149      }
     150    }
    147151    #endregion
    148152
     
    211215
    212216                int[] assignment = slnParser.Assignment;
    213                 if (assignment != null && reversedSolutions.Contains(instance.Name)) {
     217                if (assignment != null && ReversedSolutions.Contains(instance.Name)) {
    214218                  assignment = (int[])slnParser.Assignment.Clone();
    215219                  for (int i = 0; i < assignment.Length; i++)
  • trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/BoundsCalculators/GilmoreLawlerBoundCalculator.cs

    r8092 r8910  
    2222using System;
    2323using HeuristicLab.Data;
     24using HeuristicLab.Encodings.PermutationEncoding;
    2425using HeuristicLab.Problems.LinearAssignment;
    2526
     
    2728  public static class GilmoreLawlerBoundCalculator {
    2829    public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances) {
     30      Permutation tmp;
     31      return CalculateLowerBound(weights, distances, out tmp);
     32    }
     33
     34    public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances, out Permutation solution) {
    2935      int N = weights.Rows;
    3036      DoubleMatrix sortedWeights = SortEachRowExceptDiagonal(weights), sortedDistances = SortEachRowExceptDiagonal(distances);
     
    4046
    4147      double result;
    42       LinearAssignmentProblemSolver.Solve(costs, out result);
     48      solution = new Permutation(PermutationTypes.Absolute, LinearAssignmentProblemSolver.Solve(costs, out result));
    4349      return result;
    4450    }
  • trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

    r8553 r8910  
    177177      if (!Parameters.ContainsKey("AverageQuality")) {
    178178        Parameters.Add(new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution."));
    179         AverageQuality = new DoubleValue(Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows);
     179        AverageQuality = new DoubleValue(ComputeAverageQuality());
    180180      }
    181181      #endregion
     
    401401
    402402    private void UpdateParameterValues() {
    403       LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances));
    404       AverageQuality = new DoubleValue(Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows);
     403      Permutation lbSolution;
     404      // calculate the optimum of a LAP relaxation and use it as lower bound of our QAP
     405      LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances, out lbSolution));
     406      // evalute the LAP optimal solution as if it was a QAP solution
     407      var lbSolutionQuality = QAPEvaluator.Apply(lbSolution, Weights, Distances);
     408      // in case both qualities are the same it means that the LAP optimum is also a QAP optimum
     409      if (LowerBound.Value.IsAlmost(lbSolutionQuality)) {
     410        BestKnownSolution = lbSolution;
     411        BestKnownQuality = new DoubleValue(LowerBound.Value);
     412      }
     413      AverageQuality = new DoubleValue(ComputeAverageQuality());
     414    }
     415
     416    private double ComputeAverageQuality() {
     417      double rt = 0, rd = 0, wt = 0, wd = 0;
     418      int n = Weights.Rows;
     419      for (int i = 0; i < n; i++)
     420        for (int j = 0; j < n; j++) {
     421          if (i == j) {
     422            rd += Distances[i, i];
     423            wd += Weights[i, i];
     424          } else {
     425            rt += Distances[i, j];
     426            wt += Weights[i, j];
     427          }
     428        }
     429
     430      return rt * wt / (n * (n - 1)) + rd * wd / n;
    405431    }
    406432    #endregion
Note: See TracChangeset for help on using the changeset viewer.