source: branches/HeuristicLab.Problems.BioBoost/HeuristicLab.Problems.BioBoost/3.3/Operators/Crossover/PlantBasedCrossover.cs @ 13069

Last change on this file since 13069 was 13069, checked in by gkronber, 7 years ago

#2499: imported source code for HeuristicLab.BioBoost from private repository with some changes

File size: 9.7 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.ComponentModel;
4using System.Diagnostics;
5using HeuristicLab.BioBoost.Data;
6using HeuristicLab.BioBoost.ProblemDescription;
7using HeuristicLab.BioBoost.Utils;
8using HeuristicLab.Common;
9using HeuristicLab.Core;
10using HeuristicLab.Data;
11using HeuristicLab.Encodings.IntegerVectorEncoding;
12using HeuristicLab.Encodings.RealVectorEncoding;
13using HeuristicLab.Operators;
14using HeuristicLab.Optimization;
15using HeuristicLab.Parameters;
16using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
17using HeuristicLab.PluginInfrastructure;
18using System.Linq;
19using HeuristicLab.BioBoost.Representation;
20using HeuristicLab.Random;
21using DiscreteIntegerVectorCrossover = HeuristicLab.Encodings.IntegerVectorEncoding.DiscreteCrossover;
22using DiscreteRealVectorCrossover = HeuristicLab.Encodings.RealVectorEncoding.DiscreteCrossover;
23
24namespace HeuristicLab.BioBoost.Operators.Crossover {
25  [StorableClass]
26  public class PlantBasedCrossover : SingleSuccessorOperator, ICrossover, IStochasticOperator {
27
28    #region Parameters
29    public ValueLookupParameter<IntMatrix> RegionBoundsParameter {
30      get { return (ValueLookupParameter<IntMatrix>)Parameters["RegionBounds"]; }
31    }
32    public LookupParameter<BioBoostProblemData> ProblemDataParameter {
33      get { return (LookupParameter<BioBoostProblemData>)Parameters["ProblemData"]; }
34    }
35    public ILookupParameter<IRandom> RandomParameter { get { return (ILookupParameter<IRandom>) Parameters["Random"]; } }
36    public IValueLookupParameter<IntValue> OrderingParameter { get { return (IValueLookupParameter<IntValue>) Parameters["Ordering"]; } }
37    public IValueLookupParameter<IntValue> FrequencyParameter { get { return (IValueLookupParameter<IntValue>) Parameters["Frequency"]; } }
38    public IValueLookupParameter<PercentValue> FairnessParameter { get { return (IValueLookupParameter<PercentValue>) Parameters["Fairness"]; } }
39    #endregion
40
41    #region Parameter Values
42    public BioBoostProblemData ProblemData { get { return ProblemDataParameter.ActualValue; } }
43    public IRandom Random { get { return RandomParameter.ActualValue; } }
44    public int Ordering { get { return OrderingParameter.ActualValue.Value; } }
45    public int Frequency { get { return FrequencyParameter.ActualValue.Value; } }
46    public double Fairness { get { return FairnessParameter.ActualValue.Value; } }
47    #endregion
48
49    #region Construction & Cloning
50    [StorableConstructor]
51    protected PlantBasedCrossover(bool isDeserializing) : base(isDeserializing) { }
52    protected PlantBasedCrossover(PlantBasedCrossover orig, Cloner cloner) : base(orig, cloner) { }
53
54    public PlantBasedCrossover() {
55      Parameters.Add(new LookupParameter<BioBoostProblemData>("ProblemData", "The data store of the detailed problem description."));
56      Parameters.Add(new ValueLookupParameter<IntMatrix>("RegionBounds", "The limits of valid region ids."));
57      Parameters.Add(new LookupParameter<IRandom>("Random", "A/The random value generator."));
58      Parameters.Add(new ValueLookupParameter<IntValue>("Ordering", "Choose ordering 1: largest-first, -1: smallest first, 0: random", new IntValue(1)));
59      Parameters.Add(new ValueLookupParameter<IntValue>("Frequency", "Number of crossover points -1: random, 0: after every plant, n: n times", new IntValue(1)));
60      Parameters.Add(new ValueLookupParameter<PercentValue>("Fairness", "Amount of fairness: 0 don't bother, 1 avoid favoring one parent", new PercentValue(0)));
61    }
62
63    public override IDeepCloneable Clone(Cloner cloner) {
64      return new PlantBasedCrossover(this, cloner);
65    }
66
67    [StorableHook(HookType.AfterDeserialization)]
68    public void AfterDeserialization() {
69      if (!Parameters.ContainsKey("Ordering"))
70        Parameters.Add(new ValueLookupParameter<IntValue>("Ordering", "Choose ordering 1: largest-first, -1: smallest first, 0: random", new IntValue(0)));
71      if (!Parameters.ContainsKey("Frequency"))
72        Parameters.Add(new ValueLookupParameter<IntValue>("Frequency", "Number of crossover points -n: random (1-n), 0: ignore (order-based only), n: n times", new IntValue(0)));
73      if (!Parameters.ContainsKey("Fairness"))
74        Parameters.Add(new ValueLookupParameter<PercentValue>("Fairness", "Amount of fairness 0: don't bother -  1: avoid favoring one parent", new PercentValue(0)));
75    }
76    #endregion
77
78    public override IOperation Apply() {
79      var nParents = ExecutionContext.Scope.SubScopes.Count;
80      if (nParents == 0) return base.Apply();
81      foreach (var product in ProblemData.TransportTargets.CheckedItems) {
82        var targets = new IntegerVector[nParents];
83        var utilizations = new RealVector[nParents];
84        foreach (var i in Enumerable.Range(0, nParents))
85          GetVectors(ExecutionContext.Scope.SubScopes[i], product.Value.Value, out targets[i], out utilizations[i]);
86        if (targets.Any(t => t == null)) continue;
87        var plants = Enumerable.Range(0, nParents)
88          .Select(parent => targets[parent].Select((target, source) => new {parent, target, source}).GroupBy(p => p.target))
89          .Aggregate((x, y) => x.Concat(y))
90          .ToArray();
91        if (Ordering == 0) Util.Shuffle(plants, Random);
92        else if (Ordering < 0) Array.Sort(plants, (g1, g2) => g1.Count() - g2.Count());
93        else if (Ordering > 0) Array.Sort(plants, (g1, g2) => g2.Count() - g1.Count());
94        var freq = Math.Min(Math.Abs(Frequency), plants.Length);
95        var nTotalAssignedRegions = 0;
96        var nAssignRegions = new int[nParents];
97        var length = targets[0].Length;
98        var assignedRegions = Enumerable.Repeat(false, length).ToArray();
99        var newTargets = new IntegerVector(length);
100        var newUtilizations = utilizations[0] != null ? new RealVector(length) : null;
101        if (freq == 0) { // order-based
102          foreach (var plant in plants) {
103            if (nTotalAssignedRegions >= length) break;
104            if (nAssignRegions[plant.First().parent] > Fairness*nTotalAssignedRegions/nParents) // skip overrepresented parent's plant
105              break;
106            foreach (var supplier in plant) {
107              if (nTotalAssignedRegions >= length) break;
108              if (assignedRegions[supplier.source]) continue;
109              assignedRegions[supplier.source] = true;
110              newTargets[supplier.source] = supplier.target;
111              if (newUtilizations != null)
112                newUtilizations[supplier.source] = utilizations[supplier.parent][supplier.source];
113              nTotalAssignedRegions++;
114            }
115          }
116        } else { // frequency-based
117          var nCrossoverPoints = Frequency < 0 ? Random.Next(freq) : freq;
118          var crossoverPoints = Enumerable.Range(0, plants.Length);
119          if (nCrossoverPoints != plants.Length)
120            crossoverPoints = crossoverPoints.SampleRandom(Random, nCrossoverPoints);
121          var plantsByParent = plants.GroupBy(g => g.First().parent).OrderBy(g => g.Key).Select(g => g.ToQueue()).ToArray();
122          int currentParent = 0;
123          int i = 0;
124          foreach (var maxI in crossoverPoints) {
125            for (; i < maxI; i++) {
126              if (nAssignRegions[currentParent] > Fairness*nTotalAssignedRegions/nParents) // skip overrepresented parent's plant
127              foreach (var supplier in plantsByParent[currentParent].Dequeue()) {
128                if (nTotalAssignedRegions >= length) break;
129                if (assignedRegions[supplier.source]) continue;
130                assignedRegions[supplier.source] = true;
131                newTargets[supplier.source] = supplier.target;
132                if (newUtilizations != null)
133                  newUtilizations[supplier.source] = utilizations[supplier.parent][supplier.source];
134                nTotalAssignedRegions++;
135              }
136            }
137            currentParent = (currentParent + 1)%nParents;
138          }
139        }
140        foreach (var region in assignedRegions // fill unassigned regions
141          .Select((b, i) => new {selected = b, idx = i})
142          .Where(p => !p.selected).Select(p => p.idx)) { // unassigned regions
143          int newParent;
144          if (Random.NextDouble() < Fairness) { // choose a fair parent
145            newParent = nAssignRegions.Select((parent, n) => new {parent, n}).OrderBy(p => p.n).Select(p => p.parent).First();
146          } else {
147            newParent = Random.Next(nParents);
148          }
149          // assignedRegions[region] = true;
150          newTargets[region] = targets[newParent][region];
151          if (newUtilizations != null)
152            newUtilizations[region] = utilizations[newParent][region];
153        }
154        SaveVectors(ExecutionContext.Scope, product.Value.Value, newTargets, newUtilizations);
155      }
156      return base.Apply();
157    }
158
159    private void GetVectors(IScope scope, string product, out IntegerVector targets, out RealVector utilizations) {
160      IVariable targetsVar, utilizationsVar;
161      scope.Variables.TryGetValue(LayerDescriptor.TransportTargets.NameWithPrefix(product), out targetsVar);
162      scope.Variables.TryGetValue(LayerDescriptor.Utilizations.NameWithPrefix(product), out utilizationsVar);
163      targets = null;
164      utilizations = null;
165      if (targetsVar != null) targets = targetsVar.Value as IntegerVector;
166      if (utilizationsVar != null) utilizations = utilizationsVar.Value as RealVector;
167    }
168
169    private void SaveVectors(IScope scope, string product, IntegerVector targets, RealVector utilizations) {
170      scope.Variables.Add(new Variable(LayerDescriptor.TransportTargets.NameWithPrefix(product), targets));
171      scope.Variables.Add(new Variable(LayerDescriptor.Utilizations.NameWithPrefix(product), utilizations));
172    }
173
174  }
175}
Note: See TracBrowser for help on using the repository browser.