Changeset 15472

Timestamp:

11/15/17 12:14:18 (6 years ago)

Author:

abeham

Message:

#2747: worked on the CFSAP

• merged HeuristicLab.Problems.Instances from trunk
• updated best known qualities
• reduced memory footprint of run
• added convergence graph result to solving strategy

Location:

branches/CFSAP

Files:

• HeuristicLab.Problems.Instances (modified) (1 prop)
• HeuristicLab.Problems.Instances.CFSAP/3.3/BozejkoCFSAPInstanceProvider.cs (modified) (4 diffs)
• HeuristicLab.Problems.Instances.CFSAP/3.3/Plugin.cs.frame (modified) (1 diff)
• HeuristicLab.Problems.Instances/3.3/HeuristicLab.Problems.Instances-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.Instances/3.3/Types/GCPData.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.Instances/3.3/Types/GCPData.cs)
• HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAP.cs (modified) (2 diffs)
• HeuristicLab.Problems.Scheduling.CFSAP/3.3/HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAP.cs (modified) (3 diffs)
• HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAPSolvingStrategy.cs (modified) (7 diffs)
• HeuristicLab.Problems.Scheduling.CFSAP/3.3/Plugin.cs.frame (modified) (2 diffs)

branches/CFSAP/HeuristicLab.Problems.Instances.CFSAP/3.3/BozejkoCFSAPInstanceProvider.cs

@@ -107 +107 @@
 
     private static readonly Dictionary<string, int> bestKnownCycleTimes = new Dictionary<string, int>() {
-{ "gi_001", 608 },
-{ "gi_002", 623 },
-{ "gi_003", 500 },
-{ "gi_004", 585 },
-{ "gi_005", 549 },
-{ "gi_006", 629 },
-{ "gi_007", 603 },
-{ "gi_008", 506 },
-{ "gi_009", 588 },
-{ "gi_010", 493 },
-{ "gi_011", 597 },
-{ "gi_012", 554 },
-{ "gi_013", 594 },
-{ "gi_014", 505 },
-{ "gi_015", 631 },
-{ "gi_016", 626 },
-{ "gi_017", 585 },
-{ "gi_018", 529 },
-{ "gi_019", 649 },
-{ "gi_020", 561 },
-{ "gi_021", 535 },
-{ "gi_022", 586 },
-{ "gi_023", 602 },
-{ "gi_024", 607 },
-{ "gi_025", 598 },
-{ "gi_026", 572 },
-{ "gi_027", 605 },
-{ "gi_028", 619 },
-{ "gi_029", 646 },
-{ "gi_030", 591 },
-{ "gi_031", 958 },
-{ "gi_032", 838 },
-{ "gi_033", 974 },
-{ "gi_034", 904 },
+{ "gi_001",  608 },
+{ "gi_002",  623 },
+{ "gi_003",  500 },
+{ "gi_004",  585 },
+{ "gi_005",  549 },
+{ "gi_006",  629 },
+{ "gi_007",  603 },
+{ "gi_008",  506 },
+{ "gi_009",  588 },
+{ "gi_010",  493 },
+{ "gi_011",  597 },
+{ "gi_012",  554 },
+{ "gi_013",  594 },
+{ "gi_014",  505 },
+{ "gi_015",  631 },
+{ "gi_016",  626 },
+{ "gi_017",  585 },
+{ "gi_018",  529 },
+{ "gi_019",  649 },
+{ "gi_020",  561 },
+{ "gi_021",  535 },
+{ "gi_022",  586 },
+{ "gi_023",  602 },
+{ "gi_024",  607 },
+{ "gi_025",  598 },
+{ "gi_026",  572 },
+{ "gi_027",  605 },
+{ "gi_028",  619 },
+{ "gi_029",  646 },
+{ "gi_030",  591 },
+{ "gi_031",  958 },
+{ "gi_032",  838 },
+{ "gi_033",  974 },
+{ "gi_034",  904 },
 { "gi_035", 1002 },
-{ "gi_036", 998 },
-{ "gi_037", 988 },
-{ "gi_038", 872 },
+{ "gi_036",  998 },
+{ "gi_037",  988 },
+{ "gi_038",  872 },
 { "gi_039", 1009 },
 { "gi_040", 1000 },
-{ "gi_041", 992 },
+{ "gi_041",  992 },
 { "gi_042", 1097 },
-{ "gi_043", 989 },
+{ "gi_043",  989 },
 { "gi_044", 1038 },
-{ "gi_045", 998 },
+{ "gi_045",  998 },
 { "gi_046", 1077 },
-{ "gi_047", 997 },
-{ "gi_048", 921 },
-{ "gi_049", 902 },
+{ "gi_047",  997 },
+{ "gi_048",  921 },
+{ "gi_049",  902 },
 { "gi_050", 1035 },
-{ "gi_051", 914 },
+{ "gi_051",  914 },
 { "gi_052", 1019 },
-{ "gi_053", 997 },
-{ "gi_054", 928 },
-{ "gi_055", 973 },
+{ "gi_053",  997 },
+{ "gi_054",  928 },
+{ "gi_055",  973 },
 { "gi_056", 1011 },
-{ "gi_057", 943 },
-{ "gi_058", 959 },
+{ "gi_057",  943 },
+{ "gi_058",  959 },
 { "gi_059", 1079 },
-{ "gi_060", 940 },
+{ "gi_060",  940 },
 { "gi_061", 2176 },
 { "gi_062", 2100 },
@@ -186 +186 @@
 { "gi_078", 2236 },
 { "gi_079", 2223 },
-{ "gi_080", 2136 },
+{ "gi_080", 2132 },
 { "gi_081", 2147 },
 { "gi_082", 2285 },
@@ -199 +199 @@
 { "gi_091", 4465 },
 { "gi_092", 4269 },
-{ "gi_093", 4201 },
-{ "gi_094", 4330 },
-{ "gi_095", 4158 },
+{ "gi_093", 4199 },
+{ "gi_094", 4319 },
+{ "gi_095", 4154 },
 { "gi_096", 4355 },
 { "gi_097", 4363 },
-{ "gi_098", 4268 },
-{ "gi_099", 4143 },
+{ "gi_098", 4264 },
+{ "gi_099", 4133 },
 { "gi_100", 4313 },
-{ "gi_101", 4285 },
+{ "gi_101", 4284 },
 { "gi_102", 4421 },
-{ "gi_103", 4288 },
+{ "gi_103", 4279 },
 { "gi_104", 4295 },
-{ "gi_105", 4295 },
+{ "gi_105", 4290 },
 { "gi_106", 4257 },
-{ "gi_107", 4610 },
-{ "gi_108", 4579 },
-{ "gi_109", 4578 },
+{ "gi_107", 4604 },
+{ "gi_108", 4285 },
+{ "gi_109", 4570 },
 { "gi_110", 4219 },
 { "gi_111", 4472 },
@@ -230 +230 @@
   }
 }
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+

