Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 18232 was 17180, checked in by swagner, 5 years ago

#2875: Removed years in copyrights

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