Changeset 12576

Timestamp:

07/02/15 15:36:04 (9 years ago)

Author:

epitzer

Message:

#2306 Implement NKq and NKp landscape (and fix Seed parameter clash with Algorithm's seed)

Location:

branches/FitnessLandscapeAnalysis/HeuristicLab.Problems.NK

Files:

• NKBitFlipMoveEvaluator.cs (modified) (3 diffs)
• NKLandscape.cs (modified) (9 diffs)
• NKMoveEvaluator.cs (modified) (2 diffs)

branches/FitnessLandscapeAnalysis/HeuristicLab.Problems.NK/NKBitFlipMoveEvaluator.cs

@@ -61 +61 @@
       int seed = InteractionSeedParameter.ActualValue.Value;
       double moveQuality = QualityParameter.ActualValue.Value;
+      int q = QParameter.ActualValue.Value;
+      double p = PParameter.ActualValue.Value;
 
       List<int> affectedFitnessComponents = new List<int>();
@@ -71 +73 @@
       if (affectedFitnessComponents.Count * 2 > interactions.Columns) {
         double[] f_i;
-        moveQuality = NKLandscape.Evaluate(moved, interactions, weights, seed, out f_i);
+        moveQuality = NKLandscape.Evaluate(moved, interactions, weights, seed, out f_i, q, p);
       } else {
         long x = NKLandscape.Encode(binaryVector);
@@ -78 +80 @@
         double[] w = NKLandscape.Normalize(weights);
         foreach (var c in affectedFitnessComponents) {
-          moveQuality -= w[c % w.Length] * NKLandscape.F_i(x, c, g[c], seed);
-          moveQuality += w[c % w.Length] * NKLandscape.F_i(y, c, g[c], seed);
+          moveQuality -= w[c%w.Length]*NKLandscape.F_i(x, c, g[c], seed, q, p);
+          moveQuality += w[c%w.Length]*NKLandscape.F_i(y, c, g[c], seed, q, p);
         }
       }

branches/FitnessLandscapeAnalysis/HeuristicLab.Problems.NK/NKLandscape.cs

@@ -49 +49 @@
     }
     public IValueParameter<IntValue> SeedParameter {
-      get { return (IValueParameter<IntValue>)Parameters["Seed"]; }
+      get { return (IValueParameter<IntValue>)Parameters["ProblemSeed"]; }
     }
     public IValueParameter<IntValue> InteractionSeedParameter {
@@ -59 +59 @@
     public IValueParameter<IntValue> NrOfFitnessComponentsParameter {
       get { return (IValueParameter<IntValue>)Parameters["NrOfFitnessComponents"]; }
+    }
+    public IValueParameter<IntValue> QParameter {
+      get { return (IValueParameter<IntValue>)Parameters["Q"]; }
+    }
+    public IValueParameter<DoubleValue> PParameter {
+      get { return (IValueParameter<DoubleValue>)Parameters["P"]; }
     }
     public IValueParameter<DoubleArray> WeightsParameter {
@@ -93 +99 @@
       get { return WeightsInitializerParameter.Value; }
     }
+    public int Q { get { return QParameter.Value.Value; } }
+    public double P { get { return PParameter.Value.Value; } }
     public IntValue Seed {
       get { return SeedParameter.Value; }
@@ -103 +111 @@
     [ThreadStatic]
     private static HashAlgorithm hashAlgorithm;
+
+    [ThreadStatic]
+    private static HashAlgorithm hashAlgorithmP;
 
     public static HashAlgorithm HashAlgorithm {
@@ -113 +124 @@
     }
 
+    public static HashAlgorithm HashAlgorithmP {
+      get {
+        if (hashAlgorithmP == null) {
+          hashAlgorithmP = HashAlgorithm.Create("SHA1");
+        }
+        return hashAlgorithmP;
+      }
+    }
+
     [StorableConstructor]
     private NKLandscape(bool deserializing) : base(deserializing) { }
@@ -125 +145 @@
 
       Parameters.Add(new ValueParameter<BoolMatrix>("GeneInteractions", "Every column gives the participating genes for each fitness component"));
-      Parameters.Add(new ValueParameter<IntValue>("Seed", "The seed used for the random number generator.", new IntValue(0)));
+      Parameters.Add(new ValueParameter<IntValue>("ProblemSeed", "The seed used for the random number generator.", new IntValue(0)));
       random.Reset(Seed.Value);
 
@@ -131 +151 @@
       Parameters.Add(new ValueParameter<IntValue>("NrOfFitnessComponents", "Number of fitness component functions. (nr of columns in the interaction column)", new IntValue(10)));
       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)));
