Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2457_ExpertSystem/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/GQAPQualitySimilarityReducer.cs @ 17175

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

#2457: branched integer encoding, some changes

File size: 5.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 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.Collections.Generic;
23using System.Linq;
24using HEAL.Attic;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.IntegerVectorEncoding;
29using HeuristicLab.Operators;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32
33namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Operators {
34  [Item("GQAPQualitySimilarityReducer", "Reduces two populations two one by using quality and similarity information to obtain a population of high quality, but also diverse solutions.")]
35  [StorableType("3E9B9095-C0FE-4B16-B2FD-9EC349A37CD2")]
36  public class GQAPQualitySimilarityReducer : SingleSuccessorOperator, IQualityAwareGQAPOperator, IAssignmentAwareGQAPOperator, IReducer {
37    public ILookupParameter<IntegerVector> AssignmentParameter {
38      get { return (ILookupParameter<IntegerVector>)Parameters["Assignment"]; }
39    }
40    public ILookupParameter<DoubleValue> QualityParameter {
41      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
42    }
43    public ILookupParameter<Evaluation> EvaluationParameter {
44      get { return (ILookupParameter<Evaluation>)Parameters["Evaluation"]; }
45    }
46    public ILookupParameter<IntValue> MinimumPopulationSizeParameter {
47      get { return (ILookupParameter<IntValue>)Parameters["MinimumPopulationSize"]; }
48    }
49    public ILookupParameter<IntValue> MaximumPopulationSizeParameter {
50      get { return (ILookupParameter<IntValue>)Parameters["MaximumPopulationSize"]; }
51    }
52
53    [StorableConstructor]
54    protected GQAPQualitySimilarityReducer(StorableConstructorFlag _) : base(_) { }
55    protected GQAPQualitySimilarityReducer(GQAPQualitySimilarityReducer original, Cloner cloner) : base(original, cloner) { }
56    public GQAPQualitySimilarityReducer()
57      : base() {
58      Parameters.Add(new LookupParameter<IntegerVector>("Assignment", GQAPSolutionCreator.AssignmentDescription));
59      Parameters.Add(new LookupParameter<DoubleValue>("Quality", ""));
60      Parameters.Add(new LookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));
61      Parameters.Add(new LookupParameter<IntValue>("MinimumPopulationSize", "The size of the population that should not be undershot."));
62      Parameters.Add(new LookupParameter<IntValue>("MaximumPopulationSize", "The size of the population that should not be surpassed."));
63    }
64
65    public override IDeepCloneable Clone(Cloner cloner) {
66      return new GQAPQualitySimilarityReducer(this, cloner);
67    }
68
69    public override IOperation Apply() {
70      string vectorName = AssignmentParameter.TranslatedName;
71      string qualityName = QualityParameter.TranslatedName;
72      int populationSize = MaximumPopulationSizeParameter.ActualValue.Value;
73
74      IScope remaining = ExecutionContext.Scope.SubScopes[0];
75      IScope selected = ExecutionContext.Scope.SubScopes[1];
76
77      List<Individual> population =
78        remaining.SubScopes.Select(x => new Individual((IntegerVector)x.Variables[vectorName].Value,
79                                                      ((DoubleValue)x.Variables[qualityName].Value).Value,
80                                                      x)).ToList();
81      HashSet<Individual> candidates = new HashSet<Individual>(
82        selected.SubScopes.Select(x => new Individual((IntegerVector)x.Variables[vectorName].Value,
83                                                     ((DoubleValue)x.Variables[qualityName].Value).Value,
84                                                     x)));
85
86      foreach (var candidate in candidates) {
87        double[] similarities = population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution, candidate.Solution)).ToArray();
88        if (!similarities.Any()) {
89          population.Add(candidate);
90          break;
91        }
92        if (similarities.Max() == 1.0) break;
93        if (population.Count < populationSize) {
94          population.Add(candidate);
95        } else {
96          var replacement = population.Select((v, i) => new { V = v, Index = i })
97                                      .Where(x => x.V.Quality > candidate.Quality);
98          if (replacement.Any()) {
99            replacement.OrderBy(x => similarities[x.Index]).ToArray();
100            population.Remove(replacement.Last().V);
101            population.Add(candidate);
102          }
103        }
104      }
105
106      ExecutionContext.Scope.SubScopes.Clear();
107      ExecutionContext.Scope.SubScopes.AddRange(population.Select(x => x.Scope));
108
109      return base.Apply();
110    }
111
112    private class Individual {
113      internal IntegerVector Solution { get; set; }
114      internal double Quality { get; set; }
115      internal IScope Scope { get; set; }
116
117      internal Individual(IntegerVector vector, double quality, IScope scope) {
118        Solution = vector;
119        Quality = quality;
120        Scope = scope;
121      }
122    }
123  }
124}
Note: See TracBrowser for help on using the repository browser.