Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15553


Ignore:
Timestamp:
12/20/17 15:41:27 (7 years ago)
Author:
abeham
Message:

#1614:

  • Implementing basic algorithm according to paper (rechecking all operators)
  • Checking implementation with paper
  • Improved speed of move generator
  • Improved speed of randomized solution creator
Location:
branches/GeneralizedQAP
Files:
11 added
11 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/GeneralizedQAP.sln

    r15492 r15553  
    22Microsoft Visual Studio Solution File, Format Version 12.00
    33# Visual Studio 15
    4 VisualStudioVersion = 15.0.27004.2002
     4VisualStudioVersion = 15.0.27130.2010
    55MinimumVisualStudioVersion = 10.0.40219.1
    66Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3", "HeuristicLab.Problems.GeneralizedQuadraticAssignment\3.3\HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj", "{C739E6D2-5680-4804-A810-8017DA0C238F}"
    … …  
    1818Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.IntegerVectorEncoding-3.3", "HeuristicLab.Encodings.IntegerVectorEncoding\3.3\HeuristicLab.Encodings.IntegerVectorEncoding-3.3.csproj", "{DDFB14DD-2A85-493C-A52D-E69729BBAEB0}"
    1919EndProject
     20Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3", "HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms\3.3\HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj", "{577239EC-7D7F-4505-A0A4-572E34010DBA}"
     21EndProject
    2022Global
     23  GlobalSection(Performance) = preSolution
     24    HasPerformanceSessions = true
     25  EndGlobalSection
    2126  GlobalSection(SolutionConfigurationPlatforms) = preSolution
    2227    Debug|Any CPU = Debug|Any CPU
    … …  
    100105    {DDFB14DD-2A85-493C-A52D-E69729BBAEB0}.Release|x86.ActiveCfg = Release|x86
    101106    {DDFB14DD-2A85-493C-A52D-E69729BBAEB0}.Release|x86.Build.0 = Release|x86
     107    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     108    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Debug|Any CPU.Build.0 = Debug|Any CPU
     109    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Debug|x64.ActiveCfg = Debug|Any CPU
     110    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Debug|x64.Build.0 = Debug|Any CPU
     111    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Debug|x86.ActiveCfg = Debug|Any CPU
     112    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Debug|x86.Build.0 = Debug|Any CPU
     113    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Release|Any CPU.ActiveCfg = Release|Any CPU
     114    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Release|Any CPU.Build.0 = Release|Any CPU
     115    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Release|x64.ActiveCfg = Release|Any CPU
     116    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Release|x64.Build.0 = Release|Any CPU
     117    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Release|x86.ActiveCfg = Release|Any CPU
     118    {577239EC-7D7F-4505-A0A4-572E34010DBA}.Release|x86.Build.0 = Release|Any CPU
    102119  EndGlobalSection
    103120  GlobalSection(SolutionProperties) = preSolution
    … …  
    107124    SolutionGuid = {B0BBF50B-4E62-4BAB-A730-881208150933}
    108125  EndGlobalSection
     126  GlobalSection(Performance) = preSolution
     127    HasPerformanceSessions = true
     128  EndGlobalSection
     129  GlobalSection(Performance) = preSolution
     130    HasPerformanceSessions = true
     131  EndGlobalSection
     132  GlobalSection(Performance) = preSolution
     133    HasPerformanceSessions = true
     134  EndGlobalSection
    109135EndGlobal

  • branches/GeneralizedQAP/HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinking.cs

    r15507 r15553  
    3939  /// </summary>
    4040  [Item("GRASP+PR", "The algorithm combines the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking and is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
    41   [Creatable("Algorithms")]
     41  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
    4242  [StorableClass]
    4343  public sealed class GRASPWithPathRelinking : HeuristicOptimizationEngineAlgorithm, IStorableContent {

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

    r15510 r15553  
    1 using System.Collections.Generic;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System.Collections.Generic;
    223using System.Linq;
    324using HeuristicLab.Common;

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

    r15510 r15553  
    191191
    192192    public Evaluation Evaluate(IntegerVector assignment) {
    193       return EvaluateIntegerVector(assignment, Demands, Capacities,
     193      var evaluation = EvaluateIntegerVector(assignment, Demands, Capacities,
    194194        InstallationCosts, Weights, Distances);
     195      return evaluation;
    195196    }
    196197
    … …  
    217218    }
    218219
     220    public GQAPSolution ToEvaluatedSolution(IntegerVector assignment) {
     221      var evaluation = EvaluateIntegerVector(assignment, Demands, Capacities,
     222InstallationCosts, Weights, Distances);
     223      return new GQAPSolution(assignment, evaluation);
     224    }
     225
     226    public bool IsFeasible(IntegerVector assignment) {
     227      int len = assignment.Length;
     228      var utilization = new double[Capacities.Length];
     229      for (var equip = 0; equip < len; equip++) {
     230        var loc = assignment[equip];
     231        utilization[loc] += Demands[equip];
     232        if (utilization[loc] > Capacities[loc])
     233          return false;
     234      }
     235      return true;
     236    }
     237
    219238    public double ToSingleObjective(Evaluation fitness) {
    220239      return fitness.IsFeasible

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

    r15504 r15553  
    3636      get { return assignment; }
    3737      set {
    38         bool changed = (assignment != value);
     38        if (assignment == value) return;
    3939        assignment = value;
    40         if (changed) OnPropertyChanged("Assignment");
     40        OnPropertyChanged(nameof(Assignment));
    4141      }
    4242    }

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

    r15507 r15553  
    4141  </PropertyGroup>
    4242  <ItemGroup>
    43     <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=x86">
    44       <SpecificVersion>False</SpecificVersion>
     43    <Reference Include="HeuristicLab.Analysis-3.3">
     44      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Analysis-3.3.dll</HintPath>
    4545      <Private>False</Private>
    4646    </Reference>
    … …  
    6969      <Private>False</Private>
    7070    </Reference>
    71     <Reference Include="HeuristicLab.Optimization.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     71    <Reference Include="HeuristicLab.Optimization.Operators-3.3">
     72      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Optimization.Operators-3.3.dll</HintPath>
    7273      <Private>False</Private>
    7374    </Reference>
    … …  
    8485      <Private>False</Private>
    8586    </Reference>
    86     <Reference Include="HeuristicLab.Problems.Instances-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    87       <SpecificVersion>False</SpecificVersion>
     87    <Reference Include="HeuristicLab.Problems.Instances-3.3">
     88      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>
    8889      <Private>False</Private>
    8990    </Reference>
    90     <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    91       <SpecificVersion>False</SpecificVersion>
     91    <Reference Include="HeuristicLab.Random-3.3">
     92      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
    9293      <Private>False</Private>
    9394    </Reference>
    … …  
    170171    </ProjectReference>
    171172  </ItemGroup>
    172   <ItemGroup />
    173173  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    174174  <PropertyGroup>

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/StochasticNMoveSingleMoveGenerator.cs

    r15511 r15553  
    5757    }
    5858
     59    public static NMove GenerateOneMove(IRandom random, IntegerVector assignment, DoubleArray capacities) {
     60      var locations = capacities.Length;
     61      if (locations <= 1) throw new ArgumentException("There must be at least two locations.");
     62      var dim = assignment.Length;
     63      var equip = random.Next(dim);
     64      var equipments = new List<int>(1) { equip };
     65
     66      var reassignment = new int[dim];
     67      reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
     68
     69      return new NMove(reassignment, equipments);
     70    }
     71
     72    public static NMove GenerateTwoMove(IRandom random, IntegerVector assignment, DoubleArray capacities) {
     73      var locations = capacities.Length;
     74      if (locations <= 1) throw new ArgumentException("There must be at least two locations.");
     75      var dim = assignment.Length;
     76      var equipments = new List<int>(2) { random.Next(dim), -1 };
     77      do {
     78        equipments[1] = random.Next(dim);
     79      } while (equipments[0] == equipments[1]);
     80
     81      var reassignment = new int[dim];
     82      for (var i = 0; i < 2; i++) {
     83        var equip = equipments[i];
     84        reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
     85      }
     86      return new NMove(reassignment, equipments);
     87    }
     88
    5989    public static NMove GenerateExactlyN(IRandom random, IntegerVector assignment, int n, DoubleArray capacities) {
    60       if (capacities.Length <= 1) throw new ArgumentException("There must be at least two locations.");
     90      if (n == 1) return GenerateOneMove(random, assignment, capacities);
     91      if (n == 2) return GenerateTwoMove(random, assignment, capacities);
     92      var locations = capacities.Length;
     93      if (locations <= 1) throw new ArgumentException("There must be at least two locations.");
    6194      var dim = assignment.Length;
     95      var equipments = Enumerable.Range(0, dim).SampleRandomWithoutRepetition(random, n, dim).ToList();
     96
    6297      var reassignment = new int[dim];
    63       var equipments = Enumerable.Range(0, dim).SampleRandomWithoutRepetition(random, n, dim).ToList();
    6498      for (var i = 0; i < n; i++) {
    6599        var equip = equipments[i];
    66         do {
    67           reassignment[equip] = random.Next(capacities.Length) + 1;
    68         } while (reassignment[equip] == assignment[equip] + 1);
     100        reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
    69101      }
    70102      return new NMove(reassignment, equipments);
     103    }
     104
     105    private static int ReassignEquipment(IRandom random, int equip, int prevLocation, int locations) {
     106      var newLoc = random.Next(locations) + 1;
     107      while (newLoc == prevLocation + 1)
     108        newLoc = random.Next(locations) + 1;
     109      return newLoc;
    71110    }
    72111

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

    r15504 r15553  
    6161    }
    6262
    63     public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, ItemArray<DoubleValue> qualities,
    64       GQAPInstance problemInstance, double candidateSizeFactor) {
    65       if (random == null) throw new ArgumentNullException("random", "No IRandom provider is given.");
    66       if (parents == null || !parents.Any()) throw new ArgumentException("No parents given for path relinking.", "parents");
    67       if (parents.Length != 2) throw new ArgumentException(String.Format("Two parents were expected for path relinking, but {0} was/were given.", parents.Length.ToString()), "parents");
    68       if (parents[0].Length != parents[1].Length) throw new ArgumentException("The length of the parents is not equal.", "parents");
    69       if (qualities == null || qualities.Length == 0) throw new ArgumentException("The qualities are not given.", "qualities");
    70       if (qualities.Length != parents.Length) throw new ArgumentException(String.Format("There are a different number of parents ({0}) than quality values ({1})", parents.Length.ToString(), qualities.Length.ToString()));
    71      
    72       var source = parents[0];
    73       var target = parents[1];
    74       IntegerVector result;
    75       double resultQuality;
    76 
    77       int betterParent = (qualities[0].Value <= qualities[1].Value) ? 0 : 1;
    78 
    79       result = (IntegerVector)parents[betterParent].Clone();
    80       resultQuality = qualities[betterParent].Value;
    81 
     63    public static GQAPSolution Apply(IRandom random,
     64      IntegerVector source, Evaluation sourceEval,
     65      IntegerVector target, Evaluation targetEval,
     66      GQAPInstance problemInstance, double candidateSizeFactor,
     67      out int evaluatedSolutions) {
     68      evaluatedSolutions = 0;
    8269      var demands = problemInstance.Demands;
    8370      var capacities = problemInstance.Capacities;
    84 
    8571      var cmp = new IntegerVectorEqualityComparer();
    8672
    87       var pi_prime = (IntegerVector)source.Clone();
    88       var fix = new HashSet<int>();
    89       var nonFix = new HashSet<int>(Enumerable.Range(0, demands.Length));
    90       var phi = new HashSet<int>((IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)));
     73      var sFit = problemInstance.ToSingleObjective(sourceEval);
     74      var tFit = problemInstance.ToSingleObjective(targetEval);
     75      GQAPSolution pi_star = sFit < tFit ? new GQAPSolution(source, sourceEval) : new GQAPSolution(target, targetEval); // line 1 of Algorithm 4
     76      double pi_star_Fit = problemInstance.ToSingleObjective(pi_star.Evaluation); // line 2 of Algorithm 4
     77     
     78      var pi_prime = (IntegerVector)source.Clone(); // line 3 of Algorithm 4
     79      //var fix = new bool[demands.Length]; // line 3 of Algorithm 4, note that according to the description it is not necessary to track the fixed equipments
     80      var nonFix = Enumerable.Range(0, demands.Length).ToList(); // line 3 of Algorithm 4
     81      var phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
    9182
    92       while (phi.Any()) {
    93         var B = new List<Tuple<GQAPSolution, double>>();
    94         foreach (var v in phi) {
     83      while (phi.Count > 0) { // line 5 of Algorithm 4
     84        var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor)); // line 6 of Algorithm 4
     85        var B_fit = new List<double>(B.Capacity); // line 6 of Algorithm 4 (B is split into two synchronized lists)
     86        foreach (var v in phi) { // line 7 of Algorithm 4
    9587          int oldLocation = pi_prime[v];
    96           pi_prime[v] = target[v];
    97           var pi2 = MakeFeasible(random, pi_prime, v, nonFix, demands, capacities);
    98           pi_prime[v] = oldLocation;
     88          pi_prime[v] = target[v]; // line 8 of Algorithm 4
     89          var pi_dash = MakeFeasible(random, pi_prime, v, nonFix, demands, capacities); // line 9 of Algorithm 4
     90          pi_prime[v] = oldLocation; // not mentioned in Algorithm 4, but seems reasonable
     91          var pi_dash_eval = problemInstance.Evaluate(pi_dash);
     92          evaluatedSolutions++;
     93          var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
    9994
    100           var currentEval = problemInstance.Evaluate(pi2);
     95          if (problemInstance.IsFeasible(pi_dash)) { // line 10 of Algorithm 4
     96            if (B.Any(x => cmp.Equals(x.Assignment, pi_dash))) continue; // cond. 2 of line 12 and cond. 1 of line 16 in Algorithm 4
    10197
    102           if (currentEval.ExcessDemand <= 0.0) {
    103             var quality = problemInstance.ToSingleObjective(currentEval);
    104 
    105             var solution = new GQAPSolution(pi2, currentEval);
    106             if (B.Count >= candidateSizeFactor * phi.Count) {
    107               int mostSimilarIndex = -1;
    108               double mostSimilarValue = 1.0;
    109               for (int i = 0; i < B.Count; i++) {
    110                 if (quality < B[i].Item2) {
    111                   var similarity = HammingSimilarityCalculator.CalculateSimilarity(solution.Assignment, B[i].Item1.Assignment);
    112                   if (similarity == 1.0) {
    113                     mostSimilarIndex = -1;
    114                     break;
    115                   } else if (similarity < mostSimilarValue) {
    116                     mostSimilarValue = similarity;
    117                     mostSimilarIndex = i;
    118                   }
    119                 }
     98            if (B.Count >= candidateSizeFactor * phi.Count) { // line 11 of Algorithm 4
     99              var replacement = B_fit.Select((val, idx) => new { Index = idx, Fitness = val })
     100                                            .Where(x => x.Fitness >= pi_dash_fit) // cond. 1 in line 12 of Algorithm 4
     101                                            .Select(x => new { Index = x.Index, Fitness = x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
     102                                            .ToArray();
     103              if (replacement.Length > 0) {
     104                var mostSimilar = replacement.MaxItems(x => x.Similarity).First().Index;
     105                B[mostSimilar].Assignment = pi_dash; // line 13 of Algorithm 4
     106                B[mostSimilar].Evaluation = pi_dash_eval; // line 13 of Algorithm 4
     107                B_fit[mostSimilar] = pi_dash_fit; // line 13 of Algorithm 4
    120108              }
    121               if (mostSimilarIndex >= 0)
    122                 B[mostSimilarIndex] = Tuple.Create(solution, quality);
    123             } else {
    124               bool contains = false;
    125               foreach (var b in B) {
    126                 if (cmp.Equals(solution.Assignment, b.Item1.Assignment)) {
    127                   contains = true;
    128                   break;
    129                 }
    130               }
    131               if (!contains) B.Add(Tuple.Create(solution, quality));
     109            } else { // line 16, condition has been checked above already
     110              B.Add(new GQAPSolution(pi_dash, pi_dash_eval)); // line 17 of Algorithm 4
     111              B_fit.Add(pi_dash_fit); // line 17 of Algorithm 4
    132112            }
    133113          }
    134114        }
    135         if (B.Any()) {
    136           var pi = B.SampleProportional(random, 1, B.Select(x => 1.0 / x.Item2), false).First();
    137           var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Item1.Assignment, target);
    138           var I = phi.Except(diff);
    139           var i = I.SampleRandom(random);
    140           fix.Add(i);
    141           nonFix.Remove(i);
    142           pi_prime = pi.Item1.Assignment;
    143           if (pi.Item2 < resultQuality) {
    144             result = pi.Item1.Assignment;
    145             resultQuality = pi.Item2;
     115        if (B.Count > 0) { // line 21 of Algorithm 4
     116          var pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First(); // line 22 of Algorithm 4
     117          var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target); // line 23 of Algorithm 4
     118          var I = phi.Except(diff); // line 24 of Algorithm 4
     119          var i = I.SampleRandom(random); // line 25 of Algorithm 4
     120          //fix[i] = true; // line 26 of Algorithm 4
     121          nonFix.Remove(i); // line 26 of Algorithm 4
     122          pi_prime = pi.Assignment; // line 27 of Algorithm 4
     123          var fit = problemInstance.ToSingleObjective(pi.Evaluation);
     124          if (fit < pi_star_Fit) { // line 28 of Algorithm 4
     125            pi_star_Fit = fit; // line 29 of Algorithm 4
     126            pi_star = pi; // line 30 of Algorithm 4
    146127          }
    147         } else return result;
     128        } else return pi_star ?? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone());
    148129        phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
    149130      }
    150131
    151       return result;
     132      return pi_star ?? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone());
    152133    }
    153134
    154135    protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents,
    155136      GQAPInstance problemInstance) {
    156       return Apply(random, parents, QualityParameter.ActualValue, problemInstance,
    157         CandidateSizeFactorParameter.Value.Value);
     137
     138      var qualities = QualityParameter.ActualValue;
     139      var evaluations = EvaluationParameter.ActualValue;
     140      var betterParent = qualities[0].Value <= qualities[1].Value ? 0 : 1;
     141      var worseParent = 1 - betterParent;
     142      var source = parents[betterParent];
     143      var target = parents[worseParent];
     144
     145      int evaluatedSolution;
     146      return Apply(random, source, evaluations[betterParent],
     147        target, evaluations[worseParent], problemInstance,
     148        CandidateSizeFactorParameter.Value.Value, out evaluatedSolution).Assignment;
    158149    }
    159150
    160     private static IntegerVector MakeFeasible(IRandom random, IntegerVector assignment, int equipment, HashSet<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
    161       int l = assignment[equipment];
    162       var slack = ComputeSlack(assignment, demands, capacities);
    163       if (slack[l] >= 0) return (IntegerVector)assignment.Clone();
     151    private static IntegerVector MakeFeasible(IRandom random, IntegerVector pi, int equipment, List<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
     152      int l = pi[equipment];
     153      var slack = ComputeSlack(pi, demands, capacities);
     154      if (slack[l] >= 0) // line 1 of Algorithm 5
     155        return new IntegerVector(pi); // line 2 of Algorithm 5
    164156
    165       IntegerVector result = null;
    166       int k = 0;
    167       while (k < maximumTries && slack[l] < 0) {
    168         result = (IntegerVector)assignment.Clone();
    169         do {
    170           var maxSlack = slack.Max();
    171           var T = nonFix.Where(x => x != equipment && assignment[x] == l && demands[x] <= maxSlack);
    172           if (T.Any()) {
    173             int i = T.SampleProportional(random, 1, T.Select(x => demands[x]), false).First();
    174             var j = Enumerable.Range(0, capacities.Length).Where(x => slack[x] >= demands[i]).SampleRandom(random);
    175             result[i] = j;
    176             slack[j] -= demands[i];
    177             slack[l] += demands[i];
    178           } else break;
    179         } while (slack[l] < 0);
    180         k++;
     157      IntegerVector pi_prime = null;
     158      int k = 0; // line 4 of Algorithm 5
     159      while (k < maximumTries && slack[l] < 0) {  // line 5 of Algorithm 5
     160        pi_prime = new IntegerVector(pi); // line 6 of Algorithm 5
     161        do {  // line 7 of Algorithm 5
     162          var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
     163          var T = nonFix.Where(x => pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
     164          if (T.Count > 0) { // line 10 of Algorithm 5
     165            int i = T.SampleProportional(random, 1, T.Select(x => demands[x]), false).First(); // line 11 of Algorithm 5
     166            var j = Enumerable.Range(0, capacities.Length)
     167              .Where(x => slack[x] >= demands[i]) // line 12 of Algorithm 5
     168              .SampleRandom(random);  // line 13 of Algorithm 5
     169            pi_prime[i] = j; // line 14 of Algorithm 5
     170            slack[j] -= demands[i]; // line 14 of Algorithm 5
     171            slack[l] += demands[i]; // line 14 of Algorithm 5
     172          } else break; // cond. 1 in line 16 of Algorithm 5
     173        } while (slack[l] < 0); // cond. 2 in line 16 of Algorithm 5
     174        k++; // line 17 of Algorithm 5
    181175      }
    182       return result;
     176      return pi_prime; // line 19-23 of Algorithm 5
    183177    }
    184178
    185     private static DoubleArray ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
    186       var slack = (DoubleArray)capacities.Clone();
     179    private static double[] ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
     180      var slack = new double[capacities.Length];
    187181      for (int i = 0; i < assignment.Length; i++) {
    188182        slack[assignment[i]] -= demands[i];

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs

    r15512 r15553  
    9494    }
    9595
    96     /// <summary>
    97     /// The implementation differs slightly from Mateus et al. in that the maximumIterations parameter defines a cap
    98     /// on the number of steps that the local search can perform. While the maxSampleSize parameter corresponds to
    99     /// the maxItr parameter defined by Mateus et al.
    100     /// </summary>
    101     /// <param name="random">The random number generator to use.</param>
    102     /// <param name="assignment">The equipment-location assignment vector.</param>
    103     /// <param name="quality">The solution quality.</param>
    104     /// <param name="evaluation">The evaluation result of the solution.</param>
    105     /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
    106     /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
    107     /// <param name="problemInstance">The problem instance that contains the data.</param>
    108     /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
    109     /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
    110     public static void Apply(IRandom random, IntegerVector assignment,
    111       DoubleValue quality, ref Evaluation evaluation, IntValue maxCLS, IntValue maximumIterations,
    112       GQAPInstance problemInstance, IntValue evaluatedSolutions, PercentValue oneMoveProbability) {
     96    public static void Apply(IRandom random, GQAPSolution sol, int maxCLS,
     97      double oneMoveProbability, int maximumIterations,
     98      GQAPInstance problemInstance, out int evaluatedSolutions) {
     99      var fit = problemInstance.ToSingleObjective(sol.Evaluation);
     100      var eval = sol.Evaluation;
     101      Apply(random, sol.Assignment, ref fit, ref eval, maxCLS, oneMoveProbability, maximumIterations, problemInstance,
     102        out evaluatedSolutions);
     103      sol.Evaluation = eval;
     104    }
     105
     106      /// <summary>
     107      /// The implementation differs slightly from Mateus et al. in that the maximumIterations parameter defines a cap
     108      /// on the number of steps that the local search can perform. While the maxSampleSize parameter corresponds to
     109      /// the maxItr parameter defined by Mateus et al.
     110      /// </summary>
     111      /// <param name="random">The random number generator to use.</param>
     112      /// <param name="assignment">The equipment-location assignment vector.</param>
     113      /// <param name="quality">The solution quality.</param>
     114      /// <param name="evaluation">The evaluation result of the solution.</param>
     115      /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
     116      /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
     117      /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
     118      /// <param name="problemInstance">The problem instance that contains the data.</param>
     119      /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
     120      public static void Apply(IRandom random, IntegerVector assignment,
     121      ref double quality, ref Evaluation evaluation, int maxCLS,
     122      double oneMoveProbability, int maximumIterations,
     123      GQAPInstance problemInstance, out int evaluatedSolutions) {
     124      evaluatedSolutions = 0;
    113125      var capacities = problemInstance.Capacities;
    114126      var demands = problemInstance.Demands;
    … …  
    121133        do {
    122134          NMove move;
    123           if (random.NextDouble() < oneMoveProbability.Value)
    124             move = StochasticNMoveSingleMoveGenerator.GenerateExactlyN(random, assignment, 1, capacities);
    125           else move = StochasticNMoveSingleMoveGenerator.GenerateExactlyN(random, assignment, 2, capacities);
     135          if (random.NextDouble() < oneMoveProbability)
     136            move = StochasticNMoveSingleMoveGenerator.GenerateOneMove(random, assignment, capacities);
     137          else move = StochasticNMoveSingleMoveGenerator.GenerateTwoMove(random, assignment, capacities);
    126138         
    127139          var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
    … …  
    129141          double moveQuality = problemInstance.ToSingleObjective(moveEval);
    130142
    131           if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality.Value) {
     143          if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality) {
    132144            CLS.Add(Tuple.Create(move, moveQuality, moveEval));
    133145            sum += 1.0 / moveQuality;
    134146          }
    135147          count++;
    136         } while (CLS.Count < maxCLS.Value && count < maximumIterations.Value);
     148        } while (CLS.Count < maxCLS && count < maximumIterations);
    137149
    138150        if (CLS.Count == 0) {
    139           evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
     151          evaluatedSolutions += (int)Math.Ceiling(evaluations);
    140152          return; // END
    141153        } else {
    … …  
    150162          }
    151163          NMoveMaker.Apply(assignment, selected.Item1);
    152           quality.Value = selected.Item2;
     164          quality = selected.Item2;
    153165          evaluation = selected.Item3;
    154166        }
    … …  
    158170    public override IOperation Apply() {
    159171      var evaluation = EvaluationParameter.ActualValue;
     172      var quality = QualityParameter.ActualValue;
     173      var fit = quality.Value;
     174      var evaluatedSolutions = 0;
     175
    160176      Apply(RandomParameter.ActualValue,
    161177        AssignmentParameter.ActualValue,
    162         QualityParameter.ActualValue,
     178        ref fit,
    163179        ref evaluation,
    164         MaximumCandidateListSizeParameter.ActualValue,
    165         MaximumIterationsParameter.ActualValue,
     180        MaximumCandidateListSizeParameter.ActualValue.Value,
     181        OneMoveProbabilityParameter.ActualValue.Value,
     182        MaximumIterationsParameter.ActualValue.Value,
    166183        ProblemInstanceParameter.ActualValue,
    167         EvaluatedSolutionsParameter.ActualValue,
    168         OneMoveProbabilityParameter.ActualValue);
     184        out evaluatedSolutions);
     185
    169186      EvaluationParameter.ActualValue = evaluation;
     187      quality.Value = fit;
     188      EvaluatedSolutionsParameter.ActualValue.Value += evaluatedSolutions;
    170189      return base.Apply();
    171190    }

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

    r15504 r15553  
    6161      int maximumTries, bool createMostFeasibleSolution, CancellationToken cancelToken) {
    6262      var demands = problemInstance.Demands;
    63       var capacities = problemInstance.Capacities;
     63      var capacities = problemInstance.Capacities.ToArray();
     64      var equipments = demands.Length;
     65      var locations = capacities.Length;
    6466      int tries = 0;
    65       var assignment = new Dictionary<int, int>(demands.Length);
    66       DoubleArray slack = new DoubleArray(capacities.Length);
     67      var assignment = new int[equipments];
     68      var slack = new double[locations];
    6769      double minViolation = double.MaxValue;
    68       Dictionary<int, int> bestAssignment = null;
    69       HashSet<int> CF = new HashSet<int>(), // set of chosen facilities / equipments
    70           T = new HashSet<int>(), // set of facilities / equpiments that can be assigned to the set of chosen locations (CL)
    71           CL = new HashSet<int>(), // set of chosen locations
    72           F = new HashSet<int>(Enumerable.Range(0, demands.Length)), // set of (initially) all facilities / equipments
    73           L = new HashSet<int>(Enumerable.Range(0, capacities.Length)); // set of (initially) all locations
    74 
     70      int[] bestAssignment = null;
     71      var CF = new bool[equipments]; // set of chosen facilities / equipments
     72      var T = new List<int>(equipments); // set of facilities / equpiments that can be assigned to the set of chosen locations (CL)
     73      var CL_list = new List<int>(locations); // list of chosen locations
     74      var CL_selected = new bool[locations]; // bool decision if location is chosen
     75      var F = new List<int>(equipments); // set of (initially) all facilities / equipments
     76      var L = new List<int>(locations); // set of (initially) all locations
     77     
    7578      while (maximumTries <= 0 || tries < maximumTries) {
    7679        cancelToken.ThrowIfCancellationRequested();
    7780
    78         assignment.Clear();
    79         for (int i = 0; i < capacities.Length; i++) slack[i] = capacities[i];
    80         CF.Clear();
     81        Array.Copy(capacities, slack, locations);
     82        Array.Clear(CF, 0, equipments);
     83        Array.Clear(CL_selected, 0, locations);
     84        CL_list.Clear();
    8185        T.Clear();
    82         CL.Clear();
    83         F.Clear(); F.UnionWith(Enumerable.Range(0, demands.Length));
    84         L.Clear(); L.UnionWith(Enumerable.Range(0, capacities.Length));
     86
     87        F.Clear(); F.AddRange(Enumerable.Range(0, equipments));
     88        L.Clear(); L.AddRange(Enumerable.Range(0, locations));
    8589
    8690        double threshold = 1.0;
    8791        do {
    88           if (L.Any() && random.NextDouble() < threshold) {
     92          if (L.Count > 0 && random.NextDouble() < threshold) {
    8993            int l = L.SampleRandom(random);
    9094            L.Remove(l);
    91             CL.Add(l);
    92             T = new HashSet<int>(WithDemandEqualOrLess(F, GetMaximumSlack(slack, CL), demands));
     95            CL_list.Add(l);
     96            CL_selected[l] = true;
     97            T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands));
    9398          }
    94           if (T.Any()) {
    95             int f = T.SampleRandom(random);
    96             T.Remove(f);
    97             F.Remove(f);
    98             CF.Add(f);
    99             int l = WithSlackGreaterOrEqual(CL, demands[f], slack).SampleRandom(random);
    100             assignment.Add(f, l);
     99          if (T.Count > 0) {
     100            var fidx = Enumerable.Range(0, T.Count).SampleRandom(random);
     101            var f = T[fidx];
     102            T.RemoveAt(fidx);
     103            F.Remove(f); // TODO: slow
     104            CF[f] = true;
     105            int l = WhereSlackGreaterOrEqual(CL_list, demands[f], slack).SampleRandom(random);
     106            assignment[f] = l + 1;
    101107            slack[l] -= demands[f];
    102             T = new HashSet<int>(WithDemandEqualOrLess(F, GetMaximumSlack(slack, CL), demands));
     108            T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands));
    103109            threshold = 1.0 - (double)T.Count / Math.Max(F.Count, 1.0);
    104110          }
    105         } while (T.Any() || L.Any());
     111        } while (T.Count > 0 || L.Count > 0);
    106112        if (maximumTries > 0) tries++;
    107         if (!F.Any()) {
     113        if (F.Count == 0) {
    108114          bestAssignment = assignment;
    109115          break;
    … …  
    111117          // complete the solution and remember the one with least violation
    112118          foreach (var l in L.ToArray()) {
    113             CL.Add(l);
     119            CL_list.Add(l);
     120            CL_selected[l] = true;
    114121            L.Remove(l);
    115122          }
    116           while (F.Any()) {
    117             var f = F.MaxItems(x => demands[x]).SampleRandom(random);
    118             var l = CL.MaxItems(x => slack[x]).SampleRandom(random);
    119             F.Remove(f);
    120             assignment.Add(f, l);
    121             slack[l] -= demands[f];
     123          while (F.Count > 0) {
     124            var f = F.Select((v, i) => new { Index = i, Value = v }).MaxItems(x => demands[x.Value]).SampleRandom(random);
     125            var l = CL_list.MaxItems(x => slack[x]).SampleRandom(random);
     126            F.RemoveAt(f.Index);
     127            assignment[f.Value] = l + 1;
     128            slack[l] -= demands[f.Value];
    122129          }
    123130          double violation = slack.Select(x => x < 0 ? -x : 0).Sum();
    124131          if (violation < minViolation) {
    125132            bestAssignment = assignment;
    126             assignment = new Dictionary<int, int>(demands.Length);
     133            assignment = new int[equipments];
    127134            minViolation = violation;
    128135          }
    … …  
    130137      }
    131138
    132       if (bestAssignment == null || bestAssignment.Count != demands.Length) throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maximumTries));
     139      if (bestAssignment == null || bestAssignment.Any(x => x == 0))
     140        throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maximumTries));
    133141
    134       return new IntegerVector(bestAssignment.OrderBy(x => x.Key).Select(x => x.Value).ToArray());
     142      return new IntegerVector(bestAssignment.Select(x => x - 1).ToArray());
    135143    }
    136144
    … …  
    142150    }
    143151
    144     private static IEnumerable<int> WithDemandEqualOrLess(IEnumerable<int> facilities, double maximum, DoubleArray demands) {
     152    private static IEnumerable<int> WhereDemandEqualOrLess(IEnumerable<int> facilities, double maximum, DoubleArray demands) {
    145153      foreach (int f in facilities) {
    146154        if (demands[f] <= maximum) yield return f;
    … …  
    148156    }
    149157
    150     private static double GetMaximumSlack(DoubleArray slack, HashSet<int> CL) {
    151       return slack.Select((val, idx) => new { idx, val }).Where(x => CL.Contains(x.idx)).Select(x => x.val).Max();
     158    private static double GetMaximumSlack(double[] slack, bool[] CL) {
     159      var max = double.MinValue;
     160      for (var i = 0; i < slack.Length; i++) {
     161        if (CL[i] && max < slack[i]) max = slack[i];
     162      }
     163      return max;
    152164    }
    153165
    154     private static IEnumerable<int> WithSlackGreaterOrEqual(HashSet<int> locations, double minimum, DoubleArray slack) {
     166    private static IEnumerable<int> WhereSlackGreaterOrEqual(IEnumerable<int> locations, double minimum, double[] slack) {
    155167      foreach (int l in locations) {
    156168        if (slack[l] >= minimum) yield return l;

  • branches/GeneralizedQAP/UnitTests/ApproximateLocalSearchTest.cs

    r15512 r15553  
    1313    [TestMethod]
    1414    public void ApproximateLocalSearchApplyTest() {
    15       CollectionAssert.AreEqual(new[] { 0, 3, 4, 2, 2, 0, 4, 3, 2, 0 }, assignment.ToArray());
     15      CollectionAssert.AreEqual(new [] { 3, 2, 2, 0, 0, 0, 2, 3, 0, 2 }, assignment.ToArray());
    1616
    1717      var evaluation = instance.Evaluate(assignment);
    18       Assert.AreEqual(7177824, evaluation.FlowCosts);
    19       Assert.AreEqual(45, evaluation.InstallationCosts);
     18      Assert.AreEqual(3764492, evaluation.FlowCosts);
     19      Assert.AreEqual(46, evaluation.InstallationCosts);
    2020      Assert.AreEqual(0, evaluation.ExcessDemand);
    2121
    22       var quality = new DoubleValue(instance.ToSingleObjective(evaluation));
    23       Assert.AreEqual(27898616.781881168, quality.Value, 1e-9);
     22      var quality = instance.ToSingleObjective(evaluation);
     23      Assert.AreEqual(14631771.476177376, quality, 1e-9);
    2424
    25       var evaluatedSolutions = new IntValue(0);
    26       ApproximateLocalSearch.Apply(random, assignment, quality,
    27         ref evaluation, new IntValue(10), new IntValue(1000), instance,
    28         evaluatedSolutions, new PercentValue(0.5));
    29       Assert.AreEqual(896, evaluatedSolutions.Value);
    30       CollectionAssert.AreEqual(new[] { 2, 0, 0, 3, 3, 1, 0, 0, 2, 0 }, assignment.ToArray());
    31       Assert.AreEqual(11733118.305768538, quality.Value, 1e-9);
     25      var evaluatedSolutions = 0;
     26      ApproximateLocalSearch.Apply(random, assignment, ref quality,
     27        ref evaluation, 10, 0.5, 1000, instance,
     28        out evaluatedSolutions);
     29      Assert.AreEqual(300, evaluatedSolutions);
     30      CollectionAssert.AreEqual(new[] { 3, 2, 2, 0, 0, 2, 2, 3, 0, 0 }, assignment.ToArray());
     31      Assert.AreEqual(14271146.913257681, quality, 1e-9);
    3232    }
    3333
Note: See TracChangeset for help on using the changeset viewer.