source: trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/LinearAssignmentProblem.cs @ 11087

Last change on this file since 11087 was 11087, checked in by abeham, 5 years ago

#2131: Fixed maximization in LAP (by using negative cost matrix)

File size: 10.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Drawing;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.PermutationEncoding;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.PluginInfrastructure;
33
34namespace HeuristicLab.Problems.LinearAssignment {
35  [Item("LinearAssignmentProblem", "In the linear assignment problem (LAP) an assignment of workers to jobs has to be found such that each worker is assigned to exactly one job, each job is assigned to exactly one worker and the sum of the resulting costs is minimal (or maximal).")]
36  [Creatable("Problems")]
37  [StorableClass]
38  public sealed class LinearAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<ILAPEvaluator, IPermutationCreator>, IStorableContent {
39    public static readonly string CostsDescription = "The cost matrix that describes the assignment of rows to columns.";
40    public static readonly string RowNamesDescription = "The elements represented by the rows of the costs matrix.";
41    public static readonly string ColumnNamesDescription = "The elements represented by the columns of the costs matrix.";
42
43    public string Filename { get; set; }
44
45    public override Image ItemImage {
46      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
47    }
48
49    #region Parameter Properties
50    public IValueParameter<DoubleMatrix> CostsParameter {
51      get { return (IValueParameter<DoubleMatrix>)Parameters["Costs"]; }
52    }
53    public IValueParameter<ItemSet<Permutation>> BestKnownSolutionsParameter {
54      get { return (IValueParameter<ItemSet<Permutation>>)Parameters["BestKnownSolutions"]; }
55    }
56    public IValueParameter<Permutation> BestKnownSolutionParameter {
57      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
58    }
59    public IValueParameter<StringArray> RowNamesParameter {
60      get { return (IValueParameter<StringArray>)Parameters["RowNames"]; }
61    }
62    public IValueParameter<StringArray> ColumnNamesParameter {
63      get { return (IValueParameter<StringArray>)Parameters["ColumnNames"]; }
64    }
65    #endregion
66
67    #region Properties
68    public DoubleMatrix Costs {
69      get { return CostsParameter.Value; }
70      set { CostsParameter.Value = value; }
71    }
72    public StringArray RowNames {
73      get { return RowNamesParameter.Value; }
74      set { RowNamesParameter.Value = value; }
75    }
76    public StringArray ColumnNames {
77      get { return ColumnNamesParameter.Value; }
78      set { ColumnNamesParameter.Value = value; }
79    }
80    public ItemSet<Permutation> BestKnownSolutions {
81      get { return BestKnownSolutionsParameter.Value; }
82      set { BestKnownSolutionsParameter.Value = value; }
83    }
84    public Permutation BestKnownSolution {
85      get { return BestKnownSolutionParameter.Value; }
86      set { BestKnownSolutionParameter.Value = value; }
87    }
88    #endregion
89
90    [Storable]
91    private BestLAPSolutionAnalyzer bestLAPSolutionAnalyzer;
92
93    [StorableConstructor]
94    private LinearAssignmentProblem(bool deserializing) : base(deserializing) { }
95    private LinearAssignmentProblem(LinearAssignmentProblem original, Cloner cloner)
96      : base(original, cloner) {
97      this.bestLAPSolutionAnalyzer = cloner.Clone(original.bestLAPSolutionAnalyzer);
98      AttachEventHandlers();
99    }
100    public LinearAssignmentProblem()
101      : base(new LAPEvaluator(), new RandomPermutationCreator()) {
102      Parameters.Add(new ValueParameter<DoubleMatrix>("Costs", CostsDescription, new DoubleMatrix(3, 3)));
103      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));
104      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));
105      Parameters.Add(new OptionalValueParameter<StringArray>("RowNames", RowNamesDescription));
106      Parameters.Add(new OptionalValueParameter<StringArray>("ColumnNames", ColumnNamesDescription));
107
108      ((ValueParameter<DoubleMatrix>)CostsParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
109      ((OptionalValueParameter<StringArray>)RowNamesParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
110      ((OptionalValueParameter<StringArray>)ColumnNamesParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
111
112      RowNames = new StringArray(new string[] { "Eric", "Robert", "Allison" });
113      ColumnNames = new StringArray(new string[] { "MRI", "Blood test", "Angiogram" });
114      Costs[0, 0] = 4; Costs[0, 1] = 5; Costs[0, 2] = 3;
115      Costs[1, 0] = 6; Costs[1, 1] = 6; Costs[1, 2] = 4;
116      Costs[2, 0] = 5; Costs[2, 1] = 5; Costs[2, 2] = 1;
117
118      bestLAPSolutionAnalyzer = new BestLAPSolutionAnalyzer();
119      SolutionCreator.PermutationParameter.ActualName = "Assignment";
120      InitializeOperators();
121      Parameterize();
122      AttachEventHandlers();
123    }
124
125    public override IDeepCloneable Clone(Cloner cloner) {
126      return new LinearAssignmentProblem(this, cloner);
127    }
128
129    #region Events
130    protected override void OnEvaluatorChanged() {
131      base.OnEvaluatorChanged();
132      Parameterize();
133    }
134    protected override void OnOperatorsChanged() {
135      base.OnOperatorsChanged();
136      Parameterize();
137    }
138    protected override void OnSolutionCreatorChanged() {
139      base.OnSolutionCreatorChanged();
140      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
141      Parameterize();
142    }
143    private void Costs_RowsChanged(object sender, EventArgs e) {
144      if (Costs.Rows != Costs.Columns) {
145        ((IStringConvertibleMatrix)Costs).Columns = Costs.Rows;
146        Parameterize();
147      }
148    }
149    private void Costs_ColumnsChanged(object sender, EventArgs e) {
150      if (Costs.Rows != Costs.Columns) {
151        ((IStringConvertibleMatrix)Costs).Rows = Costs.Columns;
152        Parameterize();
153      }
154    }
155    private void Costs_Reset(object sender, EventArgs e) {
156      Parameterize();
157    }
158    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
159      Parameterize();
160    }
161    #endregion
162
163    #region Helpers
164    [StorableHook(HookType.AfterDeserialization)]
165    private void AfterDeserialization() {
166      AttachEventHandlers();
167    }
168
169    private void AttachEventHandlers() {
170      Costs.RowsChanged += new EventHandler(Costs_RowsChanged);
171      Costs.ColumnsChanged += new EventHandler(Costs_ColumnsChanged);
172      Costs.Reset += new EventHandler(Costs_Reset);
173      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
174    }
175
176    private void InitializeOperators() {
177      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
178      Operators.RemoveAll(x => x is IMoveOperator);
179      Operators.Add(bestLAPSolutionAnalyzer);
180    }
181
182    private void Parameterize() {
183      SolutionCreator.LengthParameter.Value = new IntValue(Costs.Rows);
184      SolutionCreator.LengthParameter.Hidden = true;
185      SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
186      SolutionCreator.PermutationTypeParameter.Hidden = true;
187      Evaluator.CostsParameter.ActualName = CostsParameter.Name;
188      Evaluator.CostsParameter.Hidden = true;
189      Evaluator.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
190      Evaluator.AssignmentParameter.Hidden = true;
191
192      foreach (var op in Operators.OfType<IPermutationCrossover>()) {
193        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
194        op.ParentsParameter.Hidden = true;
195        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
196        op.ChildParameter.Hidden = true;
197      }
198
199      foreach (var op in Operators.OfType<IPermutationManipulator>()) {
200        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
201        op.PermutationParameter.Hidden = true;
202      }
203
204      foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>()) {
205        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
206        op.PermutationParameter.Hidden = true;
207      }
208
209      bestLAPSolutionAnalyzer.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
210      bestLAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
211      bestLAPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
212      bestLAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
213      bestLAPSolutionAnalyzer.CostsParameter.ActualName = CostsParameter.Name;
214      bestLAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
215      bestLAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
216    }
217    #endregion
218  }
219}
Note: See TracBrowser for help on using the repository browser.