Changeset 8022 for trunk/sources/HeuristicLab.Problems.LinearAssignment

Timestamp:

06/18/12 02:53:03 (13 years ago)

Author:

abeham

Message:

#1855:

• Transformed LAP into a SingleObjectiveHeuristicOptimizationProblem
• Added HungarianAlgorithm as separate algorithm for solving the problem

Location:

trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3

Files:

• Analyzers (added)
• Analyzers/BestLAPSolutionAnalyzer.cs (added)
• HeuristicLab.Problems.LinearAssignment-3.3.csproj (modified) (3 diffs)
• HungarianAlgorithm.cs (added)
• Interfaces (added)
• Interfaces/ILAPEvaluator.cs (added)
• LAPAssignment.cs (added)
• LAPEvaluator.cs (added)
• LinearAssignmentProblem.cs (modified) (7 diffs)
• LinearAssignmentProblemSolver.cs (modified) (1 diff)
• Plugin.cs.frame (modified) (2 diffs)

trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/HeuristicLab.Problems.LinearAssignment-3.3.csproj

@@ -112 +112 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="HungarianAlgorithm.cs" />
+    <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" />
@@ -123 +128 @@
   </ItemGroup>
   <ItemGroup>
+    <ProjectReference Include="..\..\HeuristicLab.Analysis\3.3\HeuristicLab.Analysis-3.3.csproj">
+      <Project>{887425B4-4348-49ED-A457-B7D2C26DDBF9}</Project>
+      <Name>HeuristicLab.Analysis-3.3</Name>
+      <Private>False</Private>
+    </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Collections\3.3\HeuristicLab.Collections-3.3.csproj">
       <Project>{958B43BC-CC5C-4FA2-8628-2B3B01D890B6}</Project>
@@ -146 +156 @@
       <Project>{BBAB9DF5-5EF3-4BA8-ADE9-B36E82114937}</Project>
       <Name>HeuristicLab.Data-3.3</Name>
+      <Private>False</Private>
+    </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">
+      <Project>{DBECB8B0-B166-4133-BAF1-ED67C3FD7FCA}</Project>
+      <Name>HeuristicLab.Encodings.PermutationEncoding-3.3</Name>
       <Private>False</Private>
     </ProjectReference>

trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/LinearAssignmentProblem.cs

