1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  * and the BEACON Center for the Study of Evolution in Action.


5  *


6  * This file is part of HeuristicLab.


7  *


8  * HeuristicLab is free software: you can redistribute it and/or modify


9  * it under the terms of the GNU General Public License as published by


10  * the Free Software Foundation, either version 3 of the License, or


11  * (at your option) any later version.


12  *


13  * HeuristicLab is distributed in the hope that it will be useful,


14  * but WITHOUT ANY WARRANTY; without even the implied warranty of


15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


16  * GNU General Public License for more details.


17  *


18  * You should have received a copy of the GNU General Public License


19  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


20  */


21  #endregion


22 


23  using System;


24  using System.Linq;


25  using HeuristicLab.Common;


26  using HeuristicLab.Encodings.RealVectorEncoding;


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


28  using HeuristicLab.Random;


29 


30  namespace HeuristicLab.Algorithms.MOCMAEvolutionStrategy {


31  [StorableClass]


32  public class Individual : IDeepCloneable {


33 


34  public enum OffspringSuccess {


35  Success, NoSuccess


36  }


37 


38  #region Properties


39  [Storable]


40  private MOCMAEvolutionStrategy strategy;


41 


42  //Chromosome


43  [Storable]


44  public RealVector Mean { get; private set; }


45  [Storable]


46  private double sigma;//stepsize


47  [Storable]


48  private RealVector evolutionPath; // pc


49  [Storable]


50  private RealVector lastStep;


51  [Storable]


52  private RealVector lastZ;


53  [Storable]


54  private double[,] lowerCholesky;


55 


56 


57  //Phenotype


58  [Storable]


59  public double[] Fitness { get; set; }


60  [Storable]


61  public double[] PenalizedFitness { get; set; }


62  [Storable]


63  public bool Selected { get; set; }


64  [Storable]


65  public double Rank { get; set; }


66  [Storable]


67  public double SuccessProbability { get; set; }


68  #endregion


69 


70  #region Constructors and Cloning


71  [StorableConstructor]


72  protected Individual(bool deserializing) { }


73 


74  /// <summary>


75  ///


76  /// </summary>


77  /// <param name="mean">has to be 0vector with correct lenght</param>


78  /// <param name="pSucc">has to be ptargetsucc</param>


79  /// <param name="sigma">initialSigma</param>


80  /// <param name="pc">has to be 0vector with correct lenght</param>


81  /// <param name="c">has to be a symmetric positive definit Covariance matrix</param>


82  public Individual(RealVector mean, double pSucc, double sigma, RealVector pc, double[,] c, MOCMAEvolutionStrategy strategy) {


83  Mean = mean;


84  lastStep = new RealVector(mean.Length);


85  SuccessProbability = pSucc;


86  this.sigma = sigma;


87  evolutionPath = pc;


88  CholeskyDecomposition(c);


89  Selected = true;


90  this.strategy = strategy;


91  }


92 


93  public Individual(Individual other) {


94  SuccessProbability = other.SuccessProbability;


95  sigma = other.sigma;


96  evolutionPath = (RealVector)other.evolutionPath.Clone();


97  Mean = (RealVector)other.Mean.Clone();


98  lowerCholesky = (double[,])other.lowerCholesky.Clone();


99  Selected = true;


100  strategy = other.strategy;


101  }


102 


103  public Individual(Individual other, Cloner cloner) {


104  strategy = cloner.Clone(other.strategy);


105  Mean = cloner.Clone(other.Mean);


106  sigma = other.sigma;


107  evolutionPath = cloner.Clone(other.evolutionPath);


108  lastStep = cloner.Clone(other.evolutionPath);


109  lastZ = cloner.Clone(other.lastZ);


110  lowerCholesky = other.lowerCholesky != null ? other.lowerCholesky.Clone() as double[,] : null;


111  Fitness = other.Fitness != null ? other.Fitness.Select(x => x).ToArray() : null;


112  PenalizedFitness = other.PenalizedFitness != null ? other.PenalizedFitness.Select(x => x).ToArray() : null;


113  Selected = other.Selected;


114  Rank = other.Rank;


115  SuccessProbability = other.SuccessProbability;


116  }


117 


118  public object Clone() {


119  return new Cloner().Clone(this);


120  }


121 


122  public IDeepCloneable Clone(Cloner cloner) {


123  return new Individual(this, cloner);


124  }


125  #endregion


126 


127  public void Mutate(NormalDistributedRandom gauss) {


128  //sampling a random z from N(0,I) where I is the Identity matrix;


129  lastZ = new RealVector(Mean.Length);


130  var n = lastZ.Length;


131  for (var i = 0; i < n; i++) lastZ[i] = gauss.NextDouble();


132  //Matrixmultiplication: lastStep = lowerCholesky * lastZ;


133  lastStep = new RealVector(Mean.Length);


134  for (var i = 0; i < n; i++) {


135  double sum = 0;


136  for (var j = 0; j <= i; j++) sum += lowerCholesky[i, j] * lastZ[j];


137  lastStep[i] = sum;


138  }


139  //add the step to x weighted by stepsize;


140  for (var i = 0; i < Mean.Length; i++) Mean[i] += sigma * lastStep[i];


141  }


142 


143  public void UpdateAsParent(bool offspringSuccessful) {


144  SuccessProbability = (1  strategy.StepSizeLearningRate) * SuccessProbability + strategy.StepSizeLearningRate * (offspringSuccessful ? 1 : 0);


145  sigma *= Math.Exp(1 / strategy.StepSizeDampeningFactor * (SuccessProbability  strategy.TargetSuccessProbability) / (1  strategy.TargetSuccessProbability));


146  if (!offspringSuccessful) return;


147  if (SuccessProbability < strategy.SuccessThreshold && lastZ != null) {


148  var stepNormSqr = lastZ.Sum(d => d * d);


149  var rate = strategy.CovarianceMatrixUnlearningRate;


150  if (stepNormSqr > 1 && 1 < strategy.CovarianceMatrixUnlearningRate * (2 * stepNormSqr  1)) rate = 1 / (2 * stepNormSqr  1);


151  CholeskyUpdate(lastStep, 1 + rate, rate);


152 


153  } else RoundUpdate();


154 


155  }


156 


157  public void UpdateAsOffspring() {


158  SuccessProbability = (1  strategy.StepSizeLearningRate) * SuccessProbability + strategy.StepSizeLearningRate;


159  sigma *= Math.Exp(1 / strategy.StepSizeDampeningFactor * (SuccessProbability  strategy.TargetSuccessProbability) / (1  strategy.TargetSuccessProbability));


160  var evolutionpathUpdateWeight = strategy.EvolutionPathLearningRate * (2.0  strategy.EvolutionPathLearningRate);


161  if (SuccessProbability < strategy.SuccessThreshold) {


162  UpdateEvolutionPath(1  strategy.EvolutionPathLearningRate, evolutionpathUpdateWeight);


163  CholeskyUpdate(evolutionPath, 1  strategy.CovarianceMatrixLearningRate, strategy.CovarianceMatrixLearningRate);


164  } else {


165  RoundUpdate();


166  }


167  }


168 


169  public void UpdateEvolutionPath(double learningRate, double updateWeight) {


170  updateWeight = Math.Sqrt(updateWeight);


171  for (var i = 0; i < evolutionPath.Length; i++) {


172  evolutionPath[i] *= learningRate;


173  evolutionPath[i] += updateWeight * lastStep[i];


174  }


175  }


176 


177  #region helpers


178  private void CholeskyDecomposition(double[,] c) {


179  if (!alglib.spdmatrixcholesky(ref c, c.GetLength(0), false))


180  throw new ArgumentException("Covariancematrix is not symmetric positiv definit");


181  lowerCholesky = (double[,])c.Clone();


182  }


183 


184  private void CholeskyUpdate(RealVector v, double alpha, double beta) {


185  var n = v.Length;


186  var temp = new double[n];


187  for (var i = 0; i < n; i++) temp[i] = v[i];


188  double betaPrime = 1;


189  var a = Math.Sqrt(alpha);


190  for (var j = 0; j < n; j++) {


191  var ljj = a * lowerCholesky[j, j];


192  var dj = ljj * ljj;


193  var wj = temp[j];


194  var swj2 = beta * wj * wj;


195  var gamma = dj * betaPrime + swj2;


196  var x1 = dj + swj2 / betaPrime;


197  if (x1 < 0.0) return;//throw new ArgumentException("Update makes Covariancematrix indefinite");//TODO check wether ignoring this update is valid


198  var nLjj = Math.Sqrt(x1);


199  lowerCholesky[j, j] = nLjj;


200  betaPrime += swj2 / dj;


201  if (j + 1 >= n) continue;


202  for (var i = j + 1; i < n; i++) lowerCholesky[i, j] *= a;


203  for (var i = j + 1; i < n; i++) temp[i] = wj / ljj * lowerCholesky[i, j];


204  if (gamma.IsAlmost(0)) continue;


205  for (var i = j + 1; i < n; i++) lowerCholesky[i, j] *= nLjj / ljj;


206  for (var i = j + 1; i < n; i++) lowerCholesky[i, j] += nLjj * beta * wj / gamma * temp[i];


207 


208  }


209 


210  }


211 


212  private void RoundUpdate() {


213  var evolutionPathUpdateWeight = strategy.EvolutionPathLearningRate * (2.0  strategy.EvolutionPathLearningRate);


214  UpdateEvolutionPath(1  strategy.EvolutionPathLearningRate, 0);


215  CholeskyUpdate(evolutionPath, 1  strategy.CovarianceMatrixLearningRate + evolutionPathUpdateWeight, strategy.CovarianceMatrixLearningRate);


216  }


217  #endregion


218 


219  }


220 


221  }

