Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.Selection/3.3/EvolutionStrategyOffspringSelector.cs @ 16430

Last change on this file since 16430 was 15583, checked in by swagner, 6 years ago

#2640: Updated year of copyrights in license headers

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