@@ -22 +22 @@
 using System;
 using System.Drawing;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.PluginInfrastructure;
 
 namespace HeuristicLab.Problems.LinearAssignment {
@@ -33 +36 @@
   [Creatable("Problems")]
   [StorableClass]
-  public sealed class LinearAssignmentProblem : Problem {
+  public sealed class LinearAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<ILAPEvaluator, IPermutationCreator> {
+    public static readonly string CostsDescription = "The cost matrix that describes the assignment of rows to columns.";
+
     public override Image ItemImage {
       get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
@@ -42 +47 @@
       get { return (IValueParameter<DoubleMatrix>)Parameters["Costs"]; }
     }
-    public IValueParameter<IntArray> SolutionParameter {
-      get { return (IValueParameter<IntArray>)Parameters["Solution"]; }
+    public IValueParameter<ItemSet<Permutation>> BestKnownSolutionsParameter {
+      get { return (IValueParameter<ItemSet<Permutation>>)Parameters["BestKnownSolutions"]; }
     }
-    public IValueParameter<DoubleValue> QualityParameter {
-      get { return (IValueParameter<DoubleValue>)Parameters["Quality"]; }
+    public IValueParameter<Permutation> BestKnownSolutionParameter {
+      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
     }
     #endregion
@@ -55 +60 @@
       set { CostsParameter.Value = value; }
     }
-    public IntArray Solution {
-      get { return SolutionParameter.Value; }
-      set { SolutionParameter.Value = value; }
+    public ItemSet<Permutation> BestKnownSolutions {
+      get { return BestKnownSolutionsParameter.Value; }
+      set { BestKnownSolutionsParameter.Value = value; }
     }
-    public DoubleValue Quality {
-      get { return QualityParameter.Value; }
-      set { QualityParameter.Value = value; }
+    public Permutation BestKnownSolution {
+      get { return BestKnownSolutionParameter.Value; }
+      set { BestKnownSolutionParameter.Value = value; }
     }
+    #endregion
 
-    #endregion
+    [Storable]
+    private BestLAPSolutionAnalyzer bestLAPSolutionAnalyzer;
 
     [StorableConstructor]
@@ -70 +77 @@
     private LinearAssignmentProblem(LinearAssignmentProblem original, Cloner cloner)
       : base(original, cloner) {
+      this.bestLAPSolutionAnalyzer = cloner.Clone(original.bestLAPSolutionAnalyzer);
       AttachEventHandlers();
     }
     public LinearAssignmentProblem()
-      : base() {
-      Parameters.Add(new ValueParameter<DoubleMatrix>("Costs", "The cost matrix that describes the assignment of rows to columns.", new DoubleMatrix(3, 3)));
-      Parameters.Add(new OptionalValueParameter<IntArray>("Solution", "An optimal solution.", null));
-      Parameters.Add(new OptionalValueParameter<DoubleValue>("Quality", "The solution quality.", null));
-
+      : base(new LAPEvaluator(), new RandomPermutationCreator()) {
+      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));
+      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
+      
       ((ValueParameter<DoubleMatrix>)CostsParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
 
+      bestLAPSolutionAnalyzer = new BestLAPSolutionAnalyzer();
+      SolutionCreator.PermutationParameter.ActualName = "Assignment";
+      InitializeOperators();
+      Parameterize();
       AttachEventHandlers();
     }
@@ -88 +100 @@
 
     #region Events
+    protected override void OnEvaluatorChanged() {
+      base.OnEvaluatorChanged();
+      Parameterize();
+    }
+    protected override void OnOperatorsChanged() {
+      base.OnOperatorsChanged();
+      Parameterize();
+    }
+    protected override void OnSolutionCreatorChanged() {
+      base.OnSolutionCreatorChanged();
+      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
+      Parameterize();
+    }
     private void Costs_RowsChanged(object sender, EventArgs e) {
-      if (Costs.Rows != Costs.Columns)
+      if (Costs.Rows != Costs.Columns) {
         ((IStringConvertibleMatrix)Costs).Columns = Costs.Rows;
+        Parameterize();
+      }
     }
     private void Costs_ColumnsChanged(object sender, EventArgs e) {
-      if (Costs.Rows != Costs.Columns)
+      if (Costs.Rows != Costs.Columns) {
         ((IStringConvertibleMatrix)Costs).Rows = Costs.Columns;
+        Parameterize();
+      }
+    }
+    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
+      Parameterize();
     }
     #endregion
@@ -107 +139 @@
       Costs.RowsChanged += new EventHandler(Costs_RowsChanged);
       Costs.ColumnsChanged += new EventHandler(Costs_ColumnsChanged);
+      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
+    }
+
+    private void InitializeOperators() {
+      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
+      Operators.RemoveAll(x => x is IMoveOperator);
+      Operators.Add(bestLAPSolutionAnalyzer);
+    }
+
+    private void Parameterize() {
+      SolutionCreator.LengthParameter.Value = new IntValue(Costs.Rows);
+      SolutionCreator.LengthParameter.Hidden = false;
+      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;
+      }
+
+      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

trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/LinearAssignmentProblemSolver.cs

@@ -21 +21 @@
 
 using HeuristicLab.Common;
+using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Operators;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Problems.LinearAssignment {
-  public static class LinearAssignmentProblemSolver {
+  [Item("LinearAssignmentProblemSolver", "Uses the hungarian algorithm to solve linear assignment problems.")]
+  [StorableClass]
+  public sealed class LinearAssignmentProblemSolver : SingleSuccessorOperator {
     private const int UNASSIGNED = -1;
+
+    public ILookupParameter<DoubleMatrix> CostsParameter {
+      get { return (ILookupParameter<DoubleMatrix>)Parameters["Costs"]; }
+    }
+    public ILookupParameter<Permutation> AssignmentParameter {
+      get { return (ILookupParameter<Permutation>)Parameters["Assignment"]; }
+    }
+    public ILookupParameter<DoubleValue> QualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
+    }
+
+    [StorableConstructor]
+    private LinearAssignmentProblemSolver(bool deserializing) : base(deserializing) { }
+    private LinearAssignmentProblemSolver(LinearAssignmentProblemSolver original, Cloner cloner) : base(original, cloner) { }
+    public LinearAssignmentProblemSolver()
+      : base() {
+      Parameters.Add(new LookupParameter<DoubleMatrix>("Costs", LinearAssignmentProblem.CostsDescription));
+      Parameters.Add(new LookupParameter<Permutation>("Assignment", "The assignment solution to create."));
+      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the solution."));
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new LinearAssignmentProblemSolver(this, cloner);
+    }
+
+    public override IOperation Apply() {
+      var costs = CostsParameter.ActualValue;
+      double quality;
+      var solution = Solve(costs, out quality);
+
+      AssignmentParameter.ActualValue = new Permutation(PermutationTypes.Absolute, solution);
+      QualityParameter.ActualValue = new DoubleValue(quality);
+
+      return base.Apply();
+    }
 
     /// <summary>

trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/Plugin.cs.frame

@@ -25 +25 @@
   [Plugin("HeuristicLab.Problems.LinearAssignment", "3.3.6.$WCREV$")]
   [PluginFile("HeuristicLab.Problems.LinearAssignment-3.3.dll", PluginFileType.Assembly)]
+  [PluginDependency("HeuristicLab.Analysis", "3.3")]
   [PluginDependency("HeuristicLab.Collections", "3.3")]
   [PluginDependency("HeuristicLab.Common", "3.3")]
@@ -30 +31 @@
   [PluginDependency("HeuristicLab.Core", "3.3")]
   [PluginDependency("HeuristicLab.Data", "3.3")]
+  [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
+  [PluginDependency("HeuristicLab.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Optimization", "3.3")]
   [PluginDependency("HeuristicLab.Parameters", "3.3")]