Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2520_PersistenceReintegration/HeuristicLab.Selection/3.3/EvolutionStrategyOffspringSelector.cs @ 16462

Last change on this file since 16462 was 16462, checked in by jkarder, 5 years ago

#2520: worked on reintegration of new persistence

  • added nuget references to HEAL.Fossil
  • added StorableType attributes to many classes
  • changed signature of StorableConstructors
  • removed some classes in old persistence
  • removed some unnecessary usings
File size: 14.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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 HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Operators;
28using HeuristicLab.Parameters;
29using HEAL.Fossil;
30
31namespace HeuristicLab.Selection {
32  [Item("EvolutionStrategyOffspringSelector", "Selects among the offspring population those that are designated successful and discards the unsuccessful offspring, except for some lucky losers. It expects the parent scopes to be below the first sub-scope, and offspring scopes to be below the second sub-scope separated again in two sub-scopes, the first with the failed offspring and the second with successful offspring.")]
33  [StorableType("CE585C3C-5139-44F0-9CB2-CC901A290831")]
34  public class EvolutionStrategyOffspringSelector : SingleSuccessorOperator {
35
36    private class FitnessComparer : IComparer<IScope> {
37
38      #region IComparer<IScope> Member
39
40      private String qualityParameterName;
41      private bool maximization;
42
43      public FitnessComparer(String qualityParamName, bool maximization) {
44        this.qualityParameterName = qualityParamName;
45        this.maximization = maximization;
46      }
47
48      // less than zero if x is-better-than y
49      // larger than zero if y is-better-than x
50      // zero if both are the same
51      public int Compare(IScope x, IScope y) {
52        IVariable quality1, quality2;
53
54        if (x.Variables.TryGetValue(qualityParameterName, out quality1)
55          && y.Variables.TryGetValue(qualityParameterName, out quality2)) {
56          DoubleValue left = quality1.Value as DoubleValue;
57          DoubleValue right = quality2.Value as DoubleValue;
58          var res = left.CompareTo(right);
59          if (maximization) return -res; // in the maximization case the largest value should preceed all others in the sort order
60          else return res;
61        } else
62          throw new ArgumentException("Quality variable " + qualityParameterName + " not found.");
63      }
64
65      #endregion
66    }
67
68    public ValueLookupParameter<DoubleValue> MaximumSelectionPressureParameter {
69      get { return (ValueLookupParameter<DoubleValue>)Parameters["MaximumSelectionPressure"]; }
70    }
71    public ValueLookupParameter<DoubleValue> SuccessRatioParameter {
72      get { return (ValueLookupParameter<DoubleValue>)Parameters["SuccessRatio"]; }
73    }
74    public LookupParameter<DoubleValue> SelectionPressureParameter {
75      get { return (ValueLookupParameter<DoubleValue>)Parameters["SelectionPressure"]; }
76    }
77    public LookupParameter<DoubleValue> CurrentSuccessRatioParameter {
78      get { return (LookupParameter<DoubleValue>)Parameters["CurrentSuccessRatio"]; }
79    }
80    public LookupParameter<ItemList<IScope>> OffspringPopulationParameter {
81      get { return (LookupParameter<ItemList<IScope>>)Parameters["OffspringPopulation"]; }
82    }
83    public LookupParameter<ItemList<IScope>> OffspringVirtualPopulationParameter {
84      get { return (LookupParameter<ItemList<IScope>>)Parameters["OffspringVirtualPopulation"]; }
85    }
86    public LookupParameter<IntValue> OffspringPopulationWinnersParameter {
87      get { return (LookupParameter<IntValue>)Parameters["OffspringPopulationWinners"]; }
88    }
89    public ScopeTreeLookupParameter<BoolValue> SuccessfulOffspringParameter {
90      get { return (ScopeTreeLookupParameter<BoolValue>)Parameters["SuccessfulOffspring"]; }
91    }
92    public OperatorParameter OffspringCreatorParameter {
93      get { return (OperatorParameter)Parameters["OffspringCreator"]; }
94    }
95    public LookupParameter<IntValue> EvaluatedSolutionsParameter {
96      get { return (LookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
97    }
98    private LookupParameter<IntValue> MaximumEvaluatedSolutionsParameter {
99      get { return (LookupParameter<IntValue>)Parameters["MaximumEvaluatedSolutions"]; }
100    }
101    public ILookupParameter<DoubleValue> QualityParameter {
102      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
103    }
104    public ILookupParameter<BoolValue> MaximizationParameter {
105      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
106    }
107
108    public IOperator OffspringCreator {
109      get { return OffspringCreatorParameter.Value; }
110      set { OffspringCreatorParameter.Value = value; }
111    }
112
113    [StorableConstructor]
114    protected EvolutionStrategyOffspringSelector(StorableConstructorFlag _) : base(_) { }
115    protected EvolutionStrategyOffspringSelector(EvolutionStrategyOffspringSelector original, Cloner cloner) : base(original, cloner) { }
116    public override IDeepCloneable Clone(Cloner cloner) {
117      return new EvolutionStrategyOffspringSelector(this, cloner);
118    }
119    public EvolutionStrategyOffspringSelector()
120      : base() {
121      Parameters.Add(new ValueLookupParameter<DoubleValue>("MaximumSelectionPressure", "The maximum selection pressure which prematurely terminates the offspring selection step."));
122      Parameters.Add(new ValueLookupParameter<DoubleValue>("SuccessRatio", "The ratio of successful offspring that has to be produced."));
123      Parameters.Add(new ValueLookupParameter<DoubleValue>("SelectionPressure", "The amount of selection pressure currently necessary to fulfill the success ratio."));
124      Parameters.Add(new ValueLookupParameter<DoubleValue>("CurrentSuccessRatio", "The current success ratio indicates how much of the successful offspring have already been generated."));
125      Parameters.Add(new LookupParameter<ItemList<IScope>>("OffspringPopulation", "Temporary store of the offspring population."));
126      Parameters.Add(new LookupParameter<ItemList<IScope>>("OffspringVirtualPopulation", "Temporary store of the offspring population."));
127      Parameters.Add(new LookupParameter<IntValue>("OffspringPopulationWinners", "Temporary store the number of successful offspring in the offspring population."));
128      Parameters.Add(new ScopeTreeLookupParameter<BoolValue>("SuccessfulOffspring", "True if the offspring was more successful than its parents.", 2));
129      Parameters.Add(new OperatorParameter("OffspringCreator", "The operator used to create new offspring."));
130      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of solution evaluations."));
131      Parameters.Add(new LookupParameter<IntValue>("MaximumEvaluatedSolutions", "The maximum number of evaluated solutions (approximately)."));
132      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a child"));
133      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "Flag that indicates if the problem is a maximization problem"));
134    }
135
136    public override IOperation Apply() {
137      double maxSelPress = MaximumSelectionPressureParameter.ActualValue.Value;
138      double successRatio = SuccessRatioParameter.ActualValue.Value;
139      IScope scope = ExecutionContext.Scope;
140      IScope parents = scope.SubScopes[0];
141      IScope offspring = scope.SubScopes[1];
142      int populationSize = parents.SubScopes.Count;
143
144      // retrieve actual selection pressure and success ratio
145      DoubleValue selectionPressure = SelectionPressureParameter.ActualValue;
146      if (selectionPressure == null) {
147        selectionPressure = new DoubleValue(0);
148        SelectionPressureParameter.ActualValue = selectionPressure;
149      }
150      DoubleValue currentSuccessRatio = CurrentSuccessRatioParameter.ActualValue;
151      if (currentSuccessRatio == null) {
152        currentSuccessRatio = new DoubleValue(0);
153        CurrentSuccessRatioParameter.ActualValue = currentSuccessRatio;
154      }
155
156      // retrieve next population
157      ItemList<IScope> population = OffspringPopulationParameter.ActualValue;
158      ItemList<IScope> virtual_population = OffspringVirtualPopulationParameter.ActualValue;
159
160      IntValue successfulOffspring;
161      if (population == null) {
162        population = new ItemList<IScope>();
163        OffspringPopulationParameter.ActualValue = population;
164        selectionPressure.Value = 0; // initialize selection pressure for this round
165        currentSuccessRatio.Value = 0; // initialize current success ratio for this round
166        successfulOffspring = new IntValue(0);
167        OffspringPopulationWinnersParameter.ActualValue = successfulOffspring;
168
169        virtual_population = new ItemList<IScope>();
170        OffspringVirtualPopulationParameter.ActualValue = virtual_population;
171      } else successfulOffspring = OffspringPopulationWinnersParameter.ActualValue;
172
173      int successfulOffspringAdded = 0;
174
175      // implement the ActualValue fetch here - otherwise the parent scope would also be included, given that there may be 1000 or more parents, this is quite unnecessary
176      string tname = SuccessfulOffspringParameter.TranslatedName;
177      double tmpSelPress = selectionPressure.Value;
178      double tmpSelPressInc = 1.0 / populationSize;
179      for (int i = 0; i < offspring.SubScopes.Count; i++) {
180        // fetch value
181        IVariable tmpVar;
182        if (!offspring.SubScopes[i].Variables.TryGetValue(tname, out tmpVar)) throw new InvalidOperationException(Name + ": Could not determine if an offspring was successful or not.");
183        BoolValue tmp = (tmpVar.Value as BoolValue);
184        if (tmp == null) throw new InvalidOperationException(Name + ": The variable that indicates whether an offspring is successful or not must contain a BoolValue.");
185
186        // add to population
187        if (tmp.Value) {
188          IScope currentOffspring = offspring.SubScopes[i];
189          offspring.SubScopes.RemoveAt(i);
190          i--; // next loop should continue with the subscope at index i which replaced currentOffspring
191          population.Add(currentOffspring);
192          successfulOffspringAdded++;
193        } else {
194          IScope currentOffspring = offspring.SubScopes[i];
195          offspring.SubScopes.RemoveAt(i);
196          i--;
197          virtual_population.Add(currentOffspring); // add to losers pool
198        }
199        tmpSelPress += tmpSelPressInc;
200
201        double tmpSuccessRatio = (successfulOffspring.Value + successfulOffspringAdded) / ((double)populationSize);
202        if (tmpSuccessRatio >= successRatio && (population.Count + virtual_population.Count) >= populationSize)
203          break;
204      }
205      successfulOffspring.Value += successfulOffspringAdded;
206
207      // calculate actual selection pressure and success ratio
208      selectionPressure.Value = tmpSelPress;
209      currentSuccessRatio.Value = successfulOffspring.Value / ((double)populationSize);
210
211      // check if enough children have been generated (or limit of selection pressure or evaluted solutions is reached)
212      if (((EvaluatedSolutionsParameter.ActualValue.Value < MaximumEvaluatedSolutionsParameter.ActualValue.Value)
213          && (selectionPressure.Value < maxSelPress)
214          && (currentSuccessRatio.Value < successRatio))
215        || ((population.Count + virtual_population.Count) < populationSize)) {
216        // more children required -> reduce left and start children generation again
217        scope.SubScopes.Remove(parents);
218        scope.SubScopes.Remove(offspring);
219        while (parents.SubScopes.Count > 0) {
220          IScope parent = parents.SubScopes[0];
221          parents.SubScopes.RemoveAt(0); // TODO: repeated call of RemoveAt(0) is inefficient?
222          scope.SubScopes.Add(parent); // order of subscopes is reversed
223        }
224
225        IOperator offspringCreator = OffspringCreatorParameter.ActualValue as IOperator;
226        if (offspringCreator == null) throw new InvalidOperationException(Name + ": More offspring are required, but no operator specified for creating them.");
227        return ExecutionContext.CreateOperation(offspringCreator); // this assumes that this operator will be called again indirectly or directly
228      } else {
229        // enough children generated
230        var fitnessComparer = new FitnessComparer(QualityParameter.TranslatedName, MaximizationParameter.ActualValue.Value);
231        population.Sort(fitnessComparer); // sort individuals by descending fitness
232
233        // keeps only the best successRatio * populationSize solutions in the population (the remaining ones are added to the virtual population)
234        int removed = 0;
235        for (int i = 0; i < population.Count; i++) {
236          double tmpSuccessRatio = i / (double)populationSize;
237          if (tmpSuccessRatio > successRatio) {
238            virtual_population.Add(population[i]);
239            removed++;
240          }
241        }
242        population.RemoveRange(population.Count - removed, removed);
243
244        //fill up population with best remaining children (successful or unsuccessful)
245        virtual_population.Sort(fitnessComparer);
246        int offspringNeeded = populationSize - population.Count;
247        for (int i = 0; i < offspringNeeded && i < virtual_population.Count; i++) {
248          population.Add(virtual_population[i]); // children are sorted by descending fitness
249        }
250
251        offspring.SubScopes.Clear();
252        offspring.SubScopes.AddRange(population);
253
254        scope.Variables.Remove(OffspringPopulationParameter.TranslatedName);
255        scope.Variables.Remove(OffspringVirtualPopulationParameter.TranslatedName);
256        scope.Variables.Remove(OffspringPopulationWinnersParameter.TranslatedName);
257        return base.Apply();
258      }
259    }
260  }
261}
Note: See TracBrowser for help on using the repository browser.