1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022013 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 


22  using System;


23  using System.Linq;


24  using HeuristicLab.Analysis;


25  using HeuristicLab.Collections;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Data;


29  using HeuristicLab.Optimization;


30  using HeuristicLab.Parameters;


31  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


32 


33  namespace HeuristicLab.Problems.VehicleRouting.Encodings.General {


34  [Item("BiasedMultiVRPSolutionCrossover", "Randomly selects and applies one of its crossovers every time it is called based on the success progress.")]


35  [StorableClass]


36  public class BiasedMultiVRPSolutionCrossover : MultiVRPSolutionCrossover {


37  public ValueLookupParameter<DoubleArray> ActualProbabilitiesParameter {


38  get { return (ValueLookupParameter<DoubleArray>)Parameters["ActualProbabilities"]; }


39  }


40 


41  public ValueLookupParameter<StringValue> SuccessProgressAnalyisis {


42  get { return (ValueLookupParameter<StringValue>)Parameters["SuccessProgressAnalysis"]; }


43  }


44 


45  public ValueLookupParameter<DoubleValue> Factor {


46  get { return (ValueLookupParameter<DoubleValue>)Parameters["Factor"]; }


47  }


48 


49  public ValueParameter<DoubleValue> LowerBoundParameter {


50  get { return (ValueParameter<DoubleValue>)Parameters["LowerBound"]; }


51  }


52 


53  public ValueParameter<IntValue> DepthParameter {


54  get { return (ValueParameter<IntValue>)Parameters["Depth"]; }


55  }


56 


57  [StorableConstructor]


58  protected BiasedMultiVRPSolutionCrossover(bool deserializing) : base(deserializing) { }


59  protected BiasedMultiVRPSolutionCrossover(BiasedMultiVRPSolutionCrossover original, Cloner cloner) : base(original, cloner) { }


60  public BiasedMultiVRPSolutionCrossover()


61  : base() {


62  Parameters.Add(new ValueLookupParameter<DoubleArray>("ActualProbabilities", "The array of relative probabilities for each operator."));


63  Parameters.Add(new ValueLookupParameter<StringValue>("SuccessProgressAnalysis", "The success progress analyisis to be considered",


64  new StringValue("ExecutedCrossoverOperator")));


65 


66  Parameters.Add(new ValueLookupParameter<DoubleValue>("Factor", "The factor with which the probabilities should be updated", new DoubleValue(0.2)));


67  Parameters.Add(new ValueParameter<DoubleValue>("LowerBound", "The depth of the individuals in the scope tree.", new DoubleValue(0.01)));


68  Parameters.Add(new ValueParameter<IntValue>("Depth", "The depth of the individuals in the scope tree.", new IntValue(1)));


69 


70  SelectedOperatorParameter.ActualName = "SelectedCrossoverOperator";


71  }


72 


73  public override IDeepCloneable Clone(Cloner cloner) {


74  return new BiasedMultiVRPSolutionCrossover(this, cloner);


75  }


76 


77  public override void InitializeState() {


78  base.InitializeState();


79 


80  ActualProbabilitiesParameter.Value = null;


81  }


82 


83  public override IOperation InstrumentedApply() {


84  IOperator successor = null;


85 


86  if (ActualProbabilitiesParameter.ActualValue == null) {


87  ActualProbabilitiesParameter.Value = ProbabilitiesParameter.ActualValue.Clone() as DoubleArray;


88  } else {


89  String key = "SuccessfulOffspringAnalyzer Results";


90 


91  ResultCollection results = null;


92  IScope scope = ExecutionContext.Parent.Scope;


93  int depth = 1;


94  while (scope != null && depth < DepthParameter.Value.Value) {


95  scope = scope.Parent;


96  depth++;


97  }


98  if (scope != null)


99  results = scope.Variables["Results"].Value as ResultCollection;


100 


101  if (results != null && results.ContainsKey(key)) {


102  ResultCollection successProgressAnalysisResult = results[key].Value as ResultCollection;


103  key = SuccessProgressAnalyisis.Value.Value;


104 


105  if (successProgressAnalysisResult.ContainsKey(key)) {


106  DataTable successProgressAnalysis = successProgressAnalysisResult[key].Value as DataTable;


107 


108  for (int i = 0; i < Operators.Count; i++) {


109  IOperator current = Operators[i];


110 


111  if (successProgressAnalysis.Rows.ContainsKey(current.Name)) {


112  DataRow row = successProgressAnalysis.Rows[current.Name];


113 


114  double sum = 0.0;


115  ObservableList<double> usages = row.Values;


116 


117  sum += (double)usages.Last();


118 


119  ActualProbabilitiesParameter.ActualValue[i] += (sum / ActualProbabilitiesParameter.ActualValue[i]) * Factor.Value.Value;


120  }


121  }


122  }


123  }


124 


125  //normalize


126  double max = ActualProbabilitiesParameter.ActualValue.Max();


127  for (int i = 0; i < ActualProbabilitiesParameter.ActualValue.Length; i++) {


128  ActualProbabilitiesParameter.ActualValue[i] /= max;


129  ActualProbabilitiesParameter.ActualValue[i] =


130  Math.Max(LowerBoundParameter.Value.Value,


131  ActualProbabilitiesParameter.ActualValue[i]);


132  }


133  }


134 


135  //////////////// code has to be duplicated since ActualProbabilitiesParameter.ActualValue are updated and used for operator selection


136  IRandom random = RandomParameter.ActualValue;


137  DoubleArray probabilities = ActualProbabilitiesParameter.ActualValue;


138  if (probabilities.Length != Operators.Count) {


139  throw new InvalidOperationException(Name + ": The list of probabilities has to match the number of operators");


140  }


141  var checkedOperators = Operators.CheckedItems;


142  if (checkedOperators.Count() > 0) {


143  // select a random operator from the checked operators


144  double sum = (from indexedItem in checkedOperators select probabilities[indexedItem.Index]).Sum();


145  if (sum == 0) throw new InvalidOperationException(Name + ": All selected operators have zero probability.");


146  double r = random.NextDouble() * sum;


147  sum = 0;


148  foreach (var indexedItem in checkedOperators) {


149  sum += probabilities[indexedItem.Index];


150  if (sum > r) {


151  successor = indexedItem.Value;


152  break;


153  }


154  }


155  }


156 


157  IOperation successorOp = null;


158  if (Successor != null)


159  successorOp = ExecutionContext.CreateOperation(Successor);


160  OperationCollection next = new OperationCollection(successorOp);


161  if (successor != null) {


162  SelectedOperatorParameter.ActualValue = new StringValue(successor.Name);


163 


164  if (CreateChildOperation)


165  next.Insert(0, ExecutionContext.CreateChildOperation(successor));


166  else next.Insert(0, ExecutionContext.CreateOperation(successor));


167  } else {


168  SelectedOperatorParameter.ActualValue = new StringValue("");


169  }


170 


171  return next;


172  }


173  }


174  }

