1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022015 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 


22  using System;


23  using System.Linq;


24  using System.Security.Cryptography;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Data;


28  using HeuristicLab.Encodings.BinaryVectorEncoding;


29  using HeuristicLab.Parameters;


30  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


31  using HeuristicLab.PluginInfrastructure;


32  using HeuristicLab.Problems.Binary;


33  using HeuristicLab.Problems.NK.WeightInitializers;


34  using HeuristicLab.Random;


35 


36  namespace 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 ValueParameter<BoolMatrix> GeneInteractionsParameter {


48  get { return (ValueParameter<BoolMatrix>)Parameters["GeneInteractions"]; }


49  }


50  public ValueParameter<IntValue> InteractionSeedParameter {


51  get { return (ValueParameter<IntValue>)Parameters["InteractionSeed"]; }


52  }


53  public ValueParameter<IntValue> NrOfInteractionsParameter {


54  get { return (ValueParameter<IntValue>)Parameters["NrOfInteractions"]; }


55  }


56  public ValueParameter<IntValue> NrOfFitnessComponentsParameter {


57  get { return (ValueParameter<IntValue>)Parameters["NrOfFitnessComponents"]; }


58  }


59  public ValueParameter<DoubleArray> WeightsParameter {


60  get { return (ValueParameter<DoubleArray>)Parameters["Weights"]; }


61  }


62  public IConstrainedValueParameter<IInteractionInitializer> InteractionInitializerParameter {


63  get { return (IConstrainedValueParameter<IInteractionInitializer>)Parameters["InteractionInitializer"]; }


64  }


65  public IConstrainedValueParameter<IWeightsInitializer> WeightsInitializerParameter {


66  get { return (IConstrainedValueParameter<IWeightsInitializer>)Parameters["WeightsInitializer"]; }


67  }


68  #endregion


69 


70  #region Properties


71  public IInteractionInitializer InteractionInitializer {


72  get { return InteractionInitializerParameter.Value; }


73  }


74  public BoolMatrix GeneInteractions {


75  get { return GeneInteractionsParameter.Value; }


76  }


77  public DoubleArray Weights {


78  get { return WeightsParameter.Value; }


79  }


80  public IntValue InteractionSeed {


81  get { return InteractionSeedParameter.Value; }


82  }


83  #endregion


84 


85  [ThreadStatic]


86  private static MersenneTwister random;


87  public static MersenneTwister Random {


88  get {


89  if (random == null) {


90  random = new MersenneTwister();


91  }


92  return random;


93  }


94  }


95 


96  [ThreadStatic]


97  private static HashAlgorithm hashAlgorithm;


98 


99  public static HashAlgorithm HashAlgorithm {


100  get {


101  if (hashAlgorithm == null) {


102  hashAlgorithm = HashAlgorithm.Create("MD5");


103  }


104  return hashAlgorithm;


105  }


106  }


107 


108  [StorableConstructor]


109  private NKLandscape(bool deserializing) : base(deserializing) { }


110  private NKLandscape(NKLandscape original, Cloner cloner)


111  : base(original, cloner) {


112  RegisterEventHandlers();


113  }


114  public NKLandscape()


115  : base() {


116  Parameters.Add(new ValueParameter<BoolMatrix>("GeneInteractions", "Every column gives the participating genes for each fitness component"));


117  Parameters.Add(new ValueParameter<IntValue>("InteractionSeed", "The seed used for the hash function to generate interaction tables.", new IntValue(Random.Next())));


118  Parameters.Add(new ValueParameter<IntValue>("NrOfFitnessComponents", "Number of fitness component functions. (nr of columns in the interaction column)", new IntValue(10)));


119  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)));


120  Parameters.Add(new ValueParameter<DoubleArray>("Weights", "The weights for the component functions. If shorted, will be repeated.", new DoubleArray(new[] { 1.0 })));


121  Parameters.Add(new OptionalConstrainedValueParameter<IInteractionInitializer>("InteractionInitializer", "Initialize interactions within the component functions."));


122  Parameters.Add(new OptionalConstrainedValueParameter<IWeightsInitializer>("WeightsInitializer", "Operator to initialize weights distribution"));


123 


124  InitializeInteractionInitializerParameter();


125  InitializeWeightsInitializerParameter();


126 


127  InitializeOperators();


128  RegisterEventHandlers();


129  InitializeInteractions();


130  }


131 


132  private void InitializeInteractionInitializerParameter() {


133  foreach (var initializer in ApplicationManager.Manager.GetInstances<IInteractionInitializer>())


134  InteractionInitializerParameter.ValidValues.Add(initializer);


135  InteractionInitializerParameter.Value = InteractionInitializerParameter.ValidValues.First(v => v is RandomInteractionsInitializer);


136  }


137 


138  private void InitializeWeightsInitializerParameter() {


139  foreach (var initializer in ApplicationManager.Manager.GetInstances<IWeightsInitializer>())


140  WeightsInitializerParameter.ValidValues.Add(initializer);


141  WeightsInitializerParameter.Value = WeightsInitializerParameter.ValidValues.First(v => v is EqualWeightsInitializer);


142  }


