source: branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPool2TierUpdateMethod.cs @ 7786

Last change on this file since 7786 was 7786, checked in by jkarder, 9 years ago

#1331:

  • fixed bug in path relinking selection
  • fixed bug in ScatterSearch.Prepare()
  • added custom interface (IImprovementOperator) for Scatter Search specific improvement operators
  • switched from diversity calculation to similarity calculation
  • separated IPathRelinker from ICrossover
  • changed TestFunctionsImprovementOperator to use reflection for evaluating functions
  • changed SolutionPoolUpdateMethod to use similarity calculation for solution comparison
  • improved TravelingSalesmanImprovementOperator
  • improved operator graph
  • removed specific operators used to evaluate TestFunctions problems
  • removed custom crossover operator (NChildCrossover)
  • added parameters and adjusted types
  • adjusted event handling
  • changed access levels
  • minor code improvements
File size: 9.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Operators;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Algorithms.ScatterSearch {
33  /// <summary>
34  /// An operator that updates the solution pool using a 2-tier strategy.
35  /// </summary>
36  [Item("SolutionPool2TierUpdateMethod", "An operator that updates the solution pool using a 2-tier strategy.")]
37  [StorableClass]
38  public sealed class SolutionPool2TierUpdateMethod : SingleSuccessorOperator {
39    #region Parameter properties
40    public ScopeParameter CurrentScopeParameter {
41      get { return (ScopeParameter)Parameters["CurrentScope"]; }
42    }
43    public IValueLookupParameter<SimilarityCalculator> SimilarityCalculatorParameter {
44      get { return (IValueLookupParameter<SimilarityCalculator>)Parameters["SimilarityCalculator"]; }
45    }
46    public IValueLookupParameter<BoolValue> MaximizationParameter {
47      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
48    }
49    public IValueLookupParameter<BoolValue> NewSolutionsParameter {
50      get { return (IValueLookupParameter<BoolValue>)Parameters["NewSolutions"]; }
51    }
52    public IValueLookupParameter<IntValue> NumberOfHighQualitySolutionsParameter {
53      get { return (IValueLookupParameter<IntValue>)Parameters["NumberOfHighQualitySolutions"]; }
54    }
55    public IValueLookupParameter<IItem> QualityParameter {
56      get { return (IValueLookupParameter<IItem>)Parameters["Quality"]; }
57    }
58    public IValueLookupParameter<IntValue> ReferenceSetSizeParameter {
59      get { return (IValueLookupParameter<IntValue>)Parameters["ReferenceSetSize"]; }
60    }
61    public IValueLookupParameter<IItem> TargetParameter {
62      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
63    }
64    #endregion
65
66    #region Properties
67    private IScope CurrentScope {
68      get { return CurrentScopeParameter.ActualValue; }
69    }
70    private SimilarityCalculator SimilarityCalculator {
71      get { return SimilarityCalculatorParameter.ActualValue; }
72    }
73    private BoolValue Maximization {
74      get { return MaximizationParameter.ActualValue; }
75      set { MaximizationParameter.ActualValue = value; }
76    }
77    private BoolValue NewSolutions {
78      get { return NewSolutionsParameter.ActualValue; }
79    }
80    private IntValue NumberOfHighQualitySolutions {
81      get { return NumberOfHighQualitySolutionsParameter.ActualValue; }
82    }
83    private IItem Quality {
84      get { return QualityParameter.ActualValue; }
85    }
86    private IntValue ReferenceSetSize {
87      get { return ReferenceSetSizeParameter.ActualValue; }
88      set { ReferenceSetSizeParameter.ActualValue = value; }
89    }
90    private IItem Target {
91      get { return TargetParameter.ActualValue; }
92    }
93    #endregion
94
95    [StorableConstructor]
96    private SolutionPool2TierUpdateMethod(bool deserializing) : base(deserializing) { }
97    private SolutionPool2TierUpdateMethod(SolutionPool2TierUpdateMethod original, Cloner cloner) : base(original, cloner) { }
98    public SolutionPool2TierUpdateMethod() : base() { Initialize(); }
99
100    public override IDeepCloneable Clone(Cloner cloner) {
101      return new SolutionPool2TierUpdateMethod(this, cloner);
102    }
103
104    private void Initialize() {
105      #region Create parameters
106      Parameters.Add(new ScopeParameter("CurrentScope"));
107      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization"));
108      Parameters.Add(new ValueLookupParameter<BoolValue>("NewSolutions"));
109      Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfHighQualitySolutions"));
110      Parameters.Add(new ValueLookupParameter<IItem>("Quality"));
111      Parameters.Add(new ValueLookupParameter<IntValue>("ReferenceSetSize"));
112      Parameters.Add(new ValueLookupParameter<SimilarityCalculator>("SimilarityCalculator"));
113      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
114      #endregion
115    }
116
117    public override IOperation Apply() {
118      IScope parentsScope = new Scope("Parents");
119      IScope offspringScope = new Scope("Offspring");
120
121      // split parents and offspring
122      foreach (var scope in CurrentScope.SubScopes) {
123        parentsScope.SubScopes.AddRange(scope.SubScopes.Take(scope.SubScopes.Count - 1));
124        offspringScope.SubScopes.AddRange(scope.SubScopes.Last().SubScopes);
125      }
126
127      var orderedParents = Maximization.Value ? parentsScope.SubScopes.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
128                                                parentsScope.SubScopes.OrderBy(x => x.Variables[QualityParameter.ActualName].Value);
129      var orderedOffspring = Maximization.Value ? offspringScope.SubScopes.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
130                                                  offspringScope.SubScopes.OrderBy(x => x.Variables[QualityParameter.ActualName].Value);
131
132      var highQualityParents = orderedParents.Take(NumberOfHighQualitySolutions.Value).ToList();
133      IList<Tuple<IScope, double>> highSimilarityParents = new List<Tuple<IScope, double>>();
134      foreach (var oScope in orderedParents.Skip(NumberOfHighQualitySolutions.Value)) {
135        double similarity = 0.0;
136        foreach (var hScope in highQualityParents) {
137          similarity += SimilarityCalculator.ExecuteCalculation(oScope, hScope);
138        }
139        highSimilarityParents.Add(new Tuple<IScope, double>(oScope, similarity));
140      }
141
142      IList<Tuple<IScope, double>> offspring = new List<Tuple<IScope, double>>();
143      foreach (var oScope in orderedOffspring) {
144        double similarity = 0.0;
145        foreach (var hScope in highQualityParents) {
146          similarity += SimilarityCalculator.ExecuteCalculation(oScope, hScope);
147        }
148        offspring.Add(new Tuple<IScope, double>(oScope, similarity));
149      }
150
151      // update high quality part of the reference set
152      var hasBetterQuality = Maximization.Value ? (Func<Tuple<IScope, double>, bool>)(x => { return (x.Item1.Variables[QualityParameter.ActualName].Value as DoubleValue).Value > (highQualityParents.OrderBy(y => y.Variables[QualityParameter.ActualName].Value).First().Variables[QualityParameter.ActualName].Value as DoubleValue).Value; }) :
153                                                  (Func<Tuple<IScope, double>, bool>)(x => { return (x.Item1.Variables[QualityParameter.ActualName].Value as DoubleValue).Value < (highQualityParents.OrderByDescending(y => y.Variables[QualityParameter.ActualName].Value).First().Variables[QualityParameter.ActualName].Value as DoubleValue).Value; });
154      if (offspring.Any(hasBetterQuality)) NewSolutions.Value = true;
155      while (offspring.Any(hasBetterQuality)) { // better offspring available
156        // select best offspring
157        var bestChild = Maximization.Value ? offspring.OrderByDescending(x => x.Item1.Variables[QualityParameter.ActualName].Value).First() :
158                                             offspring.OrderBy(x => x.Item1.Variables[QualityParameter.ActualName].Value).First();
159        // select worst parent
160        var worstParent = Maximization.Value ? highQualityParents.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value).Last() :
161                                               highQualityParents.OrderBy(x => x.Variables[QualityParameter.ActualName].Value).Last();
162        highQualityParents.Remove(worstParent);
163        highQualityParents.Add(bestChild.Item1);
164        offspring.Remove(bestChild);
165      }
166
167      // update diversity part of the reference set
168      var hasBetterDiversity = (Func<Tuple<IScope, double>, bool>)(x => { return x.Item2 < highSimilarityParents.OrderByDescending(y => y.Item2).First().Item2; });
169      if (offspring.Any(hasBetterDiversity)) NewSolutions.Value = true;
170      while (offspring.Any(hasBetterDiversity)) { // better offspring available
171        // select best offspring
172        var bestChild = offspring.OrderBy(x => x.Item2).First();
173        // select worst parent
174        var worstParent = highSimilarityParents.OrderByDescending(x => x.Item2).First();
175        highSimilarityParents.Remove(worstParent);
176        highSimilarityParents.Add(bestChild);
177        offspring.Remove(bestChild);
178      }
179
180      CurrentScope.SubScopes.Replace(highQualityParents.Concat(highSimilarityParents.Select(x => x.Item1)).ToList());
181
182      return base.Apply();
183    }
184  }
185}
Note: See TracBrowser for help on using the repository browser.