1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 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 HEAL.Attic;


28  using HeuristicLab.Random;


29 


30  namespace HeuristicLab.Algorithms.MOCMAEvolutionStrategy {


31  [StorableType("8D5AF32884A049249909A113CDCFC117")]


32  public class Individual : IDeepCloneable {


33 


34  #region Properties


35  [Storable]


36  private MOCMAEvolutionStrategy strategy;


37 


38  //Chromosome


39  [Storable]


40  public RealVector Mean { get; private set; }


41  [Storable]


42  private double sigma;//stepsize


43  [Storable]


44  private RealVector evolutionPath; // pc


45  [Storable]


46  private RealVector lastStep;


47  [Storable]


48  private RealVector lastZ;


49  [Storable]


50  private double[,] lowerCholesky;


51 


52  //Phenotype


53  [Storable]


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


55  [Storable]


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


57  [Storable]


58  public bool Selected { get; set; }


59  [Storable]


60  public double SuccessProbability { get; set; }


61  #endregion


62 


63  #region Constructors and Cloning


64  [StorableConstructor]


65  protected Individual(StorableConstructorFlag _) { }


66 


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


68  Mean = mean;


69  lastStep = new RealVector(mean.Length);


70  SuccessProbability = pSucc;


71  this.sigma = sigma;


72  evolutionPath = pc;


73  CholeskyDecomposition(c);


74  Selected = true;


75  this.strategy = strategy;


76  }


77 


78  public Individual(Individual other) {


79  SuccessProbability = other.SuccessProbability;


80  sigma = other.sigma;


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


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


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


84  Selected = true;


85  strategy = other.strategy;


86  }


87 


88  public Individual(Individual other, Cloner cloner) {


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


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


91  sigma = other.sigma;


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


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


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


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


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


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


98  Selected = other.Selected;


99  SuccessProbability = other.SuccessProbability;


100  }


101 


102  public object Clone() {


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


104  }


105 


106  public IDeepCloneable Clone(Cloner cloner) {


107  return new Individual(this, cloner);


108  }


109  #endregion


110 


111  public void Mutate(NormalDistributedRandom gauss) {


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


113  lastZ = new RealVector(Mean.Length);


114  var n = lastZ.Length;


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


116  //Matrixmultiplication: lastStep = lowerCholesky * lastZ;


117  lastStep = new RealVector(Mean.Length);


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


119  double sum = 0;


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


121  lastStep[i] = sum;


122  }


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


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


125  }


126 


127  public void UpdateAsParent(bool offspringSuccessful) {


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


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


130  if (!offspringSuccessful) return;


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


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


133  var rate = strategy.CovarianceMatrixUnlearningRate;


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


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


136  } else RoundUpdate();


137  }


138 


139  public void UpdateAsOffspring() {


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


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


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


143  if (SuccessProbability < strategy.SuccessThreshold) {


144  UpdateEvolutionPath(1  strategy.EvolutionPathLearningRate, evolutionpathUpdateWeight);


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


146  } else RoundUpdate();


147  }


148 


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


150  updateWeight = Math.Sqrt(updateWeight);


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


152  evolutionPath[i] *= learningRate;


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


154  }


155  }


156 


157  #region Helpers


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


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


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


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


162  }


163 


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


165  var n = v.Length;


166  var temp = new double[n];


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


168  double betaPrime = 1;


169  var a = Math.Sqrt(alpha);


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


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


172  var dj = ljj * ljj;


173  var wj = temp[j];


174  var swj2 = beta * wj * wj;


175  var gamma = dj * betaPrime + swj2;


176  var x1 = dj + swj2 / betaPrime;


177  if (x1 < 0.0) return;


178  var nLjj = Math.Sqrt(x1);


179  lowerCholesky[j, j] = nLjj;


180  betaPrime += swj2 / dj;


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


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


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


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


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


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


187  }


188  }


189 


190  private void RoundUpdate() {


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


192  UpdateEvolutionPath(1  strategy.EvolutionPathLearningRate, 0);


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


194  }


195  #endregion


196  }


197  }

