Changeset 14496


Ignore:
Timestamp:
12/16/16 17:10:05 (4 years ago)
Author:
abeham
Message:

#2701:

  • Reusing similiarty calculator in BinaryMemPR
  • Fixing distance calculation for linear linkage and LinearLinkageMemPR
  • Small changes to base algorithm
  • Added biased model trainer for permutation (rank and fitness)
  • Fixing best known quality calculation for GCP
Location:
branches/MemPRAlgorithm
Files:
12 edited
1 copied

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs

    r14456 r14496  
    6666
    6767    protected override double Dist(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
    68       var len = a.Solution.Length;
    69       var acode = a.Solution;
    70       var bcode = b.Solution;
    71       var hamming = 0;
    72       for (var i = 0; i < len; i++)
    73         if (acode[i] != bcode[i]) hamming++;
    74       return hamming / (double)len;
     68      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a.Solution, b.Solution);
    7569    }
    7670

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/HeuristicLab.Algorithms.MemPR-3.3.csproj

    r14492 r14496  
    114114    <Compile Include="Permutation\LocalSearch\StaticAPI\Exhaustive2Opt.cs" />
    115115    <Compile Include="Permutation\LocalSearch\StaticAPI\ExhaustiveSwap2.cs" />
     116    <Compile Include="Permutation\SolutionModel\Univariate\BiasedModelTrainer.cs" />
    116117    <Compile Include="Permutation\SolutionModel\Univariate\StaticAPI\Trainer.cs" />
    117118    <Compile Include="Permutation\SolutionModel\Univariate\UnbiasedModelTrainer.cs" />

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs

    r14492 r14496  
    2626using HeuristicLab.Algorithms.MemPR.Interfaces;
    2727using HeuristicLab.Algorithms.MemPR.Util;
    28 using HeuristicLab.Collections;
    2928using HeuristicLab.Common;
    3029using HeuristicLab.Core;
    … …  
    6867
    6968    protected override double Dist(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) {
    70       return HammingSimilarityCalculator.CalculateSimilarity(a.Solution, b.Solution);
     69      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a.Solution, b.Solution);
    7170    }
    7271

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs

    r14477 r14496  
    230230        while (Context.PopulationCount < 2) {
    231231          var child = Create(token);
    232           Context.HcSteps += HillClimb(child, token);
    233           Context.AddToPopulation(child);
    234           Analyze(token);
     232          Context.LocalSearchEvaluations += HillClimb(child, token);
     233          if (Replace(child, token) >= 0)
     234            Analyze(token);
    235235          token.ThrowIfCancellationRequested();
    236236          if (Terminate()) return;
    237237        }
    238         Context.HcSteps /= 2;
     238        Context.LocalSearchEvaluations /= 2;
    239239        Context.Initialized = true;
    240240      }
    … …  
    262262      int replPos = -1;
    263263
    264       if (Context.Random.NextDouble() > parentDist) {
     264      if (Context.Random.NextDouble() > parentDist * parentDist) {
    265265        offspring = BreedAndImprove(p1, p2, token);
    266266        replPos = Replace(offspring, token);
    … …  
    271271      }
    272272
    273       if (Context.Random.NextDouble() < parentDist) {
     273      if (Context.Random.NextDouble() < Math.Sqrt(parentDist)) {
    274274        offspring = RelinkAndImprove(p1, p2, token);
    275275        replPos = Replace(offspring, token);
    … …  
    299299          offspring = (ISingleObjectiveSolutionScope<TSolution>)Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Clone();
    300300          Mutate(offspring, token);
    301           PerformTabuWalk(offspring, Context.HcSteps, token);
     301          PerformTabuWalk(offspring, Context.LocalSearchEvaluations, token);
    302302          replPos = Replace(offspring, token);
    303303          if (replPos >= 0) {
    … …  
    318318        Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    319319      else ((IntValue)res.Value).Value = Context.Iterations;
    320       if (!Results.TryGetValue("HcSteps", out res))
    321         Results.Add(new Result("HcSteps", new IntValue(Context.HcSteps)));
    322       else ((IntValue)res.Value).Value = Context.HcSteps;
     320      if (!Results.TryGetValue("LocalSearch Evaluations", out res))
     321        Results.Add(new Result("LocalSearch Evaluations", new IntValue(Context.LocalSearchEvaluations)));
     322      else ((IntValue)res.Value).Value = Context.LocalSearchEvaluations;
    323323      if (!Results.TryGetValue("ByBreeding", out res))
    324324        Results.Add(new Result("ByBreeding", new IntValue(Context.ByBreeding)));

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRContext.cs

    r14450 r14496  
    102102
    103103    [Storable]
    104     private IValueParameter<IntValue> hcSteps;
    105     public int HcSteps {
    106       get { return hcSteps.Value.Value; }
    107       set { hcSteps.Value.Value = value; }
     104    private IValueParameter<IntValue> localSearchEvaluations;
     105    public int LocalSearchEvaluations {
     106      get { return localSearchEvaluations.Value.Value; }
     107      set { localSearchEvaluations.Value.Value = value; }
    108108    }
    109109
    … …  
    196196      bestQuality = cloner.Clone(original.bestQuality);
    197197      bestSolution = cloner.Clone(original.bestSolution);
    198       hcSteps = cloner.Clone(original.hcSteps);
     198      localSearchEvaluations = cloner.Clone(original.localSearchEvaluations);
    199199      byBreeding = cloner.Clone(original.byBreeding);
    200200      byRelinking = cloner.Clone(original.byRelinking);
    … …  
    219219      Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN)));
    220220      Parameters.Add(bestSolution = new ValueParameter<TSolution>("BestSolution"));
    221       Parameters.Add(hcSteps = new ValueParameter<IntValue>("HcSteps", new IntValue(0)));
     221      Parameters.Add(localSearchEvaluations = new ValueParameter<IntValue>("LocalSearchEvaluations", new IntValue(0)));
    222222      Parameters.Add(byBreeding = new ValueParameter<IntValue>("ByBreeding", new IntValue(0)));
    223223      Parameters.Add(byRelinking = new ValueParameter<IntValue>("ByRelinking", new IntValue(0)));

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/SolutionModel/Univariate/BiasedModelTrainer.cs

    r14487 r14496  
    2424using HeuristicLab.Common;
    2525using HeuristicLab.Core;
     26using HeuristicLab.Data;
    2627using HeuristicLab.Encodings.PermutationEncoding;
    2728using HeuristicLab.Optimization;
     29using HeuristicLab.Parameters;
    2830using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2931
    3032namespace HeuristicLab.Algorithms.MemPR.Permutation.SolutionModel.Univariate {
    31   [Item("Unbiased Univariate Model Trainer (Permutation)", "", ExcludeGenericTypeInfo = true)]
     33  [Item("Biased Univariate Model Trainer (Permutation)", "", ExcludeGenericTypeInfo = true)]
    3234  [StorableClass]
    33   public class UniasedModelTrainer<TContext> : NamedItem, ISolutionModelTrainer<TContext>
     35  public class BiasedModelTrainer<TContext> : ParameterizedNamedItem, ISolutionModelTrainer<TContext>
    3436    where TContext : IPopulationBasedHeuristicAlgorithmContext<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation>,
    3537    ISolutionModelContext<Encodings.PermutationEncoding.Permutation> {
    36    
     38
     39    [Storable]
     40    private IValueParameter<EnumValue<ModelBiasOptions>> modelBiasParameter;
     41    public ModelBiasOptions ModelBias {
     42      get { return modelBiasParameter.Value.Value; }
     43      set { modelBiasParameter.Value.Value = value; }
     44    }
     45
    3746    [StorableConstructor]
    38     protected UniasedModelTrainer(bool deserializing) : base(deserializing) { }
    39     protected UniasedModelTrainer(UniasedModelTrainer<TContext> original, Cloner cloner) : base(original, cloner) { }
    40     public UniasedModelTrainer() {
    41       Name = ItemName;
    42       Description = ItemDescription;
     47    protected BiasedModelTrainer(bool deserializing) : base(deserializing) { }
     48    protected BiasedModelTrainer(BiasedModelTrainer<TContext> original, Cloner cloner)
     49      : base(original, cloner) {
     50      modelBiasParameter = cloner.Clone(original.modelBiasParameter);
     51    }
     52    public BiasedModelTrainer() {
     53      Parameters.Add(modelBiasParameter = new ValueParameter<EnumValue<ModelBiasOptions>>("Model Bias", "What kind of bias towards better individuals is chosen."));
    4354    }
    4455
    4556    public override IDeepCloneable Clone(Cloner cloner) {
    46       return new UniasedModelTrainer<TContext>(this, cloner);
     57      return new BiasedModelTrainer<TContext>(this, cloner);
    4758    }
    4859
    4960    public void TrainModel(TContext context) {
    50       context.Model = Trainer.Train(context.Random, context.Population.Select(x => x.Solution).ToList(), context.Problem.Encoding.Length);
     61      context.Model = Trainer.TrainBiased(ModelBias, context.Random, context.Problem.Maximization, context.Population.Select(x => x.Solution).ToList(), context.Population.Select(x => x.Fitness).ToList(), context.Problem.Encoding.Length);
    5162    }
    5263  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/SolutionModel/Univariate/StaticAPI/Trainer.cs

    r14450 r14496  
    2727
    2828namespace HeuristicLab.Algorithms.MemPR.Permutation.SolutionModel.Univariate {
     29  public enum ModelBiasOptions { Rank, Fitness }
     30
    2931  public static class Trainer {
    30     public static ISolutionModel<Encodings.PermutationEncoding.Permutation> Train(IRandom random, IList<Encodings.PermutationEncoding.Permutation> pop, int N) {
     32    public static ISolutionModel<Encodings.PermutationEncoding.Permutation> TrainUnbiased(IRandom random, IList<Encodings.PermutationEncoding.Permutation> pop, int N) {
    3133      ISolutionModel<Encodings.PermutationEncoding.Permutation> model;
    3234      switch (pop[0].PermutationType) {
    3335        case PermutationTypes.Absolute:
    34           model = UnivariateAbsoluteModel.Create(random, pop, N);
     36          model = UnivariateAbsoluteModel.CreateUnbiased(random, pop, N);
    3537          break;
    3638        case PermutationTypes.RelativeDirected:
    … …  
    4446      return model;
    4547    }
     48
     49    public static ISolutionModel<Encodings.PermutationEncoding.Permutation> TrainBiased(ModelBiasOptions modelBias, IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> pop, IList<double> qualities, int N) {
     50      if (pop.Count != qualities.Count) throw new ArgumentException("Unequal length of population and qualities list.");
     51      ISolutionModel<Encodings.PermutationEncoding.Permutation> model;
     52      switch (pop[0].PermutationType) {
     53        case PermutationTypes.Absolute:
     54          if (modelBias == ModelBiasOptions.Rank)
     55            model = UnivariateAbsoluteModel.CreateWithRankBias(random, maximization, pop, qualities, N);
     56          else if (modelBias == ModelBiasOptions.Fitness)
     57            model = UnivariateAbsoluteModel.CreateWithFitnessBias(random, maximization, pop, qualities, N);
     58          else throw new ArgumentException(string.Format("Bias type {0} is not supported.", modelBias));
     59          break;
     60        case PermutationTypes.RelativeDirected:
     61          if (modelBias == ModelBiasOptions.Rank)
     62            model = UnivariateRelativeModel.CreateDirectedWithRankBias(random, maximization, pop, qualities, N);
     63          else if (modelBias == ModelBiasOptions.Fitness)
     64            model = UnivariateRelativeModel.CreateDirectedWithFitnessBias(random, maximization, pop, qualities, N);
     65          else throw new ArgumentException(string.Format("Bias type {0} is not supported.", modelBias));
     66          break;
     67        case PermutationTypes.RelativeUndirected:
     68          if (modelBias == ModelBiasOptions.Rank)
     69            model = UnivariateRelativeModel.CreateUndirectedWithRankBias(random, maximization, pop, qualities, N);
     70          else if (modelBias == ModelBiasOptions.Fitness)
     71            model = UnivariateRelativeModel.CreateUndirectedWithFitnessBias(random, maximization, pop, qualities, N);
     72          else throw new ArgumentException(string.Format("Bias type {0} is not supported.", modelBias));
     73          break;
     74        default: throw new ArgumentException(string.Format("unknown permutation type {0}", pop[0].PermutationType));
     75      }
     76      return model;
     77    }
    4678  }
    4779}

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/SolutionModel/Univariate/UnbiasedModelTrainer.cs

    r14450 r14496  
    2121
    2222using System.Linq;
     23using HeuristicLab.Algorithms.MemPR.Binary.SolutionModel.Univariate;
    2324using HeuristicLab.Algorithms.MemPR.Interfaces;
    2425using HeuristicLab.Common;
    … …  
    3132  [Item("Unbiased Univariate Model Trainer (Permutation)", "", ExcludeGenericTypeInfo = true)]
    3233  [StorableClass]
    33   public class UniasedModelTrainer<TContext> : NamedItem, ISolutionModelTrainer<TContext>
     34  public class UnbiasedModelTrainer<TContext> : NamedItem, ISolutionModelTrainer<TContext>
    3435    where TContext : IPopulationBasedHeuristicAlgorithmContext<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation>,
    3536    ISolutionModelContext<Encodings.PermutationEncoding.Permutation> {
    3637   
    3738    [StorableConstructor]
    38     protected UniasedModelTrainer(bool deserializing) : base(deserializing) { }
    39     protected UniasedModelTrainer(UniasedModelTrainer<TContext> original, Cloner cloner) : base(original, cloner) { }
    40     public UniasedModelTrainer() {
     39    protected UnbiasedModelTrainer(bool deserializing) : base(deserializing) { }
     40    protected UnbiasedModelTrainer(UnbiasedModelTrainer<TContext> original, Cloner cloner) : base(original, cloner) { }
     41    public UnbiasedModelTrainer() {
    4142      Name = ItemName;
    4243      Description = ItemDescription;
    … …  
    4445
    4546    public override IDeepCloneable Clone(Cloner cloner) {
    46       return new UniasedModelTrainer<TContext>(this, cloner);
     47      return new UnbiasedModelTrainer<TContext>(this, cloner);
    4748    }
    4849
    4950    public void TrainModel(TContext context) {
    50       context.Model = Trainer.Train(context.Random, context.Population.Select(x => x.Solution).ToList(), context.Problem.Encoding.Length);
     51      context.Model = Trainer.TrainUnbiased(context.Random, context.Population.Select(x => x.Solution).ToList(), context.Problem.Encoding.Length);
    5152    }
    5253  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/SolutionModel/Univariate/UnivariateAbsoluteModel.cs

    r14450 r14496  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
    … …  
    3536  public sealed class UnivariateAbsoluteModel : Item, ISolutionModel<Encodings.PermutationEncoding.Permutation> {
    3637    [Storable]
    37     public IntMatrix Probabilities { get; set; }
     38    public DoubleMatrix Probabilities { get; set; }
    3839    [Storable]
    3940    public IRandom Random { get; set; }
    … …  
    4647      Random = cloner.Clone(original.Random);
    4748    }
    48     public UnivariateAbsoluteModel(IRandom random, int[,] probabilities) {
    49       Probabilities = new IntMatrix(probabilities);
     49    public UnivariateAbsoluteModel(IRandom random, double[,] probabilities) {
     50      Probabilities = new DoubleMatrix(probabilities);
    5051      Random = random;
    5152    }
    52     public UnivariateAbsoluteModel(IRandom random, IntMatrix probabilties) {
     53    public UnivariateAbsoluteModel(IRandom random, DoubleMatrix probabilties) {
    5354      Probabilities = probabilties;
    5455      Random = random;
    … …  
    6667      for (var i = N - 1; i > 0; i--) {
    6768        var nextIndex = indices[i];
    68         var total = 0.0;
    69         for (var v = 0; v < values.Count; v++) {
    70           total += Probabilities[nextIndex, values[v]] + 1.0 / N;
    71         }
    72         var ball = Random.NextDouble() * total;
     69        var ball = Random.NextDouble();
    7370        for (var v = 0; v < values.Count; v++) {
    7471          ball -= Probabilities[nextIndex, values[v]] + 1.0 / N;
    75           if (ball <= 0.0) {
    76             child[nextIndex] = values[v];
    77             values.RemoveAt(v);
    78             indices.RemoveAt(i);
    79             break;
    80           }
     72          if (ball > 0.0) continue;
     73          child[nextIndex] = values[v];
     74          values.RemoveAt(v);
     75          indices.RemoveAt(i);
     76          break;
     77        }
     78        if (ball > 0) {
     79          var v = values.Count - 1;
     80          child[nextIndex] = values[v];
     81          values.RemoveAt(v);
     82          indices.RemoveAt(i);
    8183        }
    8284      }
    … …  
    8587    }
    8688
    87     public static UnivariateAbsoluteModel Create(IRandom random, IList<Encodings.PermutationEncoding.Permutation> pop, int N) {
    88       var model = new int[N, N];
     89    public static UnivariateAbsoluteModel CreateUnbiased(IRandom random, IList<Encodings.PermutationEncoding.Permutation> pop, int N) {
     90      var model = new double[N, N];
     91      var factor = 1.0 / pop.Count;
    8992      for (var i = 0; i < pop.Count; i++) {
    9093        for (var j = 0; j < N; j++) {
    91           model[j, pop[i][j]]++;
     94          model[j, pop[i][j]] += factor;
     95        }
     96      }
     97      return new UnivariateAbsoluteModel(random, model);
     98    }
     99
     100    public static UnivariateAbsoluteModel CreateWithRankBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {
     101      var popSize = 0;
     102      var model = new double[N, N];
     103
     104      var pop = population.Zip(qualities, (b, q) => new { Solution = b, Fitness = q });
     105      foreach (var ind in maximization ? pop.OrderBy(x => x.Fitness) : pop.OrderByDescending(x => x.Fitness)) {
     106        // from worst to best, worst solution has 1 vote, best solution N votes
     107        popSize++;
     108        for (var j = 0; j < N; j++) {
     109          model[j, ind.Solution[j]] += popSize;
     110        }
     111      }
     112      // normalize to [0;1]
     113      var factor = 2.0 / (popSize + 1);
     114      for (var i = 0; i < N; i++) {
     115        for (var j = 0; j < N; j++)
     116          model[i, j] *= factor / popSize;
     117      }
     118      if (popSize == 0) throw new ArgumentException("Cannot train model from empty population.");
     119      return new UnivariateAbsoluteModel(random, model);
     120    }
     121
     122    public static UnivariateAbsoluteModel CreateWithFitnessBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {
     123      var proportions = RandomEnumerable.PrepareProportional(qualities, true, !maximization);
     124      var factor = 1.0 / proportions.Sum();
     125      var model = new double[N, N];
     126
     127      foreach (var ind in population.Zip(proportions, (p, q) => new { Solution = p, Proportion = q })) {
     128        for (var x = 0; x < model.Length; x++) {
     129          for (var j = 0; j < N; j++) {
     130            model[j, ind.Solution[j]] += ind.Proportion * factor;
     131          }
    92132        }
    93133      }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/SolutionModel/Univariate/UnivariateRelativeModel.cs

    r14450 r14496  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
    … …  
    3536  public sealed class UnivariateRelativeModel : Item, ISolutionModel<Encodings.PermutationEncoding.Permutation> {
    3637    [Storable]
    37     public IntMatrix Probabilities { get; set; }
     38    public DoubleMatrix Probabilities { get; set; }
    3839
    3940    [Storable]
    … …  
    5152      PermutationType = original.PermutationType;
    5253    }
    53     public UnivariateRelativeModel(IRandom random, int[,] probabilities, PermutationTypes permutationType) {
    54       Probabilities = new IntMatrix(probabilities);
     54    public UnivariateRelativeModel(IRandom random, double[,] probabilities, PermutationTypes permutationType) {
     55      Probabilities = new DoubleMatrix(probabilities);
    5556      Random = random;
    5657      PermutationType = permutationType;
    5758    }
    58     public UnivariateRelativeModel(IRandom random, IntMatrix probabilties, PermutationTypes permutationType) {
     59    public UnivariateRelativeModel(IRandom random, DoubleMatrix probabilties, PermutationTypes permutationType) {
    5960      Probabilities = probabilties;
    6061      Random = random;
    … …  
    9394
    9495    public static UnivariateRelativeModel CreateDirected(IRandom random, IList<Encodings.PermutationEncoding.Permutation> pop, int N) {
    95       var model = new int[N, N];
     96      var model = new double[N, N];
    9697      for (var i = 0; i < pop.Count; i++) {
    9798        for (var j = 0; j < N - 1; j++) {
    … …  
    105106    }
    106107
     108    public static UnivariateRelativeModel CreateDirectedWithRankBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {
     109      var popSize = 0;
     110      var model = new double[N, N];
     111
     112      var pop = population.Zip(qualities, (b, q) => new { Solution = b, Fitness = q });
     113      foreach (var ind in maximization ? pop.OrderBy(x => x.Fitness) : pop.OrderByDescending(x => x.Fitness)) {
     114        // from worst to best, worst solution has 1 vote, best solution N votes
     115        popSize++;
     116        for (var j = 0; j < N - 1; j++) {
     117          for (var k = j + 1; k < N; k++) {
     118            model[ind.Solution[j], ind.Solution[k]] += popSize;
     119          }
     120          model[ind.Solution[N - 1], ind.Solution[0]] += popSize;
     121        }
     122      }
     123      if (popSize == 0) throw new ArgumentException("Cannot train model from empty population.");
     124      return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeDirected);
     125    }
     126
     127    public static UnivariateRelativeModel CreateDirectedWithFitnessBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {
     128      var proportions = RandomEnumerable.PrepareProportional(qualities, true, !maximization);
     129      var factor = 1.0 / proportions.Sum();
     130      var model = new double[N, N];
     131
     132      foreach (var ind in population.Zip(proportions, (p, q) => new { Solution = p, Proportion = q })) {
     133        for (var x = 0; x < model.Length; x++) {
     134          for (var j = 0; j < N - 1; j++) {
     135            for (var k = j + 1; k < N; k++) {
     136              model[ind.Solution[j], ind.Solution[k]] += ind.Proportion * factor;
     137            }
     138            model[ind.Solution[N - 1], ind.Solution[0]] += ind.Proportion * factor;
     139          }
     140        }
     141      }
     142      return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeDirected);
     143    }
     144
    107145    public static UnivariateRelativeModel CreateUndirected(IRandom random, IList<Encodings.PermutationEncoding.Permutation> pop, int N) {
    108       var model = new int[N, N];
     146      var model = new double[N, N];
    109147      for (var i = 0; i < pop.Count; i++) {
    110148        for (var j = 0; j < N - 1; j++) {
    … …  
    119157      return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeUndirected);
    120158    }
     159
     160    public static UnivariateRelativeModel CreateUndirectedWithRankBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {
     161      var popSize = 0;
     162      var model = new double[N, N];
     163
     164      var pop = population.Zip(qualities, (b, q) => new { Solution = b, Fitness = q });
     165      foreach (var ind in maximization ? pop.OrderBy(x => x.Fitness) : pop.OrderByDescending(x => x.Fitness)) {
     166        // from worst to best, worst solution has 1 vote, best solution N votes
     167        popSize++;
     168        for (var j = 0; j < N - 1; j++) {
     169          for (var k = j + 1; k < N; k++) {
     170            model[ind.Solution[j], ind.Solution[k]] += popSize;
     171            model[ind.Solution[k], ind.Solution[j]] += popSize;
     172          }
     173          model[ind.Solution[0], ind.Solution[N - 1]] += popSize;
     174          model[ind.Solution[N - 1], ind.Solution[0]] += popSize;
     175        }
     176      }
     177      if (popSize == 0) throw new ArgumentException("Cannot train model from empty population.");
     178      return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeUndirected);
     179    }
     180
     181    public static UnivariateRelativeModel CreateUndirectedWithFitnessBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {
     182      var proportions = RandomEnumerable.PrepareProportional(qualities, true, !maximization);
     183      var factor = 1.0 / proportions.Sum();
     184      var model = new double[N, N];
     185
     186      foreach (var ind in population.Zip(proportions, (p, q) => new { Solution = p, Proportion = q })) {
     187        for (var x = 0; x < model.Length; x++) {
     188          for (var j = 0; j < N - 1; j++) {
     189            for (var k = j + 1; k < N; k++) {
     190              model[ind.Solution[j], ind.Solution[k]] += ind.Proportion * factor;
     191              model[ind.Solution[k], ind.Solution[j]] += ind.Proportion * factor;
     192            }
     193            model[ind.Solution[0], ind.Solution[N - 1]] += ind.Proportion * factor;
     194            model[ind.Solution[N - 1], ind.Solution[0]] += ind.Proportion * factor;
     195          }
     196        }
     197      }
     198      return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeUndirected);
     199    }
    121200  }
    122201}

  • branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/SimilarityCalculators/HammingSimilarityCalculator.cs

    r14471 r14496  
    4646    public static double CalculateSimilarity(LinearLinkage left, LinearLinkage right) {
    4747      if (left.Length != right.Length) throw new ArgumentException("Comparing encodings of unequal length");
    48       var dist = 0;
     48      var similarity = 0;
    4949      for (var i = 0; i < left.Length; i++) {
    50         if (left[i] != right[i]) dist++;
     50        if (left[i] == right[i]) similarity++;
    5151      }
    52       return dist / (double)left.Length;
     52      return similarity / (double)left.Length;
    5353    }
    5454

  • branches/MemPRAlgorithm/HeuristicLab.Problems.GraphColoring/3.3/GraphColoringProblem.cs

    r14487 r14496  
    5454      get { return fitnessFunctionParameter; }
    5555    }
     56    public FitnessFunction FitnessFunction {
     57      get { return fitnessFunctionParameter.Value.Value; }
     58      set { fitnessFunctionParameter.Value.Value = value; }
     59    }
    5660
    5761    [StorableConstructor]
    … …  
    6670      Encoding = new LinearLinkageEncoding("lle");
    6771      Parameters.Add(adjacencyListParameter = new ValueParameter<IntMatrix>("Adjacency List", "The adjacency list that describes the (symmetric) edges in the graph with nodes from 0 to N-1."));
    68       Parameters.Add(fitnessFunctionParameter = new ValueParameter<EnumValue<FitnessFunction>>("Fitness Function", "The function to use for evaluating the quality of a solution.", new EnumValue<FitnessFunction>(FitnessFunction.Prioritized)));
     72      Parameters.Add(fitnessFunctionParameter = new ValueParameter<EnumValue<FitnessFunction>>("Fitness Function", "The function to use for evaluating the quality of a solution.", new EnumValue<FitnessFunction>(FitnessFunction.Penalized)));
    6973
    7074      var imat = new IntMatrix(defaultInstance.Length, 2);
    … …  
    7579      Encoding.Length = defaultInstanceNodes;
    7680      AdjacencyListParameter.Value = imat;
    77       BestKnownQuality = 7;
     81      BestKnownQualityParameter.Value = null;
    7882
    7983      InitializeOperators();
    … …  
    112116
    113117    public override double Evaluate(Individual individual, IRandom random) {
    114       var fitFun = FitnessFunctionParameter.Value.Value;
    115118      var adjList = adjacencyListParameter.Value;
    116       var lle = individual.LinearLinkage(Encoding.Name).ToEndLinks(); // LLE-e encoding uses the highest indexed member as group number
    117 
    118       switch (fitFun) {
     119      var llee = individual.LinearLinkage(Encoding.Name).ToEndLinks(); // LLE-e encoding uses the highest indexed member as group number
     120
     121      switch (FitnessFunction) {
    119122        case FitnessFunction.Prioritized: {
    120             var conflicts = 0;
    121             var colors = lle.Distinct().Count();
    122             for (var r = 0; r < adjList.Rows; r++) {
    123               if (lle[adjList[r, 0]] == lle[adjList[r, 1]]) conflicts++; // both nodes are adjacent and have the same color (are in the same group)
    124             }
     123            var colors = llee.Distinct().Count();
     124            var conflicts = CalculateConflicts(llee);
    125125            // number of conflicts is the integer part of the quality
    126126            // number of colors constitutes the fractional part
    127127            // the number of fractional digits is defined by the maximum number of possible colors (each node its own color)
    128             var mag = Math.Pow(10, -(int)Math.Ceiling(Math.Log10(lle.Length)));
     128            var mag = Math.Pow(10, -(int)Math.Ceiling(Math.Log10(llee.Length)));
    129129            // the value is e.g. 4.03 for 4 conflicts with 3 colors (and less than 100 nodes)
    130130            return conflicts + colors * mag;
    … …  
    136136            // Operations Research 39(3), pp. 378–406.
    137137            // All local optima of this function correspond to legal colorings.
    138             var colors = lle.GroupBy(x => x).ToDictionary(x => x.Key, x => new EvaluationHelper() { ColorCount = x.Count() });
     138            // We need to calculate conflicts and nodes per color
     139            var colors = llee.GroupBy(x => x).ToDictionary(x => x.Key, x => new EvaluationHelper() { ColorCount = x.Count() });
    139140            for (var r = 0; r < adjList.Rows; r++) {
    140               var color1 = lle[adjList[r, 0]];
    141               var color2 = lle[adjList[r, 1]];
     141              var color1 = llee[adjList[r, 0]];
     142              var color2 = llee[adjList[r, 1]];
    142143              if (color1 == color2) colors[color1].ConflictCount++;
    143144            }
    144145            return 2 * colors.Sum(x => x.Value.ColorCount * x.Value.ConflictCount) - colors.Sum(x => x.Value.ColorCount * x.Value.ColorCount);
    145146          }
    146         default: throw new InvalidOperationException(string.Format("Unknown fitness function {0}.", fitFun));
     147        default: throw new InvalidOperationException(string.Format("Unknown fitness function {0}.", FitnessFunction));
    147148      }
    148149    }
    … …  
    156157      var orderedIndividuals = individuals.Zip(qualities, (i, q) => new { Individual = i, Quality = q }).OrderBy(z => z.Quality);
    157158      var best = Maximization ? orderedIndividuals.Last().Individual.LinearLinkage(Encoding.Name) : orderedIndividuals.First().Individual.LinearLinkage(Encoding.Name);
    158 
    159       var adjList = AdjacencyListParameter.Value;
     159       
    160160      var lle = best.ToEndLinks();
    161       var conflicts = 0;
    162161      var colors = lle.Distinct().Count();
    163       for (var r = 0; r < adjList.Rows; r++) {
    164         if (lle[adjList[r, 0]] == lle[adjList[r, 1]]) conflicts++; // both nodes are adjacent and have the same color (are in the same group)
    165       }
     162      var conflicts = CalculateConflicts(lle);
    166163
    167164      IResult res;
    … …  
    176173    }
    177174
     175    private int CalculateConflicts(int[] llee) {
     176      var adjList = AdjacencyListParameter.Value;
     177      var conflicts = 0;
     178      for (var r = 0; r < adjList.Rows; r++) {
     179        if (llee[adjList[r, 0]] == llee[adjList[r, 1]]) conflicts++; // both nodes are adjacent and have the same color (are in the same group)
     180      }
     181      return conflicts;
     182    }
     183
    178184    public void Load(GCPData data) {
    179185      Encoding.Length = data.Nodes;
    180186      AdjacencyListParameter.Value = new IntMatrix(data.Adjacencies);
    181       if (FitnessFunctionParameter.Value.Value == FitnessFunction.Prioritized && data.BestKnownColors.HasValue) {
     187      if (data.BestKnownColors.HasValue && FitnessFunction == FitnessFunction.Prioritized) {
    182188        var mag = Math.Pow(10, -(int)Math.Ceiling(Math.Log10(data.Nodes)));
    183         // the value is e.g. 4.03 for 4 conflicts with 3 colors (and less than 100 nodes)
     189        // the value is e.g. 0.051 for 0 conflicts with 51 colors (and less than 1000 nodes)
    184190        BestKnownQuality = data.BestKnownColors.Value * mag;
     191      } else if (data.BestKnownColoring != null && FitnessFunction == FitnessFunction.Prioritized) {
     192        var mag = Math.Pow(10, -(int)Math.Ceiling(Math.Log10(data.Nodes)));
     193        var colors = data.BestKnownColoring.Distinct().Count();
     194        BestKnownQuality = colors * mag;
     195      } else if (data.BestKnownColoring != null && FitnessFunction == FitnessFunction.Penalized) {
     196        var colors = data.BestKnownColoring.GroupBy(x => x).Select(x => x.Count());
     197        BestKnownQuality = -colors.Sum(x => x * x);
    185198      } else BestKnownQualityParameter.Value = null;
    186199      Name = data.Name;

  • branches/MemPRAlgorithm/HeuristicLab.Problems.Instances/3.3/Types/GCPData.cs

    r14471 r14496  
    4848    public int[] BestKnownColoring { get; set; }
    4949    /// <summary>
    50     /// Optional! The quality value of the <see cref="BestKnownColoring"/>
     50    /// Optional! The least amount of colors that would not result in conflicts.
     51    /// The amount of colors in <see cref="BestKnownColoring"/> if it is given as well.
    5152    /// </summary>
    52     public double? BestKnownColors { get; set; }
     53    public int? BestKnownColors { get; set; }
    5354  }
    5455}
Note: See TracChangeset for help on using the changeset viewer.