Changeset 17530

Timestamp:

05/08/20 12:06:23 (5 years ago)

Author:

abeham

Message:

#2521: Refactored linear assignment problem

Location:

branches/2521_ProblemRefactoring/HeuristicLab.Problems.LinearAssignment/3.3

Files:

• Analyzers (deleted)
• HeuristicLab.Problems.LinearAssignment-3.3.csproj (modified) (1 diff)
• HungarianAlgorithm.cs (modified) (4 diffs)
• Interfaces (deleted)
• LAPEvaluator.cs (deleted)
• LinearAssignmentProblem.cs (modified) (12 diffs)

branches/2521_ProblemRefactoring/HeuristicLab.Problems.LinearAssignment/3.3/HeuristicLab.Problems.LinearAssignment-3.3.csproj

@@ -122 +122 @@
     <Compile Include="LAPAssignment.cs" />
     <None Include="Plugin.cs.frame" />
-    <Compile Include="Analyzers\BestLAPSolutionAnalyzer.cs" />
-    <Compile Include="Interfaces\ILAPEvaluator.cs" />
-    <Compile Include="LAPEvaluator.cs" />
     <Compile Include="LinearAssignmentProblem.cs" />
     <Compile Include="LinearAssignmentProblemSolver.cs" />

branches/2521_ProblemRefactoring/HeuristicLab.Problems.LinearAssignment/3.3/HungarianAlgorithm.cs

@@ -21 +21 @@
 
 using System;
-using System.Linq;
-using HeuristicLab.Analysis;
+using System.Threading;
+using HEAL.Attic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.Operators;
+using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization;
-using HeuristicLab.Parameters;
-using HEAL.Attic;
 
 namespace HeuristicLab.Problems.LinearAssignment {
@@ -37 +35 @@
   [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 170)]
   [StorableType("2A2C1C1B-E0C3-4757-873B-C3F7C6D11A01")]
-  public sealed class HungarianAlgorithm : EngineAlgorithm, IStorableContent {
-    public string Filename { get; set; }
+  public sealed class HungarianAlgorithm : BasicAlgorithm {
+    public override bool SupportsPause => false;
 
     #region Problem Properties
@@ -50 +48 @@
     #endregion
 
-    #region Parameter Properties
-    private ValueParameter<MultiAnalyzer> AnalyzerParameter {
-      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
-    }
-    #endregion
-
-    #region Properties
-    public MultiAnalyzer Analyzer {
-      get { return AnalyzerParameter.Value; }
-      set { AnalyzerParameter.Value = value; }
-    }
-    private LinearAssignmentProblemSolver Solver {
-      get { return (LinearAssignmentProblemSolver)OperatorGraph.InitialOperator; }
-    }
-    #endregion
-
     [StorableConstructor]
     private HungarianAlgorithm(StorableConstructorFlag _) : base(_) { }
-    private HungarianAlgorithm(HungarianAlgorithm original, Cloner cloner)
-      : base(original, cloner) {
-      RegisterEventHandlers();
-    }
+    private HungarianAlgorithm(HungarianAlgorithm original, Cloner cloner) : base(original, cloner) { }
     public HungarianAlgorithm()
       : base() {
-      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the result.", new MultiAnalyzer()));
-
-      var solver = new LinearAssignmentProblemSolver();
-      OperatorGraph.InitialOperator = solver;
-
-      var placeholder = new Placeholder();
-      placeholder.Name = "(Analyzer)";
-      placeholder.OperatorParameter.ActualName = AnalyzerParameter.Name;
-      solver.Successor = placeholder;
-
-      UpdateAnalyzers();
-      RegisterEventHandlers();
-
       Problem = new LinearAssignmentProblem();
     }
@@ -94 +60 @@
     }
 
-    public override void Prepare() {
-      if (Problem != null) base.Prepare();
+    protected override void Run(CancellationToken cancellationToken) {
+      var assignment = LinearAssignmentProblemSolver.Solve(Problem.Costs, out double quality);
+
+      Problem.Analyze(new[] { new Permutation(PermutationTypes.Absolute, assignment) },
+        new[] { quality }, Results, null);
     }
-
-    #region Events
-    protected override void OnProblemChanged() {
-      Problem.SolutionCreatorChanged += new EventHandler(Problem_SolutionCreatorChanged);
-      Problem.EvaluatorChanged += new EventHandler(Problem_EvaluatorChanged);
-      UpdateAnalyzers();
-      Parameterize();
-      base.OnProblemChanged();
-    }
-
-    private void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
-      Parameterize();
-    }
-
-    private void Problem_EvaluatorChanged(object sender, EventArgs e) {
-      Parameterize();
-    }
-
-    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
-      UpdateAnalyzers();
-      base.Problem_OperatorsChanged(sender, e);
-    }
-    #endregion
-
-    #region Helpers
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      RegisterEventHandlers();
-    }
-
-    private void RegisterEventHandlers() {
-      if (Problem != null) {
-        Problem.SolutionCreatorChanged += new EventHandler(Problem_SolutionCreatorChanged);
-        Problem.EvaluatorChanged += new EventHandler(Problem_EvaluatorChanged);
-      }
-    }
-    private void UpdateAnalyzers() {
-      Analyzer.Operators.Clear();
-      if (Problem != null) {
-        foreach (var analyzer in Problem.OperatorsParameter.Value.OfType<IAnalyzer>()) {
-          foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
-            param.Depth = 0;
-          Analyzer.Operators.Add(analyzer);
-        }
-      }
-    }
-    private void Parameterize() {
-      if (Problem != null) {
-        Solver.AssignmentParameter.ActualName = Problem.SolutionCreator.PermutationParameter.ActualName;
-        Solver.CostsParameter.ActualName = Problem.CostsParameter.Name;
-        Solver.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
-      }
-    }
-    #endregion
   }
 }