branches/CFSAP/HeuristicLab.Problems.Instances.CFSAP/3.3/Plugin.cs.frame

@@ -25 +25 @@
   [Plugin("HeuristicLab.Problems.Instances.CFSAP", "Plugin that provides problem instances for the non-permutational cyclic flow shop problem with two machine nests.", "3.3.14.$WCREV$")]
   [PluginFile("HeuristicLab.Problems.Instances.CFSAP-3.3.dll", PluginFileType.Assembly)]
-  [PluginDependency("HeuristicLab.Common", "3.3")]
   [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
   public class HeuristicLabProblemsInstancesCFSAPPlugin : PluginBase { }

branches/CFSAP/HeuristicLab.Problems.Instances/3.3/HeuristicLab.Problems.Instances-3.3.csproj

@@ -129 +129 @@
     <Compile Include="ProblemInstanceManager.cs" />
     <Compile Include="IProblemInstanceExporter.cs" />
+    <Compile Include="Types\GCPData.cs" />
     <Compile Include="Types\CFSAPData.cs" />
     <Compile Include="Types\PTSPData.cs" />

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAP.cs

@@ -64 +64 @@
       : base(original, cloner) {}
     public CFSAP() {
-      Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each machine and each job."));
-      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times of each machine and between all jobs."));
+      Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each machine and each job.") { GetsCollected = false });
+      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times of each machine and between all jobs.") { GetsCollected = false });
 
       ProcessingTimesParameter.Value = new IntMatrix(new int[,] {
@@ -90 +90 @@
       Encoding.Add(new PermutationEncoding("sequence", 5, PermutationTypes.RelativeDirected));
       Encoding.Add(new BinaryVectorEncoding("assignment", 5));
+
+      EncodingParameter.GetsCollected = false;
+      foreach (var param in ((IEncoding)Encoding).Parameters.OfType<IValueParameter>().ToList()) {
+        param.GetsCollected = false;
+      }
 
       Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj

@@ -76 +76 @@
       <SpecificVersion>False</SpecificVersion>
       <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Encodings.PermutationEncoding-3.3.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
+    <Reference Include="HeuristicLab.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Operators-3.3.dll</HintPath>
       <Private>False</Private>
     </Reference>

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAP.cs

@@ -41 +41 @@
       : base(original, cloner) { }
     public MultiNestCFSAP() {
-      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("ProcessingTimes", "The processing times of each nest, each machine, each job."));
-      Parameters.Add(new ValueParameter<ItemList<ItemList<IntMatrix>>>("SetupTimes", "The sequence dependent set up times for each nest, each machine, and each job to each other."));
+      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("ProcessingTimes", "The processing times of each nest, each machine, each job.") { GetsCollected = false });
+      Parameters.Add(new ValueParameter<ItemList<ItemList<IntMatrix>>>("SetupTimes", "The sequence dependent set up times for each nest, each machine, and each job to each other.") { GetsCollected = false });
 
       ProcessingTimesParameter.Value = new ItemList<IntMatrix>() {
@@ -69 +69 @@
       Encoding.Add(new PermutationEncoding("seq0", 5, PermutationTypes.RelativeDirected));
       Encoding.Add(new BinaryVectorEncoding("assign0", 5));
+
+      EncodingParameter.GetsCollected = false;
+      foreach (var param in ((IEncoding)Encoding).Parameters.OfType<IValueParameter>().ToList()) {
+        param.GetsCollected = false;
+      }
 
       Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
@@ -124 +129 @@
         Encoding.Add(new BinaryVectorEncoding("assign" + n, data.Jobs));
       }
+
+      #region Reduce run size by removing collected parameters
+      foreach (var param in ((IEncoding)Encoding).Parameters.OfType<IValueParameter>().ToList())
+        param.GetsCollected = false;
+
+      var solCreator = SolutionCreator as IParameterizedItem;
+      if (solCreator != null) {
+        foreach (var param in solCreator.Parameters.OfType<IValueParameter>().ToList()) {
+          param.GetsCollected = false;
+          var secondLevel = param.Value as IParameterizedItem;
+          if (secondLevel != null) {
+            foreach (var secondLevelParam in secondLevel.Parameters.OfType<IValueParameter>().ToList())
+              secondLevelParam.GetsCollected = false;
+          }
+        }
+      }
+      #endregion
+
       Name = data.Name;
       Description = data.Description;

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAPSolvingStrategy.cs

@@ -3 +3 @@
 using System.Linq;
 using System.Threading;
+using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -32 +33 @@
     }
 
+
+    public IFixedValueParameter<StringValue> EvaluatedSolutionsNameParameter {
+      get { return (IFixedValueParameter<StringValue>)Parameters["EvaluatedSolutionsName"]; }
+    }
+
+    public IAlgorithm Solver {
+      get { return SolverParameter.Value; }
+      set { SolverParameter.Value = value; }
+    }
+
     public TimeSpan MaximumRuntime {
       get { return MaximumRuntimeParameter.Value.Value; }
       set { MaximumRuntimeParameter.Value.Value = value; }
+    }
+
+    public string EvaluatedSolutionsName {
+      get { return EvaluatedSolutionsNameParameter.Value.Value; }
+      set { EvaluatedSolutionsNameParameter.Value.Value = value; }
     }
 
@@ -47 +63 @@
       if (original.algorithmsResults != null)
         algorithmsResults = cloner.Clone(original.algorithmsResults);
+      if (original.qualityPerClock != null)
+        qualityPerClock = cloner.Clone(original.qualityPerClock);
+      if (original.qualityPerEvaluations != null)
+        qualityPerEvaluations = cloner.Clone(original.qualityPerEvaluations);
     }
     public MultiNestCFSAPSolvingStrategy() {
-      Parameters.Add(new ValueParameter<IAlgorithm>("Solver", "The actual solver template."));
+      Parameters.Add(new ValueParameter<IAlgorithm>("Solver", "The actual solver template.") { GetsCollected = false });
       Parameters.Add(new FixedValueParameter<TimeSpanValue>("MaximumRuntime", "The maximum time that the strategy should run.", new TimeSpanValue(TimeSpan.FromSeconds(60))));
+      Parameters.Add(new FixedValueParameter<StringValue>("EvaluatedSolutionsName", "The name of the result that shows the number of evaluated solutions by the actual solver.", new StringValue("EvaluatedSolutions")));
     }
     
     public override IDeepCloneable Clone(Cloner cloner) {
       return new MultiNestCFSAPSolvingStrategy(this, cloner);
+    }
+
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      if (!Parameters.ContainsKey("EvaluatedSolutionsName"))
+        Parameters.Add(new FixedValueParameter<StringValue>("EvaluatedSolutionsName", "The name of the result that shows the number of evaluated solutions by the actual solver.", new StringValue("EvaluatedSolutions")));
     }
 
