Changeset 17530


Ignore:
Timestamp:
05/08/20 12:06:23 (2 months ago)
Author:
abeham
Message:

#2521: Refactored linear assignment problem

Location:
branches/2521_ProblemRefactoring/HeuristicLab.Problems.LinearAssignment/3.3
Files:
3 deleted
3 edited

Legend:

Unmodified
Added
Removed
  • branches/2521_ProblemRefactoring/HeuristicLab.Problems.LinearAssignment/3.3/HeuristicLab.Problems.LinearAssignment-3.3.csproj

    r16723 r17530  
    122122    <Compile Include="LAPAssignment.cs" />
    123123    <None Include="Plugin.cs.frame" />
    124     <Compile Include="Analyzers\BestLAPSolutionAnalyzer.cs" />
    125     <Compile Include="Interfaces\ILAPEvaluator.cs" />
    126     <Compile Include="LAPEvaluator.cs" />
    127124    <Compile Include="LinearAssignmentProblem.cs" />
    128125    <Compile Include="LinearAssignmentProblemSolver.cs" />
  • branches/2521_ProblemRefactoring/HeuristicLab.Problems.LinearAssignment/3.3/HungarianAlgorithm.cs

    r17226 r17530  
    2121
    2222using System;
    23 using System.Linq;
    24 using HeuristicLab.Analysis;
     23using System.Threading;
     24using HEAL.Attic;
    2525using HeuristicLab.Common;
    2626using HeuristicLab.Core;
    27 using HeuristicLab.Operators;
     27using HeuristicLab.Encodings.PermutationEncoding;
    2828using HeuristicLab.Optimization;
    29 using HeuristicLab.Parameters;
    30 using HEAL.Attic;
    3129
    3230namespace HeuristicLab.Problems.LinearAssignment {
     
    3735  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 170)]
    3836  [StorableType("2A2C1C1B-E0C3-4757-873B-C3F7C6D11A01")]
    39   public sealed class HungarianAlgorithm : EngineAlgorithm, IStorableContent {
    40     public string Filename { get; set; }
     37  public sealed class HungarianAlgorithm : BasicAlgorithm {
     38    public override bool SupportsPause => false;
    4139
    4240    #region Problem Properties
     
    5048    #endregion
    5149
    52     #region Parameter Properties
    53     private ValueParameter<MultiAnalyzer> AnalyzerParameter {
    54       get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
    55     }
    56     #endregion
    57 
    58     #region Properties
    59     public MultiAnalyzer Analyzer {
    60       get { return AnalyzerParameter.Value; }
    61       set { AnalyzerParameter.Value = value; }
    62     }
    63     private LinearAssignmentProblemSolver Solver {
    64       get { return (LinearAssignmentProblemSolver)OperatorGraph.InitialOperator; }
    65     }
    66     #endregion
    67 
    6850    [StorableConstructor]
    6951    private HungarianAlgorithm(StorableConstructorFlag _) : base(_) { }
    70     private HungarianAlgorithm(HungarianAlgorithm original, Cloner cloner)
    71       : base(original, cloner) {
    72       RegisterEventHandlers();
    73     }
     52    private HungarianAlgorithm(HungarianAlgorithm original, Cloner cloner) : base(original, cloner) { }
    7453    public HungarianAlgorithm()
    7554      : base() {
    76       Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the result.", new MultiAnalyzer()));
    77 
    78       var solver = new LinearAssignmentProblemSolver();
    79       OperatorGraph.InitialOperator = solver;
    80 
    81       var placeholder = new Placeholder();
    82       placeholder.Name = "(Analyzer)";
    83       placeholder.OperatorParameter.ActualName = AnalyzerParameter.Name;
    84       solver.Successor = placeholder;
    85 
    86       UpdateAnalyzers();
    87       RegisterEventHandlers();
    88 
    8955      Problem = new LinearAssignmentProblem();
    9056    }
     
    9460    }
    9561
    96     public override void Prepare() {
    97       if (Problem != null) base.Prepare();
     62    protected override void Run(CancellationToken cancellationToken) {
     63      var assignment = LinearAssignmentProblemSolver.Solve(Problem.Costs, out double quality);
     64
     65      Problem.Analyze(new[] { new Permutation(PermutationTypes.Absolute, assignment) },
     66        new[] { quality }, Results, null);
    9867    }
    99 
    100     #region Events
    101     protected override void OnProblemChanged() {
    102       Problem.SolutionCreatorChanged += new EventHandler(Problem_SolutionCreatorChanged);
    103       Problem.EvaluatorChanged += new EventHandler(Problem_EvaluatorChanged);
    104       UpdateAnalyzers();
    105       Parameterize();
    106       base.OnProblemChanged();
    107     }
    108 
    109     private void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
    110       Parameterize();
    111     }
    112 
    113     private void Problem_EvaluatorChanged(object sender, EventArgs e) {
    114       Parameterize();
    115     }
    116 
    117     protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
    118       UpdateAnalyzers();
    119       base.Problem_OperatorsChanged(sender, e);
    120     }
    121     #endregion
    122 
    123     #region Helpers
    124     [StorableHook(HookType.AfterDeserialization)]
    125     private void AfterDeserialization() {
    126       RegisterEventHandlers();
    127     }
    128 
    129     private void RegisterEventHandlers() {
    130       if (Problem != null) {
    131         Problem.SolutionCreatorChanged += new EventHandler(Problem_SolutionCreatorChanged);
    132         Problem.EvaluatorChanged += new EventHandler(Problem_EvaluatorChanged);
    133       }
    134     }
    135     private void UpdateAnalyzers() {
    136       Analyzer.Operators.Clear();
    137       if (Problem != null) {
    138         foreach (var analyzer in Problem.OperatorsParameter.Value.OfType<IAnalyzer>()) {
    139           foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
    140             param.Depth = 0;
    141           Analyzer.Operators.Add(analyzer);
    142         }
    143       }
    144     }
    145     private void Parameterize() {
    146       if (Problem != null) {
    147         Solver.AssignmentParameter.ActualName = Problem.SolutionCreator.PermutationParameter.ActualName;
    148         Solver.CostsParameter.ActualName = Problem.CostsParameter.Name;
    149         Solver.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
    150       }
    151     }
    152     #endregion
    15368  }
    15469}
  • branches/2521_ProblemRefactoring/HeuristicLab.Problems.LinearAssignment/3.3/LinearAssignmentProblem.cs

    r17226 r17530  
    2323using System.Drawing;
    2424using System.Linq;
     25using System.Threading;
     26using HEAL.Attic;
    2527using HeuristicLab.Analysis;
    2628using HeuristicLab.Common;
     
    3133using HeuristicLab.Optimization.Operators;
    3234using HeuristicLab.Parameters;
    33 using HEAL.Attic;
    3435using HeuristicLab.PluginInfrastructure;
    3536
     
    3839  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 130)]
    3940  [StorableType("7766E004-A93D-4CA6-8012-AE5E8F4C4D85")]
    40   public sealed class LinearAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<ILAPEvaluator, IPermutationCreator>,
    41     ISingleObjectiveProblem<PermutationEncoding,Permutation>, IStorableContent {
     41  public sealed class LinearAssignmentProblem : PermutationProblem {
    4242    public static readonly string CostsDescription = "The cost matrix that describes the assignment of rows to columns.";
    4343    public static readonly string RowNamesDescription = "The elements represented by the rows of the costs matrix.";
    4444    public static readonly string ColumnNamesDescription = "The elements represented by the columns of the costs matrix.";
    4545
    46     public string Filename { get; set; }
    47 
    4846    public override Image ItemImage {
    4947      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
     
    6664      get { return (IValueParameter<StringArray>)Parameters["ColumnNames"]; }
    6765    }
     66    private IResultParameter<LAPAssignment> BestLAPSolutionParameter {
     67      get { return (IResultParameter<LAPAssignment>)Parameters["Best LAP Solution"]; }
     68    }
     69    public IResultDefinition<LAPAssignment> BestLAPSolution => BestLAPSolutionParameter;
    6870    #endregion
    6971
     
    9193    #endregion
    9294
    93     [Storable]
    94     private BestLAPSolutionAnalyzer bestLAPSolutionAnalyzer;
    95 
    9695    [StorableConstructor]
    9796    private LinearAssignmentProblem(StorableConstructorFlag _) : base(_) { }
    9897    private LinearAssignmentProblem(LinearAssignmentProblem original, Cloner cloner)
    9998      : base(original, cloner) {
    100       this.bestLAPSolutionAnalyzer = cloner.Clone(original.bestLAPSolutionAnalyzer);
    10199      AttachEventHandlers();
    102100    }
    103101    public LinearAssignmentProblem()
    104       : base(new LAPEvaluator(), new RandomPermutationCreator()) {
     102      : base(new PermutationEncoding("Assignment")) {
    105103      Parameters.Add(new ValueParameter<DoubleMatrix>("Costs", CostsDescription, new DoubleMatrix(3, 3)));
    106104      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));
     
    108106      Parameters.Add(new OptionalValueParameter<StringArray>("RowNames", RowNamesDescription));
    109107      Parameters.Add(new OptionalValueParameter<StringArray>("ColumnNames", ColumnNamesDescription));
     108      Parameters.Add(new ResultParameter<LAPAssignment>("Best LAP Solution", "The best so far LAP solution found."));
    110109
    111110      ((ValueParameter<DoubleMatrix>)CostsParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
     
    119118      Costs[2, 0] = 5; Costs[2, 1] = 5; Costs[2, 2] = 1;
    120119
    121       bestLAPSolutionAnalyzer = new BestLAPSolutionAnalyzer();
    122       SolutionCreator.PermutationParameter.ActualName = "Assignment";
    123120      InitializeOperators();
    124121      Parameterize();
     
    128125    public override IDeepCloneable Clone(Cloner cloner) {
    129126      return new LinearAssignmentProblem(this, cloner);
     127    }
     128
     129    public override ISingleObjectiveEvaluationResult Evaluate(Permutation assignment, IRandom random, CancellationToken cancellationToken) {
     130      var costs = Costs;
     131
     132      int len = assignment.Length;
     133      double quality = 0;
     134      for (int i = 0; i < len; i++) {
     135        quality += costs[i, assignment[i]];
     136      }
     137
     138      return new SingleObjectiveEvaluationResult(quality);
     139    }
     140
     141    public override void Analyze(Permutation[] permutations, double[] qualities, ResultCollection results, IRandom random) {
     142      base.Analyze(permutations, qualities, results, random);
     143
     144      var costs = Costs;
     145      var rowNames = RowNames;
     146      var columnNames = ColumnNames;
     147      bool max = Maximization;
     148
     149      var sorted = qualities.Select((x, index) => new { Index = index, Quality = x }).OrderBy(x => x.Quality).ToArray();
     150      if (max) Array.Reverse(sorted);
     151      int i = sorted[0].Index;
     152      var best = Tuple.Create(permutations[i], qualities[i]);
     153
     154      if (double.IsNaN(BestKnownQuality) || IsBetter(best.Item2, BestKnownQuality)) {
     155        // if there isn't a best-known quality or we improved the best-known quality we'll add the current solution as best-known
     156        BestKnownQuality = best.Item2;
     157        BestKnownSolution = (Permutation)best.Item1.Clone();
     158        BestKnownSolutions = new ItemSet<Permutation>(new PermutationEqualityComparer());
     159        BestKnownSolutions.Add((Permutation)best.Item1.Clone());
     160      } else if (BestKnownQuality == best.Item2) {
     161        // if we matched the best-known quality we'll try to set the best-known solution if it isn't null
     162        // and try to add it to the pool of best solutions if it is different
     163        if (BestKnownSolution == null) BestKnownSolution = (Permutation)best.Item1.Clone();
     164        if (BestKnownSolutions == null) BestKnownSolutions = new ItemSet<Permutation>(new PermutationEqualityComparer());
     165
     166        foreach (var k in sorted) { // for each solution that we found check if it is in the pool of best-knowns
     167          if (IsBetter(best.Item2, k.Quality)) break; // stop when we reached a solution worse than the best-known quality
     168          var p = permutations[k.Index];
     169          if (!BestKnownSolutions.Contains(p))
     170            BestKnownSolutions.Add((Permutation)permutations[k.Index].Clone());
     171        }
     172      }
     173
     174      LAPAssignment solution = BestLAPSolutionParameter.ActualValue;
     175      if (solution == null) {
     176        solution = new LAPAssignment(costs, rowNames, columnNames, (Permutation)best.Item1.Clone(), new DoubleValue(best.Item2));
     177        BestLAPSolutionParameter.ActualValue = solution;
     178      } else {
     179        if (IsBetter(best.Item2, solution.Quality.Value)) {
     180          solution.Costs = costs;
     181          solution.Assignment = (Permutation)best.Item1.Clone();
     182          solution.Quality.Value = best.Item2;
     183          if (rowNames != null)
     184            solution.RowNames = rowNames;
     185          else solution.RowNames = null;
     186          if (columnNames != null)
     187            solution.ColumnNames = columnNames;
     188          else solution.ColumnNames = null;
     189        }
     190      }
     191
    130192    }
    131193
     
    137199    protected override void OnOperatorsChanged() {
    138200      base.OnOperatorsChanged();
    139       Parameterize();
    140     }
    141     protected override void OnSolutionCreatorChanged() {
    142       base.OnSolutionCreatorChanged();
    143       SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
    144201      Parameterize();
    145202    }
     
    174231      Costs.ColumnsChanged += new EventHandler(Costs_ColumnsChanged);
    175232      Costs.Reset += new EventHandler(Costs_Reset);
    176       SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
    177233    }
    178234
     
    180236      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
    181237      Operators.RemoveAll(x => x is IMoveOperator);
    182       Operators.Add(bestLAPSolutionAnalyzer);
    183238
    184239      Operators.Add(new HammingSimilarityCalculator());
     
    188243
    189244    private void Parameterize() {
    190       SolutionCreator.LengthParameter.Value = new IntValue(Costs.Rows);
    191       SolutionCreator.LengthParameter.Hidden = true;
    192       SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
    193       SolutionCreator.PermutationTypeParameter.Hidden = true;
    194       Evaluator.CostsParameter.ActualName = CostsParameter.Name;
    195       Evaluator.CostsParameter.Hidden = true;
    196       Evaluator.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    197       Evaluator.AssignmentParameter.Hidden = true;
    198 
    199       foreach (var op in Operators.OfType<IPermutationCrossover>()) {
    200         op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    201         op.ParentsParameter.Hidden = true;
    202         op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    203         op.ChildParameter.Hidden = true;
    204       }
    205 
    206       foreach (var op in Operators.OfType<IPermutationManipulator>()) {
    207         op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    208         op.PermutationParameter.Hidden = true;
    209       }
    210 
    211       foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>()) {
    212         op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    213         op.PermutationParameter.Hidden = true;
    214       }
    215 
    216245      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
    217         similarityCalculator.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
     246        similarityCalculator.SolutionVariableName = Encoding.Name;
    218247        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
    219248      }
    220 
    221       bestLAPSolutionAnalyzer.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    222       bestLAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
    223       bestLAPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
    224       bestLAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
    225       bestLAPSolutionAnalyzer.CostsParameter.ActualName = CostsParameter.Name;
    226       bestLAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
    227       bestLAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
    228249    }
    229250    #endregion
Note: See TracChangeset for help on using the changeset viewer.