source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.NK/3.3/NKLandscape.cs @ 17270

Last change on this file since 17270 was 17270, checked in by abeham, 3 years ago

#2521: worked on removing virtual from Maximization for single-objective problems

File size: 13.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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
22using System;
23using System.Linq;
24using System.Security.Cryptography;
25using HEAL.Attic;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.BinaryVectorEncoding;
30using HeuristicLab.Parameters;
31using HeuristicLab.PluginInfrastructure;
32using HeuristicLab.Random;
33
34namespace HeuristicLab.Problems.NK {
35  [Item("NK Landscape", "Represents an NK landscape optimization problem.")]
36  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 215)]
37  [StorableType("04294537-87F2-4A9F-BC14-7D4CA700F326")]
38  public sealed class NKLandscape : BinaryVectorProblem {
39
40    #region Parameters
41    public IValueParameter<BoolMatrix> GeneInteractionsParameter {
42      get { return (IValueParameter<BoolMatrix>)Parameters["GeneInteractions"]; }
43    }
44    public IValueParameter<IntValue> SeedParameter {
45      get { return (IValueParameter<IntValue>)Parameters["ProblemSeed"]; }
46    }
47    public IValueParameter<IntValue> InteractionSeedParameter {
48      get { return (IValueParameter<IntValue>)Parameters["InteractionSeed"]; }
49    }
50    public IValueParameter<IntValue> NrOfInteractionsParameter {
51      get { return (IValueParameter<IntValue>)Parameters["NrOfInteractions"]; }
52    }
53    public IValueParameter<IntValue> NrOfFitnessComponentsParameter {
54      get { return (IValueParameter<IntValue>)Parameters["NrOfFitnessComponents"]; }
55    }
56    public IValueParameter<IntValue> QParameter {
57      get { return (IValueParameter<IntValue>)Parameters["Q"]; }
58    }
59    public IValueParameter<DoubleValue> PParameter {
60      get { return (IValueParameter<DoubleValue>)Parameters["P"]; }
61    }
62    public IValueParameter<DoubleArray> WeightsParameter {
63      get { return (IValueParameter<DoubleArray>)Parameters["Weights"]; }
64    }
65    public IConstrainedValueParameter<IInteractionInitializer> InteractionInitializerParameter {
66      get { return (IConstrainedValueParameter<IInteractionInitializer>)Parameters["InteractionInitializer"]; }
67    }
68    public IConstrainedValueParameter<IWeightsInitializer> WeightsInitializerParameter {
69      get { return (IConstrainedValueParameter<IWeightsInitializer>)Parameters["WeightsInitializer"]; }
70    }
71    #endregion
72
73    #region Properties
74    public IInteractionInitializer InteractionInitializer {
75      get { return InteractionInitializerParameter.Value; }
76    }
77    public BoolMatrix GeneInteractions {
78      get { return GeneInteractionsParameter.Value; }
79    }
80    public DoubleArray Weights {
81      get { return WeightsParameter.Value; }
82    }
83    public IntValue InteractionSeed {
84      get { return InteractionSeedParameter.Value; }
85    }
86    public IntValue NrOfFitnessComponents {
87      get { return NrOfFitnessComponentsParameter.Value; }
88    }
89    public IntValue NrOfInteractions {
90      get { return NrOfInteractionsParameter.Value; }
91    }
92    public IWeightsInitializer WeightsInitializer {
93      get { return WeightsInitializerParameter.Value; }
94    }
95    public int Q {
96      get { return QParameter.Value.Value; }
97    }
98    public double P {
99      get { return PParameter.Value.Value; }
100    }
101    public IntValue Seed {
102      get { return SeedParameter.Value; }
103    }
104    #endregion
105
106    [Storable]
107    private MersenneTwister random;
108
109    [ThreadStatic]
110    private static HashAlgorithm hashAlgorithm;
111
112    [ThreadStatic]
113    private static HashAlgorithm hashAlgorithmP;
114
115    private static HashAlgorithm HashAlgorithm {
116      get {
117        if (hashAlgorithm == null) {
118          hashAlgorithm = HashAlgorithm.Create("MD5");
119        }
120        return hashAlgorithm;
121      }
122    }
123
124    private static HashAlgorithm HashAlgorithmP {
125      get {
126        if (hashAlgorithmP == null) {
127          hashAlgorithmP = HashAlgorithm.Create("SHA1");
128        }
129        return hashAlgorithmP;
130      }
131    }
132
133    [StorableConstructor]
134    private NKLandscape(StorableConstructorFlag _) : base(_) { }
135    private NKLandscape(NKLandscape original, Cloner cloner)
136      : base(original, cloner) {
137      random = (MersenneTwister)original.random.Clone(cloner);
138      RegisterEventHandlers();
139    }
140    public NKLandscape()
141      : base() {
142      Maximization = false;
143      random = new MersenneTwister();
144
145      Parameters.Add(new ValueParameter<BoolMatrix>("GeneInteractions", "Every column gives the participating genes for each fitness component."));
146      Parameters.Add(new ValueParameter<IntValue>("ProblemSeed", "The seed used for the random number generator.", new IntValue(0)));
147      random.Reset(Seed.Value);
148
149      Parameters.Add(new ValueParameter<IntValue>("InteractionSeed", "The seed used for the hash function to generate interaction tables.", new IntValue(random.Next())));
150      Parameters.Add(new ValueParameter<IntValue>("NrOfFitnessComponents", "Number of fitness component functions. (nr of columns in the interaction column)", new IntValue(10)));
151      Parameters.Add(new ValueParameter<IntValue>("NrOfInteractions", "Number of genes interacting with each other. (nr of True values per column in the interaction matrix)", new IntValue(3)));
152      Parameters.Add(new ValueParameter<IntValue>("Q", "Number of allowed fitness values in the (virutal) random table, or zero.", new IntValue(0)));
153      Parameters.Add(new ValueParameter<DoubleValue>("P", "Probability of any entry in the (virtual) random table being zero.", new DoubleValue(0)));
154      Parameters.Add(new ValueParameter<DoubleArray>("Weights", "The weights for the component functions. If shorted, will be repeated.", new DoubleArray(new[] { 1.0 })));
155      Parameters.Add(new ConstrainedValueParameter<IInteractionInitializer>("InteractionInitializer", "Initialize interactions within the component functions."));
156      Parameters.Add(new ConstrainedValueParameter<IWeightsInitializer>("WeightsInitializer", "Operator to initialize the weights distribution."));
157
158      //allow just the standard NK[P,Q] formulations at the moment
159      WeightsParameter.Hidden = true;
160      InteractionInitializerParameter.Hidden = true;
161      WeightsInitializerParameter.Hidden = true;
162      EncodingParameter.Hidden = true;
163
164      InitializeInteractionInitializerParameter();
165      InitializeWeightsInitializerParameter();
166
167      InitializeOperators();
168      InitializeInteractions();
169      RegisterEventHandlers();
170    }
171
172    private void InitializeInteractionInitializerParameter() {
173      foreach (var initializer in ApplicationManager.Manager.GetInstances<IInteractionInitializer>())
174        InteractionInitializerParameter.ValidValues.Add(initializer);
175      InteractionInitializerParameter.Value = InteractionInitializerParameter.ValidValues.First(v => v is RandomInteractionsInitializer);
176    }
177
178    private void InitializeWeightsInitializerParameter() {
179      foreach (var initializer in ApplicationManager.Manager.GetInstances<IWeightsInitializer>())
180        WeightsInitializerParameter.ValidValues.Add(initializer);
181      WeightsInitializerParameter.Value = WeightsInitializerParameter.ValidValues.First(v => v is EqualWeightsInitializer);
182    }
183
184    public override IDeepCloneable Clone(Cloner cloner) {
185      return new NKLandscape(this, cloner);
186    }
187
188    [StorableHook(HookType.AfterDeserialization)]
189    private void AfterDeserialization() {
190      RegisterEventHandlers();
191    }
192
193    private void RegisterEventHandlers() {
194      NrOfInteractionsParameter.ValueChanged += InteractionParameter_ValueChanged;
195      NrOfInteractionsParameter.Value.ValueChanged += InteractionParameter_ValueChanged;
196      NrOfFitnessComponentsParameter.ValueChanged += InteractionParameter_ValueChanged;
197      NrOfFitnessComponentsParameter.Value.ValueChanged += InteractionParameter_ValueChanged;
198      InteractionInitializerParameter.ValueChanged += InteractionParameter_ValueChanged;
199      WeightsInitializerParameter.ValueChanged += WeightsInitializerParameter_ValueChanged;
200      SeedParameter.ValueChanged += SeedParameter_ValueChanged;
201      SeedParameter.Value.ValueChanged += SeedParameter_ValueChanged;
202
203      RegisterInteractionInitializerParameterEvents();
204      RegisterWeightsParameterEvents();
205    }
206
207    private void RegisterWeightsParameterEvents() {
208      foreach (var vv in WeightsInitializerParameter.ValidValues) {
209        foreach (var p in vv.Parameters) {
210          if (p.ActualValue != null && p.ActualValue is IStringConvertibleValue) {
211            var v = (IStringConvertibleValue)p.ActualValue;
212            v.ValueChanged += WeightsInitializerParameter_ValueChanged;
213          }
214        }
215      }
216    }
217
218    private void RegisterInteractionInitializerParameterEvents() {
219      foreach (var vv in InteractionInitializerParameter.ValidValues) {
220        foreach (var p in vv.Parameters) {
221          if (p.ActualValue != null && p.ActualValue is IStringConvertibleValue) {
222            var v = (IStringConvertibleValue)p.ActualValue;
223            v.ValueChanged += InteractionParameter_ValueChanged;
224          } else if (p.ActualValue != null && p is IConstrainedValueParameter<IBinaryVectorComparer>) {
225            ((IConstrainedValueParameter<IBinaryVectorComparer>)p).ValueChanged +=
226              InteractionParameter_ValueChanged;
227          }
228        }
229      }
230    }
231
232    protected override void LengthParameter_ValueChanged(object sender, EventArgs e) {
233      NrOfFitnessComponentsParameter.Value = new IntValue(Length);
234    }
235
236    private void SeedParameter_ValueChanged(object sender, EventArgs e) {
237      random.Reset(Seed.Value);
238      InteractionSeed.Value = random.Next();
239      InitializeInteractions();
240    }
241
242    private void WeightsInitializerParameter_ValueChanged(object sender, EventArgs e) {
243      InitializeWeights();
244    }
245
246    private void InteractionParameter_ValueChanged(object sender, EventArgs e) {
247      InitializeInteractions();
248    }
249
250    private void InitializeOperators() {
251      NKBitFlipMoveEvaluator nkEvaluator = new NKBitFlipMoveEvaluator();
252      Encoding.ConfigureOperator(nkEvaluator);
253      Operators.Add(nkEvaluator);
254    }
255
256    private void InitializeInteractions() {
257      if (InteractionInitializer != null)
258        GeneInteractionsParameter.Value = InteractionInitializer.InitializeInterations(
259          Length,
260          NrOfFitnessComponents.Value,
261          NrOfInteractions.Value, random);
262    }
263
264    private void InitializeWeights() {
265      if (WeightsInitializerParameter.Value != null)
266        WeightsParameter.Value = new DoubleArray(
267          WeightsInitializer.GetWeights(NrOfFitnessComponents.Value)
268          .ToArray());
269    }
270
271    #region Evaluation function
272    private static long Hash(long x, HashAlgorithm hashAlg) {
273      return BitConverter.ToInt64(hashAlg.ComputeHash(BitConverter.GetBytes(x), 0, 8), 0);
274    }
275
276    public static double F_i(long x, long i, long g_i, long seed, int q, double p) {
277      var hash = new Func<long, long>(y => Hash(y, HashAlgorithm));
278      var fi = Math.Abs((double)hash((x & g_i) ^ hash(g_i ^ hash(i ^ seed)))) / long.MaxValue;
279      if (q > 0) { fi = Math.Round(fi * q) / q; }
280      if (p > 0) {
281        hash = y => Hash(y, HashAlgorithmP);
282        var r = Math.Abs((double)hash((x & g_i) ^ hash(g_i ^ hash(i ^ seed)))) / long.MaxValue;
283        fi = (r <= p) ? 0 : fi;
284      }
285      return fi;
286    }
287
288    private static double F(long x, long[] g, double[] w, long seed, ref double[] f_i, int q, double p) {
289      double value = 0;
290      for (int i = 0; i < g.Length; i++) {
291        f_i[i] = F_i(x, i, g[i], seed, q, p);
292        value += w[i % w.Length] * f_i[i];
293      }
294      return value;
295    }
296
297    public static long Encode(BinaryVector v) {
298      long x = 0;
299      for (int i = 0; i < 64 && i < v.Length; i++) {
300        x |= (v[i] ? (long)1 : (long)0) << i;
301      }
302      return x;
303    }
304
305    public static long[] Encode(BoolMatrix m) {
306      long[] x = new long[m.Columns];
307      for (int c = 0; c < m.Columns; c++) {
308        x[c] = 0;
309        for (int r = 0; r < 64 && r < m.Rows; r++) {
310          x[c] |= (m[r, c] ? (long)1 : (long)0) << r;
311        }
312      }
313      return x;
314    }
315
316    public static double[] Normalize(DoubleArray weights) {
317      double sum = 0;
318      double[] w = new double[weights.Length];
319      foreach (var v in weights) {
320        sum += Math.Abs(v);
321      }
322      for (int i = 0; i < weights.Length; i++) {
323        w[i] = Math.Abs(weights[i]) / sum;
324      }
325      return w;
326    }
327
328    public static double Evaluate(BinaryVector vector, BoolMatrix interactions, DoubleArray weights, int seed, out double[] f_i, int q, double p) {
329      long x = Encode(vector);
330      long[] g = Encode(interactions);
331      double[] w = Normalize(weights);
332      f_i = new double[interactions.Columns];
333      return F(x, g, w, (long)seed, ref f_i, q, p);
334    }
335
336    public override double Evaluate(BinaryVector vector, IRandom random) {
337      double[] f_i; //useful for debugging
338      double quality = Evaluate(vector, GeneInteractions, Weights, InteractionSeed.Value, out f_i, Q, P);
339      return quality;
340    }
341    #endregion
342  }
343}
Note: See TracBrowser for help on using the repository browser.