Changeset 7775 for branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack

Timestamp:

05/02/12 19:09:48 (13 years ago)

Author:

jkarder

Message:

#1331:

• added operators for TestFunctions problems
• added more path relinking operators for the TravelingSalesman and the Knapsack problem
• added 2-tier version of the SolutionPoolUpdateMethod
• added parameters and adjusted types
• added some exception handling
• adjusted event handling
• updated plugin dependencies
• minor code improvements

Location:

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack

Files:

• BinaryVectorDiversityCalculator.cs (modified) (2 diffs)
• KnapsackImprovementOperator.cs (modified) (7 diffs)
• KnapsackMultipleGuidesPathRelinker.cs (added)
• KnapsackPathRelinker.cs (modified) (2 diffs)
• KnapsackSimultaneousPathRelinker.cs (added)
• NBinaryVectorCrossover.cs (modified) (1 diff)
• NChildCrossover.cs (modified) (3 diffs)

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/BinaryVectorDiversityCalculator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -41 +42 @@
     }
 
-    protected override int CalculateDiversity(IItem left, IItem right) {
+    protected override double CalculateDiversity(IItem left, IItem right) {
+      if (!(left is BinaryVector) || !(right is BinaryVector))
+        throw new ArgumentException("Cannot calculate diversity because one of the provided objects or both have the wrong type.");
+
       var v1 = left as BinaryVector;
       var v2 = right as BinaryVector;
-      int diversity = 0;
-      if (v1 != null && v2 != null)
-        for (int i = 0; i < v1.Length; i++)
-          if (v1[i] != v2[i]) diversity++;
+      double diversity = 0;
+      for (int i = 0; i < v1.Length; i++)
+        if (v1[i] != v2[i]) diversity++;
       return diversity;
     }

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/KnapsackImprovementOperator.cs

@@ -67 +67 @@
       get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
     }
+    public IValueLookupParameter<DoubleValue> PenaltyParameter {
+      get { return (IValueLookupParameter<DoubleValue>)Parameters["Penalty"]; }
+    }
     #region ILocalImprovementOperator Parameters
     public IValueLookupParameter<IntValue> MaximumIterationsParameter {
@@ -99 +102 @@
       get { return TargetParameter.ActualValue; }
     }
+    private DoubleValue Penalty {
+      get { return PenaltyParameter.ActualValue; }
+      set { PenaltyParameter.ActualValue = value; }
+    }
     #endregion
 
@@ -115 +122 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("KnapsackCapacity"));
       Parameters.Add(new ValueLookupParameter<IItem>("Target"));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("Penalty"));
       #endregion
       TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
@@ -128 +136 @@
       // calculate value-to-weight ratio
       double[] ratio = new double[Values.Length];
-      for (int i = 0; i < ratio.Length; i++) {
+      for (int i = 0; i < ratio.Length; i++)
         ratio[i] = (double)Values[i] / (double)Weights[i];
-      }
+
 
       // calculate order for ratio
@@ -140 +148 @@
 
       int j = sol.Length - 1;
-      while (KnapsackEvaluator.Apply(sol, KnapsackCapacity, new DoubleValue(1.0), Weights, Values).SumWeights.Value > KnapsackCapacity.Value && j >= 0) {
+      while (KnapsackEvaluator.Apply(sol, KnapsackCapacity, Penalty, Weights, Values)
+                              .SumWeights.Value > KnapsackCapacity.Value && j >= 0)
         sol[order[j--]] = false;
-      }
 
       // calculate weight
-      int lhs = 0;
-      for (int i = 0; i < sol.Length; i++) {
-        if (sol[i]) lhs += Weights[i];
-      }
+      int weight = 0;
+      for (int i = 0; i < sol.Length; i++)
+        if (sol[i]) weight += Weights[i];
 
       // improve solution
@@ -154 +161 @@
       while (feasible && j < sol.Length) {
         while (sol[order[j]]) j++;
-        if (lhs + Weights[order[j]] <= KnapsackCapacity.Value) {
+        if (weight + Weights[order[j]] <= KnapsackCapacity.Value) {
           sol[order[j]] = true;
-          lhs += Weights[order[j]];
-        } else {
-          feasible = false;
-        }
+          weight += Weights[order[j]];
+        } else feasible = false;
       }
 
@@ -166 +171 @@
       return base.Apply();
     }
-
-    private bool IsFeasiblse(BinaryVector sol) {
-      int sum = 0;
-      for (int i = 0; i < sol.Length; i++)
-        if (sol[i]) sum += Weights[i];
-      return sum <= KnapsackCapacity.Value;
-    }
   }
 }

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/KnapsackPathRelinker.cs

