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

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using HeuristicLab.BioBoost.Data;
using HeuristicLab.BioBoost.ProblemDescription;
using HeuristicLab.BioBoost.Utils;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Encodings.RealVectorEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.PluginInfrastructure;
using System.Linq;
using HeuristicLab.BioBoost.Representation;
using HeuristicLab.Random;
using DiscreteIntegerVectorCrossover = HeuristicLab.Encodings.IntegerVectorEncoding.DiscreteCrossover;
using DiscreteRealVectorCrossover = HeuristicLab.Encodings.RealVectorEncoding.DiscreteCrossover;

namespace HeuristicLab.BioBoost.Operators.Crossover {
  [StorableClass]
  public class PlantBasedCrossover : SingleSuccessorOperator, ICrossover, IStochasticOperator {

    #region Parameters
    public ValueLookupParameter<IntMatrix> RegionBoundsParameter {
      get { return (ValueLookupParameter<IntMatrix>)Parameters["RegionBounds"]; }
    }
    public LookupParameter<BioBoostProblemData> ProblemDataParameter {
      get { return (LookupParameter<BioBoostProblemData>)Parameters["ProblemData"]; }
    }
    public ILookupParameter<IRandom> RandomParameter { get { return (ILookupParameter<IRandom>) Parameters["Random"]; } }
    public IValueLookupParameter<IntValue> OrderingParameter { get { return (IValueLookupParameter<IntValue>) Parameters["Ordering"]; } }
    public IValueLookupParameter<IntValue> FrequencyParameter { get { return (IValueLookupParameter<IntValue>) Parameters["Frequency"]; } }
    public IValueLookupParameter<PercentValue> FairnessParameter { get { return (IValueLookupParameter<PercentValue>) Parameters["Fairness"]; } }
    #endregion

    #region Parameter Values
    public BioBoostProblemData ProblemData { get { return ProblemDataParameter.ActualValue; } }
    public IRandom Random { get { return RandomParameter.ActualValue; } }
    public int Ordering { get { return OrderingParameter.ActualValue.Value; } }
    public int Frequency { get { return FrequencyParameter.ActualValue.Value; } }
    public double Fairness { get { return FairnessParameter.ActualValue.Value; } }
    #endregion

    #region Construction & Cloning
    [StorableConstructor]
    protected PlantBasedCrossover(bool isDeserializing) : base(isDeserializing) { }
    protected PlantBasedCrossover(PlantBasedCrossover orig, Cloner cloner) : base(orig, cloner) { }

    public PlantBasedCrossover() {
      Parameters.Add(new LookupParameter<BioBoostProblemData>("ProblemData", "The data store of the detailed problem description."));
      Parameters.Add(new ValueLookupParameter<IntMatrix>("RegionBounds", "The limits of valid region ids."));
      Parameters.Add(new LookupParameter<IRandom>("Random", "A/The random value generator."));
      Parameters.Add(new ValueLookupParameter<IntValue>("Ordering", "Choose ordering 1: largest-first, -1: smallest first, 0: random", new IntValue(1)));
      Parameters.Add(new ValueLookupParameter<IntValue>("Frequency", "Number of crossover points -1: random, 0: after every plant, n: n times", new IntValue(1)));
      Parameters.Add(new ValueLookupParameter<PercentValue>("Fairness", "Amount of fairness: 0 don't bother, 1 avoid favoring one parent", new PercentValue(0)));
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new PlantBasedCrossover(this, cloner);
    }

