Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/31/12 15:17:16 (12 years ago)
Author:
abeham
Message:

#1614

  • updated gqap (finished path-relinking)
  • fixed some bugs
Location:
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common/3.3
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common/3.3/ExtensionMethods.cs

    r7415 r7432  
    2828  public static class ExtensionMethods {
    2929
    30     /// <summary>
    31     /// Selects an element from an enumerable randomly with equal probability for each element. If the sequence is empty, selected will be false and default(T) will be returned.
    32     /// </summary>
    33     /// <typeparam name="T">The type of the items that are to be selected.</typeparam>
    34     /// <param name="source">The enumerable that contains the items.</param>
    35     /// <param name="random">The random number generator, its NextDouble() method must return a value in the range [0;1).</param>
    36     /// <param name="selected">True if an element was selected, false otherwise (only because of an empty sequence).</param>
    37     /// <returns>The selected item.</returns>
    38     public static T ChooseRandomOrDefault<T>(this IEnumerable<T> source, IRandom random, out bool selected) {
    39       if (source == null) throw new ArgumentNullException("SelectRandomOrDefault: source is null");
    40       uint counter = 1;
    41       selected = false;
    42       T selectedItem = default(T);
    43       foreach (T item in source) {
    44         if (counter * random.NextDouble() < 1.0) { // use multiplication instead of division
    45           selectedItem = item;
    46           selected = true;
    47         }
    48         counter++;
    49       }
    50       return selectedItem;
    51     }
    52 
    53     /// <summary>
    54     /// Selects an element from an enumerable randomly with equal probability for each element.
    55     /// </summary>
    56     /// <typeparam name="T">The type of the items that are to be selected.</typeparam>
    57     /// <param name="source">The enumerable that contains the items.</param>
    58     /// <param name="random">The random number generator, its NextDouble() method must return a value in the range [0;1).</param>
    59     /// <returns>The selected item.</returns>
    60     public static T ChooseRandom<T>(this IEnumerable<T> source, IRandom random) {
    61       if (source == null) throw new ArgumentNullException("SelectRandom: source is null");
    62       if (!source.Any()) throw new ArgumentException("SelectRandom: sequence is empty.");
    63       uint counter = 1;
    64       T selectedItem = default(T);
    65       foreach (T item in source) {
    66         if (counter * random.NextDouble() < 1.0) // use multiplication instead of division
    67           selectedItem = item;
    68         counter++;
    69       }
    70       return selectedItem;
    71     }
    72 
    73     /// <summary>
    74     /// Shuffles an enumerable and returns an new enumerable according to the Fisher-Yates shuffle.
    75     /// </summary>
    76     /// <remarks>
    77     /// Source code taken from http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm.
    78     /// Note that this is an online shuffle, but the source enumerable is transformed into an array.
    79     /// </remarks>
    80     /// <typeparam name="T">The type of the items that are to be shuffled.</typeparam>
    81     /// <param name="source">The enumerable that contains the items.</param>
    82     /// <param name="random">The random number generator, its Next(int) method must deliver uniformly distributed random numbers.</param>
    83     /// <returns>An enumerable with the elements shuffled.</returns>
    84     public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, IRandom random) {
    85       T[] elements = source.ToArray();
    86       // Note i > 0 to avoid final pointless iteration
    87       for (int i = elements.Length - 1; i > 0; i--) {
    88         // Swap element "i" with a random earlier element it (or itself)
    89         int swapIndex = random.Next(i + 1);
    90         yield return elements[swapIndex];
    91         elements[swapIndex] = elements[i];
    92         // we don't actually perform the swap, we can forget about the
    93         // swapped element because we already returned it.
    94       }
    95 
    96       // there is one item remaining that was not returned - we return it now
    97       yield return elements[0];
    98     }
     30    #region Choosing from a sequence
     31    /// <summary>
     32    /// Chooses one elements from a sequence under equal chances for each element.
     33    /// </summary>
     34    /// <remarks>
     35    /// Runtime complexity is O(1) for sequences that are <see cref="IList{T}"/> and
     36    /// O(N) for all other.
     37    /// </remarks>
     38    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     39    /// <param name="source">The sequence of elements.</param>
     40    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     41    /// <param name="count">The number of items to be selected.</param>
     42    /// <returns>A sequence of elements that have been chosen randomly.</returns>
     43    public static T ChooseUniformRandom<T>(this IEnumerable<T> source, IRandom random) {
     44      return source.ChooseUniformRandom(random, 1).First();
     45    }
     46    /// <summary>
     47    /// Chooses <paramref name="count"/> elements from a sequence with repetition under equal chances for each element.
     48    /// </summary>
     49    /// <remarks>
     50    /// Runtime complexity is O(count) for sequences that are <see cref="IList{T}"/> and
     51    /// O(N * count) for all other.
     52    ///
     53    /// The method is online.
     54    /// </remarks>
     55    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     56    /// <param name="source">The sequence of elements.</param>
     57    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     58    /// <param name="count">The number of items to be selected.</param>
     59    /// <returns>A sequence of elements that have been chosen randomly.</returns>
     60    public static IEnumerable<T> ChooseUniformRandom<T>(this IEnumerable<T> source, IRandom random, int count) {
     61      if (source == null) throw new ArgumentNullException("source", "sequence is null");
     62      if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");
     63
     64      var listSource = source as IList<T>;
     65      if (listSource != null)
     66        while (count > 0) {
     67          yield return listSource[random.Next(listSource.Count)];
     68          count--;
     69        }
     70
     71      while (count > 0) {
     72        var enumerator = source.GetEnumerator();
     73        enumerator.MoveNext();
     74        T selectedItem = enumerator.Current;
     75        int counter = 1;
     76        while (enumerator.MoveNext()) {
     77          counter++;
     78          if (counter * random.NextDouble() < 1.0)
     79            selectedItem = enumerator.Current;
     80        }
     81        yield return selectedItem;
     82        count--;
     83      }
     84    }
     85    /// <summary>
     86    /// Chooses <paramref name="count"/> elements from a sequence without repetition under equal chances for each element.
     87    /// </summary>
     88    /// <remarks>
     89    /// Runtime complexity is O(count) for sequences that are <see cref="IList{T}"/> and
     90    /// O(N * count) for all other.
     91    ///
     92    /// The method is online, but the source enumerable is transformed into an array.
     93    /// </remarks>
     94    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     95    /// <param name="source">The sequence of elements.</param>
     96    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     97    /// <param name="count">The number of items to be selected.</param>
     98    /// <returns>A sequence of elements that have been chosen randomly.</returns>
     99    public static IEnumerable<T> ChooseUniformRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count) {
     100      return source.Shuffle(random).Take(count);
     101    }
     102
     103    /// <summary>
     104    /// Chooses items out of a sequence with repetition. The chance that an item is selected is proportional or inverse-proportional
     105    /// to the value obtained from <paramref name="valueSelector"/>.
     106    /// </summary>
     107    /// <remarks>
     108    /// In case both <paramref name="maximization"/> and <paramref name="windowing"/> are false values must be &gt; 0,
     109    /// otherwise an InvalidOperationException is thrown.
     110    ///
     111    /// The method is online, but internally holds two arrays: One that is the sequence itself and another one for the values. The <paramref name="valueSelector"/>
     112    /// is only applied once for each item.
     113    /// </remarks>
     114    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     115    /// <param name="source">The sequence of elements.</param>
     116    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     117    /// <param name="count">The number of items to be selected.</param>
     118    /// <param name="valueSelector">The function that calculates a proportional value for each item.</param>
     119    /// <param name="windowing">Whether to scale the proportional values or not.</param>
     120    /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
     121    /// <returns>A sequence of selected items. The sequence might contain the same item more than once.</returns>
     122    public static IEnumerable<T> ChooseProportionalRandom<T>(this IEnumerable<T> source, IRandom random, int count, Func<T, double> valueSelector, bool windowing, bool maximization) {
     123      return source.ChooseProportionalRandom(random, valueSelector, windowing, maximization).Take(count);
     124    }
     125    /// <summary>
     126    /// Same as <seealso cref="ChooseProportionalRandom<T>"/>, but selects each item exactly once.
     127    /// </summary>
     128    /// <remarks>
     129    /// In case both <paramref name="maximization"/> and <paramref name="windowing"/> are false values must be &gt; 0,
     130    /// otherwise an InvalidOperationException is thrown.
     131    ///
     132    /// The method is online, but internally holds two arrays: One that is the sequence itself and another one for the values. The <paramref name="valueSelector"/>
     133    /// is only applied once for each item.
     134    /// </remarks>
     135    /// <typeparam name="T">The type of the items to be selected.</typeparam>
     136    /// <param name="source">The sequence of elements.</param>
     137    /// <param name="random">The random number generator to use, its NextDouble() method must produce values in the range [0;1)</param>
     138    /// <param name="count">The number of items to be selected.</param>
     139    /// <param name="valueSelector">The function that calculates a proportional value for each item.</param>
     140    /// <param name="windowing">Whether to scale the proportional values or not.</param>
     141    /// <param name="maximization">Determines whether to choose proportionally (true) or inverse-proportionally (false).</param>
     142    /// <returns>A sequence of selected items.</returns>
     143    public static IEnumerable<T> ChooseProportionalRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, int count, Func<T, double> valueSelector, bool windowing, bool maximization) {
     144      return source.ChooseProportionalRandomWithoutRepetition(random, valueSelector, windowing, maximization).Take(count);
     145    }
     146    #region Proportional Helpers
     147    private static IEnumerable<T> ChooseProportionalRandom<T>(this IEnumerable<T> source, IRandom random, Func<T, double> valueSelector, bool windowing, bool maximization) {
     148      if (source == null) throw new ArgumentNullException("source", "sequence is null");
     149      if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");
     150
     151      var sourceArray = source.ToArray();
     152      var valueArray = PrepareProportional<T>(sourceArray, valueSelector, windowing, maximization);
     153      double total = valueArray.Sum();
     154
     155      while (true) {
     156        int index = 0;
     157        double ball = valueArray[index], sum = random.NextDouble() * total;
     158        while (ball < sum)
     159          ball += valueArray[++index];
     160        yield return sourceArray[index];
     161      }
     162    }
     163    private static IEnumerable<T> ChooseProportionalRandomWithoutRepetition<T>(this IEnumerable<T> source, IRandom random, Func<T, double> valueSelector, bool windowing, bool maximization) {
     164      if (source == null) throw new ArgumentNullException("source", "sequence is null");
     165      if (!source.Any()) throw new ArgumentException("sequence is empty.", "source");
     166
     167      var sourceArray = source.ToArray();
     168      var valueArray = PrepareProportional<T>(sourceArray, valueSelector, windowing, maximization);
     169      double total = valueArray.Sum();
     170
     171      HashSet<int> chosenIndices = new HashSet<int>();
     172      while (chosenIndices.Count < sourceArray.Length) {
     173        int index = 0;
     174        double ball = valueArray[index], sum = random.NextDouble() * total;
     175        while (ball < sum) {
     176          index++;
     177          if (!chosenIndices.Contains(index))
     178            ball += valueArray[++index];
     179        }
     180        yield return sourceArray[index];
     181        chosenIndices.Add(index);
     182        total -= valueArray[index];
     183      }
     184    }
     185    private static double[] PrepareProportional<T>(IList<T> sourceArray, Func<T, double> valueSelector, bool windowing, bool maximization) {
     186      double maxValue = double.MinValue, minValue = double.MaxValue;
     187      double[] valueArray = new double[sourceArray.Count];
     188
     189      for (int i = 0; i < sourceArray.Count; i++) {
     190        valueArray[i] = valueSelector(sourceArray[i]);
     191        if (valueArray[i] > maxValue) maxValue = valueArray[i];
     192        if (valueArray[i] < minValue) minValue = valueArray[i];
     193      }
     194      if (minValue == maxValue) {  // all values are equal
     195        for (int i = 0; i < sourceArray.Count; i++) {
     196          valueArray[i] = 1.0;
     197        }
     198      } else {
     199        if (windowing) {
     200          if (maximization) ProportionalScale(valueArray, minValue);
     201          else InverseProportionalScale(valueArray, maxValue);
     202        } else {
     203          if (minValue < 0.0) throw new InvalidOperationException("Proportional selection without windowing does not work with values < 0.");
     204          if (!maximization) InverseProportionalScale(valueArray, 2 * maxValue);
     205        }
     206      }
     207      return valueArray;
     208    }
     209    private static void ProportionalScale(double[] values, double minValue) {
     210      for (int i = 0; i < values.Length; i++) {
     211        values[i] = values[i] - minValue;
     212      }
     213    }
     214    private static void InverseProportionalScale(double[] values, double maxValue) {
     215      for (int i = 0; i < values.Length; i++) {
     216        values[i] = maxValue - values[i];
     217      }
     218    }
     219    #endregion
    99220
    100221    /// <summary>
    … …  
    109230    /// <param name="keySelector">The function that selects the key.</param>
    110231    /// <returns>The element in the enumeration where the selected key is the maximum.</returns>
    111     public static T SelectMax<T, TComparable>(this IEnumerable<T> source, Func<T, TComparable> keySelector) where TComparable : IComparable {
     232    public static T ChooseMax<T, TComparable>(this IEnumerable<T> source, Func<T, TComparable> keySelector) where TComparable : IComparable {
     233      if (source == null) throw new ArgumentNullException("source", "sequence is null");
    112234      IEnumerator<T> enumerator = source.GetEnumerator();
    113       if (!enumerator.MoveNext()) throw new InvalidOperationException("Sequence is empty!");
     235      if (!enumerator.MoveNext()) throw new ArgumentException("sequence is empty", "source");
    114236      T result = enumerator.Current;
    115237      TComparable max = keySelector(result);
    … …  
    136258    /// <param name="keySelector">The function that selects the key.</param>
    137259    /// <returns>The element in the enumeration where the selected key is the minimum.</returns>
    138     public static T SelectMin<T, TComparable>(this IEnumerable<T> source, Func<T, TComparable> keySelector) where TComparable : IComparable {
     260    public static T ChooseMin<T, TComparable>(this IEnumerable<T> source, Func<T, TComparable> keySelector) where TComparable : IComparable {
     261      if (source == null) throw new ArgumentNullException("source", "sequence is null");
    139262      IEnumerator<T> enumerator = source.GetEnumerator();
    140       if (!enumerator.MoveNext()) throw new InvalidOperationException("Sequence is empty!");
     263      if (!enumerator.MoveNext()) throw new ArgumentException("sequence is empty", "source");
    141264      T result = enumerator.Current;
    142265      TComparable min = keySelector(result);
    … …  
    151274      return result;
    152275    }
    153 
     276    #endregion
     277
     278    #region Shuffling
     279    /// <summary>
     280    /// Shuffles an enumerable and returns a new enumerable according to the Fisher-Yates shuffle.
     281    /// </summary>
     282    /// <remarks>
     283    /// Note that this is an online shuffle, but the source enumerable is transformed into an array.
     284    ///
     285    /// The implementation is described in http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm.
     286    /// </remarks>
     287    /// <typeparam name="T">The type of the items that are to be shuffled.</typeparam>
     288    /// <param name="source">The enumerable that contains the items.</param>
     289    /// <param name="random">The random number generator, its Next(n) method must deliver uniformly distributed random numbers in the range [0;n).</param>
     290    /// <returns>An enumerable with the elements shuffled.</returns>
     291    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, IRandom random) {
     292      T[] elements = source.ToArray();
     293      for (int i = elements.Length - 1; i > 0; i--) {
     294        // Swap element "i" with a random earlier element it (or itself)
     295        int swapIndex = random.Next(i + 1);
     296        yield return elements[swapIndex];
     297        elements[swapIndex] = elements[i];
     298        // we don't actually perform the swap, we can forget about the
     299        // swapped element because we already returned it.
     300      }
     301      yield return elements[0];
     302    }
     303    #endregion
     304
     305    #region Graph walk
    154306    /// <summary>
    155307    /// Walks an operator graph in that it jumps from one operator to all its operator parameters and yields each operator it touches.
    … …  
    178330      }
    179331    }
    180 
     332    #endregion
    181333  }
    182334}

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common/3.3/IntegerVectorEqualityComparer.cs

    r7412 r7432  
    3838      return obj.GetHashCode();
    3939    }
     40
     41    public static double GetSimilarity(IntegerVector a, IntegerVector b) {
     42      int similar = 0;
     43      for (int i = 0; i < a.Length; i++) {
     44        if (a[i] == b[i]) similar++;
     45      }
     46      return similar / (double)a.Length;
     47    }
     48
     49    public static double GetDistance(IntegerVector a, IntegerVector b) {
     50      return 1.0 - GetSimilarity(a, b);
     51    }
     52
     53    public static IEnumerable<int> GetDifferingIndices(IntegerVector a, IntegerVector b) {
     54      for (int i = 0; i < a.Length; i++)
     55        if (a[i] != b[i]) yield return i;
     56    }
    4057  }
    4158}
Note: See TracChangeset for help on using the changeset viewer.