Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 3580 was 3510, checked in by abeham, 15 years ago

Added a parameter to set the amount of selected parents #839, #976

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.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Operators;
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    #endregion
104
105    #region Properties
106    public IntValue Seed {
107      get { return SeedParameter.Value; }
108      set { SeedParameter.Value = value; }
109    }
110    public BoolValue SetSeedRandomly {
111      get { return SetSeedRandomlyParameter.Value; }
112      set { SetSeedRandomlyParameter.Value = value; }
113    }
114    public IntValue PopulationSize {
115      get { return PopulationSizeParameter.Value; }
116      set { PopulationSizeParameter.Value = value; }
117    }
118    public ISelector Selector {
119      get { return SelectorParameter.Value; }
120      set { SelectorParameter.Value = value; }
121    }
122    public ICrossover Crossover {
123      get { return CrossoverParameter.Value; }
124      set { CrossoverParameter.Value = value; }
125    }
126    public PercentValue MutationProbability {
127      get { return MutationProbabilityParameter.Value; }
128      set { MutationProbabilityParameter.Value = value; }
129    }
130    public IManipulator Mutator {
131      get { return MutatorParameter.Value; }
132      set { MutatorParameter.Value = value; }
133    }
134    public IntValue Elites {
135      get { return ElitesParameter.Value; }
136      set { ElitesParameter.Value = value; }
137    }
138    public IntValue MaximumGenerations {
139      get { return MaximumGenerationsParameter.Value; }
140      set { MaximumGenerationsParameter.Value = value; }
141    }
142    public DoubleValue SuccessRatio {
143      get { return SuccessRatioParameter.Value; }
144      set { SuccessRatioParameter.Value = value; }
145    }
146    public DoubleValue ComparisonFactorLowerBound {
147      get { return ComparisonFactorLowerBoundParameter.Value; }
148      set { ComparisonFactorLowerBoundParameter.Value = value; }
149    }
150    public DoubleValue ComparisonFactorUpperBound {
151      get { return ComparisonFactorUpperBoundParameter.Value; }
152      set { ComparisonFactorUpperBoundParameter.Value = value; }
153    }
154    public IDiscreteDoubleValueModifier ComparisonFactorModifier {
155      get { return ComparisonFactorModifierParameter.Value; }
156      set { ComparisonFactorModifierParameter.Value = value; }
157    }
158    public DoubleValue MaximumSelectionPressure {
159      get { return MaximumSelectionPressureParameter.Value; }
160      set { MaximumSelectionPressureParameter.Value = value; }
161    }
162    public BoolValue OffspringSelectionBeforeMutation {
163      get { return OffspringSelectionBeforeMutationParameter.Value; }
164      set { OffspringSelectionBeforeMutationParameter.Value = value; }
165    }
166    public IntValue SelectedParents {
167      get { return SelectedParentsParameter.Value; }
168      set { SelectedParentsParameter.Value = value; }
169    }
170    private RandomCreator RandomCreator {
171      get { return (RandomCreator)OperatorGraph.InitialOperator; }
172    }
173    private SolutionsCreator SolutionsCreator {
174      get { return (SolutionsCreator)RandomCreator.Successor; }
175    }
176    private OffspringSelectionGeneticAlgorithmMainLoop MainLoop {
177      get { return (OffspringSelectionGeneticAlgorithmMainLoop)SolutionsCreator.Successor; }
178    }
179    private List<ISelector> selectors;
180    private IEnumerable<ISelector> Selectors {
181      get { return selectors; }
182    }
183    private List<IDiscreteDoubleValueModifier> comparisonFactorModifiers;
184    #endregion
185
186    [StorableConstructor]
187    private OffspringSelectionGeneticAlgorithm(bool deserializing) : base(deserializing) { }
188    public OffspringSelectionGeneticAlgorithm()
189      : base() {
190      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
191      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
192      Parameters.Add(new ValueParameter<IntValue>("PopulationSize", "The size of the population of solutions.", new IntValue(100)));
193      Parameters.Add(new ConstrainedValueParameter<ISelector>("Selector", "The operator used to select solutions for reproduction."));
194      Parameters.Add(new ConstrainedValueParameter<ICrossover>("Crossover", "The operator used to cross solutions."));
195      Parameters.Add(new ValueParameter<PercentValue>("MutationProbability", "The probability that the mutation operator is applied on a solution.", new PercentValue(0.05)));
196      Parameters.Add(new OptionalConstrainedValueParameter<IManipulator>("Mutator", "The operator used to mutate solutions."));
197      Parameters.Add(new ValueParameter<IntValue>("Elites", "The numer of elite solutions which are kept in each generation.", new IntValue(1)));
198      Parameters.Add(new ValueParameter<IntValue>("MaximumGenerations", "The maximum number of generations which should be processed.", new IntValue(1000)));
199      Parameters.Add(new ValueLookupParameter<DoubleValue>("SuccessRatio", "The ratio of successful to total children that should be achieved.", new DoubleValue(1)));
200      Parameters.Add(new ValueLookupParameter<DoubleValue>("ComparisonFactorLowerBound", "The lower bound of the comparison factor (start).", new DoubleValue(0)));
201      Parameters.Add(new ValueLookupParameter<DoubleValue>("ComparisonFactorUpperBound", "The upper bound of the comparison factor (end).", new DoubleValue(1)));
202      Parameters.Add(new OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>("ComparisonFactorModifier", "The operator used to modify the comparison factor.", new ItemSet<IDiscreteDoubleValueModifier>(new IDiscreteDoubleValueModifier[] { new LinearDiscreteDoubleValueModifier() }), new LinearDiscreteDoubleValueModifier()));
203      Parameters.Add(new ValueLookupParameter<DoubleValue>("MaximumSelectionPressure", "The maximum selection pressure that terminates the algorithm.", new DoubleValue(100)));
204      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)));
205      Parameters.Add(new ValueLookupParameter<IntValue>("SelectedParents", "Should be about 2 * PopulationSize, for large problems use a smaller value to decrease memory footprint.", new IntValue(200)));
206
207      RandomCreator randomCreator = new RandomCreator();
208      SolutionsCreator solutionsCreator = new SolutionsCreator();
209      OffspringSelectionGeneticAlgorithmMainLoop mainLoop = new OffspringSelectionGeneticAlgorithmMainLoop();
210      OperatorGraph.InitialOperator = randomCreator;
211
212      randomCreator.RandomParameter.ActualName = "Random";
213      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
214      randomCreator.SeedParameter.Value = null;
215      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
216      randomCreator.SetSeedRandomlyParameter.Value = null;
217      randomCreator.Successor = solutionsCreator;
218
219      solutionsCreator.NumberOfSolutionsParameter.ActualName = PopulationSizeParameter.Name;
220      solutionsCreator.Successor = mainLoop;
221
222      mainLoop.SelectorParameter.ActualName = SelectorParameter.Name;
223      mainLoop.CrossoverParameter.ActualName = CrossoverParameter.Name;
224      mainLoop.ElitesParameter.ActualName = ElitesParameter.Name;
225      mainLoop.MaximumGenerationsParameter.ActualName = MaximumGenerationsParameter.Name;
226      mainLoop.MutatorParameter.ActualName = MutatorParameter.Name;
227      mainLoop.MutationProbabilityParameter.ActualName = MutationProbabilityParameter.Name;
228      mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
229      mainLoop.ResultsParameter.ActualName = "Results";
230
231      Initialize();
232    }
233
234    public override IDeepCloneable Clone(Cloner cloner) {
235      OffspringSelectionGeneticAlgorithm clone = (OffspringSelectionGeneticAlgorithm)base.Clone(cloner);
236      clone.Initialize();
237      return clone;
238    }
239
240    public override void Prepare() {
241      if (Problem != null) base.Prepare();
242    }
243
244    #region Events
245    protected override void OnProblemChanged() {
246      ParameterizeStochasticOperator(Problem.SolutionCreator);
247      ParameterizeStochasticOperator(Problem.Evaluator);
248      ParameterizeStochasticOperator(Problem.Visualizer);
249      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
250      ParameterizeSolutionsCreator();
251      ParameterizMainLoop();
252      ParameterizeSelectors();
253      UpdateCrossovers();
254      UpdateMutators();
255      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
256      if (Problem.Visualizer != null) Problem.Visualizer.VisualizationParameter.ActualNameChanged += new EventHandler(Visualizer_VisualizationParameter_ActualNameChanged);
257      base.OnProblemChanged();
258    }
259
260    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
261      ParameterizeStochasticOperator(Problem.SolutionCreator);
262      ParameterizeSolutionsCreator();
263      base.Problem_SolutionCreatorChanged(sender, e);
264    }
265    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
266      ParameterizeStochasticOperator(Problem.Evaluator);
267      ParameterizeSolutionsCreator();
268      ParameterizMainLoop();
269      ParameterizeSelectors();
270      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
271      base.Problem_EvaluatorChanged(sender, e);
272    }
273    protected override void Problem_VisualizerChanged(object sender, EventArgs e) {
274      ParameterizeStochasticOperator(Problem.Visualizer);
275      ParameterizMainLoop();
276      if (Problem.Visualizer != null) Problem.Visualizer.VisualizationParameter.ActualNameChanged += new EventHandler(Visualizer_VisualizationParameter_ActualNameChanged);
277      base.Problem_VisualizerChanged(sender, e);
278    }
279    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
280      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
281      UpdateCrossovers();
282      UpdateMutators();
283      base.Problem_OperatorsChanged(sender, e);
284    }
285    private void ElitesParameter_ValueChanged(object sender, EventArgs e) {
286      Elites.ValueChanged += new EventHandler(Elites_ValueChanged);
287      ParameterizeSelectors();
288    }
289    private void Elites_ValueChanged(object sender, EventArgs e) {
290      ParameterizeSelectors();
291    }
292    private void PopulationSizeParameter_ValueChanged(object sender, EventArgs e) {
293      PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
294      ParameterizeSelectors();
295    }
296    private void PopulationSize_ValueChanged(object sender, EventArgs e) {
297      ParameterizeSelectors();
298    }
299    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
300      ParameterizMainLoop();
301      ParameterizeSelectors();
302    }
303    private void Visualizer_VisualizationParameter_ActualNameChanged(object sender, EventArgs e) {
304      ParameterizMainLoop();
305    }
306    #endregion
307
308    #region Helpers
309    [StorableHook(HookType.AfterDeserialization)]
310    private void Initialize() {
311      InitializeSelectors();
312      UpdateSelectors();
313      InitializeComparisonFactorModifiers();
314      UpdateComparisonFactorModifiers();
315      PopulationSizeParameter.ValueChanged += new EventHandler(PopulationSizeParameter_ValueChanged);
316      PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
317      ElitesParameter.ValueChanged += new EventHandler(ElitesParameter_ValueChanged);
318      Elites.ValueChanged += new EventHandler(Elites_ValueChanged);
319      if (Problem != null) {
320        UpdateCrossovers();
321        UpdateMutators();
322        Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
323        if (Problem.Visualizer != null) Problem.Visualizer.VisualizationParameter.ActualNameChanged += new EventHandler(Visualizer_VisualizationParameter_ActualNameChanged);
324      }
325    }
326    private void ParameterizeSolutionsCreator() {
327      SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
328      SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
329    }
330    private void ParameterizMainLoop() {
331      MainLoop.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
332      MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
333      MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
334      MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
335      MainLoop.VisualizerParameter.ActualName = Problem.VisualizerParameter.Name;
336      if (Problem.Visualizer != null)
337        MainLoop.VisualizationParameter.ActualName = Problem.Visualizer.VisualizationParameter.ActualName;
338    }
339    private void ParameterizeStochasticOperator(IOperator op) {
340      if (op is IStochasticOperator)
341        ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
342    }
343    private void InitializeSelectors() {
344      selectors = new List<ISelector>();
345      selectors.AddRange(ApplicationManager.Manager.GetInstances<ISelector>().Where(x => !(x is IMultiObjectiveSelector)).OrderBy(x => x.Name));
346      ParameterizeSelectors();
347    }
348    private void InitializeComparisonFactorModifiers() {
349      comparisonFactorModifiers = new List<IDiscreteDoubleValueModifier>();
350      comparisonFactorModifiers.AddRange(ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name));
351      ParameterizeComparisonFactorModifiers();
352    }
353    private void ParameterizeSelectors() {
354      foreach (ISelector selector in Selectors) {
355        selector.CopySelected = new BoolValue(true);
356        selector.NumberOfSelectedSubScopesParameter.Value = null;
357        selector.NumberOfSelectedSubScopesParameter.ActualName = SelectedParentsParameter.Name;
358        ParameterizeStochasticOperator(selector);
359      }
360      if (Problem != null) {
361        foreach (ISingleObjectiveSelector selector in Selectors.OfType<ISingleObjectiveSelector>()) {
362          selector.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
363          selector.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
364        }
365      }
366    }
367    private void ParameterizeComparisonFactorModifiers() {
368      foreach (IDiscreteDoubleValueModifier modifier in comparisonFactorModifiers) {
369        modifier.IndexParameter.ActualName = "Generations";
370        modifier.EndIndexParameter.ActualName = MaximumGenerationsParameter.Name;
371        modifier.EndValueParameter.ActualName = ComparisonFactorUpperBoundParameter.Name;
372        modifier.StartIndexParameter.Value = new IntValue(0);
373        modifier.StartValueParameter.ActualName = ComparisonFactorLowerBoundParameter.Name;
374        modifier.ValueParameter.ActualName = "ComparisonFactor";
375      }
376    }
377    private void UpdateSelectors() {
378      ISelector oldSelector = SelectorParameter.Value;
379      SelectorParameter.ValidValues.Clear();
380      foreach (ISelector selector in Selectors.OrderBy(x => x.Name))
381        SelectorParameter.ValidValues.Add(selector);
382
383      ISelector proportionalSelector = SelectorParameter.ValidValues.FirstOrDefault(x => x.GetType().Name.Equals("ProportionalSelector"));
384      if (proportionalSelector != null) SelectorParameter.Value = proportionalSelector;
385
386      if (oldSelector != null) {
387        ISelector selector = SelectorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldSelector.GetType());
388        if (selector != null) SelectorParameter.Value = selector;
389      }
390    }
391    private void UpdateComparisonFactorModifiers() {
392      IDiscreteDoubleValueModifier oldModifier = ComparisonFactorModifier;
393
394      ComparisonFactorModifierParameter.ValidValues.Clear();
395      foreach (IDiscreteDoubleValueModifier modifier in comparisonFactorModifiers)
396        ComparisonFactorModifierParameter.ValidValues.Add(modifier);
397
398      if (oldModifier != null) {
399        IDiscreteDoubleValueModifier mod = ComparisonFactorModifierParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldModifier.GetType());
400        if (mod != null) ComparisonFactorModifierParameter.Value = mod;
401      }
402    }
403    private void UpdateCrossovers() {
404      ICrossover oldCrossover = CrossoverParameter.Value;
405      CrossoverParameter.ValidValues.Clear();
406      foreach (ICrossover crossover in Problem.Operators.OfType<ICrossover>().OrderBy(x => x.Name))
407        CrossoverParameter.ValidValues.Add(crossover);
408      if (oldCrossover != null) {
409        ICrossover crossover = CrossoverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldCrossover.GetType());
410        if (crossover != null) CrossoverParameter.Value = crossover;
411      }
412    }
413    private void UpdateMutators() {
414      IManipulator oldMutator = MutatorParameter.Value;
415      MutatorParameter.ValidValues.Clear();
416      foreach (IManipulator mutator in Problem.Operators.OfType<IManipulator>().OrderBy(x => x.Name))
417        MutatorParameter.ValidValues.Add(mutator);
418      if (oldMutator != null) {
419        IManipulator mutator = MutatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMutator.GetType());
420        if (mutator != null) MutatorParameter.Value = mutator;
421      }
422    }
423    #endregion
424  }
425}
Note: See TracBrowser for help on using the repository browser.