Changeset 10743

Timestamp:

04/11/14 15:05:55 (11 years ago)

Author:

abeham

Message:

#2146: merged r10407,r10465,r10466,r10474,r10503,r10504,r10646 into stable

Location:

stable

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.VehicleRouting (modified) (1 prop)
• HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Crossovers/BiasedMultiVRPSolutionCrossover.cs (modified) (2 diffs)
• HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Manipulators/BiasedMultiVRPSolutionManipulator.cs (modified) (2 diffs)
• HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.VehicleRouting/3.4/Plugin.cs.frame (modified) (1 diff)
• HeuristicLab.Random/3.3/RandomEnumerable.cs (modified) (6 diffs)
• HeuristicLab.Tests (modified) (1 prop)
• HeuristicLab.Tests/HeuristicLab.Random-3.3 (copied) (copied from trunk/sources/HeuristicLab.Tests/HeuristicLab.Random-3.3)
• HeuristicLab.Tests/HeuristicLab.Tests.csproj (modified) (1 diff)

stable/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Crossovers/BiasedMultiVRPSolutionCrossover.cs

@@ -30 +30 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.General {
@@ -140 +141 @@
       if (checkedOperators.Count() > 0) {
         // select a random operator from the checked operators
-        double sum = (from indexedItem in checkedOperators select probabilities[indexedItem.Index]).Sum();
-        if (sum == 0) throw new InvalidOperationException(Name + ": All selected operators have zero probability.");
-        double r = random.NextDouble() * sum;
-        sum = 0;
-        foreach (var indexedItem in checkedOperators) {
-          sum += probabilities[indexedItem.Index];
-          if (sum > r) {
-            successor = indexedItem.Value;
-            break;
-          }
-        }
+        successor = checkedOperators.SampleProportional(random, 1, probabilities, false, false).First().Value;
       }
 

stable/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Manipulators/BiasedMultiVRPSolutionManipulator.cs

@@ -30 +30 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.General {
@@ -140 +141 @@
       if (checkedOperators.Count() > 0) {
         // select a random operator from the checked operators
-        double sum = (from indexedItem in checkedOperators select probabilities[indexedItem.Index]).Sum();
-        if (sum == 0) throw new InvalidOperationException(Name + ": All selected operators have zero probability.");
-        double r = random.NextDouble() * sum;
-        sum = 0;
-        foreach (var indexedItem in checkedOperators) {
-          sum += probabilities[indexedItem.Index];
-          if (sum > r) {
-            successor = indexedItem.Value;
-            break;
-          }
-        }
+        successor =
+          checkedOperators.SampleProportional(random, 1, probabilities, false, false).First().Value;
       }
 

stable/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

@@ -465 +465 @@
       <Private>False</Private>
     </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Random\3.3\HeuristicLab.Random-3.3.csproj">
+      <Project>{F4539FB6-4708-40C9-BE64-0A1390AEA197}</Project>
+      <Name>HeuristicLab.Random-3.3</Name>
+    </ProjectReference>
   </ItemGroup>
   <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />

stable/HeuristicLab.Problems.VehicleRouting/3.4/Plugin.cs.frame

@@ -41 +41 @@
   [PluginDependency("HeuristicLab.Persistence", "3.3")]
   [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
+  [PluginDependency("HeuristicLab.Random", "3.3")]
   public class HeuristicLabProblemsVehicleRoutingPlugin : PluginBase {
   }

stable/HeuristicLab.Random/3.3/RandomEnumerable.cs

@@ -36 +36 @@
 
     //algorithm taken from progamming pearls page 127
-    //IMPORTANT because IEnumerables with yield are used the seed must best be specified to return always 
+    //IMPORTANT because IEnumerables with yield are used the seed must be specified to return always 
     //the same sequence of numbers without caching the values.
     public static IEnumerable<int> SampleRandomNumbers(int seed, int start, int end, int count) {
@@ -166 +166 @@
     /// 
     /// The method internally holds two arrays: One that is the sequence itself and another one for the values.
+    /// 
+    /// The method does not check if the number of elements in source and weights are the same.
     /// </remarks>
     /// <typeparam name="T">The type of the items to be selected.</typeparam>
@@ -173 +175 @@
     /// <param name="weights">The weight values for the items.</param>
     /// <param name="windowing">Whether to scale the proportional values or not.</param>
-    /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
-    /// <returns>A sequence of selected items.</returns>
+    /// <param name="inverseProportional">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
+    /// <returns>A sequence of selected items. Might actually be shorter than <paramref name="count"/> elements if source has less than <paramref name="count"/> elements.</returns>
     public static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {
       return source.SampleProportionalWithoutRepetition(random, weights, windowing, inverseProportional).Take(count);
@@ -181 +183 @@
     private static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
       var sourceArray = source.ToArray();
-      var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
+      var valueArray = PrepareProportional(sourceArray, weights, windowing, inverseProportional);
       double total = valueArray.Sum();
 
@@ -193 +195 @@
     }
     private static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
-      var sourceArray = source.ToArray();
-      var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
+      var valueArray = PrepareProportional(source.ToArray(), weights, windowing, inverseProportional);
+      var list = new LinkedList<Tuple<T, double>>(source.Zip(valueArray, Tuple.Create));
       double total = valueArray.Sum();
 
-      HashSet<int> chosenIndices = new HashSet<int>();
-      while (chosenIndices.Count < sourceArray.Length) {
-        int index = 0;
-        double ball = valueArray[index], sum = random.NextDouble() * total;
+      while (list.Count > 0) {        
+        var cur = list.First;        
+        double ball = cur.Value.Item2, sum = random.NextDouble() * total; // assert: sum < total. When there is only one item remaining: sum < ball
         while (ball < sum) {
-          index++;
-          if (!chosenIndices.Contains(index))
-            ball += valueArray[++index];
-        }
-        yield return sourceArray[index];
-        chosenIndices.Add(index);
-        total -= valueArray[index];
-      }
-    }
+          cur = cur.Next;
+          ball += cur.Value.Item2;
+        }
+        yield return cur.Value.Item1;
+        list.Remove(cur);
+        total -= cur.Value.Item2;
+      }
+    }
+
     private static double[] PrepareProportional<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
       double maxValue = double.MinValue, minValue = double.MaxValue;
@@ -274 +275 @@
   }
 }
+

stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj

@@ -464 +464 @@
     <Compile Include="HeuristicLab.Problems.TravelingSalesman-3.3\TSPMoveEvaluatorTest.cs" />
     <Compile Include="HeuristicLab.Problems.LinearAssignment-3.3\LinearAssignmentProblemSolverTest.cs" />
+    <Compile Include="HeuristicLab.Random-3.3\RandomEnumerableSampleTest.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="TestRandom.cs" />