Free cookie consent management tool by TermsFeed Policy Generator

source: branches/FitnessLandscapeAnalysis/HeuristicLab.Problems.NK/NKLandscape.cs @ 12573

Last change on this file since 12573 was 12573, checked in by ascheibe, 10 years ago

#2306 hopefully fixed random number generation problem

File size: 11.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.PluginInfrastructure;
32using HeuristicLab.Problems.Binary;
33using HeuristicLab.Problems.NK.WeightInitializers;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Problems.NK {
37
38  [Item("NK Landscape", "Represents an NK landscape optimization problem.")]
39  [Creatable("Problems")]
40  [StorableClass]
41  public sealed class NKLandscape : BinaryProblem {
42    public override bool Maximization {
43      get { return false; }
44    }
45
46    #region Parameters
47    public IValueParameter<BoolMatrix> GeneInteractionsParameter {
48      get { return (IValueParameter<BoolMatrix>)Parameters["GeneInteractions"]; }
49    }
50    public IValueParameter<IntValue> SeedParameter {
51      get { return (IValueParameter<IntValue>)Parameters["Seed"]; }
52    }
53    public IValueParameter<IntValue> InteractionSeedParameter {
54      get { return (IValueParameter<IntValue>)Parameters["InteractionSeed"]; }
55    }
56    public IValueParameter<IntValue> NrOfInteractionsParameter {
57      get { return (IValueParameter<IntValue>)Parameters["NrOfInteractions"]; }
58    }
59    public IValueParameter<IntValue> NrOfFitnessComponentsParameter {
60      get { return (IValueParameter<IntValue>)Parameters["NrOfFitnessComponents"]; }
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 IntValue Seed {
96      get { return SeedParameter.Value; }
97    }
98    #endregion
99
100    [Storable]
101    private MersenneTwister random;
102
103    [ThreadStatic]
104    private static HashAlgorithm hashAlgorithm;
105
106    public static HashAlgorithm HashAlgorithm {
107      get {
108        if (hashAlgorithm == null) {
109          hashAlgorithm = HashAlgorithm.Create("MD5");
110        }
111        return hashAlgorithm;
112      }
113    }
114
115    [StorableConstructor]
116    private NKLandscape(bool deserializing) : base(deserializing) { }
117    private NKLandscape(NKLandscape original, Cloner cloner)
118      : base(original, cloner) {
119      random = (MersenneTwister)original.random.Clone(cloner);
120      RegisterEventHandlers();
121    }
122    public NKLandscape()
123      : base() {
124      random = new MersenneTwister();
125
126      Parameters.Add(new ValueParameter<BoolMatrix>("GeneInteractions", "Every column gives the participating genes for each fitness component"));
127      Parameters.Add(new ValueParameter<IntValue>("Seed", "The seed used for the random number generator.", new IntValue(0)));
128      random.Reset(Seed.Value);
129
130      Parameters.Add(new ValueParameter<IntValue>("InteractionSeed", "The seed used for the hash function to generate interaction tables.", new IntValue(random.Next())));
131      Parameters.Add(new ValueParameter<IntValue>("NrOfFitnessComponents", "Number of fitness component functions. (nr of columns in the interaction column)", new IntValue(10)));
132      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)));
133      Parameters.Add(new ValueParameter<DoubleArray>("Weights", "The weights for the component functions. If shorted, will be repeated.", new DoubleArray(new[] { 1.0 })));
134      Parameters.Add(new OptionalConstrainedValueParameter<IInteractionInitializer>("InteractionInitializer", "Initialize interactions within the component functions."));
135      Parameters.Add(new OptionalConstrainedValueParameter<IWeightsInitializer>("WeightsInitializer", "Operator to initialize weights distribution"));
136
137      InitializeInteractionInitializerParameter();
138      InitializeWeightsInitializerParameter();
139
140      InitializeOperators();
141      RegisterEventHandlers();
142      InitializeInteractions();
143    }
144
145    private void InitializeInteractionInitializerParameter() {
146      foreach (var initializer in ApplicationManager.Manager.GetInstances<IInteractionInitializer>())
147        InteractionInitializerParameter.ValidValues.Add(initializer);
148      InteractionInitializerParameter.Value = InteractionInitializerParameter.ValidValues.First(v => v is RandomInteractionsInitializer);
149    }
150
151    private void InitializeWeightsInitializerParameter() {
152      foreach (var initializer in ApplicationManager.Manager.GetInstances<IWeightsInitializer>())
153        WeightsInitializerParameter.ValidValues.Add(initializer);
154      WeightsInitializerParameter.Value = WeightsInitializerParameter.ValidValues.First(v => v is EqualWeightsInitializer);
155    }
156
157    public override IDeepCloneable Clone(Cloner cloner) {
158      return new NKLandscape(this, cloner);
159    }
160
161    #region Events
162    protected override void LengthParameter_ValueChanged(object sender, EventArgs e) {
163      BestKnownQualityParameter.Value = new DoubleValue(Length);
164      NrOfFitnessComponentsParameter.Value = new IntValue(Length);
165    }
166    #endregion
167
168    #region Helpers
169    [StorableHook(HookType.AfterDeserialization)]
170    private void AfterDeserialization() {
171      RegisterEventHandlers();
172    }
173
174    private void RegisterEventHandlers() {
175      NrOfInteractionsParameter.ValueChanged += InteractionParameterChanged;
176      NrOfInteractionsParameter.Value.ValueChanged += InteractionParameterChanged;
177      NrOfFitnessComponentsParameter.ValueChanged += InteractionParameterChanged;
178      NrOfFitnessComponentsParameter.Value.ValueChanged += InteractionParameterChanged;
179      InteractionInitializerParameter.ValueChanged += InteractionInitializerParameter_ValueChanged;
180      WeightsInitializerParameter.ValueChanged += WeightsInitializerParameter_ValueChanged;
181      SeedParameter.ValueChanged += SeedParameter_ValueChanged;
182      SeedParameter.Value.ValueChanged += SeedParameter_ValueChanged;
183    }
184
185    private void SeedParameter_ValueChanged(object sender, EventArgs e) {
186      random.Reset(Seed.Value);
187      InteractionSeed.Value = random.Next();
188      InitializeInteractions();
189    }
190
191    private void WeightsInitializerParameter_ValueChanged(object sender, EventArgs e) {
192      InitializeWeights();
193    }
194
195    private void InteractionInitializerParameter_ValueChanged(object sender, EventArgs e) {
196      InitializeInteractions();
197    }
198
199    private void InteractionParameterChanged(object sender, EventArgs e) {
200      InitializeInteractions();
201    }
202
203    private void InitializeOperators() {
204      NKBitFlipMoveEvaluator nkEvaluator = new NKBitFlipMoveEvaluator();
205      Encoding.ConfigureOperator(nkEvaluator);
206      Operators.Add(nkEvaluator);
207    }
208
209    private void InitializeInteractions() {
210      if (InteractionInitializer != null)
211        GeneInteractionsParameter.Value = InteractionInitializer.InitializeInterations(
212          Length,
213          NrOfFitnessComponents.Value,
214          NrOfInteractions.Value, random);
215    }
216
217    private void InitializeWeights() {
218      if (WeightsInitializerParameter.Value != null)
219        WeightsParameter.Value = new DoubleArray(
220          WeightsInitializer.GetWeights(NrOfFitnessComponents.Value)
221          .ToArray());
222    }
223    #endregion
224
225    #region Evaluation function
226    public static long Hash(long x) {
227      return BitConverter.ToInt64(HashAlgorithm.ComputeHash(BitConverter.GetBytes(x), 0, 8), 0);
228    }
229
230    public static double F_i(long x, long i, long g_i, long seed) {
231      return Math.Abs((double)Hash((x & g_i) ^ Hash(g_i ^ Hash(i ^ seed)))) / long.MaxValue;
232    }
233
234    public static double F(long x, long[] g, double[] w, long seed, ref double[] f_i) {
235      double value = 0;
236      for (int i = 0; i < g.Length; i++) {
237        f_i[i] = F_i(x, i, g[i], seed);
238        value += w[i % w.Length] * f_i[i];
239      }
240      return value;
241    }
242
243    public static long Encode(BinaryVector v) {
244      long x = 0;
245      for (int i = 0; i < 64 && i < v.Length; i++) {
246        x |= (v[i] ? (long)1 : (long)0) << i;
247      }
248      return x;
249    }
250
251    public static long[] Encode(BoolMatrix m) {
252      long[] x = new long[m.Columns];
253      for (int c = 0; c < m.Columns; c++) {
254        x[c] = 0;
255        for (int r = 0; r < 64 && r < m.Rows; r++) {
256          x[c] |= (m[r, c] ? (long)1 : (long)0) << r;
257        }
258      }
259      return x;
260    }
261
262    public static double[] Normalize(DoubleArray weights) {
263      double sum = 0;
264      double[] w = new double[weights.Length];
265      foreach (var v in weights) {
266        sum += Math.Abs(v);
267      }
268      for (int i = 0; i < weights.Length; i++) {
269        w[i] = Math.Abs(weights[i]) / sum;
270      }
271      return w;
272    }
273
274    public static double Evaluate(BinaryVector vector, BoolMatrix interactions, DoubleArray weights, int seed, out double[] f_i) {
275      long x = Encode(vector);
276      long[] g = Encode(interactions);
277      double[] w = Normalize(weights);
278      f_i = new double[interactions.Columns];
279      return F(x, g, w, (long)seed, ref f_i);
280    }
281
282    public override double Evaluate(BinaryVector vector, IRandom random) {
283      double[] f_i;//not used atm
284      double quality = Evaluate(vector, GeneInteractions, Weights, InteractionSeed.Value, out f_i);
285      return quality;
286    }
287    #endregion
288  }
289}
Note: See TracBrowser for help on using the repository browser.