branches/2521_ProblemRefactoring/HeuristicLab.Problems.LinearAssignment/3.3/LinearAssignmentProblem.cs

@@ -23 +23 @@
 using System.Drawing;
 using System.Linq;
+using System.Threading;
+using HEAL.Attic;
 using HeuristicLab.Analysis;
 using HeuristicLab.Common;
@@ -31 +33 @@
 using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
-using HEAL.Attic;
 using HeuristicLab.PluginInfrastructure;
 
@@ -38 +39 @@
   [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 130)]
   [StorableType("7766E004-A93D-4CA6-8012-AE5E8F4C4D85")]
-  public sealed class LinearAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<ILAPEvaluator, IPermutationCreator>,
-    ISingleObjectiveProblem<PermutationEncoding,Permutation>, IStorableContent {
+  public sealed class LinearAssignmentProblem : PermutationProblem {
     public static readonly string CostsDescription = "The cost matrix that describes the assignment of rows to columns.";
     public static readonly string RowNamesDescription = "The elements represented by the rows of the costs matrix.";
     public static readonly string ColumnNamesDescription = "The elements represented by the columns of the costs matrix.";
 
-    public string Filename { get; set; }
-
     public override Image ItemImage {
       get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
@@ -66 +64 @@
       get { return (IValueParameter<StringArray>)Parameters["ColumnNames"]; }
     }
+    private IResultParameter<LAPAssignment> BestLAPSolutionParameter {
+      get { return (IResultParameter<LAPAssignment>)Parameters["Best LAP Solution"]; }
+    }
+    public IResultDefinition<LAPAssignment> BestLAPSolution => BestLAPSolutionParameter;
     #endregion
 
@@ -91 +93 @@
     #endregion
 
-    [Storable]
-    private BestLAPSolutionAnalyzer bestLAPSolutionAnalyzer;
-
     [StorableConstructor]
     private LinearAssignmentProblem(StorableConstructorFlag _) : base(_) { }
     private LinearAssignmentProblem(LinearAssignmentProblem original, Cloner cloner)
       : base(original, cloner) {
-      this.bestLAPSolutionAnalyzer = cloner.Clone(original.bestLAPSolutionAnalyzer);
       AttachEventHandlers();
     }
     public LinearAssignmentProblem()
-      : base(new LAPEvaluator(), new RandomPermutationCreator()) {
+      : base(new PermutationEncoding("Assignment")) {
       Parameters.Add(new ValueParameter<DoubleMatrix>("Costs", CostsDescription, new DoubleMatrix(3, 3)));
       Parameters.Add(new OptionalValueParameter<ItemSet<Permutation>>("BestKnownSolutions", "The list of best known solutions which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
@@ -108 +106 @@
       Parameters.Add(new OptionalValueParameter<StringArray>("RowNames", RowNamesDescription));
       Parameters.Add(new OptionalValueParameter<StringArray>("ColumnNames", ColumnNamesDescription));
+      Parameters.Add(new ResultParameter<LAPAssignment>("Best LAP Solution", "The best so far LAP solution found."));
 
       ((ValueParameter<DoubleMatrix>)CostsParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
@@ -119 +118 @@
       Costs[2, 0] = 5; Costs[2, 1] = 5; Costs[2, 2] = 1;
 
-      bestLAPSolutionAnalyzer = new BestLAPSolutionAnalyzer();
-      SolutionCreator.PermutationParameter.ActualName = "Assignment";
       InitializeOperators();
       Parameterize();
@@ -128 +125 @@
     public override IDeepCloneable Clone(Cloner cloner) {
       return new LinearAssignmentProblem(this, cloner);
+    }
+
+    public override ISingleObjectiveEvaluationResult Evaluate(Permutation assignment, IRandom random, CancellationToken cancellationToken) {
+      var costs = Costs;
+
+      int len = assignment.Length;
+      double quality = 0;
+      for (int i = 0; i < len; i++) {
+        quality += costs[i, assignment[i]];
+      }
+
+      return new SingleObjectiveEvaluationResult(quality);
+    }
+
+    public override void Analyze(Permutation[] permutations, double[] qualities, ResultCollection results, IRandom random) {
+      base.Analyze(permutations, qualities, results, random);
+
+      var costs = Costs;
+      var rowNames = RowNames;
+      var columnNames = ColumnNames;
+      bool max = Maximization;
+
+      var sorted = qualities.Select((x, index) => new { Index = index, Quality = x }).OrderBy(x => x.Quality).ToArray();
+      if (max) Array.Reverse(sorted);
+      int i = sorted[0].Index;
+      var best = Tuple.Create(permutations[i], qualities[i]);
+
+      if (double.IsNaN(BestKnownQuality) || IsBetter(best.Item2, BestKnownQuality)) {
+        // if there isn't a best-known quality or we improved the best-known quality we'll add the current solution as best-known
+        BestKnownQuality = best.Item2;
+        BestKnownSolution = (Permutation)best.Item1.Clone();
+        BestKnownSolutions = new ItemSet<Permutation>(new PermutationEqualityComparer());
+        BestKnownSolutions.Add((Permutation)best.Item1.Clone());
+      } else if (BestKnownQuality == best.Item2) {
+        // if we matched the best-known quality we'll try to set the best-known solution if it isn't null
+        // and try to add it to the pool of best solutions if it is different
+        if (BestKnownSolution == null) BestKnownSolution = (Permutation)best.Item1.Clone();
+        if (BestKnownSolutions == null) BestKnownSolutions = new ItemSet<Permutation>(new PermutationEqualityComparer());
+
+        foreach (var k in sorted) { // for each solution that we found check if it is in the pool of best-knowns
+          if (IsBetter(best.Item2, k.Quality)) break; // stop when we reached a solution worse than the best-known quality
+          var p = permutations[k.Index];
+          if (!BestKnownSolutions.Contains(p))
+            BestKnownSolutions.Add((Permutation)permutations[k.Index].Clone());
+        }
+      }
+
+      LAPAssignment solution = BestLAPSolutionParameter.ActualValue;
+      if (solution == null) {
+        solution = new LAPAssignment(costs, rowNames, columnNames, (Permutation)best.Item1.Clone(), new DoubleValue(best.Item2));
+        BestLAPSolutionParameter.ActualValue = solution;
+      } else {
+        if (IsBetter(best.Item2, solution.Quality.Value)) {
+          solution.Costs = costs;
+          solution.Assignment = (Permutation)best.Item1.Clone();
+          solution.Quality.Value = best.Item2;
+          if (rowNames != null)
+            solution.RowNames = rowNames;
+          else solution.RowNames = null;
+          if (columnNames != null)
+            solution.ColumnNames = columnNames;
+          else solution.ColumnNames = null;
+        }
+      }
+
     }
 
@@ -137 +199 @@
     protected override void OnOperatorsChanged() {
       base.OnOperatorsChanged();
-      Parameterize();
-    }
-    protected override void OnSolutionCreatorChanged() {
-      base.OnSolutionCreatorChanged();
-      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
       Parameterize();
     }
@@ -174 +231 @@
       Costs.ColumnsChanged += new EventHandler(Costs_ColumnsChanged);
       Costs.Reset += new EventHandler(Costs_Reset);
-      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
     }
 
@@ -180 +236 @@
       Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
       Operators.RemoveAll(x => x is IMoveOperator);
-      Operators.Add(bestLAPSolutionAnalyzer);
 
       Operators.Add(new HammingSimilarityCalculator());
@@ -188 +243 @@
 
     private void Parameterize() {
-      SolutionCreator.LengthParameter.Value = new IntValue(Costs.Rows);
-      SolutionCreator.LengthParameter.Hidden = true;
-      SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
-      SolutionCreator.PermutationTypeParameter.Hidden = true;
-      Evaluator.CostsParameter.ActualName = CostsParameter.Name;
-      Evaluator.CostsParameter.Hidden = true;
-      Evaluator.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-      Evaluator.AssignmentParameter.Hidden = true;
-
-      foreach (var op in Operators.OfType<IPermutationCrossover>()) {
-        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-        op.ParentsParameter.Hidden = true;
-        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-        op.ChildParameter.Hidden = true;
-      }
-
-      foreach (var op in Operators.OfType<IPermutationManipulator>()) {
-        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-        op.PermutationParameter.Hidden = true;
-      }
-
-      foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>()) {
-        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-        op.PermutationParameter.Hidden = true;
-      }
-
       foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
-        similarityCalculator.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
+        similarityCalculator.SolutionVariableName = Encoding.Name;
         similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
       }
-
-      bestLAPSolutionAnalyzer.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-      bestLAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
-      bestLAPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
-      bestLAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
-      bestLAPSolutionAnalyzer.CostsParameter.ActualName = CostsParameter.Name;
-      bestLAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
-      bestLAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
     }
     #endregion