Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.NK/3.3/NKLandscape.cs @ 17943

Last change on this file since 17943 was 17181, checked in by swagner, 5 years ago

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