Changeset 16076 for branches/1614_GeneralizedQAP

Timestamp:

08/14/18 10:46:59 (6 years ago)

Author:

abeham

Message:

#1614: pending updates

Location:

branches/1614_GeneralizedQAP/GQAPSolver

Files:

• ALPS Instance.hl (added)
• GQAPSolver.csproj (modified) (4 diffs)
• Program.cs (modified) (8 diffs)
• Properties/Resources.Designer.cs (added)
• Properties/Resources.resx (added)

branches/1614_GeneralizedQAP/GQAPSolver/GQAPSolver.csproj

@@ -35 +35 @@
       <HintPath>..\packages\CommandLineParser.2.2.1\lib\net45\CommandLine.dll</HintPath>
     </Reference>
+    <Reference Include="HeuristicLab.Algorithms.ALPS-3.3">
+      <HintPath>..\..\..\trunk\bin\HeuristicLab.Algorithms.ALPS-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="HeuristicLab.Collections-3.3">
       <HintPath>..\..\..\trunk\bin\HeuristicLab.Collections-3.3.dll</HintPath>
@@ -44 +47 @@
       <HintPath>..\..\..\trunk\bin\HeuristicLab.Core-3.3.dll</HintPath>
     </Reference>
+    <Reference Include="HeuristicLab.Cplex-12.7.0">
+      <HintPath>..\..\..\trunk\bin\HeuristicLab.Cplex-12.7.0.dll</HintPath>
+    </Reference>
     <Reference Include="HeuristicLab.Data-3.3">
       <HintPath>..\..\..\trunk\bin\HeuristicLab.Data-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.LocalSolver-7.5">
+      <HintPath>..\..\..\trunk\bin\HeuristicLab.LocalSolver-7.5.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\bin\HeuristicLab.Operators-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Operators.Views.GraphVisualization-3.3">
+      <HintPath>..\..\..\trunk\bin\HeuristicLab.Operators.Views.GraphVisualization-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Persistence-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\bin\HeuristicLab.Persistence-3.3.dll</HintPath>
     </Reference>
     <Reference Include="HeuristicLab.Problems.Instances-3.3">
@@ -52 +72 @@
     <Reference Include="HeuristicLab.Problems.Instances.CordeauGQAP-3.3">
       <HintPath>..\..\..\trunk\bin\HeuristicLab.Problems.Instances.CordeauGQAP-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Selection-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\bin\HeuristicLab.Selection-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.SequentialEngine-3.3">
+      <HintPath>..\..\..\trunk\bin\HeuristicLab.SequentialEngine-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="localsolvernet, Version=7.5.0.0, Culture=neutral, processorArchitecture=AMD64">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\bin\localsolvernet.dll</HintPath>
+    </Reference>
+    <Reference Include="oplall, Version=12.7.0.0, Culture=neutral, PublicKeyToken=7906592bc7cc7340, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\bin\oplall.dll</HintPath>
     </Reference>
     <Reference Include="System" />
@@ -65 +100 @@
     <Compile Include="Program.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="Properties\Resources.Designer.cs">
+      <AutoGen>True</AutoGen>
+      <DesignTime>True</DesignTime>
+      <DependentUpon>Resources.resx</DependentUpon>
+    </Compile>
   </ItemGroup>
   <ItemGroup>
+    <None Include="ALPS Instance.hl" />
+    <EmbeddedResource Include="Properties\Resources.resx">
+      <Generator>ResXFileCodeGenerator</Generator>
+      <LastGenOutput>Resources.Designer.cs</LastGenOutput>
+    </EmbeddedResource>
     <None Include="App.config" />
     <None Include="packages.config" />

branches/1614_GeneralizedQAP/GQAPSolver/Program.cs

@@ -1 +1 @@
 using System;
+using System.IO;
 using System.Linq;
 using CommandLine;
+using HeuristicLab.Algorithms.ALPS;
 using HeuristicLab.Data;