143 


144  public override IDeepCloneable Clone(Cloner cloner) {


145  return new NKLandscape(this, cloner);


146  }


147 


148  #region Events


149  protected override void LengthParameter_ValueChanged(object sender, EventArgs e) {


150  BestKnownQualityParameter.Value = new DoubleValue(Length);


151  NrOfFitnessComponentsParameter.Value = new IntValue(Length);


152  }


153  #endregion


154 


155  #region Helpers


156  [StorableHook(HookType.AfterDeserialization)]


157  private void AfterDeserialization() {


158  RegisterEventHandlers();


159  }


160 


161  private void RegisterEventHandlers() {


162  NrOfInteractionsParameter.ValueChanged += InteractionParameterChanged;


163  NrOfInteractionsParameter.Value.ValueChanged += InteractionParameterChanged;


164  NrOfFitnessComponentsParameter.ValueChanged += InteractionParameterChanged;


165  NrOfFitnessComponentsParameter.Value.ValueChanged += InteractionParameterChanged;


166  InteractionInitializerParameter.ValueChanged += InteractionInitializerParameter_ValueChanged;


167  WeightsInitializerParameter.ValueChanged += WeightsInitializerParameter_ValueChanged;


168  }


169 


170  void WeightsInitializerParameter_ValueChanged(object sender, EventArgs e) {


171  InitializeWeights();


172  }


173 


174  void InteractionInitializerParameter_ValueChanged(object sender, EventArgs e) {


175  InitializeInteractions();


176  }


177 


178  private void InteractionParameterChanged(object sender, EventArgs e) {


179  InitializeInteractions();


180  }


181 


182  private void InitializeOperators() {


183  NKBitFlipMoveEvaluator nkEvaluator = new NKBitFlipMoveEvaluator();


184  Encoding.ConfigureOperator(nkEvaluator);


185  Operators.Add(nkEvaluator);


186  }


187 


188  private void InitializeInteractions() {


189  if (InteractionInitializer != null)


190  GeneInteractionsParameter.Value = InteractionInitializer.InitializeInterations(


191  Length,


192  NrOfFitnessComponentsParameter.Value.Value,


193  NrOfInteractionsParameter.Value.Value, Random);


194  }


195 


196  private void InitializeWeights() {


197  if (WeightsInitializerParameter.Value != null)


198  WeightsParameter.Value = new DoubleArray(


199  WeightsInitializerParameter.Value.GetWeights(NrOfFitnessComponentsParameter.Value.Value)


200  .ToArray());


201  }


202  #endregion


203 


204  #region Evaluation function


205  public static long Hash(long x) {


206  return BitConverter.ToInt64(HashAlgorithm.ComputeHash(BitConverter.GetBytes(x), 0, 8), 0);


207  }


208 


209  public static double F_i(long x, long i, long g_i, long seed) {


210  return Math.Abs((double)Hash((x & g_i) ^ Hash(g_i ^ Hash(i ^ seed)))) / long.MaxValue;


211  }


212 


213  public static double F(long x, long[] g, double[] w, long seed, ref double[] f_i) {


214  double value = 0;


215  for (int i = 0; i < g.Length; i++) {


216  f_i[i] = F_i(x, i, g[i], seed);


217  value += w[i % w.Length] * f_i[i];


218  }


219  return value;


220  }


221 


222  public static long Encode(BinaryVector v) {


223  long x = 0;


224  for (int i = 0; i < 64 && i < v.Length; i++) {


225  x = (v[i] ? (long)1 : (long)0) << i;


226  }


227  return x;


228  }


229 


230  public static long[] Encode(BoolMatrix m) {


231  long[] x = new long[m.Columns];


232  for (int c = 0; c < m.Columns; c++) {


233  x[c] = 0;


234  for (int r = 0; r < 64 && r < m.Rows; r++) {


235  x[c] = (m[r, c] ? (long)1 : (long)0) << r;


236  }


237  }


238  return x;


239  }


240 


241  public static double[] Normalize(DoubleArray weights) {


242  double sum = 0;


243  double[] w = new double[weights.Length];


244  foreach (var v in weights) {


245  sum += Math.Abs(v);


246  }


247  for (int i = 0; i < weights.Length; i++) {


248  w[i] = Math.Abs(weights[i]) / sum;


249  }


250  return w;


251  }


252 


253  public static double Evaluate(BinaryVector vector, BoolMatrix interactions, DoubleArray weights, int seed, out double[] f_i) {


254  long x = Encode(vector);


255  long[] g = Encode(interactions);


256  double[] w = Normalize(weights);


257  f_i = new double[interactions.Columns];


258  return F(x, g, w, (long)seed, ref f_i);


259  }


260 


261  public override double Evaluate(BinaryVector vector, IRandom random) {


262  double[] f_i;//not used atm


263  double quality = Evaluate(vector, GeneInteractions, Weights, InteractionSeed.Value, out f_i);


264  return quality;


265  }


266  #endregion


267  }


268  }

