Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2706:

  • Added or updated similarity calculators and population similarity analysis for several problems (BinPacking, LAP, Orienteering, Parameter optimization, PTSP, QAP, TF, TSP, VRP)
  • Made TSPSimilarityCalculator obsolete since it's essentially the same as the one in the permutation plugin
  • Made QAPPopulationDiversityAnalyzer obsolete as it is replaced by the newer PopulationSimilarityAnalyzer
  • Removed genotype specific similarity code in QAPPermutationProximityCalculator (again identical to the permutation plugin)
  • Changed QAPSimilarityCalculator to perform phenotype similarity instead of genotype similarity (has not been previously used)
File size: 10.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.PermutationEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Optimization.Operators;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.PluginInfrastructure;
35
36namespace HeuristicLab.Problems.LinearAssignment {
37  [Item("Linear Assignment Problem (LAP)", "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).")]
38  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 130)]
39  [StorableClass]
40  public sealed class LinearAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<ILAPEvaluator, IPermutationCreator>, IStorableContent {
41    public static readonly string CostsDescription = "The cost matrix that describes the assignment of rows to columns.";
42    public static readonly string RowNamesDescription = "The elements represented by the rows of the costs matrix.";
43    public static readonly string ColumnNamesDescription = "The elements represented by the columns of the costs matrix.";
44
45    public string Filename { get; set; }
46
47    public override Image ItemImage {
48      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
49    }
50
51    #region Parameter Properties
52    public IValueParameter<DoubleMatrix> CostsParameter {
53      get { return (IValueParameter<DoubleMatrix>)Parameters["Costs"]; }
54    }
55    public IValueParameter<ItemSet<Permutation>> BestKnownSolutionsParameter {
56      get { return (IValueParameter<ItemSet<Permutation>>)Parameters["BestKnownSolutions"]; }
57    }
58    public IValueParameter<Permutation> BestKnownSolutionParameter {
59      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
60    }
61    public IValueParameter<StringArray> RowNamesParameter {
62      get { return (IValueParameter<StringArray>)Parameters["RowNames"]; }
63    }
64    public IValueParameter<StringArray> ColumnNamesParameter {
65      get { return (IValueParameter<StringArray>)Parameters["ColumnNames"]; }
66    }
67    #endregion
68
69    #region Properties
70    public DoubleMatrix Costs {
71      get { return CostsParameter.Value; }
72      set { CostsParameter.Value = value; }
73    }
74    public StringArray RowNames {
75      get { return RowNamesParameter.Value; }
76      set { RowNamesParameter.Value = value; }
77    }
78    public StringArray ColumnNames {
79      get { return ColumnNamesParameter.Value; }
80      set { ColumnNamesParameter.Value = value; }
81    }
82    public ItemSet<Permutation> BestKnownSolutions {
83      get { return BestKnownSolutionsParameter.Value; }
84      set { BestKnownSolutionsParameter.Value = value; }
85    }
86    public Permutation BestKnownSolution {
87      get { return BestKnownSolutionParameter.Value; }
88      set { BestKnownSolutionParameter.Value = value; }
89    }
90    #endregion
91
92    [Storable]
93    private BestLAPSolutionAnalyzer bestLAPSolutionAnalyzer;
94
95    [StorableConstructor]
96    private LinearAssignmentProblem(bool deserializing) : base(deserializing) { }
97    private LinearAssignmentProblem(LinearAssignmentProblem original, Cloner cloner)
98      : base(original, cloner) {
99      this.bestLAPSolutionAnalyzer = cloner.Clone(original.bestLAPSolutionAnalyzer);
100      AttachEventHandlers();
101    }
102    public LinearAssignmentProblem()
103      : base(new LAPEvaluator(), new RandomPermutationCreator()) {
104      Parameters.Add(new ValueParameter<DoubleMatrix>("Costs", CostsDescription, new DoubleMatrix(3, 3)));
105      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));
106      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));
107      Parameters.Add(new OptionalValueParameter<StringArray>("RowNames", RowNamesDescription));
108      Parameters.Add(new OptionalValueParameter<StringArray>("ColumnNames", ColumnNamesDescription));
109
110      ((ValueParameter<DoubleMatrix>)CostsParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
111      ((OptionalValueParameter<StringArray>)RowNamesParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
112      ((OptionalValueParameter<StringArray>)ColumnNamesParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
113
114      RowNames = new StringArray(new string[] { "Eric", "Robert", "Allison" });
115      ColumnNames = new StringArray(new string[] { "MRI", "Blood test", "Angiogram" });
116      Costs[0, 0] = 4; Costs[0, 1] = 5; Costs[0, 2] = 3;
117      Costs[1, 0] = 6; Costs[1, 1] = 6; Costs[1, 2] = 4;
118      Costs[2, 0] = 5; Costs[2, 1] = 5; Costs[2, 2] = 1;
119
120      bestLAPSolutionAnalyzer = new BestLAPSolutionAnalyzer();
121      SolutionCreator.PermutationParameter.ActualName = "Assignment";
122      InitializeOperators();
123      Parameterize();
124      AttachEventHandlers();
125    }
126
127    public override IDeepCloneable Clone(Cloner cloner) {
128      return new LinearAssignmentProblem(this, cloner);
129    }
130
131    #region Events
132    protected override void OnEvaluatorChanged() {
133      base.OnEvaluatorChanged();
134      Parameterize();
135    }
136    protected override void OnOperatorsChanged() {
137      base.OnOperatorsChanged();
138      Parameterize();
139    }
140    protected override void OnSolutionCreatorChanged() {
141      base.OnSolutionCreatorChanged();
142      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
143      Parameterize();
144    }
145    private void Costs_RowsChanged(object sender, EventArgs e) {
146      if (Costs.Rows != Costs.Columns) {
147        ((IStringConvertibleMatrix)Costs).Columns = Costs.Rows;
148        Parameterize();
149      }
150    }
151    private void Costs_ColumnsChanged(object sender, EventArgs e) {
152      if (Costs.Rows != Costs.Columns) {
153        ((IStringConvertibleMatrix)Costs).Rows = Costs.Columns;
154        Parameterize();
155      }
156    }
157    private void Costs_Reset(object sender, EventArgs e) {
158      Parameterize();
159    }
160    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
161      Parameterize();
162    }
163    #endregion
164
165    #region Helpers
166    [StorableHook(HookType.AfterDeserialization)]
167    private void AfterDeserialization() {
168      AttachEventHandlers();
169    }
170
171    private void AttachEventHandlers() {
172      Costs.RowsChanged += new EventHandler(Costs_RowsChanged);
173      Costs.ColumnsChanged += new EventHandler(Costs_ColumnsChanged);
174      Costs.Reset += new EventHandler(Costs_Reset);
175      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
176    }
177
178    private void InitializeOperators() {
179      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
180      Operators.RemoveAll(x => x is IMoveOperator);
181      Operators.Add(bestLAPSolutionAnalyzer);
182
183      Operators.Add(new HammingSimilarityCalculator());
184      Operators.Add(new QualitySimilarityCalculator());
185      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
186    }
187
188    private void Parameterize() {
189      SolutionCreator.LengthParameter.Value = new IntValue(Costs.Rows);
190      SolutionCreator.LengthParameter.Hidden = true;
191      SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
192      SolutionCreator.PermutationTypeParameter.Hidden = true;
193      Evaluator.CostsParameter.ActualName = CostsParameter.Name;
194      Evaluator.CostsParameter.Hidden = true;
195      Evaluator.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
196      Evaluator.AssignmentParameter.Hidden = true;
197
198      foreach (var op in Operators.OfType<IPermutationCrossover>()) {
199        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
200        op.ParentsParameter.Hidden = true;
201        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
202        op.ChildParameter.Hidden = true;
203      }
204
205      foreach (var op in Operators.OfType<IPermutationManipulator>()) {
206        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
207        op.PermutationParameter.Hidden = true;
208      }
209
210      foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>()) {
211        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
212        op.PermutationParameter.Hidden = true;
213      }
214
215      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
216        similarityCalculator.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
217        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
218      }
219
220      bestLAPSolutionAnalyzer.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
221      bestLAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
222      bestLAPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
223      bestLAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
224      bestLAPSolutionAnalyzer.CostsParameter.ActualName = CostsParameter.Name;
225      bestLAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
226      bestLAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
227    }
228    #endregion
229  }
230}
Note: See TracBrowser for help on using the repository browser.