Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/09/16 15:56:22 (7 years ago)
Author:
abeham
Message:

#2701:

  • Updated GraphColoringProblem and Problems.Instances
    • Added new fitness function from literature
    • Added DIMACS benchmark instances
  • Updated LinearLinkageEncoding
    • Added HammingSimilarityCalculator
Location:
branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS
Files:
11 added
3 copied

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS/3.3/GcolDataDescriptor.cs

    r14429 r14471  
    2020#endregion
    2121
    22 namespace HeuristicLab.Problems.Instances.QAPLIB {
    23   internal class QAPLIBDataDescriptor : IDataDescriptor {
     22namespace HeuristicLab.Problems.Instances.DIMACS {
     23  internal class GcolDataDescriptor : IDataDescriptor {
    2424    public string Name { get; internal set; }
    2525    public string Description { get; internal set; }
    2626
    2727    internal string InstanceIdentifier { get; set; }
    28     internal string SolutionIdentifier { get; set; }
    2928
    30     internal QAPLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
     29    internal GcolDataDescriptor(string name, string description, string instanceIdentifier) {
    3130      this.Name = name;
    3231      this.Description = description;
    3332      this.InstanceIdentifier = instanceIdentifier;
    34       this.SolutionIdentifier = solutionIdentifier;
    3533    }
    3634  }

  • branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS/3.3/GcolInstanceProvider.cs

    r14429 r14471  
    2828using System.Text.RegularExpressions;
    2929
    30 namespace HeuristicLab.Problems.Instances.QAPLIB {
    31   public class QAPLIBInstanceProvider : ProblemInstanceProvider<QAPData> {
    32     #region Reversed instances
    33     // These instances specified their best known solution in the wrong order
    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     }
    151     #endregion
     30namespace HeuristicLab.Problems.Instances.DIMACS {
     31  public class GcolInstanceProvider : ProblemInstanceProvider<GCPData> {
    15232
    15333    public override string Name {
    154       get { return "QAPLIB"; }
     34      get { return "DIMACS Graph Coloring"; }
    15535    }
    15636
    15737    public override string Description {
    158       get { return "Quadratic Assignment Problem Library"; }
     38      get { return "Graph Coloring problem instance library"; }
    15939    }
    16040
    16141    public override Uri WebLink {
    162       get { return new Uri("http://www.seas.upenn.edu/qaplib/"); }
     42      get { return new Uri("https://turing.cs.hbg.psu.edu/txn131/graphcoloring.html"); }
    16343    }
    16444
    16545    public override string ReferencePublication {
    16646      get {
    167         return @"R. E. Burkard, S. E. Karisch, and F. Rendl. 1997.
    168 QAPLIB - A Quadratic Assignment Problem Library.
    169 Journal of Global Optimization, 10, pp. 391-403.";
     47        return string.Empty;
    17048      }
    17149    }
    17250
    173     protected virtual string FileName { get { return "qap"; } }
     51    protected virtual string FileName { get { return "col"; } }
    17452
    17553    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    176       Dictionary<string, string> solutions = new Dictionary<string, string>();
    177       var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip");
    178       if (!String.IsNullOrEmpty(solutionsArchiveName)) {
    179         using (var solutionsZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName), ZipArchiveMode.Read)) {
    180           foreach (var entry in solutionsZipFile.Entries)
    181             solutions.Add(Path.GetFileNameWithoutExtension(entry.Name) + ".dat", entry.Name);
    182         }
    183       }
    184       var instanceArchiveName = GetResourceName(FileName + @"\.dat\.zip");
     54      var instanceArchiveName = GetResourceName(FileName + @"\.zip");
    18555      if (String.IsNullOrEmpty(instanceArchiveName)) yield break;
    18656
    18757      using (var instanceStream = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) {
    18858        foreach (var entry in instanceStream.Entries.Select(x => x.Name).OrderBy(x => x)) {
    189           yield return new QAPLIBDataDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry, solutions.ContainsKey(entry) ? solutions[entry] : String.Empty);
     59          yield return new GcolDataDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry);
    19060        }
    19161      }
    19262    }
    19363
    194     public override QAPData LoadData(IDataDescriptor id) {
    195       var descriptor = (QAPLIBDataDescriptor)id;
    196       var instanceArchiveName = GetResourceName(FileName + @"\.dat\.zip");
     64    public override GCPData LoadData(IDataDescriptor id) {
     65      var descriptor = (GcolDataDescriptor)id;
     66      var instanceArchiveName = GetResourceName(FileName + @"\.zip");
    19767      using (var instancesZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) {
    19868        var entry = instancesZipFile.GetEntry(descriptor.InstanceIdentifier);
    19969
    20070        using (var stream = entry.Open()) {
    201           var parser = new QAPLIBParser();
     71          var parser = new Parser();
    20272          parser.Parse(stream);
    20373          var instance = Load(parser);
    20474          instance.Name = id.Name;
    20575          instance.Description = id.Description;
    206 
    207           if (!String.IsNullOrEmpty(descriptor.SolutionIdentifier)) {
    208             var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip");
    209             using (var solutionsZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName), ZipArchiveMode.Read)) {
    210               entry = solutionsZipFile.GetEntry(descriptor.SolutionIdentifier);
    211               using (var solStream = entry.Open()) {
    212                 var slnParser = new QAPLIBSolutionParser();
    213                 slnParser.Parse(solStream, true);
    214                 if (slnParser.Error != null) throw slnParser.Error;
    215 
    216                 int[] assignment = slnParser.Assignment;
    217                 if (assignment != null && ReversedSolutions.Contains(instance.Name)) {
    218                   assignment = (int[])slnParser.Assignment.Clone();
    219                   for (int i = 0; i < assignment.Length; i++)
    220                     assignment[slnParser.Assignment[i]] = i;
    221                 }
    222                 instance.BestKnownAssignment = assignment;
    223                 instance.BestKnownQuality = slnParser.Quality;
    224               }
    225             }
    226           }
     76          int bestknown;
     77          if (bkq.TryGetValue(instance.Name, out bestknown))
     78            instance.BestKnownColors = bestknown;
    22779          return instance;
    22880        }
    … …  
    23385      get { return true; }
    23486    }
    235     public override QAPData ImportData(string path) {
    236       var parser = new QAPLIBParser();
     87    public override GCPData ImportData(string path) {
     88      var parser = new Parser();
    23789      parser.Parse(path);
    23890      var instance = Load(parser);
    … …  
    24294    }
    24395
    244     private QAPData Load(QAPLIBParser parser) {
    245       var instance = new QAPData();
    246       instance.Dimension = parser.Size;
    247       instance.Distances = parser.Distances;
    248       instance.Weights = parser.Weights;
     96    private GCPData Load(Parser parser) {
     97      var instance = new GCPData();
     98      instance.Nodes = parser.Nodes;
     99      var adjacencies = new int[parser.Edges, 2];
     100      var i = 0;
     101      foreach (var a in parser.AdjacencyList) {
     102        adjacencies[i, 0] = a.Item1 - 1;
     103        adjacencies[i, 1] = a.Item2 - 1;
     104        i++;
     105      }
     106      instance.Adjacencies = adjacencies;
    249107      return instance;
    250108    }
    … …  
    258116              .Where(x => Regex.Match(x, @".*\.Data\." + fileName).Success).SingleOrDefault();
    259117    }
     118
     119    private Dictionary<string, int> bkq = new Dictionary<string, int> {
     120      { "fpsol2.i.1", 65 },
     121      { "fpsol2.i.2", 30 },
     122      { "fpsol2.i.3", 30 },
     123      { "inithx.i.1", 54 },
     124      { "inithx.i.2", 31 },
     125      { "inithx.i.3", 31 },
     126      { "le450_5a", 5 },
     127      { "le450_5b", 5 },
     128      { "le450_5c", 5 },
     129      { "le450_5d", 5 },
     130      { "le450_15a", 15 },
     131      { "le450_15b", 15 },
     132      { "le450_15c", 15 },
     133      { "le450_15d", 15 },
     134      { "le450_25a", 25 },
     135      { "le450_25b", 25 },
     136      { "le450_25c", 25 },
     137      { "le450_25d", 25 },
     138      { "mulsol.i.1", 49 },
     139      { "mulsol.i.2", 31 },
     140      { "mulsol.i.3", 31 },
     141      { "mulsol.i.4", 31 },
     142      { "mulsol.i.5", 31 },
     143      { "zeroin.i.1", 49 },
     144      { "zeroin.i.2", 30 },
     145      { "zeroin.i.3", 30 },
     146      { "anna", 11 },
     147      { "david", 11 },
     148      { "homer", 13 },
     149      { "huck", 11 },
     150      { "jean", 10 },
     151      { "games120", 9 },
     152      { "miles250", 8 },
     153      { "miles500", 20 },
     154      { "miles750", 31 },
     155      { "miles1000", 42 },
     156      { "miles1500", 73 },
     157      { "queen5_5", 5 },
     158      { "queen6_6", 7 },
     159      { "queen7_7", 7 },
     160      { "queen8_8", 9 },
     161      { "queen8_12", 12 },
     162      { "queen9_9", 10 },
     163      { "queen11_11", 11 },
     164      { "queen13_13", 13 },
     165      { "myciel3", 4 },
     166      { "myciel4", 5 },
     167      { "myciel5", 6 },
     168      { "myciel6", 7 },
     169      { "myciel7", 8 },
     170      { "mugg88_1", 4 },
     171      { "mugg88_25", 4 },
     172      { "mugg100_1", 4 },
     173      { "mugg100_25", 4 },
     174      { "1-Insertions_4", 4 },
     175      { "2-Insertions_3", 4 },
     176      { "2-Insertions_4", 4 },
     177      { "3-Insertions_3", 4 },
     178      { "4-Insertions_3", 3 },
     179      { "qg.order30", 30 },
     180      { "qg.order40", 40 },
     181      { "qg.order60", 60 },
     182      { "qg.order100", 100 }
     183    };
    260184  }
    261185}

  • branches/MemPRAlgorithm/HeuristicLab.Problems.Instances.DIMACS/3.3/Parser.cs

    r14429 r14471  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.IO;
    2425
    25 namespace HeuristicLab.Problems.Instances.QAPLIB {
    26   public class QAPLIBParser {
    27     public int Size { get; private set; }
    28     public double[,] Distances { get; private set; }
    29     public double[,] Weights { get; private set; }
     26namespace HeuristicLab.Problems.Instances.DIMACS {
     27  public class Parser {
     28    public int Nodes { get; private set; }
     29    public int Edges { get; private set; }
     30    public ICollection<Tuple<int, int>> AdjacencyList { get { return edges; } }
     31    private HashSet<Tuple<int, int>> edges;
    3032
    31     public QAPLIBParser() {
     33    public Parser() {
    3234      Reset();
    3335    }
    3436
    3537    public void Reset() {
    36       Size = 0;
    37       Distances = null;
    38       Weights = null;
     38      Nodes = 0;
     39      Edges = 0;
     40      edges = new HashSet<Tuple<int, int>>();
    3941    }
    4042
    … …  
    5456    /// <returns>True if the file was successfully read or false otherwise.</returns>
    5557    public void Parse(Stream stream) {
     58      char[] delim = new char[] { ' ', '\t' };
    5659      var reader = new StreamReader(stream);
    57       Size = int.Parse(reader.ReadLine());
    58       Distances = new double[Size, Size];
    59       Weights = new double[Size, Size];
    60       char[] delim = new char[] { ' ', '\t' };
     60      var line = reader.ReadLine().Trim();
     61      // skip comments
     62      while (line.StartsWith("c", StringComparison.InvariantCultureIgnoreCase)) line = reader.ReadLine().Trim();
    6163
    62       Weights = ParseMatrix(reader, delim);
    63       Distances = ParseMatrix(reader, delim);
    64     }
    65 
    66     private double[,] ParseMatrix(StreamReader reader, char[] delim) {
    67       int read = 0, k = 0;
    68       double[,] result = new double[Size, Size];
    69       while (k < Size) {
    70         if (reader.EndOfStream) throw new InvalidDataException("Reached end of stream while reading second matrix.");
    71         string valLine = reader.ReadLine();
    72         while (String.IsNullOrWhiteSpace(valLine)) valLine = reader.ReadLine();
    73         string[] vals = valLine.Split(delim, StringSplitOptions.RemoveEmptyEntries);
    74         foreach (string val in vals) {
    75           result[k, read++] = double.Parse(val);
    76           if (read == Size) {
    77             read = 0;
    78             k++;
    79           }
    80         }
    81       }
    82       return result;
     64      // p edge NODES EDGES
     65      var split = line.Split(delim, StringSplitOptions.RemoveEmptyEntries);
     66      Nodes = int.Parse(split[2]);
     67      do {
     68        line = reader.ReadLine();
     69        if (string.IsNullOrEmpty(line)) break;
     70        // e XX YY
     71        split = line.Split(delim, StringSplitOptions.RemoveEmptyEntries);
     72        var src = int.Parse(split[1]);
     73        var tgt = int.Parse(split[2]);
     74        Tuple<int, int> e = null;
     75        if (src < tgt) e = Tuple.Create(src, tgt);
     76        else if (src > tgt) e = Tuple.Create(tgt, src);
     77        else continue; // src == tgt
     78        if (edges.Add(e)) Edges++;
     79      } while (!reader.EndOfStream);
    8380    }
    8481  }
Note: See TracChangeset for help on using the changeset viewer.