Free cookie consent management tool by TermsFeed Policy Generator

source: branches/gteufl/HeuristicLab.Selection/3.3/EvolutionStrategyOffspringSelector.cs @ 13229

Last change on this file since 13229 was 12968, checked in by gkronber, 9 years ago

#2478 complete changes by gteufl for offspring selection ES

File size: 13.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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 HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
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  [StorableClass]
34  public class EvolutionStrategyOffspringSelector : SingleSuccessorOperator {
35
36    private class QualityComparer : IComparer<IScope> {
37
38      #region IComparer<IScope> Member
39
40      private String qualityParameterName;
41
42      public QualityComparer(String qualityParamName) {
43        this.qualityParameterName = qualityParamName;
44      }
45
46      public int Compare(IScope x, IScope y) {
47          IVariable quality1, quality2;
48
49          if (x.Variables.TryGetValue(qualityParameterName, out quality1)
50            && y.Variables.TryGetValue(qualityParameterName, out quality2)) {
51            DoubleValue dblVal = quality1.Value as DoubleValue;
52            DoubleValue dblVal2 = quality2.Value as DoubleValue;
53            return dblVal.CompareTo(dblVal2);
54          }
55          else
56            throw new Exception("ERROR!!! Quality Param: "+qualityParameterName);
57      }
58
59      #endregion
60    }
61
62    public ValueLookupParameter<DoubleValue> MaximumSelectionPressureParameter {
63      get { return (ValueLookupParameter<DoubleValue>)Parameters["MaximumSelectionPressure"]; }
64    }
65    public ValueLookupParameter<DoubleValue> SuccessRatioParameter {
66      get { return (ValueLookupParameter<DoubleValue>)Parameters["SuccessRatio"]; }
67    }
68    public LookupParameter<DoubleValue> SelectionPressureParameter {
69      get { return (ValueLookupParameter<DoubleValue>)Parameters["SelectionPressure"]; }
70    }
71    public LookupParameter<DoubleValue> CurrentSuccessRatioParameter {
72      get { return (LookupParameter<DoubleValue>)Parameters["CurrentSuccessRatio"]; }
73    }
74    public LookupParameter<ItemList<IScope>> OffspringPopulationParameter {
75      get { return (LookupParameter<ItemList<IScope>>)Parameters["OffspringPopulation"]; }
76    }
77    public LookupParameter<ItemList<IScope>> OffspringVirtualPopulationParameter {
78      get { return (LookupParameter<ItemList<IScope>>)Parameters["OffspringVirtualPopulation"]; }
79    }
80    public LookupParameter<IntValue> OffspringPopulationWinnersParameter {
81      get { return (LookupParameter<IntValue>)Parameters["OffspringPopulationWinners"]; }
82    }
83    public ScopeTreeLookupParameter<BoolValue> SuccessfulOffspringParameter {
84      get { return (ScopeTreeLookupParameter<BoolValue>)Parameters["SuccessfulOffspring"]; }
85    }
86    public OperatorParameter OffspringCreatorParameter {
87      get { return (OperatorParameter)Parameters["OffspringCreator"]; }
88    }
89    public LookupParameter<IntValue> EvaluatedSolutionsParameter {
90      get { return (LookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
91    }
92    private LookupParameter<IntValue> MaximumEvaluatedSolutionsParameter {
93      get { return (LookupParameter<IntValue>)Parameters["MaximumEvaluatedSolutions"]; }
94    }
95    public ILookupParameter<DoubleValue> QualityParameter {
96      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
97    }
98
99    public IOperator OffspringCreator {
100      get { return OffspringCreatorParameter.Value; }
101      set { OffspringCreatorParameter.Value = value; }
102    }
103
104    [StorableConstructor]
105    protected EvolutionStrategyOffspringSelector(bool deserializing) : base(deserializing) { }
106    protected EvolutionStrategyOffspringSelector(EvolutionStrategyOffspringSelector original, Cloner cloner) : base(original, cloner) { }
107    public override IDeepCloneable Clone(Cloner cloner) {
108      return new EvolutionStrategyOffspringSelector(this, cloner);
109    }
110    public EvolutionStrategyOffspringSelector()
111      : base() {
112      Parameters.Add(new ValueLookupParameter<DoubleValue>("MaximumSelectionPressure", "The maximum selection pressure which prematurely terminates the offspring selection step."));
113      Parameters.Add(new ValueLookupParameter<DoubleValue>("SuccessRatio", "The ratio of successful offspring that has to be produced."));
114      Parameters.Add(new ValueLookupParameter<DoubleValue>("SelectionPressure", "The amount of selection pressure currently necessary to fulfill the success ratio."));
115      Parameters.Add(new ValueLookupParameter<DoubleValue>("CurrentSuccessRatio", "The current success ratio indicates how much of the successful offspring have already been generated."));
116      Parameters.Add(new LookupParameter<ItemList<IScope>>("OffspringPopulation", "Temporary store of the offspring population."));
117      Parameters.Add(new LookupParameter<ItemList<IScope>>("OffspringVirtualPopulation", "Temporary store of the offspring population."));
118      Parameters.Add(new LookupParameter<IntValue>("OffspringPopulationWinners", "Temporary store the number of successful offspring in the offspring population."));
119      Parameters.Add(new ScopeTreeLookupParameter<BoolValue>("SuccessfulOffspring", "True if the offspring was more successful than its parents.", 2));
120      Parameters.Add(new OperatorParameter("OffspringCreator", "The operator used to create new offspring."));
121      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of times solutions have been evaluated."));
122      Parameters.Add(new LookupParameter<IntValue>("MaximumEvaluatedSolutions", "The maximum number of evaluated solutions (approximately)."));
123      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a child"));
124    }
125
126    public override IOperation Apply() {
127      double maxSelPress = MaximumSelectionPressureParameter.ActualValue.Value;
128      double successRatio = SuccessRatioParameter.ActualValue.Value;
129      IScope scope = ExecutionContext.Scope;
130      IScope parents = scope.SubScopes[0];
131      IScope offspring = scope.SubScopes[1];
132      int populationSize = parents.SubScopes.Count;
133
134      // retrieve actual selection pressure and success ratio
135      DoubleValue selectionPressure = SelectionPressureParameter.ActualValue;
136      if (selectionPressure == null) {
137        selectionPressure = new DoubleValue(0);
138        SelectionPressureParameter.ActualValue = selectionPressure;
139      }
140      DoubleValue currentSuccessRatio = CurrentSuccessRatioParameter.ActualValue;
141      if (currentSuccessRatio == null) {
142        currentSuccessRatio = new DoubleValue(0);
143        CurrentSuccessRatioParameter.ActualValue = currentSuccessRatio;
144      }
145
146      // retrieve next population
147      ItemList<IScope> population = OffspringPopulationParameter.ActualValue;
148      ItemList<IScope> virtual_population = OffspringVirtualPopulationParameter.ActualValue;
149
150      IntValue successfulOffspring;
151      if (population == null) {
152        population = new ItemList<IScope>();
153        OffspringPopulationParameter.ActualValue = population;
154        selectionPressure.Value = 0; // initialize selection pressure for this round
155        currentSuccessRatio.Value = 0; // initialize current success ratio for this round
156        successfulOffspring = new IntValue(0);
157        OffspringPopulationWinnersParameter.ActualValue = successfulOffspring;
158
159        virtual_population = new ItemList<IScope>();
160        OffspringVirtualPopulationParameter.ActualValue = virtual_population;
161      } else successfulOffspring = OffspringPopulationWinnersParameter.ActualValue;
162
163      int successfulOffspringNeeded = (int)((successRatio) * populationSize) - (successfulOffspring.Value);
164      int successfulOffspringAdded = 0;
165
166      // 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
167      string tname = SuccessfulOffspringParameter.TranslatedName;
168      double tmpSelPress = selectionPressure.Value, tmpSelPressInc = 1.0 / populationSize;
169      for (int i = 0; i < offspring.SubScopes.Count; i++) {
170        // fetch value
171        IVariable tmpVar;
172        if (!offspring.SubScopes[i].Variables.TryGetValue(tname, out tmpVar)) throw new InvalidOperationException(Name + ": Could not determine if an offspring was successful or not.");
173        BoolValue tmp = (tmpVar.Value as BoolValue);
174        if (tmp == null) throw new InvalidOperationException(Name + ": The variable that indicates whether an offspring is successful or not must contain a BoolValue.");
175
176        // add to population
177        if (tmp.Value) {
178          IScope currentOffspring = offspring.SubScopes[i];
179          offspring.SubScopes.Remove(currentOffspring);
180          i--;
181          population.Add(currentOffspring);
182          successfulOffspringAdded++;
183        }
184        else {
185          IScope currentOffspring = offspring.SubScopes[i];
186          offspring.SubScopes.Remove(currentOffspring);
187          i--;
188          virtual_population.Add(currentOffspring);
189        }
190        tmpSelPress += tmpSelPressInc;
191
192        double tmpSuccessRatio = (successfulOffspring.Value+successfulOffspringAdded) / ((double)populationSize);
193        if (tmpSuccessRatio >= successRatio && (population.Count + virtual_population.Count) >= populationSize)
194          break;
195      }
196      successfulOffspring.Value += successfulOffspringAdded;
197
198      // calculate actual selection pressure and success ratio
199      selectionPressure.Value = tmpSelPress;
200      currentSuccessRatio.Value = successfulOffspring.Value / ((double)populationSize);
201
202      // check if enough children have been generated (or limit of selection pressure or evaluted solutions is reached)
203      if (((EvaluatedSolutionsParameter.ActualValue.Value < MaximumEvaluatedSolutionsParameter.ActualValue.Value)
204          && (selectionPressure.Value < maxSelPress)
205          && (currentSuccessRatio.Value < successRatio))
206        || ((population.Count + virtual_population.Count) < populationSize)) {
207        // more children required -> reduce left and start children generation again
208        scope.SubScopes.Remove(parents);
209        scope.SubScopes.Remove(offspring);
210        while (parents.SubScopes.Count > 0) {
211          IScope parent = parents.SubScopes[0];
212          parents.SubScopes.RemoveAt(0);
213          scope.SubScopes.Add(parent);
214        }
215
216        IOperator moreOffspring = OffspringCreatorParameter.ActualValue as IOperator;
217        if (moreOffspring == null) throw new InvalidOperationException(Name + ": More offspring are required, but no operator specified for creating them.");
218        return ExecutionContext.CreateOperation(moreOffspring);
219      } else {
220        // enough children generated
221        QualityComparer qualityComparer = new QualityComparer(QualityParameter.TranslatedName);
222        population.Sort(qualityComparer);
223
224        //only keep minimum best successful children in population
225        int removed = 0;
226        for (int i = 0; i < population.Count; i++) {
227          double tmpSuccessRatio = i / (double)populationSize;
228          if (tmpSuccessRatio > successRatio) {
229              virtual_population.Add(population[i]);
230              removed++;
231          }
232        }
233        population.RemoveRange(population.Count - removed, removed);
234
235        //fill up population with best remaining children (successful or unsuccessful)
236        virtual_population.Sort(qualityComparer);
237        int offspringNeeded = populationSize - population.Count;
238        for (int i = 0; i < offspringNeeded && i < virtual_population.Count; i++) {
239          population.Add(virtual_population[i]);
240        }
241
242        offspring.SubScopes.Clear();
243        offspring.SubScopes.AddRange(population);
244
245        scope.Variables.Remove(OffspringPopulationParameter.TranslatedName);
246        scope.Variables.Remove(OffspringVirtualPopulationParameter.TranslatedName);
247        scope.Variables.Remove(OffspringPopulationWinnersParameter.TranslatedName);
248        return base.Apply();
249      }
250    }
251  }
252}
Note: See TracBrowser for help on using the repository browser.