+      Parameters.Add(new ValueParameter<IntValue>("Q", "Number of allowed fitness values in the (virutal) random table, or zero", new IntValue(0)));
+      Parameters.Add(new ValueParameter<DoubleValue>("P", "Probability of any entry in the (virtual) random table being zero", new DoubleValue(0)));
       Parameters.Add(new ValueParameter<DoubleArray>("Weights", "The weights for the component functions. If shorted, will be repeated.", new DoubleArray(new[] { 1.0 })));
       Parameters.Add(new OptionalConstrainedValueParameter<IInteractionInitializer>("InteractionInitializer", "Initialize interactions within the component functions."));
@@ -224 +246 @@
 
     #region Evaluation function
-    public static long Hash(long x) {
-      return BitConverter.ToInt64(HashAlgorithm.ComputeHash(BitConverter.GetBytes(x), 0, 8), 0);
-    }
-
-    public static double F_i(long x, long i, long g_i, long seed) {
-      return Math.Abs((double)Hash((x & g_i) ^ Hash(g_i ^ Hash(i ^ seed)))) / long.MaxValue;
-    }
-
-    public static double F(long x, long[] g, double[] w, long seed, ref double[] f_i) {
+    public static long Hash(long x, HashAlgorithm hashAlg) {
+      return BitConverter.ToInt64(hashAlg.ComputeHash(BitConverter.GetBytes(x), 0, 8), 0);
+    }
+
+    public static double F_i(long x, long i, long g_i, long seed, int q, double p) {
+      var hash = new Func<long,long>(y => Hash(y, HashAlgorithm));
+      var fi = Math.Abs((double)hash((x & g_i) ^ hash(g_i ^ hash(i ^ seed)))) / long.MaxValue;
+      if (q > 0) { fi = Math.Round(fi*q)/q; }
+      if (p > 0) {
+        hash = y => Hash(y, HashAlgorithmP);
+        var r = Math.Abs((double)hash((x & g_i) ^ hash(g_i ^ hash(i ^ seed)))) / long.MaxValue;
+        fi = (r <= p) ? 0 : fi;
+      }
+      return fi;
+    }
+
+    public static double F(long x, long[] g, double[] w, long seed, ref double[] f_i, int q, double p) {
       double value = 0;
       for (int i = 0; i < g.Length; i++) {
-        f_i[i] = F_i(x, i, g[i], seed);
+        f_i[i] = F_i(x, i, g[i], seed, q, p);
         value += w[i % w.Length] * f_i[i];
       }
@@ -272 +302 @@
     }
 
-    public static double Evaluate(BinaryVector vector, BoolMatrix interactions, DoubleArray weights, int seed, out double[] f_i) {
+    public static double Evaluate(BinaryVector vector, BoolMatrix interactions, DoubleArray weights, int seed, out double[] f_i, int q, double p) {
       long x = Encode(vector);
       long[] g = Encode(interactions);
       double[] w = Normalize(weights);
       f_i = new double[interactions.Columns];
-      return F(x, g, w, (long)seed, ref f_i);
+      return F(x, g, w, (long)seed, ref f_i, q, p);
     }
 
     public override double Evaluate(BinaryVector vector, IRandom random) {
       double[] f_i;//not used atm
-      double quality = Evaluate(vector, GeneInteractions, Weights, InteractionSeed.Value, out f_i);
+      double quality = Evaluate(vector, GeneInteractions, Weights, InteractionSeed.Value, out f_i, Q, P);
       return quality;
     }

branches/FitnessLandscapeAnalysis/HeuristicLab.Problems.NK/NKMoveEvaluator.cs

@@ -52 +52 @@
       get { return (ILookupParameter<DoubleArray>)Parameters["Weights"]; }
     }
+    public ILookupParameter<IntValue> QParameter { get { return (ILookupParameter<IntValue>)Parameters["Q"]; } }
+    public ILookupParameter<DoubleValue> PParameter { get { return (ILookupParameter<DoubleValue>)Parameters["P"]; } }
 
     [StorableConstructor]
@@ -64 +66 @@
       Parameters.Add(new LookupParameter<IntValue>("InteractionSeed", "Seed used for randomly generting gene interactions."));
       Parameters.Add(new LookupParameter<DoubleArray>("Weights", "The weights for the component functions. If shorter, will be repeated."));
+      Parameters.Add(new LookupParameter<IntValue>("Q", "Number of allowed fitness values in the (virutal) random table, or zero"));
+      Parameters.Add(new LookupParameter<DoubleValue>("P", "Probability of any entry in the (virtual) random table being zero"));
     }
   }