Changeset 8322


Ignore:
Timestamp:
07/25/12 10:14:58 (7 years ago)
Author:
jkarder
Message:

#1331:

Location:
branches/ScatterSearch (trunk integration)
Files:
13 edited

Legend:

Unmodified
Added
Removed
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs

    r8319 r8322  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using System.Linq;
    2524using HeuristicLab.Common;
     
    129128      if (orderedOffspring.Any(hasBetterQuality)) {
    130129        // produce the set union
    131         var union = orderedParents.Union(orderedOffspring.Where(hasBetterQuality), new SolutionEqualityComparer<IScope>(SimilarityCalculator.CalculateSolutionSimilarity));
     130        var union = orderedParents.Union(orderedOffspring.Where(hasBetterQuality), SimilarityCalculator);
    132131        if (union.Count() > orderedParents.Count()) {
    133132          var orderedUnion = Maximization.Value ? union.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
     
    140139      return base.Apply();
    141140    }
    142 
    143     // derive SingleObjectiveSolutionSimilarityCalculator from EqualityComparer
    144     // delete this ...
    145     public class SolutionEqualityComparer<T> : EqualityComparer<T> {
    146       private readonly Func<T, T, double> similarityCalculator;
    147 
    148       public SolutionEqualityComparer(Func<T, T, double> similarityCalculator) {
    149         this.similarityCalculator = similarityCalculator;
    150       }
    151 
    152       public override bool Equals(T x, T y) {
    153         if (object.ReferenceEquals(x, y)) return true;
    154         if (x == null || y == null) return false;
    155         return similarityCalculator(x, y) == 1.0;
    156       }
    157 
    158       public override int GetHashCode(T obj) {
    159         return 0; // return the same hash code for each object, otherwise Equals will not be called
    160       }
    161     }
    162141  }
    163142}
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization.Operators/3.3/SingleObjectiveSolutionSimilarityCalculator.cs

    r8319 r8322  
    3434    #region Properties
    3535    [Storable]
     36    public string SolutionVariableName { get; set; }
     37    [Storable]
    3638    public string QualityVariableName { get; set; }
    37     [Storable]
    38     public string SolutionVariableName { get; set; }
    3939    #endregion
    4040
     
    4343    protected SingleObjectiveSolutionSimilarityCalculator(SingleObjectiveSolutionSimilarityCalculator original, Cloner cloner)
    4444      : base(original, cloner) {
    45       if (original.QualityVariableName != null)
    46         this.QualityVariableName = (string)original.QualityVariableName.Clone();
     45      this.SolutionVariableName = original.SolutionVariableName;
     46      this.QualityVariableName = original.QualityVariableName;
    4747    }
    4848    protected SingleObjectiveSolutionSimilarityCalculator() : base() { }
    4949
    5050    public override int GetHashCode(IScope scope) {
    51       var quality = ((DoubleValue)scope.Variables[QualityVariableName].Value).Value;
    52       return quality.ToString().GetHashCode();
     51      return ((DoubleValue)scope.Variables[QualityVariableName].Value).Value.GetHashCode();
    5352    }
    5453  }
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization.Operators/3.3/SolutionSimilarityCalculator.cs

    r8319 r8322  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using System.Linq;
    2524using HeuristicLab.Common;
     
    3332  [Item("SimilarityCalculator", "A base class for items that perform similarity calculation between two solutions.")]
    3433  [StorableClass]
    35   public abstract class SolutionSimilarityCalculator : Item, ISolutionSimilarityCalculator, IEqualityComparer<IScope> {
     34  public abstract class SolutionSimilarityCalculator : Item, ISolutionSimilarityCalculator {
    3635    [StorableConstructor]
    3736    protected SolutionSimilarityCalculator(bool deserializing) : base(deserializing) { }
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization/3.3/Interfaces/ISingleObjectiveSolutionSimilarityCalculator.cs

    r8319 r8322  
    2525  /// </summary>
    2626  public interface ISingleObjectiveSolutionSimilarityCalculator : ISolutionSimilarityCalculator {
     27    string SolutionVariableName { get; set; }
    2728    string QualityVariableName { get; set; }
    28     string SolutionVariableName { get; set; }
    2929  }
    3030}
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization/3.3/Interfaces/ISolutionSimilarityCalculator.cs

    r8319 r8322  
    2020#endregion
    2121
     22using System.Collections.Generic;
    2223using HeuristicLab.Core;
    2324
     
    2627  /// An interface which represents an operator for similarity calculation.
    2728  /// </summary>
    28   public interface ISolutionSimilarityCalculator : IItem {
     29  public interface ISolutionSimilarityCalculator : IItem, IEqualityComparer<IScope> {
    2930    /// <summary>
    3031    /// Calculates the similarity of two solutions.
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs

    r8319 r8322  
    305305      foreach (KnapsackSimilarityCalculator op in Operators.OfType<KnapsackSimilarityCalculator>()) {
    306306        op.SolutionVariableName = SolutionCreator.BinaryVectorParameter.ActualName;
     307        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
    307308      }
    308309    }
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TestFunctions/3.3/Improvers/SingleObjectiveTestFunctionImprovementOperator.cs

    r8319 r8322  
    3636  /// </summary>
    3737  /// <remarks>
    38   /// It is implemented as described in Gao, F. and Han, L. (2010). Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications, Vol. 51. Springer.<br />
    39   /// The operator is an implementation of the Nelder-Mead method and conducts relection, expansion, contraction and reduction on the test functions solution.
     38  /// It is implemented as described in Laguna, M. and Martí, R. (2003). Scatter Search: Methodology and Implementations in C. Operations Research/Computer Science Interfaces Series, Vol. 24. Springer.<br />
     39  /// The operator uses an implementation of the Nelder-Mead method with adaptive parameters as described in Gao, F. and Han, L. (2010). Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications, Vol. 51. Springer. and conducts relection, expansion, contraction and reduction on the test functions solution.
    4040  /// </remarks>
    4141  [Item("SingleObjectiveTestFunctionImprovementOperator", "An operator that improves test functions solutions.")]
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TestFunctions/3.3/PathRelinkers/SingleObjectiveTestFunctionPathRelinker.cs

    r8319 r8322  
    3636  /// </summary>
    3737  /// <remarks>
    38   /// TODO: add reference and remarks
     38  /// It is implemented as described in Duarte, A., Martí, R., and Gortazar, F. (2011). Path Relinking for Large Scale Global Optimization. Soft Computing, Vol. 15.
     39  /// The operator incrementally assimilates the initiating solution into the guiding solution by adapting the solution vector's elements.
    3940  /// </remarks>
    4041  [Item("SingleObjectiveTestFunctionPathRelinker", "An operator that relinks paths between test functions solutions.")]
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TestFunctions/3.3/SingleObjectiveTestFunctionProblem.cs

    r8319 r8322  
    377377      foreach (SingleObjectiveTestFunctionSimilarityCalculator op in Operators.OfType<SingleObjectiveTestFunctionSimilarityCalculator>()) {
    378378        op.SolutionVariableName = SolutionCreator.RealVectorParameter.ActualName;
     379        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
    379380        op.Bounds = Bounds;
    380381      }
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/PathRelinkers/TSPMultipleGuidesPathRelinker.cs

    r8319 r8322  
    8585        int bestCityIndex = (i + 1) % v1.Length;
    8686        double currDistance = distances[v1[currCityIndex], v1[bestCityIndex]];
     87        // check each guiding solution
    8788        targets.ToList().ForEach(solution => {
    88           var node = solution.Select((x, index) => new { Id = x, Index = index }).First(x => x.Id == v1[currCityIndex]);
     89          // locate current city
     90          var node = solution.Select((x, index) => new { Id = x, Index = index }).Single(x => x.Id == v1[currCityIndex]);
    8991          int pred = solution[(node.Index - 1 + solution.Length) % solution.Length];
    9092          int succ = solution[(node.Index + 1) % solution.Length];
     93          // get distances to neighbors
    9194          var results = new[] { pred, succ }.Select(x => new { Id = x, Distance = distances[x, node.Id] });
    92           if (results.Any(x => x.Distance < currDistance)) {
    93             var bestCity = results.OrderBy(x => x.Distance).First();
    94             bestCityIndex = v1.Select((x, index) => new { Id = x, Index = index }).First(x => x.Id == bestCity.Id).Index;
     95          var bestCity = results.Where(x => x.Distance < currDistance).OrderBy(x => x.Distance).FirstOrDefault();
     96          if (bestCity != null) {
     97            bestCityIndex = v1.Select((x, index) => new { Id = x, Index = index }).Single(x => x.Id == bestCity.Id).Index;
    9598            currDistance = bestCity.Distance;
    9699          }
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs

    r8319 r8322  
    6767    private static double CalculateAbsolute(Permutation left, Permutation right) {
    6868      double similarity = 0.0;
    69       for (int i = 0; i < left.Length && left[i] == right[i]; similarity = ++i) ;
     69      for (int i = 0; i < left.Length; i++)
     70        if (left[i] == right[i]) similarity++;
     71
    7072      return similarity / left.Length;
    7173    }
    7274
    7375    private static double CalculateRelativeDirected(Permutation left, Permutation right) {
    74       throw new NotImplementedException();
     76      int[] edges = new int[right.Length];
     77      for (int i = 0; i < right.Length; i++)
     78        edges[right[i]] = right[(i + 1) % right.Length];
     79
     80      double similarity = 0.0;
     81      for (int i = 0; i < left.Length; i++)
     82        if (left[(i + 1) % left.Length] == edges[left[i]]) similarity++;
     83
     84      return similarity / left.Length;
    7585    }
    7686
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

    r8319 r8322  
    352352      foreach (TSPSimilarityCalculator op in Operators.OfType<TSPSimilarityCalculator>()) {
    353353        op.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
     354        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
    354355      }
    355356    }
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/VehicleRoutingProblem.cs

    r8319 r8322  
    531531      foreach (VRPSimilarityCalculator op in Operators.OfType<VRPSimilarityCalculator>()) {
    532532        op.SolutionVariableName = SolutionCreator.VRPToursParameter.ActualName;
     533        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
    533534      }
    534535    }
Note: See TracChangeset for help on using the changeset viewer.