source: branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs @ 7744

Last change on this file since 7744 was 7744, checked in by jkarder, 8 years ago

#1331:

  • added problem specific improvement operators (KnapsackImprovementOperator, TravelingSalesmanImprovementOperator)
  • added custom interface (IScatterSearchTargetProcessor) for Scatter Search specific operators that use a target parameter
  • added custom operator (OffspringProcessor) to process multiple children that were created by crossovers
  • extracted diversity calculation and added problem/encoding specific operators (BinaryVectorDiversityCalculator, PermutationDiversityCalculator) for it
  • added parameters and adjusted types
  • adjusted event handling
  • minor code improvements
File size: 7.1 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.
35  /// </summary>
36  [Item("SolutionPoolUpdateMethod", "An operator that updates the solution pool.")]
37  [StorableClass]
38  public sealed class SolutionPoolUpdateMethod : SingleSuccessorOperator, IScatterSearchTargetProcessor {
39    #region Parameter properties
40    public ScopeParameter CurrentScopeParameter {
41      get { return (ScopeParameter)Parameters["CurrentScope"]; }
42    }
43    public IValueLookupParameter<BoolValue> MaximizationParameter {
44      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
45    }
46    public IValueLookupParameter<BoolValue> NewSolutionsParameter {
47      get { return (IValueLookupParameter<BoolValue>)Parameters["NewSolutions"]; }
48    }
49    public IValueLookupParameter<IntValue> ReferenceSetSizeParameter {
50      get { return (IValueLookupParameter<IntValue>)Parameters["ReferenceSetSize"]; }
51    }
52    public IValueLookupParameter<IItem> QualityParameter {
53      get { return (IValueLookupParameter<IItem>)Parameters["Quality"]; }
54    }
55    public IValueLookupParameter<IItem> TargetParameter {
56      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
57    }
58    #endregion
59
60    #region Properties
61    private IScope CurrentScope {
62      get { return CurrentScopeParameter.ActualValue; }
63    }
64    private BoolValue Maximization {
65      get { return MaximizationParameter.ActualValue; }
66      set { MaximizationParameter.ActualValue = value; }
67    }
68    private BoolValue NewSolutions {
69      get { return NewSolutionsParameter.ActualValue; }
70    }
71    private IntValue ReferenceSetSize {
72      get { return ReferenceSetSizeParameter.ActualValue; }
73      set { ReferenceSetSizeParameter.ActualValue = value; }
74    }
75    private IItem Quality {
76      get { return QualityParameter.ActualValue; }
77    }
78    private IItem Target {
79      get { return TargetParameter.ActualValue; }
80    }
81    #endregion
82
83    [StorableConstructor]
84    private SolutionPoolUpdateMethod(bool deserializing) : base(deserializing) { }
85    private SolutionPoolUpdateMethod(SolutionPoolUpdateMethod original, Cloner cloner) : base(original, cloner) { }
86    public SolutionPoolUpdateMethod() : base() { Initialize(); }
87
88    public override IDeepCloneable Clone(Cloner cloner) {
89      return new SolutionPoolUpdateMethod(this, cloner);
90    }
91
92    private void Initialize() {
93      #region Create parameters
94      Parameters.Add(new ScopeParameter("CurrentScope"));
95      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization"));
96      Parameters.Add(new ValueLookupParameter<BoolValue>("NewSolutions"));
97      Parameters.Add(new ValueLookupParameter<IntValue>("ReferenceSetSize"));
98      Parameters.Add(new ValueLookupParameter<IItem>("Quality"));
99      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
100      #endregion
101      TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
102    }
103
104    public override IOperation Apply() {
105      var parentsScope = new Scope("Parents");
106      var offspringScope = new Scope("Offspring");
107
108      // split parents and offspring
109      foreach (var scope in CurrentScope.SubScopes) {
110        parentsScope.SubScopes.AddRange(scope.SubScopes.Take(scope.SubScopes.Count - 1));
111        offspringScope.SubScopes.AddRange(scope.SubScopes.Last().SubScopes);
112      }
113
114      CurrentScope.SubScopes.Clear();
115
116      var orderedParents = Maximization.Value ? parentsScope.SubScopes.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
117                                                parentsScope.SubScopes.OrderBy(x => x.Variables[QualityParameter.ActualName].Value);
118      var orderedOffspring = Maximization.Value ? offspringScope.SubScopes.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
119                                                  offspringScope.SubScopes.OrderBy(x => x.Variables[QualityParameter.ActualName].Value);
120
121      CurrentScope.SubScopes.AddRange(orderedParents);
122
123      var worstParentQuality = (orderedParents.Last().Variables[QualityParameter.ActualName].Value as DoubleValue).Value;
124
125      var Constraint = Maximization.Value ? (Func<IScope, bool>)(x => { return (x.Variables[QualityParameter.ActualName].Value as DoubleValue).Value > worstParentQuality; }) :
126                                            (Func<IScope, bool>)(x => { return (x.Variables[QualityParameter.ActualName].Value as DoubleValue).Value < worstParentQuality; });
127
128      // is there any offspring better than the worst parent?
129      if (orderedOffspring.Any(Constraint)) {
130        // produce the set union
131        // attention: distinction might cause a too small reference set! (e.g. reference set = {1, 2, 2, 2, ..., 2} -> union = {1, 2}
132        var union = orderedParents.Union(orderedOffspring.Where(Constraint), new KeyEqualityComparer<IScope>(x => x.Variables[TargetParameter.ActualName].Value.ToString()));
133        if (union.Count() > orderedParents./*Distinct(new KeyEqualityComparer<IScope>(x => x.Variables[TargetParameter.ActualName].Value.ToString())).*/Count()) {
134          var orderedUnion = Maximization.Value ? union.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
135                                                  union.OrderBy(x => x.Variables[QualityParameter.ActualName].Value);
136          CurrentScope.SubScopes.Replace(orderedUnion.Take(ReferenceSetSize.Value).ToList());
137          NewSolutions.Value = true;
138        }
139      }
140
141      return base.Apply();
142    }
143
144    private class KeyEqualityComparer<T> : IEqualityComparer<T> {
145      private readonly Func<T, object> keyExtractor;
146
147      public KeyEqualityComparer(Func<T, object> keyExtractor) {
148        this.keyExtractor = keyExtractor;
149      }
150
151      public bool Equals(T x, T y) {
152        return keyExtractor(x).Equals(keyExtractor(y));
153      }
154
155      public int GetHashCode(T obj) {
156        return keyExtractor(obj).GetHashCode();
157      }
158    }
159  }
160}
Note: See TracBrowser for help on using the repository browser.