+using HeuristicLab.Optimization;
+using HeuristicLab.Persistence.Default.Xml;
 using HeuristicLab.Problems.GeneralizedQuadraticAssignment;
+using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.CPLEX;
 using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary;
 using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP;
+using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC;
 using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch;
+using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSolverNet;
 using HeuristicLab.Problems.Instances.CordeauGQAP;
+using HeuristicLab.Selection;
 
 namespace GQAPSolver {
-  public enum AlgorithmType { OSGA = 1, ILS = 2, ES = 3, GRASP = 4 }
+  public enum AlgorithmType { ALPS = 0, OSGA = 1, ES = 2, ILS = 3, MLS = 4, GRASP = 5, PLAHCS = 6, CPLEX_FY = 7, CPLEX_KB = 8, LOSOL_01 = 9, LOSOL_N = 10 }
 
   class CLOptions {
@@ -23 +31 @@
     public string ProblemInstance { get; set; }
 
-    [Option('a', "alg", Default = AlgorithmType.OSGA, HelpText = "Either: OSGA, ILS, ES, GRASP")]
+    [Option('a', "alg", Required = true, HelpText = "Algorithm: ALPS, OSGA, ES, ILS, MLS, GRASP, PLAHCS, CPLEX_FY, CPLEX_KB, LOSOL_01, LOSOL_N")]
     public AlgorithmType Algorithm { get; set; }
 
@@ -39 +47 @@
     public int MaxEvaluations { get; set; }
 
-    [Option("popsize", Default = 500, HelpText = "Population size (OSGA)")]
+    [Option("agegap", Default = 20, HelpText = "Age gap (ALPS)")]
+    public int AgeGap { get; set; }
+    [Option("agescheme", Default = AgingScheme.Polynomial, HelpText = "Aging Scheme: Linear, Polynomial, Fibonacci, Exponentional (ALPS)")]
+    public AgingScheme AgingScheme { get; set; }
+    [Option("elites", Default = 1, HelpText = "Elite solutions (ALPS)")]
+    public int Elites { get; set; }
+    [Option("layers", Default = 10, HelpText = "Number of layers (ALPS)")]
+    public int NumberOfLayers { get; set; }
+    [Option("selpress", Default = 4, HelpText = "Selection pressure (ALPS)")]
+    public double SelectionPressure { get; set; }
+
+    [Option("popsize", Default = 500, HelpText = "Population size (OSGA, ALPS)")]
     public int PopulationSize { get; set; }
-    [Option("mutprob", Default = 0.05, HelpText = "Mutation probability (OSGA)")]
+    [Option("mutprob", Default = 0.05, HelpText = "Mutation probability (OSGA, ALPS)")]
     public double MutationProbability { get; set; }
-
-    [Option("pertstr", Default = 0.5, HelpText = "Perturbation strength (ILS)")]
-    public double PerturbationStrength { get; set; }
 
     [Option("mu", Default = 10, HelpText = "Parent population size (ES)")]
@@ -51 +67 @@
     [Option("lambda", Default = 10, HelpText = "Offspring population size (ES)")]
     public int Lambda { get; set; }
-    [Option("evosel", Default = ESSelection.Plus, HelpText = "Selection strategy + or , (ES)")]
+    [Option("evosel", Default = ESSelection.Plus, HelpText = "Selection strategy + or , (ES, ALPS)")]
     public ESSelection Selection { get; set; }
     [Option("recomb", Default = 0, HelpText = "Use recombination 0 or 1 (ES)")]
     public int Recombination { get; set; }
+
+    [Option("pertstr", Default = 0.5, HelpText = "Perturbation strength (ILS)")]
+    public double PerturbationStrength { get; set; }
 
     [Option("eliteset", Default = 10, HelpText = "Size of the elite set (GRASP)")]
@@ -82 +101 @@
       var descriptors = provider.GetDataDescriptors().ToList();
       var avgBest = 0.0;
+      var gqapInstance = provider.LoadData(descriptors.Single(x => x.Name == opts.ProblemInstance));
+
       for (var t = 0; t < opts.Tries; t++) {
-        HeuristicLab.Optimization.IAlgorithm alg = null;
+        IAlgorithm alg = null;
         switch (opts.Algorithm) {
+          case AlgorithmType.ALPS:
+            using (var stream = new MemoryStream(Properties.Resources.ALPS)) {
+              var alps = (AlpsGeneticAlgorithm)XmlParser.Deserialize(stream, CompressionType.Zip);
+              alps.Seed.Value = (int)opts.Seed;
+              alps.SetSeedRandomly.Value = true;
+              #region Termination
+              var execTimeTerm = alps.Terminators.Operators.OfType<ExecutionTimeTerminator>().SingleOrDefault();
+              if (execTimeTerm != null) {
+                alps.Terminators.Operators.SetItemCheckedState(execTimeTerm, opts.MaxRuntime > 0);
+                execTimeTerm.Threshold.Value = TimeSpan.FromSeconds(opts.MaxRuntime);
+              }
+              var compTerm = alps.Terminators.Operators.OfType<ComparisonTerminator<IntValue>>().SingleOrDefault(x => x.Name == "Generations");
+              if (compTerm != null) {
+                alps.Terminators.Operators.SetItemCheckedState(compTerm, opts.MaxIterations > 0);
+                compTerm.Threshold.Value = opts.MaxIterations;
+              }
+              compTerm = alps.Terminators.Operators.OfType<ComparisonTerminator<IntValue>>().SingleOrDefault(x => x.Name == "Evaluations");
+              if (compTerm != null) {
+                alps.Terminators.Operators.SetItemCheckedState(compTerm, opts.MaxEvaluations > 0);
+                compTerm.Threshold.Value = opts.MaxEvaluations;
+              }
+              var fitTerm = alps.Terminators.Operators.OfType<SingleObjectiveQualityTerminator>().SingleOrDefault();
+              if (fitTerm != null) {
+                alps.Terminators.Operators.SetItemCheckedState(fitTerm, gqapInstance.BestKnownQuality.HasValue);
+                fitTerm.Threshold.Value = gqapInstance.BestKnownQuality.GetValueOrDefault();
+              }
+              if (alps.Terminators.Operators.CheckedItems.Count() == 0) throw new InvalidOperationException("No termination criteria defined for ALPS");
+              #endregion
+              alps.AgeGap.Value = opts.AgeGap;
+              alps.AgingScheme.Value = opts.AgingScheme;
+              alps.Elites.Value = opts.Elites;
+              alps.NumberOfLayers.Value = opts.NumberOfLayers;
+              if (!(alps.Selector is GeneralizedRankSelector))
+                alps.Selector = alps.SelectorParameter.ValidValues.OfType<GeneralizedRankSelector>().Single();
+              var sel = alps.Selector as GeneralizedRankSelector;
+              sel.PressureParameter.Value.Value = opts.SelectionPressure;
+              alps.PopulationSize.Value = opts.PopulationSize;
+              alps.MutationProbability.Value = opts.MutationProbability;
+              alps.PlusSelection = opts.Selection == ESSelection.Plus;
+              alg = alps;
+            }
+            break;
           case AlgorithmType.OSGA:
             alg = new OSGA() {
@@ -92 +155 @@
               PopulationSize = opts.PopulationSize,
               MutationProbability = opts.MutationProbability,
-              StopAtBestKnownQuality = true,
-              Seed = (int)opts.Seed,
-              SetSeedRandomly = false
-            };
-            break;
-          case AlgorithmType.ILS:
-            alg = new IteratedLS() {
-              MaximumEvaluations = opts.MaxEvaluations,
-              MaximumIterations = opts.MaxIterations,
-              MaximumRuntime = TimeSpan.FromSeconds(opts.MaxRuntime),
-              PerturbationStrength = opts.PerturbationStrength,
               StopAtBestKnownQuality = true,
               Seed = (int)opts.Seed,
@@ -117 +169 @@
               Selection = opts.Selection,
               UseRecombination = opts.Recombination > 0,
+              StopAtBestKnownQuality = true,
+              Seed = (int)opts.Seed,
+              SetSeedRandomly = false
+            };
+            break;
+          case AlgorithmType.ILS:
+            alg = new IteratedLS() {
+              MaximumEvaluations = opts.MaxEvaluations,
+              MaximumIterations = opts.MaxIterations,
+              MaximumRuntime = TimeSpan.FromSeconds(opts.MaxRuntime),
+              PerturbationStrength = opts.PerturbationStrength,
+              StopAtBestKnownQuality = true,
+              Seed = (int)opts.Seed,
+              SetSeedRandomly = false
+            };
+            break;
+          case AlgorithmType.MLS:
+            alg = new MultistartLS() {
+              MaximumEvaluations = opts.MaxEvaluations,
+              MaximumIterations = opts.MaxIterations,
+              MaximumRuntime = TimeSpan.FromSeconds(opts.MaxRuntime),
               StopAtBestKnownQuality = true,
               Seed = (int)opts.Seed,
@@ -139 +212 @@
             };
             break;
+          case AlgorithmType.PLAHCS:
+            alg = new PLAHCS() {
+              MaximumEvaluations = opts.MaxEvaluations,
+              MaximumIterations = opts.MaxIterations,
+              MaximumRuntime = TimeSpan.FromSeconds(opts.MaxRuntime),
+              MaximumExponent = 20,
+              StopAtBestKnownQuality = true,
+              Seed = (int)opts.Seed,
+              SetSeedRandomly = false
+            };
+            break;
+          case AlgorithmType.CPLEX_FY:
+            alg = new GQAP_FY() {
+              MaximumEvaluations = opts.MaxEvaluations,
+              MaximumIterations = opts.MaxIterations,
+              MaximumRuntime = TimeSpan.FromSeconds(opts.MaxRuntime),
+              StopAtBestKnownQuality = true
+            };
+            break;
+          case AlgorithmType.CPLEX_KB:
+            alg = new GQAP_KB() {
+              MaximumEvaluations = opts.MaxEvaluations,
+              MaximumIterations = opts.MaxIterations,
+              MaximumRuntime = TimeSpan.FromSeconds(opts.MaxRuntime),
+              StopAtBestKnownQuality = true
+            };
+            break;
+          case AlgorithmType.LOSOL_01:
+            alg = new GQAPBinarySolver() {
+              MaximumEvaluations = opts.MaxEvaluations,
+              MaximumIterations = opts.MaxIterations,
+              MaximumRuntime = TimeSpan.FromSeconds(opts.MaxRuntime),
+              StopAtBestKnownQuality = true
+            };
+            break;
+          case AlgorithmType.LOSOL_N:
+            alg = new GQAPIntegerSolver() {
+              MaximumEvaluations = opts.MaxEvaluations,
+              MaximumIterations = opts.MaxIterations,
+              MaximumRuntime = TimeSpan.FromSeconds(opts.MaxRuntime),
+              StopAtBestKnownQuality = true
+            };
+            break;
         }
-        if (alg == null) throw new InvalidOperationException("Unknown algorithm.");
+        if (alg == null) throw new InvalidOperationException("Unknown algorithm " + opts.Algorithm + ".");
         var prob = alg.Problem as GQAP;
         if (prob == null) alg.Problem = prob = new GQAP();
-        prob.Load(provider.LoadData(descriptors.Single(x => x.Name == opts.ProblemInstance)));
+        prob.Load(gqapInstance);
         alg.Start();
         avgBest += ((DoubleValue)alg.Results["BestQuality"].Value).Value;