Free cookie consent management tool by TermsFeed Policy Generator

source: branches/gteufl/HeuristicLab.Selection/3.3/CMAEvolutionStrategyOffspringSelector.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: 12.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("CMAEvolutionStrategyOffspringSelector", "Selects among the offspring population those that are designated successful and discards the unsuccessful offspring, except for some lucky losers. It expects the offspring scopes to be below the main scope.")]
33  [StorableClass]
34  public class CMAEvolutionStrategyOffspringSelector : 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 CMAEvolutionStrategyOffspringSelector(bool deserializing) : base(deserializing) { }
106    protected CMAEvolutionStrategyOffspringSelector(CMAEvolutionStrategyOffspringSelector original, Cloner cloner) : base(original, cloner) { }
107    public override IDeepCloneable Clone(Cloner cloner) {
108      return new CMAEvolutionStrategyOffspringSelector(this, cloner);
109    }
110    public CMAEvolutionStrategyOffspringSelector()
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 offspring = scope;
131      int populationSize = offspring.SubScopes.Count;
132
133      // retrieve actual selection pressure and success ratio
134      DoubleValue selectionPressure = SelectionPressureParameter.ActualValue;
135      if (selectionPressure == null) {
136        selectionPressure = new DoubleValue(0);
137        SelectionPressureParameter.ActualValue = selectionPressure;
138      }
139      DoubleValue currentSuccessRatio = CurrentSuccessRatioParameter.ActualValue;
140      if (currentSuccessRatio == null) {
141        currentSuccessRatio = new DoubleValue(0);
142        CurrentSuccessRatioParameter.ActualValue = currentSuccessRatio;
143      }
144
145      // retrieve next population
146      ItemList<IScope> population = OffspringPopulationParameter.ActualValue;
147      ItemList<IScope> virtual_population = OffspringVirtualPopulationParameter.ActualValue;
148
149      IntValue successfulOffspring;
150      if (population == null) {
151        population = new ItemList<IScope>();
152        OffspringPopulationParameter.ActualValue = population;
153        selectionPressure.Value = 0; // initialize selection pressure for this round
154        currentSuccessRatio.Value = 0; // initialize current success ratio for this round
155        successfulOffspring = new IntValue(0);
156        OffspringPopulationWinnersParameter.ActualValue = successfulOffspring;
157
158        virtual_population = new ItemList<IScope>();
159        OffspringVirtualPopulationParameter.ActualValue = virtual_population;
160      } else successfulOffspring = OffspringPopulationWinnersParameter.ActualValue;
161
162      int successfulOffspringNeeded = (int)((successRatio) * populationSize) - (successfulOffspring.Value);
163      int successfulOffspringAdded = 0;
164
165      // implement the ActualValue fetch here
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
207       
208        IOperator moreOffspring = OffspringCreatorParameter.ActualValue as IOperator;
209        offspring.SubScopes.Clear();
210
211        if (moreOffspring == null) throw new InvalidOperationException(Name + ": More offspring are required, but no operator specified for creating them.");
212        return ExecutionContext.CreateOperation(moreOffspring);
213      } else {
214        // enough children generated
215        QualityComparer qualityComparer = new QualityComparer(QualityParameter.TranslatedName);
216
217        //fill up population with best remaining children (unsuccessful)
218        virtual_population.Sort(qualityComparer);
219        int offspringNeeded = populationSize - population.Count;
220        for (int i = 0; i < offspringNeeded && i < virtual_population.Count; i++) {
221          population.Add(virtual_population[i]);
222        }
223
224        offspring.SubScopes.Clear();
225        offspring.SubScopes.AddRange(population);
226
227        scope.Variables.Remove(OffspringPopulationParameter.TranslatedName);
228        scope.Variables.Remove(OffspringVirtualPopulationParameter.TranslatedName);
229        scope.Variables.Remove(OffspringPopulationWinnersParameter.TranslatedName);
230        return base.Apply();
231      }
232    }
233  }
234}
Note: See TracBrowser for help on using the repository browser.