@@ -49 +49 @@
 
     public static ItemArray<IItem> Apply(IItem initiator, IItem guide, PercentValue n) {
+      if (!(initiator is BinaryVector) || !(guide is BinaryVector))
+        throw new ArgumentException("Cannot relink path because one of the provided solutions or both have the wrong type.");
+      if (n.Value <= 0.0)
+        throw new ArgumentException("RelinkingAccuracy must be greater than 0.");
+
       var v1 = initiator.Clone() as BinaryVector;
       var v2 = guide as BinaryVector;
 
       if (v1.Length != v2.Length)
-        throw new ArgumentException("KnapsackPathRelinker: The solutions are of different length.");
-      if (n.Value == 0.0)
-        throw new ArgumentException("KnapsackPathRelinker: RelinkingAccuracy is 0.");
+        throw new ArgumentException("The solutions are of different length.");
 
       var solutions = new List<BinaryVector>();
-      for (int i = 0; i < v1.Length; i++) {
+      for (int i = 0; i < v1.Length; i++)
         if (v1[i] != v2[i]) {
           v1[i] = v2[i];
-          solutions.Add((BinaryVector)v1.Clone());
+          solutions.Add(v1.Clone() as BinaryVector);
         }
-      }
 
-      var stepSize = 1 / n.Value;
       var selection = new List<IItem>();
-      for (int i = 0; i < solutions.Count; i = (int)Math.Round(i + stepSize)) {
-        selection.Add(solutions.ElementAt(i));
+      if (solutions.Count > 0) {
+        var noSol = (int)Math.Round(solutions.Count * n.Value);
+        if (noSol <= 0) noSol++;
+        var stepSize = (double)solutions.Count / (double)noSol;
+        for (int i = 0; i < noSol; i++)
+          selection.Add(solutions.ElementAt((int)Math.Round((i + 1) * stepSize - stepSize * 0.5)));
       }
 
@@ -75 +80 @@
 
     protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
-      if (parents.Length != 2) throw new ArgumentException("KnapsackPathRelinker: The number of parents is not equal to 2.");
+      if (parents.Length != 2)
+        throw new ArgumentException("The number of parents is not equal to 2.");
       return Apply(parents[0], parents[1], n);
     }

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/NBinaryVectorCrossover.cs

@@ -72 +72 @@
     public sealed override IOperation Apply() {
       var offspringSolutions = Cross(RandomParameter.ActualValue, ParentsParameter.ActualValue);
-      for (int i = 0; i < offspringSolutions.Length; i++) {
+      for (int i = 0; i < offspringSolutions.Length; i++)
         CurrentScope.Variables.Add(new Variable(string.Format("Child {0}", i), offspringSolutions[i]));
-      }
       return base.Apply();
     }

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/NChildCrossover.cs

@@ -58 +58 @@
       if (parent1.Length != parent2.Length)
         throw new ArgumentException("NChildCrossover: The parents are of different length.");
-
       if (n.Value > Math.Pow(2, parent1.Length) - 2)
         throw new ArgumentException("NChildCrossover: There cannot be more children than 2^size of parents - 2.");
-
       if (n.Value < 1)
         throw new ArgumentException("NChildCrossover: N cannot be < 1.");
@@ -68 +66 @@
       for (int i = 0; i < n.Value; i++) {
         var solution = new BinaryVector(parent1.Length);
-        for (int j = 0; j < solution.Length; j++) {
+        for (int j = 0; j < solution.Length; j++)
           solution[j] = random.Next(2) % 2 == 0 ? parent1[j] : parent2[j];
-        }
         solutions[i] = solution;
       }
@@ -78 +75 @@
 
     protected override ItemArray<BinaryVector> Cross(IRandom random, ItemArray<BinaryVector> parents) {
-      if (parents.Length != 2) throw new ArgumentException("NChildCrossover: The number of parents is not equal to 2.");
-
-      if (NParameter.ActualValue == null) throw new InvalidOperationException("NChildCrossover: Parameter " + NParameter.ActualName + " could not be found.");
-
+      if (parents.Length != 2)
+        throw new ArgumentException("NChildCrossover: The number of parents is not equal to 2.");
+      if (NParameter.ActualValue == null)
+        throw new InvalidOperationException("NChildCrossover: Parameter " + NParameter.ActualName + " could not be found.");
       return Apply(random, parents[0], parents[1], NParameter.Value);
     }