Changeset 14466 for branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnivariateSolutionModel.cs

Timestamp:

12/07/16 23:46:29 (7 years ago)

Author:

abeham

Message:

#2701:

• Added MemPR for linear linkage (tabu walk still missing)
• Added graph coloring problem

Location:

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage

Files:

• . (added)
• SolutionModel (added)
• SolutionModel/Univariate (added)
• SolutionModel/Univariate/UnivariateSolutionModel.cs (copied) (copied from branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/SolutionModel/Univariate/UnivariateSolutionModel.cs) (3 diffs)

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnivariateSolutionModel.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
-using System.Linq;
 using HeuristicLab.Algorithms.MemPR.Interfaces;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
-using HeuristicLab.Encodings.BinaryVectorEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Random;
 
-namespace HeuristicLab.Algorithms.MemPR.Binary.SolutionModel.Univariate {
-  [Item("Univariate solution model (binary)", "")]
+namespace HeuristicLab.Algorithms.MemPR.LinearLinkage.SolutionModel.Univariate {
+  [Item("Univariate solution model (linear linkage)", "")]
   [StorableClass]
-  public sealed class UnivariateModel : Item, ISolutionModel<BinaryVector> {
+  public sealed class UnivariateModel : Item, ISolutionModel<Encodings.LinearLinkageEncoding.LinearLinkage> {
     [Storable]
-    public DoubleArray Probabilities { get; set; }
+    public IntMatrix Frequencies { get; set; }
     [Storable]
     public IRandom Random { get; set; }
+    [Storable]
+    public IntValue Maximum { get; set; }
 
     [StorableConstructor]
@@ -44 +43 @@
     private UnivariateModel(UnivariateModel original, Cloner cloner)
       : base(original, cloner) {
-      Probabilities = cloner.Clone(original.Probabilities);
+      Frequencies = cloner.Clone(original.Frequencies);
       Random = cloner.Clone(original.Random);
     }
-    public UnivariateModel(IRandom random, int N) : this(random, Enumerable.Range(0, N).Select(x => 0.5).ToArray()) { }
-    public UnivariateModel(IRandom random, double[] probabilities) {
-      Probabilities = new DoubleArray(probabilities);
+    public UnivariateModel(IRandom random, int[,] frequencies, int max) {
+      Frequencies = new IntMatrix(frequencies);
       Random = random;
+      Maximum = new IntValue(max);
     }
-    public UnivariateModel(IRandom random, DoubleArray probabilties) {
-      Probabilities = probabilties;
+    public UnivariateModel(IRandom random, IntMatrix frequencies, int max) {
+      Frequencies = frequencies;
       Random = random;
+      Maximum = new IntValue(max);
     }
 
@@ -61 +61 @@
     }
 
-    public BinaryVector Sample() {
-      var vec = new BinaryVector(Probabilities.Length);
-      for (var i = 0; i < Probabilities.Length; i++)
-        vec[i] = Random.NextDouble() < Probabilities[i];
-      return vec;
+    public Encodings.LinearLinkageEncoding.LinearLinkage Sample() {
+      var N = Frequencies.Rows;
+      var centroid = new Encodings.LinearLinkageEncoding.LinearLinkage(N);
+      var dict = new Dictionary<int, int>();
+      for (var i = N - 1; i >= 0; i--) {
+        centroid[i] = i; // default be a cluster of your own
+        for (var j = i + 1; j < N; j++) {
+          // try to find a suitable link
+          if (Maximum.Value * Random.NextDouble() < Frequencies[i, j]) {
+            int pred;
+            if (dict.TryGetValue(j, out pred)) {
+              int tmp, k = pred;
+              while (dict.TryGetValue(k, out tmp)) {
+                if (k == tmp) break;
+                k = tmp;
+              }
+              centroid[i] = k;
+            } else centroid[i] = j;
+            dict[centroid[i]] = i;
+            break;
+          }
+        }
+      }
+      return centroid;
     }
 
-    public static ISolutionModel<BinaryVector> CreateWithoutBias(IRandom random, IEnumerable<BinaryVector> population) {
-      double[] model = null;
-      var popSize = 0;
-      foreach (var p in population) {
+    public static ISolutionModel<Encodings.LinearLinkageEncoding.LinearLinkage> Create(IRandom random, IEnumerable<Encodings.LinearLinkageEncoding.LinearLinkage> population) {
+      var iter = population.GetEnumerator();
+      if (!iter.MoveNext()) throw new ArgumentException("Cannot create solution model from empty population.");
+      var popSize = 1;
+      var N = iter.Current.Length;
+      var freq = new int[N, N];
+      do {
+        var current = iter.Current;
         popSize++;
-        if (model == null) model = new double[p.Length];
-        for (var x = 0; x < model.Length; x++) {
-          if (p[x]) model[x]++;
+        foreach (var g in current.GetGroups()) {
+          for (var i = 0; i < g.Count - 1; i++)
+            for (var j = i + 1; j < g.Count; j++) {
+              freq[g[i], g[j]]++;
+              freq[g[j], g[i]]++;
+            }
         }
-      }
-      if (model == null) throw new ArgumentException("Cannot train model from empty population.");
-      // normalize to [0;1]
-      var factor = 1.0 / popSize;
-      for (var x = 0; x < model.Length; x++) {
-        model[x] *= factor;
-      }
-      return new UnivariateModel(random, model);
-    }
-
-    public static ISolutionModel<BinaryVector> CreateWithRankBias(IRandom random, bool maximization, IEnumerable<BinaryVector> population, IEnumerable<double> qualities) {
-      var popSize = 0;
-
-      double[] model = null;
-      var pop = population.Zip(qualities, (b, q) => new { Solution = b, Fitness = q });
-      foreach (var ind in maximization ? pop.OrderBy(x => x.Fitness) : pop.OrderByDescending(x => x.Fitness)) {
-        // from worst to best, worst solution has 1 vote, best solution N votes
-        popSize++;
-        if (model == null) model = new double[ind.Solution.Length];
-        for (var x = 0; x < model.Length; x++) {
-          if (ind.Solution[x]) model[x] += popSize;
-        }
-      }
-      if (model == null) throw new ArgumentException("Cannot train model from empty population.");
-      // normalize to [0;1]
-      var factor = 2.0 / (popSize + 1);
-      for (var i = 0; i < model.Length; i++) {
-        model[i] *= factor / popSize;
-      }
-      return new UnivariateModel(random, model);
-    }
-
-    public static ISolutionModel<BinaryVector> CreateWithFitnessBias(IRandom random, bool maximization, IEnumerable<BinaryVector> population, IEnumerable<double> qualities) {
-      var proportions = RandomEnumerable.PrepareProportional(qualities, true, !maximization);
-      var factor = 1.0 / proportions.Sum();
-      double[] model = null;
-      foreach (var ind in population.Zip(proportions, (p, q) => new { Solution = p, Proportion = q })) {
-        if (model == null) model = new double[ind.Solution.Length];
-        for (var x = 0; x < model.Length; x++) {
-          if (ind.Solution[x]) model[x] += ind.Proportion * factor;
-        }
-      }
-      if (model == null) throw new ArgumentException("Cannot train model from empty population.");
-      return new UnivariateModel(random, model);
+      } while (iter.MoveNext());
+      return new UnivariateModel(random, freq, popSize);
     }
   }