source: trunk/sources/HeuristicLab.Selection/3.3/EvolutionStrategyOffspringSelector.cs @ 13164

Last change on this file since 13164 was 13164, checked in by gkronber, 3 years ago

#2478: copied selected parts from OSES branch to trunk

File size: 12.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 successfulOffspringAdded = 0;
164
165      // 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
166      string tname = SuccessfulOffspringParameter.TranslatedName;
167      double tmpSelPress = selectionPressure.Value, tmpSelPressInc = 1.0 / populationSize;
168      for (int i = 0; i < offspring.SubScopes.Count; i++) {
169        // fetch value
170        IVariable tmpVar;
171        if (!offspring.SubScopes[i].Variables.TryGetValue(tname, out tmpVar)) throw new InvalidOperationException(Name + ": Could not determine if an offspring was successful or not.");
172        BoolValue tmp = (tmpVar.Value as BoolValue);
173        if (tmp == null) throw new InvalidOperationException(Name + ": The variable that indicates whether an offspring is successful or not must contain a BoolValue.");
174
175        // add to population
176        if (tmp.Value) {
177          IScope currentOffspring = offspring.SubScopes[i];
178          offspring.SubScopes.Remove(currentOffspring);
179          i--;
180          population.Add(currentOffspring);
181          successfulOffspringAdded++;
182        }
183        else {
184          IScope currentOffspring = offspring.SubScopes[i];
185          offspring.SubScopes.Remove(currentOffspring);
186          i--;
187          virtual_population.Add(currentOffspring);
188        }
189        tmpSelPress += tmpSelPressInc;
190
191        double tmpSuccessRatio = (successfulOffspring.Value+successfulOffspringAdded) / ((double)populationSize);
192        if (tmpSuccessRatio >= successRatio && (population.Count + virtual_population.Count) >= populationSize)
193          break;
194      }
195      successfulOffspring.Value += successfulOffspringAdded;
196
197      // calculate actual selection pressure and success ratio
198      selectionPressure.Value = tmpSelPress;
199      currentSuccessRatio.Value = successfulOffspring.Value / ((double)populationSize);
200
201      // check if enough children have been generated (or limit of selection pressure or evaluted solutions is reached)
202      if (((EvaluatedSolutionsParameter.ActualValue.Value < MaximumEvaluatedSolutionsParameter.ActualValue.Value) 
203          && (selectionPressure.Value < maxSelPress) 
204          && (currentSuccessRatio.Value < successRatio)) 
205        || ((population.Count + virtual_population.Count) < populationSize)) {
206        // more children required -> reduce left and start children generation again
207        scope.SubScopes.Remove(parents);
208        scope.SubScopes.Remove(offspring);
209        while (parents.SubScopes.Count > 0) {
210          IScope parent = parents.SubScopes[0];
211          parents.SubScopes.RemoveAt(0);
212          scope.SubScopes.Add(parent);
213        }
214
215        IOperator moreOffspring = OffspringCreatorParameter.ActualValue as IOperator;
216        if (moreOffspring == null) throw new InvalidOperationException(Name + ": More offspring are required, but no operator specified for creating them.");
217        return ExecutionContext.CreateOperation(moreOffspring);
218      } else {
219        // enough children generated
220        QualityComparer qualityComparer = new QualityComparer(QualityParameter.TranslatedName);
221        population.Sort(qualityComparer);
222
223        //only keep minimum best successful children in population
224        int removed = 0;
225        for (int i = 0; i < population.Count; i++) {
226          double tmpSuccessRatio = i / (double)populationSize;
227          if (tmpSuccessRatio > successRatio) {
228              virtual_population.Add(population[i]);
229              removed++;
230          }
231        }
232        population.RemoveRange(population.Count - removed, removed);
233
234        //fill up population with best remaining children (successful or unsuccessful)
235        virtual_population.Sort(qualityComparer);
236        int offspringNeeded = populationSize - population.Count;
237        for (int i = 0; i < offspringNeeded && i < virtual_population.Count; i++) {
238          population.Add(virtual_population[i]);
239        }
240
241        offspring.SubScopes.Clear();
242        offspring.SubScopes.AddRange(population);
243
244        scope.Variables.Remove(OffspringPopulationParameter.TranslatedName);
245        scope.Variables.Remove(OffspringVirtualPopulationParameter.TranslatedName);
246        scope.Variables.Remove(OffspringPopulationWinnersParameter.TranslatedName);
247        return base.Apply();
248      }
249    }
250  }
251}
Note: See TracBrowser for help on using the repository browser.