Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Algorithms.OffspringSelectionGeneticAlgorithm/3.3/OffspringSelectionGeneticAlgorithm.cs @ 3735

Last change on this file since 3735 was 3735, checked in by abeham, 14 years ago

#893

  • updated description of selected parents
File size: 22.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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.Linq;
25using HeuristicLab.Analysis;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.PluginInfrastructure;
33using HeuristicLab.Random;
34using HeuristicLab.Common;
35
36namespace HeuristicLab.Algorithms.OffspringSelectionGeneticAlgorithm {
37  /// <summary>
38  /// An offspring selection genetic algorithm.
39  /// </summary>
40  [Item("Offspring Selection Genetic Algorithm", "An offspring selection genetic algorithm (Affenzeller, M. et al. 2009. Genetic Algorithms and Genetic Programming - Modern Concepts and Practical Applications. CRC Press).")]
41  [Creatable("Algorithms")]
42  [StorableClass]
43  public sealed class OffspringSelectionGeneticAlgorithm : EngineAlgorithm {
44    #region Problem Properties
45    public override Type ProblemType {
46      get { return typeof(ISingleObjectiveProblem); }
47    }
48    public new ISingleObjectiveProblem Problem {
49      get { return (ISingleObjectiveProblem)base.Problem; }
50      set { base.Problem = value; }
51    }
52    #endregion
53
54    #region Parameter Properties
55    private ValueParameter<IntValue> SeedParameter {
56      get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
57    }
58    private ValueParameter<BoolValue> SetSeedRandomlyParameter {
59      get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
60    }
61    private ValueParameter<IntValue> PopulationSizeParameter {
62      get { return (ValueParameter<IntValue>)Parameters["PopulationSize"]; }
63    }
64    private ConstrainedValueParameter<ISelector> SelectorParameter {
65      get { return (ConstrainedValueParameter<ISelector>)Parameters["Selector"]; }
66    }
67    private ConstrainedValueParameter<ICrossover> CrossoverParameter {
68      get { return (ConstrainedValueParameter<ICrossover>)Parameters["Crossover"]; }
69    }
70    private ValueParameter<PercentValue> MutationProbabilityParameter {
71      get { return (ValueParameter<PercentValue>)Parameters["MutationProbability"]; }
72    }
73    private OptionalConstrainedValueParameter<IManipulator> MutatorParameter {
74      get { return (OptionalConstrainedValueParameter<IManipulator>)Parameters["Mutator"]; }
75    }
76    private ValueParameter<IntValue> ElitesParameter {
77      get { return (ValueParameter<IntValue>)Parameters["Elites"]; }
78    }
79    private ValueParameter<IntValue> MaximumGenerationsParameter {
80      get { return (ValueParameter<IntValue>)Parameters["MaximumGenerations"]; }
81    }
82    private ValueLookupParameter<DoubleValue> SuccessRatioParameter {
83      get { return (ValueLookupParameter<DoubleValue>)Parameters["SuccessRatio"]; }
84    }
85    private ValueLookupParameter<DoubleValue> ComparisonFactorLowerBoundParameter {
86      get { return (ValueLookupParameter<DoubleValue>)Parameters["ComparisonFactorLowerBound"]; }
87    }
88    private ValueLookupParameter<DoubleValue> ComparisonFactorUpperBoundParameter {
89      get { return (ValueLookupParameter<DoubleValue>)Parameters["ComparisonFactorUpperBound"]; }
90    }
91    private OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier> ComparisonFactorModifierParameter {
92      get { return (OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters["ComparisonFactorModifier"]; }
93    }
94    private ValueLookupParameter<DoubleValue> MaximumSelectionPressureParameter {
95      get { return (ValueLookupParameter<DoubleValue>)Parameters["MaximumSelectionPressure"]; }
96    }
97    private ValueLookupParameter<BoolValue> OffspringSelectionBeforeMutationParameter {
98      get { return (ValueLookupParameter<BoolValue>)Parameters["OffspringSelectionBeforeMutation"]; }
99    }
100    private ValueLookupParameter<IntValue> SelectedParentsParameter {
101      get { return (ValueLookupParameter<IntValue>)Parameters["SelectedParents"]; }
102    }
103    private ValueParameter<MultiAnalyzer> AnalyzerParameter {
104      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
105    }
106    #endregion
107
108    #region Properties
109    public IntValue Seed {
110      get { return SeedParameter.Value; }
111      set { SeedParameter.Value = value; }
112    }
113    public BoolValue SetSeedRandomly {
114      get { return SetSeedRandomlyParameter.Value; }
115      set { SetSeedRandomlyParameter.Value = value; }
116    }
117    public IntValue PopulationSize {
118      get { return PopulationSizeParameter.Value; }
119      set { PopulationSizeParameter.Value = value; }
120    }
121    public ISelector Selector {
122      get { return SelectorParameter.Value; }
123      set { SelectorParameter.Value = value; }
124    }
125    public ICrossover Crossover {
126      get { return CrossoverParameter.Value; }
127      set { CrossoverParameter.Value = value; }
128    }
129    public PercentValue MutationProbability {
130      get { return MutationProbabilityParameter.Value; }
131      set { MutationProbabilityParameter.Value = value; }
132    }
133    public IManipulator Mutator {
134      get { return MutatorParameter.Value; }
135      set { MutatorParameter.Value = value; }
136    }
137    public IntValue Elites {
138      get { return ElitesParameter.Value; }
139      set { ElitesParameter.Value = value; }
140    }
141    public IntValue MaximumGenerations {
142      get { return MaximumGenerationsParameter.Value; }
143      set { MaximumGenerationsParameter.Value = value; }
144    }
145    public DoubleValue SuccessRatio {
146      get { return SuccessRatioParameter.Value; }
147      set { SuccessRatioParameter.Value = value; }
148    }
149    public DoubleValue ComparisonFactorLowerBound {
150      get { return ComparisonFactorLowerBoundParameter.Value; }
151      set { ComparisonFactorLowerBoundParameter.Value = value; }
152    }
153    public DoubleValue ComparisonFactorUpperBound {
154      get { return ComparisonFactorUpperBoundParameter.Value; }
155      set { ComparisonFactorUpperBoundParameter.Value = value; }
156    }
157    public IDiscreteDoubleValueModifier ComparisonFactorModifier {
158      get { return ComparisonFactorModifierParameter.Value; }
159      set { ComparisonFactorModifierParameter.Value = value; }
160    }
161    public DoubleValue MaximumSelectionPressure {
162      get { return MaximumSelectionPressureParameter.Value; }
163      set { MaximumSelectionPressureParameter.Value = value; }
164    }
165    public BoolValue OffspringSelectionBeforeMutation {
166      get { return OffspringSelectionBeforeMutationParameter.Value; }
167      set { OffspringSelectionBeforeMutationParameter.Value = value; }
168    }
169    public IntValue SelectedParents {
170      get { return SelectedParentsParameter.Value; }
171      set { SelectedParentsParameter.Value = value; }
172    }
173    public MultiAnalyzer Analyzer {
174      get { return AnalyzerParameter.Value; }
175      set { AnalyzerParameter.Value = value; }
176    }
177    private RandomCreator RandomCreator {
178      get { return (RandomCreator)OperatorGraph.InitialOperator; }
179    }
180    private SolutionsCreator SolutionsCreator {
181      get { return (SolutionsCreator)RandomCreator.Successor; }
182    }
183    private OffspringSelectionGeneticAlgorithmMainLoop MainLoop {
184      get { return (OffspringSelectionGeneticAlgorithmMainLoop)SolutionsCreator.Successor; }
185    }
186    [Storable]
187    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
188    [Storable]
189    private ValueAnalyzer selectionPressureAnalyzer;
190    #endregion
191
192    [StorableConstructor]
193    private OffspringSelectionGeneticAlgorithm(bool deserializing) : base(deserializing) { }
194    public OffspringSelectionGeneticAlgorithm()
195      : base() {
196      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
197      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
198      Parameters.Add(new ValueParameter<IntValue>("PopulationSize", "The size of the population of solutions.", new IntValue(100)));
199      Parameters.Add(new ConstrainedValueParameter<ISelector>("Selector", "The operator used to select solutions for reproduction."));
200      Parameters.Add(new ConstrainedValueParameter<ICrossover>("Crossover", "The operator used to cross solutions."));
201      Parameters.Add(new ValueParameter<PercentValue>("MutationProbability", "The probability that the mutation operator is applied on a solution.", new PercentValue(0.05)));
202      Parameters.Add(new OptionalConstrainedValueParameter<IManipulator>("Mutator", "The operator used to mutate solutions."));
203      Parameters.Add(new ValueParameter<IntValue>("Elites", "The numer of elite solutions which are kept in each generation.", new IntValue(1)));
204      Parameters.Add(new ValueParameter<IntValue>("MaximumGenerations", "The maximum number of generations which should be processed.", new IntValue(1000)));
205      Parameters.Add(new ValueLookupParameter<DoubleValue>("SuccessRatio", "The ratio of successful to total children that should be achieved.", new DoubleValue(1)));
206      Parameters.Add(new ValueLookupParameter<DoubleValue>("ComparisonFactorLowerBound", "The lower bound of the comparison factor (start).", new DoubleValue(0)));
207      Parameters.Add(new ValueLookupParameter<DoubleValue>("ComparisonFactorUpperBound", "The upper bound of the comparison factor (end).", new DoubleValue(1)));
208      Parameters.Add(new OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>("ComparisonFactorModifier", "The operator used to modify the comparison factor.", new ItemSet<IDiscreteDoubleValueModifier>(new IDiscreteDoubleValueModifier[] { new LinearDiscreteDoubleValueModifier() }), new LinearDiscreteDoubleValueModifier()));
209      Parameters.Add(new ValueLookupParameter<DoubleValue>("MaximumSelectionPressure", "The maximum selection pressure that terminates the algorithm.", new DoubleValue(100)));
210      Parameters.Add(new ValueLookupParameter<BoolValue>("OffspringSelectionBeforeMutation", "True if the offspring selection step should be applied before mutation, false if it should be applied after mutation.", new BoolValue(false)));
211      Parameters.Add(new ValueLookupParameter<IntValue>("SelectedParents", "How much parents should be selected each time the offspring selection step is performed until the population is filled. This parameter should be about the same or twice the size of PopulationSize for smaller problems, and less for large problems.", new IntValue(200)));
212      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
213     
214      RandomCreator randomCreator = new RandomCreator();
215      SolutionsCreator solutionsCreator = new SolutionsCreator();
216      OffspringSelectionGeneticAlgorithmMainLoop mainLoop = new OffspringSelectionGeneticAlgorithmMainLoop();
217      OperatorGraph.InitialOperator = randomCreator;
218
219      randomCreator.RandomParameter.ActualName = "Random";
220      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
221      randomCreator.SeedParameter.Value = null;
222      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
223      randomCreator.SetSeedRandomlyParameter.Value = null;
224      randomCreator.Successor = solutionsCreator;
225
226      solutionsCreator.NumberOfSolutionsParameter.ActualName = PopulationSizeParameter.Name;
227      solutionsCreator.Successor = mainLoop;
228
229      mainLoop.SelectorParameter.ActualName = SelectorParameter.Name;
230      mainLoop.CrossoverParameter.ActualName = CrossoverParameter.Name;
231      mainLoop.ElitesParameter.ActualName = ElitesParameter.Name;
232      mainLoop.MaximumGenerationsParameter.ActualName = MaximumGenerationsParameter.Name;
233      mainLoop.MutatorParameter.ActualName = MutatorParameter.Name;
234      mainLoop.MutationProbabilityParameter.ActualName = MutationProbabilityParameter.Name;
235      mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
236      mainLoop.ResultsParameter.ActualName = "Results";
237
238      foreach (ISelector selector in ApplicationManager.Manager.GetInstances<ISelector>().Where(x => !(x is IMultiObjectiveSelector)).OrderBy(x => x.Name))
239        SelectorParameter.ValidValues.Add(selector);
240      ISelector proportionalSelector = SelectorParameter.ValidValues.FirstOrDefault(x => x.GetType().Name.Equals("ProportionalSelector"));
241      if (proportionalSelector != null) SelectorParameter.Value = proportionalSelector;
242      ParameterizeSelectors();
243
244      foreach (IDiscreteDoubleValueModifier modifier in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name))
245        ComparisonFactorModifierParameter.ValidValues.Add(modifier);
246      IDiscreteDoubleValueModifier linearModifier = ComparisonFactorModifierParameter.ValidValues.FirstOrDefault(x => x.GetType().Name.Equals("LinearDiscreteDoubleValueModifier"));
247      if (linearModifier != null) ComparisonFactorModifierParameter.Value = linearModifier;
248      ParameterizeComparisonFactorModifiers();
249
250      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
251      selectionPressureAnalyzer = new ValueAnalyzer();
252      ParameterizeAnalyzers();
253      UpdateAnalyzers();
254
255      Initialize();
256    }
257
258    public override IDeepCloneable Clone(Cloner cloner) {
259      OffspringSelectionGeneticAlgorithm clone = (OffspringSelectionGeneticAlgorithm)base.Clone(cloner);
260      clone.qualityAnalyzer = (BestAverageWorstQualityAnalyzer)cloner.Clone(qualityAnalyzer);
261      clone.selectionPressureAnalyzer = (ValueAnalyzer)cloner.Clone(selectionPressureAnalyzer);
262      clone.Initialize();
263      return clone;
264    }
265
266    public override void Prepare() {
267      if (Problem != null) base.Prepare();
268    }
269
270    #region Events
271    protected override void OnProblemChanged() {
272      ParameterizeStochasticOperator(Problem.SolutionCreator);
273      ParameterizeStochasticOperator(Problem.Evaluator);
274      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
275      ParameterizeSolutionsCreator();
276      ParameterizMainLoop();
277      ParameterizeSelectors();
278      ParameterizeAnalyzers();
279      UpdateCrossovers();
280      UpdateMutators();
281      UpdateAnalyzers();
282      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
283      base.OnProblemChanged();
284    }
285
286    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
287      ParameterizeStochasticOperator(Problem.SolutionCreator);
288      ParameterizeSolutionsCreator();
289      base.Problem_SolutionCreatorChanged(sender, e);
290    }
291    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
292      ParameterizeStochasticOperator(Problem.Evaluator);
293      ParameterizeSolutionsCreator();
294      ParameterizMainLoop();
295      ParameterizeSelectors();
296      ParameterizeAnalyzers();
297      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
298      base.Problem_EvaluatorChanged(sender, e);
299    }
300    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
301      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
302      UpdateCrossovers();
303      UpdateMutators();
304      UpdateAnalyzers();
305      base.Problem_OperatorsChanged(sender, e);
306    }
307    private void ElitesParameter_ValueChanged(object sender, EventArgs e) {
308      Elites.ValueChanged += new EventHandler(Elites_ValueChanged);
309      ParameterizeSelectors();
310    }
311    private void Elites_ValueChanged(object sender, EventArgs e) {
312      ParameterizeSelectors();
313    }
314    private void PopulationSizeParameter_ValueChanged(object sender, EventArgs e) {
315      PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
316      ParameterizeSelectors();
317    }
318    private void PopulationSize_ValueChanged(object sender, EventArgs e) {
319      ParameterizeSelectors();
320    }
321    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
322      ParameterizMainLoop();
323      ParameterizeSelectors();
324      ParameterizeAnalyzers();
325    }
326    #endregion
327
328    #region Helpers
329    [StorableHook(HookType.AfterDeserialization)]
330    private void Initialize() {
331      PopulationSizeParameter.ValueChanged += new EventHandler(PopulationSizeParameter_ValueChanged);
332      PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
333      ElitesParameter.ValueChanged += new EventHandler(ElitesParameter_ValueChanged);
334      Elites.ValueChanged += new EventHandler(Elites_ValueChanged);
335      if (Problem != null) {
336        Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
337      }
338    }
339    private void ParameterizeSolutionsCreator() {
340      SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
341      SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
342    }
343    private void ParameterizMainLoop() {
344      MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
345      MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
346      MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
347    }
348    private void ParameterizeStochasticOperator(IOperator op) {
349      if (op is IStochasticOperator)
350        ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
351    }
352    private void ParameterizeSelectors() {
353      foreach (ISelector selector in SelectorParameter.ValidValues) {
354        selector.CopySelected = new BoolValue(true);
355        selector.NumberOfSelectedSubScopesParameter.Value = null;
356        selector.NumberOfSelectedSubScopesParameter.ActualName = SelectedParentsParameter.Name;
357        ParameterizeStochasticOperator(selector);
358      }
359      if (Problem != null) {
360        foreach (ISingleObjectiveSelector selector in SelectorParameter.ValidValues.OfType<ISingleObjectiveSelector>()) {
361          selector.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
362          selector.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
363        }
364      }
365    }
366    private void ParameterizeAnalyzers() {
367      qualityAnalyzer.ResultsParameter.ActualName = "Results";
368      selectionPressureAnalyzer.Name = "SelectionPressure Analyzer";
369      selectionPressureAnalyzer.ResultsParameter.ActualName = "Results";
370      selectionPressureAnalyzer.ValueParameter.ActualName = "SelectionPressure";
371      selectionPressureAnalyzer.ValueParameter.Depth = 0;
372      selectionPressureAnalyzer.ValuesParameter.ActualName = "Selection Pressure History";
373      if (Problem != null) {
374        qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
375        qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
376        qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
377      }
378    }
379    private void ParameterizeComparisonFactorModifiers() {
380      foreach (IDiscreteDoubleValueModifier modifier in ComparisonFactorModifierParameter.ValidValues) {
381        modifier.IndexParameter.ActualName = "Generations";
382        modifier.EndIndexParameter.ActualName = MaximumGenerationsParameter.Name;
383        modifier.EndValueParameter.ActualName = ComparisonFactorUpperBoundParameter.Name;
384        modifier.StartIndexParameter.Value = new IntValue(0);
385        modifier.StartValueParameter.ActualName = ComparisonFactorLowerBoundParameter.Name;
386        modifier.ValueParameter.ActualName = "ComparisonFactor";
387      }
388    }
389    private void UpdateCrossovers() {
390      ICrossover oldCrossover = CrossoverParameter.Value;
391      CrossoverParameter.ValidValues.Clear();
392      foreach (ICrossover crossover in Problem.Operators.OfType<ICrossover>().OrderBy(x => x.Name))
393        CrossoverParameter.ValidValues.Add(crossover);
394      if (oldCrossover != null) {
395        ICrossover crossover = CrossoverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldCrossover.GetType());
396        if (crossover != null) CrossoverParameter.Value = crossover;
397      }
398    }
399    private void UpdateMutators() {
400      IManipulator oldMutator = MutatorParameter.Value;
401      MutatorParameter.ValidValues.Clear();
402      foreach (IManipulator mutator in Problem.Operators.OfType<IManipulator>().OrderBy(x => x.Name))
403        MutatorParameter.ValidValues.Add(mutator);
404      if (oldMutator != null) {
405        IManipulator mutator = MutatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMutator.GetType());
406        if (mutator != null) MutatorParameter.Value = mutator;
407      }
408    }
409    private void UpdateAnalyzers() {
410      Analyzer.Operators.Clear();
411      Analyzer.Operators.Add(qualityAnalyzer);
412      Analyzer.Operators.Add(selectionPressureAnalyzer);
413      if (Problem != null) {
414        foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>().OrderBy(x => x.Name)) {
415          foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
416            param.Depth = 1;
417          Analyzer.Operators.Add(analyzer);
418        }
419      }
420    }
421    #endregion
422  }
423}
Note: See TracBrowser for help on using the repository browser.