Free cookie consent management tool by TermsFeed Policy Generator

Changeset 5814


Ignore:
Timestamp:
03/23/11 12:03:24 (12 years ago)
Author:
abeham
Message:

#1330

  • Added a test if the reported quality of the solution instances is similar to the evaluated qualities of these solutions
  • Adapted parsing of the solution file and added another parameter whether the permutation should be treated as facility->location (HeuristicLab default) or location->facility.
  • Adapted QuadraticAssignmentProblem to use that method that corresponds with the reported quality since there is no consistent encoding over all files
  • Improved API documentation of the parsing methods
Location:
branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/Parsers/QAPLIBSolutionParser.cs

    r5648 r5814  
    11using System;
     2using System.Globalization;
    23using System.IO;
    34
     
    67    public int Size { get; private set; }
    78    public int[] Assignment { get; private set; }
    8     public double Qualiy { get; private set; }
     9    public double Quality { get; private set; }
    910    public Exception Error { get; private set; }
    1011
     
    1617      Size = 0;
    1718      Assignment = null;
    18       Qualiy = double.NaN;
     19      Quality = double.NaN;
    1920      Error = null;
    2021    }
    2122
    22     public bool Parse(string file) {
     23    /// <summary>
     24    /// Reads from the given stream data which is expected to be in the QAPLIB solution format.
     25    ///
     26    /// The QAPLIB solution file format (.sln) is as follows:
     27    /// First line: Size of the permutation followed by a blank followed by the quality formatted using no thousands separator and if a fractional number with the "." as decimal symbol
     28    /// Remaining lines: The values of the permutation separated by blanks. Values must lie in the range [1;size of the permutation].
     29    /// </summary>
     30    /// <param name="file">The file to read data from.</param>
     31    /// <param name="valueAsLocation">The numbers can be interpreted either as facilities or locations.
     32    /// HeuristicLab always encodes the permutation such that the index denotes the facility and the value the location.
     33    /// If this parameter is true, then the permutation is expected to follow this encoding.
     34    /// If this parameter is false, the meaning of value and index will be swapped when reading the permutation.</param>
     35    /// <returns></returns>
     36    public bool Parse(string file, bool valueAsLocation) {
    2337      using (Stream stream = new FileStream(file, FileMode.Open, FileAccess.Read)) {
    24         return Parse(stream);
     38        return Parse(stream, valueAsLocation);
    2539      }
    2640    }
    2741
    2842    /// <summary>
    29     /// Reads from the given stream data which is expected to be in the QAPLIB format.
     43    /// Reads from the given stream data which is expected to be in the QAPLIB solution format.
     44    ///
     45    /// The QAPLIB solution file format (.sln) is as follows:
     46    /// First line: Size of the permutation followed by a blank followed by the quality formatted using no thousands separator and if a fractional number with the "." as decimal symbol
     47    /// Remaining lines: The values of the permutation separated by blanks. Values must lie in the range [1;size of the permutation].
    3048    /// </summary>
    3149    /// <remarks>
     
    3351    /// </remarks>
    3452    /// <param name="stream">The stream to read data from.</param>
     53    /// <param name="valueAsLocation">The numbers can be interpreted either as facilities or locations.
     54    /// HeuristicLab always encodes the permutation such that the index denotes the facility and the value the location.
     55    /// If this parameter is true, then the permutation is expected to follow this encoding.
     56    /// If this parameter is false, the meaning of value and index will be swapped when reading the permutation.</param>
    3557    /// <returns>True if the file was successfully read or false otherwise.</returns>
    36     public bool Parse(Stream stream) {
     58    public bool Parse(Stream stream, bool valueAsLocation) {
    3759      Error = null;
    3860      try {
     
    4163        string[] firstline = reader.ReadLine().Split(delim, StringSplitOptions.RemoveEmptyEntries);
    4264        Size = int.Parse(firstline[0]);
    43         Qualiy = double.Parse(firstline[1]);
     65        Quality = double.Parse(firstline[1], CultureInfo.InvariantCulture.NumberFormat);
    4466        Assignment = new int[Size];
    4567        int read = 0;
     
    4870          string[] vals = valLine.Split(delim, StringSplitOptions.RemoveEmptyEntries);
    4971          for (int j = 0; j < vals.Length; j++) {
    50             Assignment[read++] = int.Parse(vals[j]);
     72            if (valueAsLocation)
     73              Assignment[int.Parse(vals[j]) - 1] = read++;
     74            else Assignment[read++] = int.Parse(vals[j]) - 1;
    5175          }
    5276        }
  • branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

    r5811 r5814  
    325325          .GetManifestResourceStream(InstancePrefix + instance + ".sln")) {
    326326          QAPLIBSolutionParser solParser = new QAPLIBSolutionParser();
    327           solParser.Parse(solStream);
     327          solParser.Parse(solStream, false); // most sln's seem to be of the type index = location => value = facility
    328328          if (solParser.Error != null) throw solParser.Error;
    329           BestKnownQuality = new DoubleValue(solParser.Qualiy);
    330           BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
     329          if (!solParser.Quality.IsAlmost(QAPEvaluator.Apply(new Permutation(PermutationTypes.Absolute, solParser.Assignment), Weights, DistanceMatrix))) {
     330            solStream.Seek(0, SeekOrigin.Begin);
     331            solParser.Parse(solStream, true); // some sln's seem to be of the type index = facility => value = location
     332            if (solParser.Error != null) throw solParser.Error;
     333            if (solParser.Quality.IsAlmost(QAPEvaluator.Apply(new Permutation(PermutationTypes.Absolute, solParser.Assignment), Weights, DistanceMatrix))) {
     334              BestKnownQuality = new DoubleValue(solParser.Quality);
     335              BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
     336            } else {
     337              BestKnownQuality = null;
     338              BestKnownSolution = null;
     339            }
     340          } else {
     341            BestKnownQuality = new DoubleValue(solParser.Quality);
     342            BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
     343          }
    331344        }
    332345      } else {
  • branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPLIBInstancesTest.cs

    r5648 r5814  
    11using System;
    22using System.Text;
     3using HeuristicLab.Common;
    34using HeuristicLab.Problems.QuadraticAssignment;
    45using Microsoft.VisualStudio.TestTools.UnitTesting;
     
    2021      Assert.IsTrue(failedInstances.Length == 0, "Following instances failed to load: " + Environment.NewLine + failedInstances.ToString());
    2122    }
     23
     24    [TestMethod]
     25    public void TestReportedSolutionQuality() {
     26      StringBuilder failedInstances = new StringBuilder();
     27      QuadraticAssignmentProblem qap = new QuadraticAssignmentProblem();
     28      foreach (string instance in qap.EmbeddedInstances) {
     29        try {
     30          qap.LoadEmbeddedInstance(instance);
     31        } catch {
     32          Assert.Fail("Not all instances load correctly");
     33        }
     34        if (qap.BestKnownSolution != null) {
     35          double quality = double.NaN;
     36          try {
     37            quality = QAPEvaluator.Apply(qap.BestKnownSolution, qap.Weights, qap.DistanceMatrix);
     38          } catch (Exception ex) {
     39            failedInstances.AppendLine("An unknown problem occurred evaluating solution of instance " + instance + ": " + ex.Message);
     40          }
     41          if (!quality.IsAlmost(qap.BestKnownQuality.Value)) {
     42            failedInstances.AppendLine(instance + ": Reported quality: " + qap.BestKnownQuality.Value.ToString() + ", evaluated fitness: " + quality.ToString() + ".");
     43          }
     44        }
     45
     46      }
     47      Assert.IsTrue(failedInstances.Length == 0, "Following instances report divergent fitness values: " + Environment.NewLine + failedInstances.ToString());
     48    }
    2249  }
    2350}
Note: See TracChangeset for help on using the changeset viewer.