    [StorableHook(HookType.AfterDeserialization)]
    public void AfterDeserialization() {
      if (!Parameters.ContainsKey("Ordering"))
        Parameters.Add(new ValueLookupParameter<IntValue>("Ordering", "Choose ordering 1: largest-first, -1: smallest first, 0: random", new IntValue(0)));
      if (!Parameters.ContainsKey("Frequency"))
        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)));
      if (!Parameters.ContainsKey("Fairness"))
        Parameters.Add(new ValueLookupParameter<PercentValue>("Fairness", "Amount of fairness 0: don't bother -  1: avoid favoring one parent", new PercentValue(0)));
    }
    #endregion

    public override IOperation Apply() {
      var nParents = ExecutionContext.Scope.SubScopes.Count;
      if (nParents == 0) return base.Apply();
      foreach (var product in ProblemData.TransportTargets.CheckedItems) {
        var targets = new IntegerVector[nParents];
        var utilizations = new RealVector[nParents];
        foreach (var i in Enumerable.Range(0, nParents))
          GetVectors(ExecutionContext.Scope.SubScopes[i], product.Value.Value, out targets[i], out utilizations[i]);
        if (targets.Any(t => t == null)) continue;
        var plants = Enumerable.Range(0, nParents)
          .Select(parent => targets[parent].Select((target, source) => new {parent, target, source}).GroupBy(p => p.target))
          .Aggregate((x, y) => x.Concat(y))
          .ToArray();
        if (Ordering == 0) Util.Shuffle(plants, Random);
        else if (Ordering < 0) Array.Sort(plants, (g1, g2) => g1.Count() - g2.Count());
        else if (Ordering > 0) Array.Sort(plants, (g1, g2) => g2.Count() - g1.Count());
        var freq = Math.Min(Math.Abs(Frequency), plants.Length);
        var nTotalAssignedRegions = 0;
        var nAssignRegions = new int[nParents];
        var length = targets[0].Length;
        var assignedRegions = Enumerable.Repeat(false, length).ToArray();
        var newTargets = new IntegerVector(length);
        var newUtilizations = utilizations[0] != null ? new RealVector(length) : null;
        if (freq == 0) { // order-based
          foreach (var plant in plants) {
            if (nTotalAssignedRegions >= length) break;
            if (nAssignRegions[plant.First().parent] > Fairness*nTotalAssignedRegions/nParents) // skip overrepresented parent's plant
              break;
            foreach (var supplier in plant) {
              if (nTotalAssignedRegions >= length) break;
              if (assignedRegions[supplier.source]) continue;
              assignedRegions[supplier.source] = true;
              newTargets[supplier.source] = supplier.target;
              if (newUtilizations != null)
                newUtilizations[supplier.source] = utilizations[supplier.parent][supplier.source];
              nTotalAssignedRegions++;
            }
          }
        } else { // frequency-based
          var nCrossoverPoints = Frequency < 0 ? Random.Next(freq) : freq;
          var crossoverPoints = Enumerable.Range(0, plants.Length);
          if (nCrossoverPoints != plants.Length)
            crossoverPoints = crossoverPoints.SampleRandom(Random, nCrossoverPoints);
          var plantsByParent = plants.GroupBy(g => g.First().parent).OrderBy(g => g.Key).Select(g => g.ToQueue()).ToArray();
          int currentParent = 0;
          int i = 0; 
          foreach (var maxI in crossoverPoints) {
            for (; i < maxI; i++) {
              if (nAssignRegions[currentParent] > Fairness*nTotalAssignedRegions/nParents) // skip overrepresented parent's plant
              foreach (var supplier in plantsByParent[currentParent].Dequeue()) {
                if (nTotalAssignedRegions >= length) break;
                if (assignedRegions[supplier.source]) continue;
                assignedRegions[supplier.source] = true;
                newTargets[supplier.source] = supplier.target;
                if (newUtilizations != null)
                  newUtilizations[supplier.source] = utilizations[supplier.parent][supplier.source];
                nTotalAssignedRegions++;
              }
            }
            currentParent = (currentParent + 1)%nParents;
          }
        }
        foreach (var region in assignedRegions // fill unassigned regions
          .Select((b, i) => new {selected = b, idx = i})
          .Where(p => !p.selected).Select(p => p.idx)) { // unassigned regions
          int newParent;
          if (Random.NextDouble() < Fairness) { // choose a fair parent
            newParent = nAssignRegions.Select((parent, n) => new {parent, n}).OrderBy(p => p.n).Select(p => p.parent).First();
          } else {
            newParent = Random.Next(nParents);
          }
          // assignedRegions[region] = true;
          newTargets[region] = targets[newParent][region];
          if (newUtilizations != null)
            newUtilizations[region] = utilizations[newParent][region];
        }
        SaveVectors(ExecutionContext.Scope, product.Value.Value, newTargets, newUtilizations);
      }
      return base.Apply();
    }

    private void GetVectors(IScope scope, string product, out IntegerVector targets, out RealVector utilizations) {
      IVariable targetsVar, utilizationsVar;
      scope.Variables.TryGetValue(LayerDescriptor.TransportTargets.NameWithPrefix(product), out targetsVar);
      scope.Variables.TryGetValue(LayerDescriptor.Utilizations.NameWithPrefix(product), out utilizationsVar);
      targets = null;
      utilizations = null;
      if (targetsVar != null) targets = targetsVar.Value as IntegerVector;
      if (utilizationsVar != null) utilizations = utilizationsVar.Value as RealVector;
    }

    private void SaveVectors(IScope scope, string product, IntegerVector targets, RealVector utilizations) {
      scope.Variables.Add(new Variable(LayerDescriptor.TransportTargets.NameWithPrefix(product), targets));
      scope.Variables.Add(new Variable(LayerDescriptor.Utilizations.NameWithPrefix(product), utilizations));
    }

  }
}