#region License Information /* HeuristicLab * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Linq; using System.Security.Cryptography; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.BinaryVectorEncoding; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.PluginInfrastructure; using HeuristicLab.Problems.Binary; using HeuristicLab.Random; namespace HeuristicLab.Problems.NK { [Item("NK Landscape", "Represents an NK landscape optimization problem.")] [Creatable("Problems")] [StorableClass] public sealed class NKLandscape : BinaryProblem { public override bool Maximization { get { return false; } } #region Parameters public IValueParameter GeneInteractionsParameter { get { return (IValueParameter)Parameters["GeneInteractions"]; } } public IValueParameter SeedParameter { get { return (IValueParameter)Parameters["ProblemSeed"]; } } public IValueParameter InteractionSeedParameter { get { return (IValueParameter)Parameters["InteractionSeed"]; } } public IValueParameter NrOfInteractionsParameter { get { return (IValueParameter)Parameters["NrOfInteractions"]; } } public IValueParameter NrOfFitnessComponentsParameter { get { return (IValueParameter)Parameters["NrOfFitnessComponents"]; } } public IValueParameter QParameter { get { return (IValueParameter)Parameters["Q"]; } } public IValueParameter PParameter { get { return (IValueParameter)Parameters["P"]; } } public IValueParameter WeightsParameter { get { return (IValueParameter)Parameters["Weights"]; } } public IConstrainedValueParameter InteractionInitializerParameter { get { return (IConstrainedValueParameter)Parameters["InteractionInitializer"]; } } public IConstrainedValueParameter WeightsInitializerParameter { get { return (IConstrainedValueParameter)Parameters["WeightsInitializer"]; } } #endregion #region Properties public IInteractionInitializer InteractionInitializer { get { return InteractionInitializerParameter.Value; } } public BoolMatrix GeneInteractions { get { return GeneInteractionsParameter.Value; } } public DoubleArray Weights { get { return WeightsParameter.Value; } } public IntValue InteractionSeed { get { return InteractionSeedParameter.Value; } } public IntValue NrOfFitnessComponents { get { return NrOfFitnessComponentsParameter.Value; } } public IntValue NrOfInteractions { get { return NrOfInteractionsParameter.Value; } } public IWeightsInitializer WeightsInitializer { 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; } } #endregion [Storable] private MersenneTwister random; [ThreadStatic] private static HashAlgorithm hashAlgorithm; [ThreadStatic] private static HashAlgorithm hashAlgorithmP; private static HashAlgorithm HashAlgorithm { get { if (hashAlgorithm == null) { hashAlgorithm = HashAlgorithm.Create("MD5"); } return hashAlgorithm; } } private static HashAlgorithm HashAlgorithmP { get { if (hashAlgorithmP == null) { hashAlgorithmP = HashAlgorithm.Create("SHA1"); } return hashAlgorithmP; } } [StorableConstructor] private NKLandscape(bool deserializing) : base(deserializing) { } private NKLandscape(NKLandscape original, Cloner cloner) : base(original, cloner) { random = (MersenneTwister)original.random.Clone(cloner); RegisterEventHandlers(); } public NKLandscape() : base() { random = new MersenneTwister(); Parameters.Add(new ValueParameter("GeneInteractions", "Every column gives the participating genes for each fitness component.")); Parameters.Add(new ValueParameter("ProblemSeed", "The seed used for the random number generator.", new IntValue(0))); random.Reset(Seed.Value); Parameters.Add(new ValueParameter("InteractionSeed", "The seed used for the hash function to generate interaction tables.", new IntValue(random.Next()))); Parameters.Add(new ValueParameter("NrOfFitnessComponents", "Number of fitness component functions. (nr of columns in the interaction column)", new IntValue(10))); Parameters.Add(new ValueParameter("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("Q", "Number of allowed fitness values in the (virutal) random table, or zero.", new IntValue(0))); Parameters.Add(new ValueParameter("P", "Probability of any entry in the (virtual) random table being zero.", new DoubleValue(0))); Parameters.Add(new ValueParameter("Weights", "The weights for the component functions. If shorted, will be repeated.", new DoubleArray(new[] { 1.0 }))); Parameters.Add(new ConstrainedValueParameter("InteractionInitializer", "Initialize interactions within the component functions.")); Parameters.Add(new ConstrainedValueParameter("WeightsInitializer", "Operator to initialize the weights distribution.")); //allow just the standard NK[P,Q] formulations at the moment WeightsParameter.Hidden = true; InteractionInitializerParameter.Hidden = true; WeightsInitializerParameter.Hidden = true; EncodingParameter.Hidden = true; InitializeInteractionInitializerParameter(); InitializeWeightsInitializerParameter(); InitializeOperators(); InitializeInteractions(); RegisterEventHandlers(); } private void InitializeInteractionInitializerParameter() { foreach (var initializer in ApplicationManager.Manager.GetInstances()) InteractionInitializerParameter.ValidValues.Add(initializer); InteractionInitializerParameter.Value = InteractionInitializerParameter.ValidValues.First(v => v is RandomInteractionsInitializer); } private void InitializeWeightsInitializerParameter() { foreach (var initializer in ApplicationManager.Manager.GetInstances()) WeightsInitializerParameter.ValidValues.Add(initializer); WeightsInitializerParameter.Value = WeightsInitializerParameter.ValidValues.First(v => v is EqualWeightsInitializer); } public override IDeepCloneable Clone(Cloner cloner) { return new NKLandscape(this, cloner); } [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { RegisterEventHandlers(); } private void RegisterEventHandlers() { NrOfInteractionsParameter.ValueChanged += InteractionParameter_ValueChanged; NrOfInteractionsParameter.Value.ValueChanged += InteractionParameter_ValueChanged; NrOfFitnessComponentsParameter.ValueChanged += InteractionParameter_ValueChanged; NrOfFitnessComponentsParameter.Value.ValueChanged += InteractionParameter_ValueChanged; InteractionInitializerParameter.ValueChanged += InteractionParameter_ValueChanged; WeightsInitializerParameter.ValueChanged += WeightsInitializerParameter_ValueChanged; SeedParameter.ValueChanged += SeedParameter_ValueChanged; SeedParameter.Value.ValueChanged += SeedParameter_ValueChanged; RegisterInteractionInitializerParameterEvents(); RegisterWeightsParameterEvents(); } private void RegisterWeightsParameterEvents() { foreach (var vv in WeightsInitializerParameter.ValidValues) { foreach (var p in vv.Parameters) { if (p.ActualValue != null && p.ActualValue is IStringConvertibleValue) { var v = (IStringConvertibleValue)p.ActualValue; v.ValueChanged += WeightsInitializerParameter_ValueChanged; } } } } private void RegisterInteractionInitializerParameterEvents() { foreach (var vv in InteractionInitializerParameter.ValidValues) { foreach (var p in vv.Parameters) { if (p.ActualValue != null && p.ActualValue is IStringConvertibleValue) { var v = (IStringConvertibleValue)p.ActualValue; v.ValueChanged += InteractionParameter_ValueChanged; } else if (p.ActualValue != null && p is IConstrainedValueParameter) { ((IConstrainedValueParameter)p).ValueChanged += InteractionParameter_ValueChanged; } } } } protected override void LengthParameter_ValueChanged(object sender, EventArgs e) { NrOfFitnessComponentsParameter.Value = new IntValue(Length); } private void SeedParameter_ValueChanged(object sender, EventArgs e) { random.Reset(Seed.Value); InteractionSeed.Value = random.Next(); InitializeInteractions(); } private void WeightsInitializerParameter_ValueChanged(object sender, EventArgs e) { InitializeWeights(); } private void InteractionParameter_ValueChanged(object sender, EventArgs e) { InitializeInteractions(); } private void InitializeOperators() { NKBitFlipMoveEvaluator nkEvaluator = new NKBitFlipMoveEvaluator(); Encoding.ConfigureOperator(nkEvaluator); Operators.Add(nkEvaluator); } private void InitializeInteractions() { if (InteractionInitializer != null) GeneInteractionsParameter.Value = InteractionInitializer.InitializeInterations( Length, NrOfFitnessComponents.Value, NrOfInteractions.Value, random); } private void InitializeWeights() { if (WeightsInitializerParameter.Value != null) WeightsParameter.Value = new DoubleArray( WeightsInitializer.GetWeights(NrOfFitnessComponents.Value) .ToArray()); } #region Evaluation function private 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(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; } private 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, q, p); value += w[i % w.Length] * f_i[i]; } return value; } public static long Encode(BinaryVector v) { long x = 0; for (int i = 0; i < 64 && i < v.Length; i++) { x |= (v[i] ? (long)1 : (long)0) << i; } return x; } public static long[] Encode(BoolMatrix m) { long[] x = new long[m.Columns]; for (int c = 0; c < m.Columns; c++) { x[c] = 0; for (int r = 0; r < 64 && r < m.Rows; r++) { x[c] |= (m[r, c] ? (long)1 : (long)0) << r; } } return x; } public static double[] Normalize(DoubleArray weights) { double sum = 0; double[] w = new double[weights.Length]; foreach (var v in weights) { sum += Math.Abs(v); } for (int i = 0; i < weights.Length; i++) { w[i] = Math.Abs(weights[i]) / sum; } return w; } 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, q, p); } public override double Evaluate(BinaryVector vector, IRandom random) { double[] f_i; //useful for debugging double quality = Evaluate(vector, GeneInteractions, Weights, InteractionSeed.Value, out f_i, Q, P); return quality; } #endregion } }