source: trunk/sources/HeuristicLab.Optimization.Operators/3.3/MultiCrossover.cs @ 3418

Last change on this file since 3418 was 3418, checked in by abeham, 12 years ago

Moved TabuMaker from Optimization to Optimization.Operators (and updated references)
Added StochasticMultiBranch
Implemented MultiCrossover and PermutationMultiCrossover
#976, #840

File size: 6.6 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.Collections.ObjectModel;
25using System.Linq;
26using HeuristicLab.Collections;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34
35namespace HeuristicLab.Operators {
36  /// <summary>
37  /// Base class for multi crossover operators.
38  /// </summary>
39  [Item("MultiCrossover", "Base class for multi crossover operators.")]
40  [StorableClass]
41  public class MultiCrossover<T> : MultiOperator<T>, IStochasticOperator where T : class, ICrossover {
42    public ValueLookupParameter<DoubleArray> ProbabilitiesParameter {
43      get { return (ValueLookupParameter<DoubleArray>)Parameters["Probabilities"]; }
44    }
45    public ILookupParameter<IRandom> RandomParameter {
46      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
47    }
48
49    public DoubleArray Probabilities {
50      get { return ProbabilitiesParameter.Value; }
51      set { ProbabilitiesParameter.Value = value; }
52    }
53
54    [StorableConstructor]
55    protected MultiCrossover(bool deserializing) : base(deserializing) { }
56    /// <summary>
57    /// Initializes a new instance of <see cref="StochasticMultiBranch"/> with two parameters
58    /// (<c>Probabilities</c> and <c>Random</c>).
59    /// </summary>
60    public MultiCrossover()
61      : base() {
62      Parameters.Add(new ValueLookupParameter<DoubleArray>("Probabilities", "The array of relative probabilities for each operator.", new DoubleArray()));
63      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
64      Initialize();
65    }
66
67    [StorableHook(HookType.AfterDeserialization)]
68    private void Initialize() {
69      Operators.ItemsAdded += new CollectionItemsChangedEventHandler<IndexedItem<T>>(Operators_ItemsAdded);
70      Operators.ItemsRemoved += new CollectionItemsChangedEventHandler<IndexedItem<T>>(Operators_ItemsRemoved);
71      Operators.ItemsMoved += new CollectionItemsChangedEventHandler<IndexedItem<T>>(Operators_ItemsMoved);
72      IEnumerable<Type> types = ApplicationManager.Manager.GetTypes(typeof(T), true);
73      foreach (Type type in types) {
74        if (type != this.GetType())
75          Operators.Add((T)Activator.CreateInstance(type));
76      }
77    }
78
79    void Operators_ItemsMoved(object sender, CollectionItemsChangedEventArgs<IndexedItem<T>> e) {
80      if (Probabilities != null) {
81        DoubleArray oldProb = (DoubleArray)Probabilities.Clone();
82        foreach (IndexedItem<T> old in e.OldItems) {
83          foreach (IndexedItem<T> item in e.Items) {
84            if (old.Value == item.Value && item.Index < Probabilities.Length && old.Index < oldProb.Length)
85              Probabilities[item.Index] = oldProb[old.Index];
86          }
87        }
88      }
89    }
90
91    void Operators_ItemsRemoved(object sender, CollectionItemsChangedEventArgs<IndexedItem<T>> e) {
92      if (Probabilities != null && Probabilities.Length > Operators.Count) {
93        List<double> probs = new List<double>(Probabilities.Cast<double>());
94        var sorted = e.Items.OrderByDescending(x => x.Index);
95        foreach (IndexedItem<T> item in sorted)
96          if (probs.Count > item.Index) probs.RemoveAt(item.Index);
97        Probabilities = new DoubleArray(probs.ToArray());
98      }
99    }
100
101    private void Operators_ItemsAdded(object sender, HeuristicLab.Collections.CollectionItemsChangedEventArgs<IndexedItem<T>> e) {
102      if (Probabilities != null && Probabilities.Length < Operators.Count) {
103        DoubleArray probs = new DoubleArray(Operators.Count);
104        double avg = 0;
105        if (Probabilities.Length > 0) {
106          for (int i = 0; i < Probabilities.Length; i++)
107            avg += Probabilities[i];
108          avg /= (double)Probabilities.Length;
109        } else avg = 1;
110
111        var added = e.Items.OrderBy(x => x.Index).ToList();
112        int insertCount = 0;
113        for (int i = 0; i < Operators.Count; i++) {
114          if (insertCount < added.Count && i == added[insertCount].Index) {
115            probs[i] = avg;
116            insertCount++;
117          } else if (i - insertCount < Probabilities.Length) {
118            probs[i] = Probabilities[i - insertCount];
119          } else probs[i] = avg;
120        }
121        Probabilities = probs;
122      }
123    }
124
125    /// <summary>
126    /// Applies an operator of the branches to the current scope with a
127    /// specific probability.
128    /// </summary>
129    /// <exception cref="InvalidOperationException">Thrown when the list of probabilites does not
130    /// match the number of operators.</exception>
131    /// <returns>A new operation with the operator that was selected followed by the current operator's successor.</returns>
132    public override IOperation Apply() {
133      IRandom random = RandomParameter.ActualValue;
134      DoubleArray probabilities = ProbabilitiesParameter.ActualValue;
135      if(probabilities.Length != Operators.Count) {
136        throw new InvalidOperationException("MultiCrossover: The list of probabilities has to match the number of operators");
137      }
138      double sum = 0;
139      for (int i = 0; i < Operators.Count; i++) {
140        sum += probabilities[i];
141      }
142      double r = random.NextDouble() * sum;
143      sum = 0;
144      IOperator successor = null;
145      for(int i = 0; i < Operators.Count; i++) {
146        sum += probabilities[i];
147        if(sum > r) {
148          successor = Operators[i];
149          break;
150        }
151      }
152      OperationCollection next = new OperationCollection(base.Apply());
153      if (successor != null) {
154        next.Insert(0, ExecutionContext.CreateChildOperation(successor));
155      }
156      return next;
157    }
158  }
159}
Note: See TracBrowser for help on using the repository browser.