Free cookie consent management tool by TermsFeed Policy Generator

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

#1614

  • updated gqap (finished path-relinking)
  • fixed some bugs
Location:
branches/GeneralizedQAP
Files:
2 deleted
12 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}

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Analyzers/BestGQAPSolutionAnalyzer.cs

    r7423 r7432  
    155155      int bestIndex;
    156156      var tmp = qualities.Select((x, index) => new { Index = index, Value = x.Value });
    157       if (maximization) bestIndex = tmp.SelectMax(x => x.Value).Index;
    158       else bestIndex = tmp.SelectMin(x => x.Value).Index;
     157      if (maximization) bestIndex = tmp.ChooseMax(x => x.Value).Index;
     158      else bestIndex = tmp.ChooseMin(x => x.Value).Index;
    159159
    160160      if (bestKnownQuality == null || HasSolutionImproved(bestKnownQuality.Value, qualities[bestIndex].Value, maximization)) {

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAPAssignment.cs

    r7418 r7432  
    2828
    2929namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
    30   [Item("Generalized QAP Assignment", "Represents a solution to the generalized QAP.")]
     30  [Item("Generalized QAP Assignment", "Represents the solution as well as the problem parameters of a GQAP instance.")]
    3131  [StorableClass]
    3232  public sealed class GQAPAssignment : Item, INotifyPropertyChanged {

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAPAssignmentArchive.cs

    r7418 r7432  
    145145    private GQAPAssignmentArchive(GQAPAssignmentArchive original, Cloner cloner)
    146146      : base(original, cloner) {
     147      solutions = cloner.Clone(original.solutions);
    147148      equipmentNames = cloner.Clone(original.equipmentNames);
    148149      locationNames = cloner.Clone(original.locationNames);

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GeneralizedQuadraticAssignmentProblem.cs

    r7423 r7432  
    142142    private GeneralizedQuadraticAssignmentProblem(GeneralizedQuadraticAssignmentProblem original, Cloner cloner)
    143143      : base(original, cloner) {
    144       AttachEventHandlers();
     144      RegisterEventHandlers();
    145145    }
    146146    public GeneralizedQuadraticAssignmentProblem()
    … …  
    186186
    187187      InitializeOperators();
    188       AttachEventHandlers();
     188      RegisterEventHandlers();
    189189    }
    190190
    … …  
    220220    [StorableHook(HookType.AfterDeserialization)]
    221221    private void AfterDeserialization() {
    222       AttachEventHandlers();
    223     }
    224 
    225     private void AttachEventHandlers() {
     222      RegisterEventHandlers();
     223    }
     224
     225    private void RegisterEventHandlers() {
    226226      Evaluator.QualityParameter.ActualNameChanged += new System.EventHandler(Evaluator_QualityParameter_ActualNameChanged);
    227227      SolutionCreator.AssignmentParameter.ActualNameChanged += new EventHandler(SolutionCreator_IntegerVectorParameter_ActualNameChanged);

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj

    r7419 r7432  
    9797    <Compile Include="GeneralizedQuadraticAssignmentProblem.cs" />
    9898    <Compile Include="GQAPAssignmentArchive.cs" />
    99     <Compile Include="GQAPIntegerVectorProximityCalculator.cs" />
    10099    <Compile Include="GQAPSolution.cs" />
    101100    <Compile Include="Interfaces\IQualitiesAwareGQAPOperator.cs" />

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/DemandEquivalentSwapEquipmentManipluator.cs

    r7419 r7432  
    7979          assignment[equipment2] = location1;
    8080          groupedLocations[location2].Remove(equipment2);
    81           bool selected;
    82           equipment2 = groupedLocations[location2].ChooseRandomOrDefault(random, out selected);
    83           if (!selected) break;
     81          if (!groupedLocations[location2].Any()) break;
     82          equipment2 = groupedLocations[location2].ChooseUniformRandom(random);
    8483        }
    8584      }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/GQAPPathRelinking.cs

    r7425 r7432  
    7373    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
    7474      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
     75    }
     76
     77    public IValueParameter<PercentValue> CandidateSizeFactorParameter {
     78      get { return (IValueParameter<PercentValue>)Parameters["CandidateSizeFactor"]; }
    7579    }
    7680
    … …  
    9296      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
    9397      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
     98      Parameters.Add(new ValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path-relinking step relative to the maximum size. A value of 50% means that only half of all possible moves are considered each step.", new PercentValue(0.5)));
    9499    }
    95100
    … …  
    98103    }
    99104
    100     public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, ItemArray<DoubleValue> qualities, DoubleArray demands,
    101       DoubleArray capacities, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts, DoubleValue transportationCosts,
    102       DoubleValue overbookedCapacityPenalty) {
     105    public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, BoolValue maximization, ItemArray<DoubleValue> qualities,
     106      ItemArray<DoubleValue> flowDistanceQualities, ItemArray<DoubleValue> installationQualities, ItemArray<DoubleValue> overbookedCapacities,
     107      DoubleArray demands, DoubleArray capacities, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
     108      DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty, DoubleValue candidateSizeFactor) {
    103109      if (random == null) throw new ArgumentNullException("random", "No IRandom provider is given.");
    104110      if (parents == null || !parents.Any()) throw new ArgumentException("No parents given for path relinking.", "parents");
    … …  
    110116      var source = parents[0];
    111117      var target = parents[1];
    112 
    113       var nu = 1.0;
     118      IntegerVector result;
     119      double resultQuality, resultFDQ, resultIQ, resultOC;
     120
     121      int betterParent = 1;
     122      if ((maximization.Value && qualities[0].Value >= qualities[1].Value)
     123        || (!maximization.Value && qualities[0].Value <= qualities[1].Value))
     124        betterParent = 0;
     125
     126      result = (IntegerVector)parents[betterParent].Clone();
     127      resultQuality = qualities[betterParent].Value;
     128      resultFDQ = flowDistanceQualities[betterParent].Value;
     129      resultIQ = installationQualities[betterParent].Value;
     130      resultOC = overbookedCapacities[betterParent].Value;
     131
    114132      var pi_prime = (IntegerVector)source.Clone();
    115133      var fix = new HashSet<int>();
    116134      var nonFix = new HashSet<int>(Enumerable.Range(0, demands.Length));
    117       var phi = new HashSet<int>(GQAPIntegerVectorProximityCalculator.GetDifference(pi_prime, target));
     135      var phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
    118136
    119137      while (phi.Any()) {
    120         var B = new HashSet<GQAPSolution>(new GQAPSolutionStructuralEqualityComparer());
     138        var B = new List<GQAPSolution>();
    121139        foreach (var v in phi) {
     140          int oldLocation = pi_prime[v];
    122141          pi_prime[v] = target[v];
    123           var pi2 = makeFeasible(pi_prime, v);
    124 
    125           double flowDistanceQuality, installationQuality, overbookedCapacity;
     142          var pi2 = makeFeasible(random, pi_prime, v, nonFix, demands, capacities);
     143          pi_prime[v] = oldLocation;
     144
     145          double currentFDQ, currentIQ, currentOC;
    126146          GQAPEvaluator.Evaluate(pi2, weights, distances, installationCosts, demands, capacities,
    127             out flowDistanceQuality, out installationQuality, out overbookedCapacity);
    128 
    129           if (overbookedCapacity <= 0.0) {
    130             var quality = GQAPEvaluator.GetCombinedQuality(flowDistanceQuality, installationQuality, overbookedCapacity,
     147            out currentFDQ, out currentIQ, out currentOC);
     148
     149          if (currentOC <= 0.0) {
     150            var quality = GQAPEvaluator.GetCombinedQuality(currentFDQ, currentIQ, currentOC,
    131151                transportationCosts.Value, overbookedCapacityPenalty.Value);
    132             var solution = new GQAPSolution(pi2, new DoubleValue(quality), new DoubleValue(flowDistanceQuality), new DoubleValue(installationQuality), new DoubleValue(overbookedCapacity));
    133             if (B.Count >= nu * phi.Count) {
    134               if (!B.Contains(solution) && quality <= B.Select(x => x.Quality.Value).Max()) {
    135                 // TODO: replace most similar element in B with worse cost
     152            var solution = new GQAPSolution(pi2, new DoubleValue(quality), new DoubleValue(currentFDQ),
     153              new DoubleValue(currentIQ), new DoubleValue(currentOC));
     154            if (B.Count >= candidateSizeFactor.Value * phi.Count) {
     155              int mostSimilarIndex = -1;
     156              double mostSimilarValue = 1.0;
     157              for (int i = 0; i < B.Count; i++) {
     158                if (IsBetter(maximization.Value, solution.Quality.Value, B[i].Quality.Value)) {
     159                  var similarity = IntegerVectorEqualityComparer.GetSimilarity(solution.Assignment, B[i].Assignment);
     160                  if (similarity == 1.0) {
     161                    mostSimilarIndex = -1;
     162                    break;
     163                  } else if (similarity < mostSimilarValue) {
     164                    mostSimilarValue = similarity;
     165                    mostSimilarIndex = i;
     166                  }
     167                }
    136168              }
    137             } else if (!B.Contains(solution)) {
    138               B.Add(solution);
     169              if (mostSimilarIndex >= 0)
     170                B[mostSimilarIndex] = solution;
     171            } else {
     172              bool contains = false;
     173              foreach (var b in B) {
     174                if (!IntegerVectorEqualityComparer.GetDifferingIndices(solution.Assignment, b.Assignment).Any()) {
     175                  contains = true;
     176                  break;
     177                }
     178              }
     179              if (!contains) B.Add(solution);
    139180            }
    140181          }
    141182        }
    142183        if (B.Any()) {
    143           var pi = B.ChooseRandom(random);
    144           var diff = GQAPIntegerVectorProximityCalculator.GetDifference(pi.Assignment, target);
    145           var I = phi.Except(phi.Intersect(diff));
    146           var i = I.ChooseRandom(random);
     184          GQAPSolution pi;
     185          if (maximization.Value) pi = B.ChooseProportionalRandom(random, 1, x => x.Quality.Value, false, true).First();
     186          else pi = B.ChooseProportionalRandom(random, 1, x => 1.0 / x.Quality.Value, false, true).First();
     187          var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target);
     188          var I = phi.Except(diff);
     189          var i = I.ChooseUniformRandom(random);
    147190          fix.Add(i);
    148191          nonFix.Remove(i);
    149192          pi_prime = pi.Assignment;
    150           // TODO
    151         }
     193          if (IsBetter(maximization.Value, pi.Quality.Value, resultQuality)) {
     194            result = pi.Assignment;
     195            resultQuality = pi.Quality.Value;
     196            resultFDQ = pi.FlowDistanceQuality.Value;
     197            resultIQ = pi.InstallationQuality.Value;
     198            resultOC = pi.OverbookedCapacity.Value;
     199          }
     200        } else return result;
     201        phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
    152202      }
    153203
    154       return pi_prime;
     204      return result;
    155205    }
    156206
    157207    protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents) {
    158       return Apply(random, parents, QualityParameter.ActualValue, DemandsParameter.ActualValue,
     208      return Apply(random, parents, MaximizationParameter.ActualValue, QualityParameter.ActualValue, FlowDistanceQualityParameter.ActualValue,
     209        InstallationQualityParameter.ActualValue, OverbookedCapacityParameter.ActualValue, DemandsParameter.ActualValue,
    159210        CapacitiesParameter.ActualValue, WeightsParameter.ActualValue, DistancesParameter.ActualValue,
    160211        InstallationCostsParameter.ActualValue, TransportationCostsParameter.ActualValue,
    161         OverbookedCapacityPenaltyParameter.ActualValue);
    162     }
    163 
    164     private static IntegerVector makeFeasible(IntegerVector assignment, int equipment) {
    165       // TODO: implement
    166       return assignment;
     212        OverbookedCapacityPenaltyParameter.ActualValue, CandidateSizeFactorParameter.Value);
     213    }
     214
     215    private static IntegerVector makeFeasible(IRandom random, IntegerVector assignment, int equipment, HashSet<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
     216      int l = assignment[equipment];
     217      var slack = ComputeSlack(assignment, demands, capacities);
     218      if (slack[l] >= 0) return (IntegerVector)assignment.Clone();
     219
     220      IntegerVector result = null;
     221      int k = 0;
     222      while (k < maximumTries && slack[l] < 0) {
     223        result = (IntegerVector)assignment.Clone();
     224        do {
     225          var maxSlack = slack.Max();
     226          var T = nonFix.Where(x => x != equipment && assignment[x] == l && demands[x] <= maxSlack);
     227          if (T.Any()) {
     228            int i = T.ChooseProportionalRandom(random, 1, x => demands[x], false, true).First();
     229            var j = Enumerable.Range(0, capacities.Length).Where(x => slack[x] >= demands[i]).ChooseUniformRandom(random);
     230            result[i] = j;
     231            slack[j] -= demands[i];
     232            slack[l] += demands[i];
     233          } else break;
     234        } while (slack[l] < 0);
     235        k++;
     236      }
     237      return result;
     238    }
     239
     240    private static DoubleArray ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
     241      var slack = (DoubleArray)capacities.Clone();
     242      for (int i = 0; i < assignment.Length; i++) {
     243        slack[assignment[i]] -= demands[i];
     244      }
     245      return slack;
     246    }
     247
     248    private static bool IsBetter(bool maximization, double quality, double otherQuality) {
     249      return maximization && quality > otherQuality || !maximization && quality < otherQuality;
    167250    }
    168251  }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/GreedyRandomizedSolutionCreator.cs

    r7415 r7432  
    7070        do {
    7171          if (L.Any() && random.NextDouble() < threshold) {
    72             int l = L.ChooseRandom(random);
     72            int l = L.ChooseUniformRandom(random);
    7373            L.Remove(l);
    7474            CL.Add(l);
    … …  
    7676          }
    7777          if (T.Any()) {
    78             int f = T.ChooseRandom(random);
     78            int f = T.ChooseUniformRandom(random);
    7979            T.Remove(f);
    8080            F.Remove(f);
    8181            CF.Add(f);
    82             int l = WithSlackGreaterOrEqual(CL, demands[f], slack).ChooseRandom(random);
     82            int l = WithSlackGreaterOrEqual(CL, demands[f], slack).ChooseUniformRandom(random);
    8383            assignment.Add(f, l);
    8484            slack[l] -= demands[f];

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/QualitySimilarityMerger.cs

    r7419 r7432  
    9494
    9595      foreach (var candidate in candidates) {
    96         double[] similarities = population.Select(x => GQAPIntegerVectorProximityCalculator.CalculateGenotypeSimilarity(x.Solution, candidate.Solution)).ToArray();
     96        double[] similarities = population.Select(x => IntegerVectorEqualityComparer.GetSimilarity(x.Solution, candidate.Solution)).ToArray();
    9797        if (!similarities.Any()) {
    9898          population.Add(candidate);

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/RelocateEquipmentManipluator.cs

    r7419 r7432  
    7272      }
    7373
    74       bool selected;
    75       var overstuffedLocation = usedCapacities.Where(x => capacities[x.Key] < x.Value).ChooseRandomOrDefault(random, out selected);
    76       if (selected) {
    77         int equipment = groupedLocations[overstuffedLocation.Key].ChooseRandomOrDefault(random, out selected);
    78         var freeLocations = usedCapacities.Where(x => capacities[x.Key] > x.Value).ToList();
    79         var location = freeLocations.Where(x => capacities[x.Key] > x.Value + demands[equipment]).ChooseRandomOrDefault(random, out selected);
    80         if (selected) {
    81           assignment[equipment] = location.Key;
    82         } else {
    83           location = freeLocations.ChooseRandomOrDefault(random, out selected);
    84           if (selected) assignment[equipment] = location.Key;
    85           else assignment[equipment] = random.Next(locations);
    86         }
    87       } else {
     74      var overbookedLocations = usedCapacities.Where(x => capacities[x.Key] < x.Value);
     75      var freeLocations = usedCapacities.Where(x => capacities[x.Key] > x.Value);
     76      if (!overbookedLocations.Any() || !freeLocations.Any()) { // perform a random relocation
    8877        assignment[random.Next(assignment.Length)] = random.Next(locations);
     78        return;
     79      }
     80
     81      var sourceLocation = overbookedLocations.ChooseUniformRandom(random);
     82      int equipmentToRelocate = groupedLocations[sourceLocation.Key].ChooseUniformRandom(random);
     83      var bestFreeLocations = freeLocations.Where(x => capacities[x.Key] > x.Value + demands[equipmentToRelocate]);
     84
     85      if (bestFreeLocations.Any()) { // a feasible solution will still be feasible, an infeasible solution might become feasible
     86        var selected = bestFreeLocations.ChooseUniformRandom(random);
     87        assignment[equipmentToRelocate] = sourceLocation.Key;
     88      } else { // the solution will become infeasible
     89        sourceLocation = freeLocations.ChooseUniformRandom(random);
     90        assignment[equipmentToRelocate] = sourceLocation.Key;
    8991      }
    9092    }
Note: See TracChangeset for help on using the changeset viewer.