Free cookie consent management tool by TermsFeed Policy Generator

Changeset 10743


Ignore:
Timestamp:
04/11/14 15:05:55 (9 years ago)
Author:
abeham
Message:

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

Location:
stable
Files:
9 edited
1 copied

Legend:

Unmodified
Added
Removed
  • stable

  • stable/HeuristicLab.Problems.VehicleRouting

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

    r10507 r10743  
    3030using HeuristicLab.Parameters;
    3131using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     32using HeuristicLab.Random;
    3233
    3334namespace HeuristicLab.Problems.VehicleRouting.Encodings.General {
     
    140141      if (checkedOperators.Count() > 0) {
    141142        // select a random operator from the checked operators
    142         double sum = (from indexedItem in checkedOperators select probabilities[indexedItem.Index]).Sum();
    143         if (sum == 0) throw new InvalidOperationException(Name + ": All selected operators have zero probability.");
    144         double r = random.NextDouble() * sum;
    145         sum = 0;
    146         foreach (var indexedItem in checkedOperators) {
    147           sum += probabilities[indexedItem.Index];
    148           if (sum > r) {
    149             successor = indexedItem.Value;
    150             break;
    151           }
    152         }
     143        successor = checkedOperators.SampleProportional(random, 1, probabilities, false, false).First().Value;
    153144      }
    154145
  • stable/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Manipulators/BiasedMultiVRPSolutionManipulator.cs

    r10507 r10743  
    3030using HeuristicLab.Parameters;
    3131using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     32using HeuristicLab.Random;
    3233
    3334namespace HeuristicLab.Problems.VehicleRouting.Encodings.General {
     
    140141      if (checkedOperators.Count() > 0) {
    141142        // select a random operator from the checked operators
    142         double sum = (from indexedItem in checkedOperators select probabilities[indexedItem.Index]).Sum();
    143         if (sum == 0) throw new InvalidOperationException(Name + ": All selected operators have zero probability.");
    144         double r = random.NextDouble() * sum;
    145         sum = 0;
    146         foreach (var indexedItem in checkedOperators) {
    147           sum += probabilities[indexedItem.Index];
    148           if (sum > r) {
    149             successor = indexedItem.Value;
    150             break;
    151           }
    152         }
     143        successor =
     144          checkedOperators.SampleProportional(random, 1, probabilities, false, false).First().Value;
    153145      }
    154146
  • stable/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

    r8894 r10743  
    465465      <Private>False</Private>
    466466    </ProjectReference>
     467    <ProjectReference Include="..\..\HeuristicLab.Random\3.3\HeuristicLab.Random-3.3.csproj">
     468      <Project>{F4539FB6-4708-40C9-BE64-0A1390AEA197}</Project>
     469      <Name>HeuristicLab.Random-3.3</Name>
     470    </ProjectReference>
    467471  </ItemGroup>
    468472  <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
  • stable/HeuristicLab.Problems.VehicleRouting/3.4/Plugin.cs.frame

    r10032 r10743  
    4141  [PluginDependency("HeuristicLab.Persistence", "3.3")]
    4242  [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
     43  [PluginDependency("HeuristicLab.Random", "3.3")]
    4344  public class HeuristicLabProblemsVehicleRoutingPlugin : PluginBase {
    4445  }
  • stable/HeuristicLab.Random/3.3/RandomEnumerable.cs

    r9456 r10743  
    3636
    3737    //algorithm taken from progamming pearls page 127
    38     //IMPORTANT because IEnumerables with yield are used the seed must best be specified to return always
     38    //IMPORTANT because IEnumerables with yield are used the seed must be specified to return always
    3939    //the same sequence of numbers without caching the values.
    4040    public static IEnumerable<int> SampleRandomNumbers(int seed, int start, int end, int count) {
     
    166166    ///
    167167    /// The method internally holds two arrays: One that is the sequence itself and another one for the values.
     168    ///
     169    /// The method does not check if the number of elements in source and weights are the same.
    168170    /// </remarks>
    169171    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     
    173175    /// <param name="weights">The weight values for the items.</param>
    174176    /// <param name="windowing">Whether to scale the proportional values or not.</param>
    175     /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
    176     /// <returns>A sequence of selected items.</returns>
     177    /// <param name="inverseProportional">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
     178    /// <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>
    177179    public static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, IEnumerable<double> weights, bool windowing = true, bool inverseProportional = false) {
    178180      return source.SampleProportionalWithoutRepetition(random, weights, windowing, inverseProportional).Take(count);
     
    181183    private static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
    182184      var sourceArray = source.ToArray();
    183       var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
     185      var valueArray = PrepareProportional(sourceArray, weights, windowing, inverseProportional);
    184186      double total = valueArray.Sum();
    185187
     
    193195    }
    194196    private static IEnumerable<T> SampleProportionalWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
    195       var sourceArray = source.ToArray();
    196       var valueArray = PrepareProportional<T>(sourceArray, weights, windowing, inverseProportional);
     197      var valueArray = PrepareProportional(source.ToArray(), weights, windowing, inverseProportional);
     198      var list = new LinkedList<Tuple<T, double>>(source.Zip(valueArray, Tuple.Create));
    197199      double total = valueArray.Sum();
    198200
    199       HashSet<int> chosenIndices = new HashSet<int>();
    200       while (chosenIndices.Count < sourceArray.Length) {
    201         int index = 0;
    202         double ball = valueArray[index], sum = random.NextDouble() * total;
     201      while (list.Count > 0) {       
     202        var cur = list.First;       
     203        double ball = cur.Value.Item2, sum = random.NextDouble() * total; // assert: sum < total. When there is only one item remaining: sum < ball
    203204        while (ball < sum) {
    204           index++;
    205           if (!chosenIndices.Contains(index))
    206             ball += valueArray[++index];
    207         }
    208         yield return sourceArray[index];
    209         chosenIndices.Add(index);
    210         total -= valueArray[index];
    211       }
    212     }
     205          cur = cur.Next;
     206          ball += cur.Value.Item2;
     207        }
     208        yield return cur.Value.Item1;
     209        list.Remove(cur);
     210        total -= cur.Value.Item2;
     211      }
     212    }
     213
    213214    private static double[] PrepareProportional<T>(IList<T> sourceArray, IEnumerable<double> weights, bool windowing, bool inverseProportional) {
    214215      double maxValue = double.MinValue, minValue = double.MaxValue;
     
    274275  }
    275276}
     277
  • stable/HeuristicLab.Tests

  • stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r9979 r10743  
    464464    <Compile Include="HeuristicLab.Problems.TravelingSalesman-3.3\TSPMoveEvaluatorTest.cs" />
    465465    <Compile Include="HeuristicLab.Problems.LinearAssignment-3.3\LinearAssignmentProblemSolverTest.cs" />
     466    <Compile Include="HeuristicLab.Random-3.3\RandomEnumerableSampleTest.cs" />
    466467    <Compile Include="Properties\AssemblyInfo.cs" />
    467468    <Compile Include="TestRandom.cs" />
Note: See TracChangeset for help on using the changeset viewer.