@@ -63 +91 @@
     [Storable]
     private ResultCollection algorithmsResults;
+    [Storable]
+    private IndexedDataTable<double> qualityPerClock;
+    [Storable]
+    private IndexedDataTable<double> qualityPerEvaluations;
 
     protected override void OnPrepared() {
@@ -68 +100 @@
       algorithms = null;
       qualities = null;
+      algorithmsResults = null;
+      qualityPerClock = null;
+      qualityPerEvaluations = null;
     }
 
@@ -89 +124 @@
       var min = worst.Quality;
 
+      qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
+      var qpcRow = new IndexedDataRow<double>("First-hit Graph");
+      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
+      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
+      qualityPerClock.Rows.Add(qpcRow);
+      qualityPerEvaluations = new IndexedDataTable<double>("Quality per Evaluations");
+      var qpeRow = new IndexedDataRow<double>("First-hit Graph");
+      qualityPerEvaluations.Rows.Add(qpeRow);
+      double evaluations = GetEvaluatedSolutions();
+      qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
+      qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
+
       Results.Add(new Result("Nest with maximum T", new IntValue(worst.Index + 1)));
       Results.Add(new Result("Maximum T", new IntValue(min)));
+      Results.Add(new Result("BestQuality", new DoubleValue(min)));
       Results.Add(new Result("Best Solution Found At", new TimeSpanValue(ExecutionTime)));
       Results.Add(new Result("Delta T", new PercentValue((min - Problem.BestKnownQuality) / Problem.BestKnownQuality)));
       Results.Add(new Result("Nest Results", algorithmsResults));
