Changeset 15472


Ignore:
Timestamp:
11/15/17 12:14:18 (2 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:
9 edited
1 copied

Legend:

Unmodified
Added
Removed
  • branches/CFSAP/HeuristicLab.Problems.Instances

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

    r15460 r15472  
    107107
    108108    private static readonly Dictionary<string, int> bestKnownCycleTimes = new Dictionary<string, int>() {
    109 { "gi_001", 608 },
    110 { "gi_002", 623 },
    111 { "gi_003", 500 },
    112 { "gi_004", 585 },
    113 { "gi_005", 549 },
    114 { "gi_006", 629 },
    115 { "gi_007", 603 },
    116 { "gi_008", 506 },
    117 { "gi_009", 588 },
    118 { "gi_010", 493 },
    119 { "gi_011", 597 },
    120 { "gi_012", 554 },
    121 { "gi_013", 594 },
    122 { "gi_014", 505 },
    123 { "gi_015", 631 },
    124 { "gi_016", 626 },
    125 { "gi_017", 585 },
    126 { "gi_018", 529 },
    127 { "gi_019", 649 },
    128 { "gi_020", 561 },
    129 { "gi_021", 535 },
    130 { "gi_022", 586 },
    131 { "gi_023", 602 },
    132 { "gi_024", 607 },
    133 { "gi_025", 598 },
    134 { "gi_026", 572 },
    135 { "gi_027", 605 },
    136 { "gi_028", 619 },
    137 { "gi_029", 646 },
    138 { "gi_030", 591 },
    139 { "gi_031", 958 },
    140 { "gi_032", 838 },
    141 { "gi_033", 974 },
    142 { "gi_034", 904 },
     109{ "gi_001",  608 },
     110{ "gi_002",  623 },
     111{ "gi_003",  500 },
     112{ "gi_004",  585 },
     113{ "gi_005",  549 },
     114{ "gi_006",  629 },
     115{ "gi_007",  603 },
     116{ "gi_008",  506 },
     117{ "gi_009",  588 },
     118{ "gi_010",  493 },
     119{ "gi_011",  597 },
     120{ "gi_012",  554 },
     121{ "gi_013",  594 },
     122{ "gi_014",  505 },
     123{ "gi_015",  631 },
     124{ "gi_016",  626 },
     125{ "gi_017",  585 },
     126{ "gi_018",  529 },
     127{ "gi_019",  649 },
     128{ "gi_020",  561 },
     129{ "gi_021",  535 },
     130{ "gi_022",  586 },
     131{ "gi_023",  602 },
     132{ "gi_024",  607 },
     133{ "gi_025",  598 },
     134{ "gi_026",  572 },
     135{ "gi_027",  605 },
     136{ "gi_028",  619 },
     137{ "gi_029",  646 },
     138{ "gi_030",  591 },
     139{ "gi_031",  958 },
     140{ "gi_032",  838 },
     141{ "gi_033",  974 },
     142{ "gi_034",  904 },
    143143{ "gi_035", 1002 },
    144 { "gi_036", 998 },
    145 { "gi_037", 988 },
    146 { "gi_038", 872 },
     144{ "gi_036",  998 },
     145{ "gi_037",  988 },
     146{ "gi_038",  872 },
    147147{ "gi_039", 1009 },
    148148{ "gi_040", 1000 },
    149 { "gi_041", 992 },
     149{ "gi_041",  992 },
    150150{ "gi_042", 1097 },
    151 { "gi_043", 989 },
     151{ "gi_043",  989 },
    152152{ "gi_044", 1038 },
    153 { "gi_045", 998 },
     153{ "gi_045",  998 },
    154154{ "gi_046", 1077 },
    155 { "gi_047", 997 },
    156 { "gi_048", 921 },
    157 { "gi_049", 902 },
     155{ "gi_047",  997 },
     156{ "gi_048",  921 },
     157{ "gi_049",  902 },
    158158{ "gi_050", 1035 },
    159 { "gi_051", 914 },
     159{ "gi_051",  914 },
    160160{ "gi_052", 1019 },
    161 { "gi_053", 997 },
    162 { "gi_054", 928 },
    163 { "gi_055", 973 },
     161{ "gi_053",  997 },
     162{ "gi_054",  928 },
     163{ "gi_055",  973 },
    164164{ "gi_056", 1011 },
    165 { "gi_057", 943 },
    166 { "gi_058", 959 },
     165{ "gi_057",  943 },
     166{ "gi_058",  959 },
    167167{ "gi_059", 1079 },
    168 { "gi_060", 940 },
     168{ "gi_060",  940 },
    169169{ "gi_061", 2176 },
    170170{ "gi_062", 2100 },
     
    186186{ "gi_078", 2236 },
    187187{ "gi_079", 2223 },
    188 { "gi_080", 2136 },
     188{ "gi_080", 2132 },
    189189{ "gi_081", 2147 },
    190190{ "gi_082", 2285 },
     
    199199{ "gi_091", 4465 },
    200200{ "gi_092", 4269 },
    201 { "gi_093", 4201 },
    202 { "gi_094", 4330 },
    203 { "gi_095", 4158 },
     201{ "gi_093", 4199 },
     202{ "gi_094", 4319 },
     203{ "gi_095", 4154 },
    204204{ "gi_096", 4355 },
    205205{ "gi_097", 4363 },
    206 { "gi_098", 4268 },
    207 { "gi_099", 4143 },
     206{ "gi_098", 4264 },
     207{ "gi_099", 4133 },
    208208{ "gi_100", 4313 },
    209 { "gi_101", 4285 },
     209{ "gi_101", 4284 },
    210210{ "gi_102", 4421 },
    211 { "gi_103", 4288 },
     211{ "gi_103", 4279 },
    212212{ "gi_104", 4295 },
    213 { "gi_105", 4295 },
     213{ "gi_105", 4290 },
    214214{ "gi_106", 4257 },
    215 { "gi_107", 4610 },
    216 { "gi_108", 4579 },
    217 { "gi_109", 4578 },
     215{ "gi_107", 4604 },
     216{ "gi_108", 4285 },
     217{ "gi_109", 4570 },
    218218{ "gi_110", 4219 },
    219219{ "gi_111", 4472 },
     
    230230  }
    231231}
     232
     233
     234
     235
     236
     237
     238
     239
     240
     241
     242
     243
     244
     245
     246
     247
     248
     249
     250
     251
     252
     253
     254
     255
     256
     257
     258
     259
     260
     261
     262
     263
     264
     265
     266
     267
     268
     269
     270
     271
     272
     273
     274
     275
     276
     277
     278
     279
     280
     281
     282
     283
     284
     285
     286
     287
     288
     289
     290
     291
     292
     293
     294
     295
     296
     297
     298
     299
     300
     301
     302
     303
     304
     305
     306
     307
     308
     309
     310
     311
     312
     313
     314
     315
     316
     317
     318
     319
     320
     321
     322
     323
     324
     325
     326
     327
     328
     329
     330
     331
     332
     333
     334
     335
     336
     337
     338
     339
     340
     341
     342
     343
     344
     345
     346
     347
     348
     349
     350
     351
  • branches/CFSAP/HeuristicLab.Problems.Instances.CFSAP/3.3/Plugin.cs.frame

    r14757 r15472  
    2525  [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$")]
    2626  [PluginFile("HeuristicLab.Problems.Instances.CFSAP-3.3.dll", PluginFileType.Assembly)]
    27   [PluginDependency("HeuristicLab.Common", "3.3")]
    2827  [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
    2928  public class HeuristicLabProblemsInstancesCFSAPPlugin : PluginBase { }
  • branches/CFSAP/HeuristicLab.Problems.Instances/3.3/HeuristicLab.Problems.Instances-3.3.csproj

    r14757 r15472  
    129129    <Compile Include="ProblemInstanceManager.cs" />
    130130    <Compile Include="IProblemInstanceExporter.cs" />
     131    <Compile Include="Types\GCPData.cs" />
    131132    <Compile Include="Types\CFSAPData.cs" />
    132133    <Compile Include="Types\PTSPData.cs" />
  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAP.cs

    r15460 r15472  
    6464      : base(original, cloner) {}
    6565    public CFSAP() {
    66       Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each machine and each job."));
    67       Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times of each machine and between all jobs."));
     66      Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each machine and each job.") { GetsCollected = false });
     67      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times of each machine and between all jobs.") { GetsCollected = false });
    6868
    6969      ProcessingTimesParameter.Value = new IntMatrix(new int[,] {
     
    9090      Encoding.Add(new PermutationEncoding("sequence", 5, PermutationTypes.RelativeDirected));
    9191      Encoding.Add(new BinaryVectorEncoding("assignment", 5));
     92
     93      EncodingParameter.GetsCollected = false;
     94      foreach (var param in ((IEncoding)Encoding).Parameters.OfType<IValueParameter>().ToList()) {
     95        param.GetsCollected = false;
     96      }
    9297
    9398      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj

    r15460 r15472  
    7676      <SpecificVersion>False</SpecificVersion>
    7777      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Encodings.PermutationEncoding-3.3.dll</HintPath>
     78      <Private>False</Private>
     79    </Reference>
     80    <Reference Include="HeuristicLab.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     81      <SpecificVersion>False</SpecificVersion>
     82      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Operators-3.3.dll</HintPath>
    7883      <Private>False</Private>
    7984    </Reference>
  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAP.cs

    r15460 r15472  
    4141      : base(original, cloner) { }
    4242    public MultiNestCFSAP() {
    43       Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("ProcessingTimes", "The processing times of each nest, each machine, each job."));
    44       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."));
     43      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("ProcessingTimes", "The processing times of each nest, each machine, each job.") { GetsCollected = false });
     44      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 });
    4545
    4646      ProcessingTimesParameter.Value = new ItemList<IntMatrix>() {
     
    6969      Encoding.Add(new PermutationEncoding("seq0", 5, PermutationTypes.RelativeDirected));
    7070      Encoding.Add(new BinaryVectorEncoding("assign0", 5));
     71
     72      EncodingParameter.GetsCollected = false;
     73      foreach (var param in ((IEncoding)Encoding).Parameters.OfType<IValueParameter>().ToList()) {
     74        param.GetsCollected = false;
     75      }
    7176
    7277      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
     
    124129        Encoding.Add(new BinaryVectorEncoding("assign" + n, data.Jobs));
    125130      }
     131
     132      #region Reduce run size by removing collected parameters
     133      foreach (var param in ((IEncoding)Encoding).Parameters.OfType<IValueParameter>().ToList())
     134        param.GetsCollected = false;
     135
     136      var solCreator = SolutionCreator as IParameterizedItem;
     137      if (solCreator != null) {
     138        foreach (var param in solCreator.Parameters.OfType<IValueParameter>().ToList()) {
     139          param.GetsCollected = false;
     140          var secondLevel = param.Value as IParameterizedItem;
     141          if (secondLevel != null) {
     142            foreach (var secondLevelParam in secondLevel.Parameters.OfType<IValueParameter>().ToList())
     143              secondLevelParam.GetsCollected = false;
     144          }
     145        }
     146      }
     147      #endregion
     148
    126149      Name = data.Name;
    127150      Description = data.Description;
  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAPSolvingStrategy.cs

    r15460 r15472  
    33using System.Linq;
    44using System.Threading;
     5using HeuristicLab.Analysis;
    56using HeuristicLab.Common;
    67using HeuristicLab.Core;
     
    3233    }
    3334
     35
     36    public IFixedValueParameter<StringValue> EvaluatedSolutionsNameParameter {
     37      get { return (IFixedValueParameter<StringValue>)Parameters["EvaluatedSolutionsName"]; }
     38    }
     39
     40    public IAlgorithm Solver {
     41      get { return SolverParameter.Value; }
     42      set { SolverParameter.Value = value; }
     43    }
     44
    3445    public TimeSpan MaximumRuntime {
    3546      get { return MaximumRuntimeParameter.Value.Value; }
    3647      set { MaximumRuntimeParameter.Value.Value = value; }
     48    }
     49
     50    public string EvaluatedSolutionsName {
     51      get { return EvaluatedSolutionsNameParameter.Value.Value; }
     52      set { EvaluatedSolutionsNameParameter.Value.Value = value; }
    3753    }
    3854
     
    4763      if (original.algorithmsResults != null)
    4864        algorithmsResults = cloner.Clone(original.algorithmsResults);
     65      if (original.qualityPerClock != null)
     66        qualityPerClock = cloner.Clone(original.qualityPerClock);
     67      if (original.qualityPerEvaluations != null)
     68        qualityPerEvaluations = cloner.Clone(original.qualityPerEvaluations);
    4969    }
    5070    public MultiNestCFSAPSolvingStrategy() {
    51       Parameters.Add(new ValueParameter<IAlgorithm>("Solver", "The actual solver template."));
     71      Parameters.Add(new ValueParameter<IAlgorithm>("Solver", "The actual solver template.") { GetsCollected = false });
    5272      Parameters.Add(new FixedValueParameter<TimeSpanValue>("MaximumRuntime", "The maximum time that the strategy should run.", new TimeSpanValue(TimeSpan.FromSeconds(60))));
     73      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")));
    5374    }
    5475   
    5576    public override IDeepCloneable Clone(Cloner cloner) {
    5677      return new MultiNestCFSAPSolvingStrategy(this, cloner);
     78    }
     79
     80
     81    [StorableHook(HookType.AfterDeserialization)]
     82    private void AfterDeserialization() {
     83      if (!Parameters.ContainsKey("EvaluatedSolutionsName"))
     84        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")));
    5785    }
    5886
     
    6391    [Storable]
    6492    private ResultCollection algorithmsResults;
     93    [Storable]
     94    private IndexedDataTable<double> qualityPerClock;
     95    [Storable]
     96    private IndexedDataTable<double> qualityPerEvaluations;
    6597
    6698    protected override void OnPrepared() {
     
    68100      algorithms = null;
    69101      qualities = null;
     102      algorithmsResults = null;
     103      qualityPerClock = null;
     104      qualityPerEvaluations = null;
    70105    }
    71106
     
    89124      var min = worst.Quality;
    90125
     126      qualityPerClock = new IndexedDataTable<double>("Quality per Clock");
     127      var qpcRow = new IndexedDataRow<double>("First-hit Graph");
     128      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
     129      qpcRow.Values.Add(Tuple.Create(ExecutionTime.TotalSeconds, (double)min));
     130      qualityPerClock.Rows.Add(qpcRow);
     131      qualityPerEvaluations = new IndexedDataTable<double>("Quality per Evaluations");
     132      var qpeRow = new IndexedDataRow<double>("First-hit Graph");
     133      qualityPerEvaluations.Rows.Add(qpeRow);
     134      double evaluations = GetEvaluatedSolutions();
     135      qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
     136      qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
     137
    91138      Results.Add(new Result("Nest with maximum T", new IntValue(worst.Index + 1)));
    92139      Results.Add(new Result("Maximum T", new IntValue(min)));
     140      Results.Add(new Result("BestQuality", new DoubleValue(min)));
    93141      Results.Add(new Result("Best Solution Found At", new TimeSpanValue(ExecutionTime)));
    94142      Results.Add(new Result("Delta T", new PercentValue((min - Problem.BestKnownQuality) / Problem.BestKnownQuality)));
    95143      Results.Add(new Result("Nest Results", algorithmsResults));
     144      Results.Add(new Result("QualityPerClock", qualityPerClock));
     145      Results.Add(new Result("QualityPerEvaluations", qualityPerEvaluations));
    96146
    97147      base.Initialize(cancellationToken);
     148    }
     149
     150    private double GetEvaluatedSolutions() {
     151      if (algorithmsResults == null) throw new InvalidOperationException("Strategy has not been started yet.");
     152      return algorithmsResults.Select(x => {
     153        IResult res;
     154        if (((ResultCollection)x.Value).TryGetValue(EvaluatedSolutionsName, out res)) {
     155          var itm = res.Value;
     156          if (itm is IntValue) return ((IntValue)itm).Value;
     157          else if (itm is DoubleValue) return ((DoubleValue)itm).Value;
     158        }
     159        throw new InvalidOperationException("No result " + EvaluatedSolutionsName + " in the collection of " + x.Name);
     160      }).Sum();
    98161    }
    99162
     
    106169        qualities[worst.Index] = (int)((DoubleValue)algorithms[worst.Index].Results["BestQuality"].Value).Value;
    107170        worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
     171
     172        var evaluations = GetEvaluatedSolutions();
     173        var time = ExecutionTime.TotalSeconds;
     174        var qpcRow = qualityPerClock.Rows.First();
     175        var qpeRow = qualityPerEvaluations.Rows.First();
     176        qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, (double)min);
     177        qpeRow.Values[qpeRow.Values.Count - 1] = Tuple.Create(evaluations, (double)min);
     178
    108179        if (worst.Quality < min) {
    109180          min = worst.Quality;
    110           Results["Nest with maximum T"].Value = new IntValue(worst.Index + 1);
    111           Results["Maximum T"].Value = new IntValue(min);
    112           Results["Best Solution Found At"].Value = new TimeSpanValue(ExecutionTime);
    113           Results["Delta T"].Value = new PercentValue((min - Problem.BestKnownQuality) / Problem.BestKnownQuality);
     181          ((IntValue)Results["Nest with maximum T"].Value).Value = worst.Index + 1;
     182          ((IntValue)Results["Maximum T"].Value).Value = min;
     183          ((DoubleValue)Results["BestQuality"].Value).Value = min;
     184          ((TimeSpanValue)Results["Best Solution Found At"].Value).Value = TimeSpan.FromSeconds(time);
     185          ((PercentValue)Results["Delta T"].Value).Value = (min - Problem.BestKnownQuality) / Problem.BestKnownQuality;
     186          qpcRow.Values.Add(Tuple.Create(time, (double)min));
     187          qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
    114188        }
     189
    115190        if (cancellationToken.IsCancellationRequested) return;
    116191      }
  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/Plugin.cs.frame

    r14757 r15472  
    3030  [PluginDependency("HeuristicLab.Collections", "3.3")]
    3131  [PluginDependency("HeuristicLab.Common", "3.3")]
    32   [PluginDependency("HeuristicLab.Common.Resources", "3.3")]
    3332  [PluginDependency("HeuristicLab.Core", "3.3")]
    3433  [PluginDependency("HeuristicLab.Data", "3.3")]
     
    3837  [PluginDependency("HeuristicLab.Parameters", "3.3")]
    3938  [PluginDependency("HeuristicLab.Persistence", "3.3")]
    40   [PluginDependency("HeuristicLab.SimSharp", "3.0.9")]
     39  [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
    4140  public class HeuristicLabProblemsSchedulingCFSAPPlugin : PluginBase  {
    4241  }
Note: See TracChangeset for help on using the changeset viewer.