1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2016 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 0-vector 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 0-vector 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 | }
|
---|