+      Results.Add(new Result("QualityPerClock", qualityPerClock));
+      Results.Add(new Result("QualityPerEvaluations", qualityPerEvaluations));
 
       base.Initialize(cancellationToken);
+    }
+
+    private double GetEvaluatedSolutions() {
+      if (algorithmsResults == null) throw new InvalidOperationException("Strategy has not been started yet.");
+      return algorithmsResults.Select(x => {
+        IResult res;
+        if (((ResultCollection)x.Value).TryGetValue(EvaluatedSolutionsName, out res)) {
+          var itm = res.Value;
+          if (itm is IntValue) return ((IntValue)itm).Value;
+          else if (itm is DoubleValue) return ((DoubleValue)itm).Value;
+        }
+        throw new InvalidOperationException("No result " + EvaluatedSolutionsName + " in the collection of " + x.Name);
+      }).Sum();
     }
 
@@ -106 +169 @@
         qualities[worst.Index] = (int)((DoubleValue)algorithms[worst.Index].Results["BestQuality"].Value).Value;
         worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
+
+        var evaluations = GetEvaluatedSolutions();
+        var time = ExecutionTime.TotalSeconds;
+        var qpcRow = qualityPerClock.Rows.First();
+        var qpeRow = qualityPerEvaluations.Rows.First();
+        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, (double)min);
+        qpeRow.Values[qpeRow.Values.Count - 1] = Tuple.Create(evaluations, (double)min);
+
         if (worst.Quality < min) {
           min = worst.Quality;
-          Results["Nest with maximum T"].Value = new IntValue(worst.Index + 1);
-          Results["Maximum T"].Value = new IntValue(min);
-          Results["Best Solution Found At"].Value = new TimeSpanValue(ExecutionTime);
-          Results["Delta T"].Value = new PercentValue((min - Problem.BestKnownQuality) / Problem.BestKnownQuality);
+          ((IntValue)Results["Nest with maximum T"].Value).Value = worst.Index + 1;
+          ((IntValue)Results["Maximum T"].Value).Value = min;
+          ((DoubleValue)Results["BestQuality"].Value).Value = min;
+          ((TimeSpanValue)Results["Best Solution Found At"].Value).Value = TimeSpan.FromSeconds(time);
+          ((PercentValue)Results["Delta T"].Value).Value = (min - Problem.BestKnownQuality) / Problem.BestKnownQuality;
+          qpcRow.Values.Add(Tuple.Create(time, (double)min));
+          qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
         }
+
         if (cancellationToken.IsCancellationRequested) return;
       }

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/Plugin.cs.frame

@@ -30 +30 @@
   [PluginDependency("HeuristicLab.Collections", "3.3")]
   [PluginDependency("HeuristicLab.Common", "3.3")]
-  [PluginDependency("HeuristicLab.Common.Resources", "3.3")]
   [PluginDependency("HeuristicLab.Core", "3.3")]
   [PluginDependency("HeuristicLab.Data", "3.3")]
@@ -38 +37 @@
   [PluginDependency("HeuristicLab.Parameters", "3.3")]
   [PluginDependency("HeuristicLab.Persistence", "3.3")]
-  [PluginDependency("HeuristicLab.SimSharp", "3.0.9")]
+  [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
   public class HeuristicLabProblemsSchedulingCFSAPPlugin : PluginBase  {
   }