Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
05/02/12 19:09:48 (13 years ago)
Author:
jkarder
Message:

#1331:

  • added operators for TestFunctions problems
  • added more path relinking operators for the TravelingSalesman and the Knapsack problem
  • added 2-tier version of the SolutionPoolUpdateMethod
  • added parameters and adjusted types
  • added some exception handling
  • adjusted event handling
  • updated plugin dependencies
  • minor code improvements
Location:
branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3
Files:
19 added
17 edited

Legend:

Unmodified
Added
Removed

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/DiversityCalculator.cs

    r7744 r7775  
    4242    }
    4343
    44     public int ExecuteCalculation(IItem left, IItem right) {
    45       if (left == null || right == null) throw new ArgumentException("Cannot calculate diversity because one of the provided objects is null.");
    46       if (left.GetType() != right.GetType()) throw new ArgumentException("Cannot calculate diversity because the provided objects differ in type.");
     44    public double ExecuteCalculation(IItem left, IItem right) {
     45      if (left == null || right == null)
     46        throw new ArgumentException("Cannot calculate diversity because one of the provided objects is null.");
     47      if (left.GetType() != right.GetType())
     48        throw new ArgumentException("Cannot calculate diversity because the provided objects differ in type.");
     49
    4750      if (left == right) return 0;
    4851      else return CalculateDiversity(left, right);
    4952    }
    5053
    51     protected abstract int CalculateDiversity(IItem left, IItem right);
     54    protected abstract double CalculateDiversity(IItem left, IItem right);
    5255  }
    5356}

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/HeuristicLab.Algorithms.ScatterSearch-3.3.csproj

    r7756 r7775  
    3939  </PropertyGroup>
    4040  <ItemGroup>
    41     <Reference Include="HeuristicLab.Algorithms.LocalSearch-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    4241    <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    4342    <Reference Include="HeuristicLab.Collections-3.3">
    … …  
    5554    <Reference Include="HeuristicLab.Encodings.BinaryVectorEncoding-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    5655    <Reference Include="HeuristicLab.Encodings.PermutationEncoding-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
     56    <Reference Include="HeuristicLab.Encodings.RealVectorEncoding-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    5757    <Reference Include="HeuristicLab.Operators-3.3">
    5858      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Operators-3.3.dll</HintPath>
    … …  
    7272    <Reference Include="HeuristicLab.PluginInfrastructure-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    7373    <Reference Include="HeuristicLab.Problems.Knapsack-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
     74    <Reference Include="HeuristicLab.Problems.TestFunctions-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    7475    <Reference Include="HeuristicLab.Problems.TravelingSalesman-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    7576    <Reference Include="HeuristicLab.Random-3.3">
    … …  
    8687  </ItemGroup>
    8788  <ItemGroup>
     89    <Compile Include="SolutionPool2TierUpdateMethod.cs" />
    8890    <Compile Include="DiversityCalculator.cs" />
    8991    <Compile Include="IPathRelinker.cs" />
    9092    <Compile Include="Knapsack\BinaryVectorDiversityCalculator.cs" />
     93    <Compile Include="Knapsack\KnapsackMultipleGuidesPathRelinker.cs" />
     94    <Compile Include="Knapsack\KnapsackSimultaneousPathRelinker.cs" />
    9195    <Compile Include="Knapsack\KnapsackPathRelinker.cs" />
     96    <Compile Include="TestFunctions\TestFunctionsZakharovImprovementOperator.cs" />
     97    <Compile Include="TestFunctions\TestFunctionsSumSquaresImprovementOperator.cs" />
     98    <Compile Include="TestFunctions\TestFunctionsSchwefelImprovementOperator.cs" />
     99    <Compile Include="TestFunctions\TestFunctionsRosenbrockImprovementOperator.cs" />
     100    <Compile Include="TestFunctions\TestFunctionsMatyasImprovementOperator.cs" />
     101    <Compile Include="TestFunctions\TestFunctionsLevyImprovementOperator.cs" />
     102    <Compile Include="TestFunctions\TestFunctionsGriewankImprovementOperator.cs" />
     103    <Compile Include="TestFunctions\TestFunctionsBoothImprovementOperator.cs" />
     104    <Compile Include="TestFunctions\TestFunctionsBealeImprovementOperator.cs" />
     105    <Compile Include="TestFunctions\TestFunctionsAckleyImprovementOperator.cs" />
     106    <Compile Include="TestFunctions\TestFunctionsPathRelinker.cs" />
     107    <Compile Include="TestFunctions\RealVectorDiversityCalculator.cs" />
     108    <Compile Include="TestFunctions\TestFunctionsImprovementOperator.cs" />
     109    <Compile Include="TravelingSalesman\TravelingSalesmanMultipleGuidesPathRelinker.cs" />
     110    <Compile Include="TravelingSalesman\TravelingSalesmanSimultaneousPathRelinker.cs" />
    92111    <Compile Include="TravelingSalesman\TravelingSalesmanPathRelinker.cs" />
    93112    <Compile Include="PathRelinker.cs" />

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/IScatterSearchTargetProcessor.cs

    r7744 r7775  
    2323
    2424namespace HeuristicLab.Algorithms.ScatterSearch {
     25  /// <summary>
     26  /// An interface which represents an operator that uses a target parameter.
     27  /// </summary>
    2528  public interface IScatterSearchTargetProcessor {
    2629    IValueLookupParameter<IItem> TargetParameter { get; }

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/BinaryVectorDiversityCalculator.cs

    r7756 r7775  
    2020#endregion
    2121
     22using System;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
    … …  
    4142    }
    4243
    43     protected override int CalculateDiversity(IItem left, IItem right) {
     44    protected override double CalculateDiversity(IItem left, IItem right) {
     45      if (!(left is BinaryVector) || !(right is BinaryVector))
     46        throw new ArgumentException("Cannot calculate diversity because one of the provided objects or both have the wrong type.");
     47
    4448      var v1 = left as BinaryVector;
    4549      var v2 = right as BinaryVector;
    46       int diversity = 0;
    47       if (v1 != null && v2 != null)
    48         for (int i = 0; i < v1.Length; i++)
    49           if (v1[i] != v2[i]) diversity++;
     50      double diversity = 0;
     51      for (int i = 0; i < v1.Length; i++)
     52        if (v1[i] != v2[i]) diversity++;
    5053      return diversity;
    5154    }

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/KnapsackImprovementOperator.cs

    r7756 r7775  
    6767      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
    6868    }
     69    public IValueLookupParameter<DoubleValue> PenaltyParameter {
     70      get { return (IValueLookupParameter<DoubleValue>)Parameters["Penalty"]; }
     71    }
    6972    #region ILocalImprovementOperator Parameters
    7073    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
    … …  
    99102      get { return TargetParameter.ActualValue; }
    100103    }
     104    private DoubleValue Penalty {
     105      get { return PenaltyParameter.ActualValue; }
     106      set { PenaltyParameter.ActualValue = value; }
     107    }
    101108    #endregion
    102109
    … …  
    115122      Parameters.Add(new ValueLookupParameter<IntValue>("KnapsackCapacity"));
    116123      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
     124      Parameters.Add(new ValueLookupParameter<DoubleValue>("Penalty"));
    117125      #endregion
    118126      TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
    … …  
    128136      // calculate value-to-weight ratio
    129137      double[] ratio = new double[Values.Length];
    130       for (int i = 0; i < ratio.Length; i++) {
     138      for (int i = 0; i < ratio.Length; i++)
    131139        ratio[i] = (double)Values[i] / (double)Weights[i];
    132       }
     140
    133141
    134142      // calculate order for ratio
    … …  
    140148
    141149      int j = sol.Length - 1;
    142       while (KnapsackEvaluator.Apply(sol, KnapsackCapacity, new DoubleValue(1.0), Weights, Values).SumWeights.Value > KnapsackCapacity.Value && j >= 0) {
     150      while (KnapsackEvaluator.Apply(sol, KnapsackCapacity, Penalty, Weights, Values)
     151                              .SumWeights.Value > KnapsackCapacity.Value && j >= 0)
    143152        sol[order[j--]] = false;
    144       }
    145153
    146154      // calculate weight
    147       int lhs = 0;
    148       for (int i = 0; i < sol.Length; i++) {
    149         if (sol[i]) lhs += Weights[i];
    150       }
     155      int weight = 0;
     156      for (int i = 0; i < sol.Length; i++)
     157        if (sol[i]) weight += Weights[i];
    151158
    152159      // improve solution
    … …  
    154161      while (feasible && j < sol.Length) {
    155162        while (sol[order[j]]) j++;
    156         if (lhs + Weights[order[j]] <= KnapsackCapacity.Value) {
     163        if (weight + Weights[order[j]] <= KnapsackCapacity.Value) {
    157164          sol[order[j]] = true;
    158           lhs += Weights[order[j]];
    159         } else {
    160           feasible = false;
    161         }
     165          weight += Weights[order[j]];
     166        } else feasible = false;
    162167      }
    163168
    … …  
    166171      return base.Apply();
    167172    }
    168 
    169     private bool IsFeasiblse(BinaryVector sol) {
    170       int sum = 0;
    171       for (int i = 0; i < sol.Length; i++)
    172         if (sol[i]) sum += Weights[i];
    173       return sum <= KnapsackCapacity.Value;
    174     }
    175173  }
    176174}

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/KnapsackPathRelinker.cs

    r7756 r7775  
    4949
    5050    public static ItemArray<IItem> Apply(IItem initiator, IItem guide, PercentValue n) {
     51      if (!(initiator is BinaryVector) || !(guide is BinaryVector))
     52        throw new ArgumentException("Cannot relink path because one of the provided solutions or both have the wrong type.");
     53      if (n.Value <= 0.0)
     54        throw new ArgumentException("RelinkingAccuracy must be greater than 0.");
     55
    5156      var v1 = initiator.Clone() as BinaryVector;
    5257      var v2 = guide as BinaryVector;
    5358
    5459      if (v1.Length != v2.Length)
    55         throw new ArgumentException("KnapsackPathRelinker: The solutions are of different length.");
    56       if (n.Value == 0.0)
    57         throw new ArgumentException("KnapsackPathRelinker: RelinkingAccuracy is 0.");
     60        throw new ArgumentException("The solutions are of different length.");
    5861
    5962      var solutions = new List<BinaryVector>();
    60       for (int i = 0; i < v1.Length; i++) {
     63      for (int i = 0; i < v1.Length; i++)
    6164        if (v1[i] != v2[i]) {
    6265          v1[i] = v2[i];
    63           solutions.Add((BinaryVector)v1.Clone());
     66          solutions.Add(v1.Clone() as BinaryVector);
    6467        }
    65       }
    6668
    67       var stepSize = 1 / n.Value;
    6869      var selection = new List<IItem>();
    69       for (int i = 0; i < solutions.Count; i = (int)Math.Round(i + stepSize)) {
    70         selection.Add(solutions.ElementAt(i));
     70      if (solutions.Count > 0) {
     71        var noSol = (int)Math.Round(solutions.Count * n.Value);
     72        if (noSol <= 0) noSol++;
     73        var stepSize = (double)solutions.Count / (double)noSol;
     74        for (int i = 0; i < noSol; i++)
     75          selection.Add(solutions.ElementAt((int)Math.Round((i + 1) * stepSize - stepSize * 0.5)));
    7176      }
    7277
    … …  
    7580
    7681    protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
    77       if (parents.Length != 2) throw new ArgumentException("KnapsackPathRelinker: The number of parents is not equal to 2.");
     82      if (parents.Length != 2)
     83        throw new ArgumentException("The number of parents is not equal to 2.");
    7884      return Apply(parents[0], parents[1], n);
    7985    }

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/NBinaryVectorCrossover.cs

    r7756 r7775  
    7272    public sealed override IOperation Apply() {
    7373      var offspringSolutions = Cross(RandomParameter.ActualValue, ParentsParameter.ActualValue);
    74       for (int i = 0; i < offspringSolutions.Length; i++) {
     74      for (int i = 0; i < offspringSolutions.Length; i++)
    7575        CurrentScope.Variables.Add(new Variable(string.Format("Child {0}", i), offspringSolutions[i]));
    76       }
    7776      return base.Apply();
    7877    }

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/NChildCrossover.cs

    r7756 r7775  
    5858      if (parent1.Length != parent2.Length)
    5959        throw new ArgumentException("NChildCrossover: The parents are of different length.");
    60 
    6160      if (n.Value > Math.Pow(2, parent1.Length) - 2)
    6261        throw new ArgumentException("NChildCrossover: There cannot be more children than 2^size of parents - 2.");
    63 
    6462      if (n.Value < 1)
    6563        throw new ArgumentException("NChildCrossover: N cannot be < 1.");
    … …  
    6866      for (int i = 0; i < n.Value; i++) {
    6967        var solution = new BinaryVector(parent1.Length);
    70         for (int j = 0; j < solution.Length; j++) {
     68        for (int j = 0; j < solution.Length; j++)
    7169          solution[j] = random.Next(2) % 2 == 0 ? parent1[j] : parent2[j];
    72         }
    7370        solutions[i] = solution;
    7471      }
    … …  
    7875
    7976    protected override ItemArray<BinaryVector> Cross(IRandom random, ItemArray<BinaryVector> parents) {
    80       if (parents.Length != 2) throw new ArgumentException("NChildCrossover: The number of parents is not equal to 2.");
    81 
    82       if (NParameter.ActualValue == null) throw new InvalidOperationException("NChildCrossover: Parameter " + NParameter.ActualName + " could not be found.");
    83 
     77      if (parents.Length != 2)
     78        throw new ArgumentException("NChildCrossover: The number of parents is not equal to 2.");
     79      if (NParameter.ActualValue == null)
     80        throw new InvalidOperationException("NChildCrossover: Parameter " + NParameter.ActualName + " could not be found.");
    8481      return Apply(random, parents[0], parents[1], NParameter.Value);
    8582    }

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/PathRelinker.cs

    r7756 r7775  
    3131  /// A base class for operators that perform path relinking.
    3232  /// </summary>
    33   [Item("PathRelinker", "A base class for operators that perform a crossover of bool-valued vectors.")]
     33  [Item("PathRelinker", "A base class for operators that perform path relinking.")]
    3434  [StorableClass]
    3535  public abstract class PathRelinker : SingleSuccessorOperator, IPathRelinker {
    … …  
    3838      get { return (ScopeParameter)Parameters["CurrentScope"]; }
    3939    }
    40     public IValueLookupParameter<PercentValue> RelinkingAccuracyParameter {
    41       get { return (IValueLookupParameter<PercentValue>)Parameters["RelinkingAccuracy"]; }
     40    public IValueParameter<PercentValue> RelinkingAccuracyParameter {
     41      get { return (IValueParameter<PercentValue>)Parameters["RelinkingAccuracy"]; }
    4242    }
    4343    public ILookupParameter<ItemArray<IItem>> ParentsParameter {
    … …  
    5050      get { return CurrentScopeParameter.ActualValue; }
    5151    }
     52    private PercentValue RelinkingAccuracy {
     53      get { return RelinkingAccuracyParameter.Value; }
     54    }
     55    private ItemArray<IItem> Parents {
     56      get { return ParentsParameter.ActualValue; }
     57    }
    5258    #endregion
    5359
    … …  
    5965      #region Create parameters
    6066      Parameters.Add(new ScopeParameter("CurrentScope"));
    61       Parameters.Add(new ValueLookupParameter<PercentValue>("RelinkingAccuracy", new PercentValue(0.25)));
     67      Parameters.Add(new ValueParameter<PercentValue>("RelinkingAccuracy", new PercentValue(0.25)));
    6268      Parameters.Add(new ScopeTreeLookupParameter<IItem>("Parents"));
    6369      #endregion
    … …  
    6571
    6672    public sealed override IOperation Apply() {
    67       var relinkedSolutions = Relink(ParentsParameter.ActualValue, RelinkingAccuracyParameter.ActualValue);
    68       for (int i = 0; i < relinkedSolutions.Length; i++) {
     73      var relinkedSolutions = Relink(Parents, RelinkingAccuracy);
     74      for (int i = 0; i < relinkedSolutions.Length; i++)
    6975        CurrentScope.Variables.Add(new Variable(string.Format("Child {0}", i), relinkedSolutions[i]));
    70       }
    7176      return base.Apply();
    7277    }

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Plugin.cs.frame

    r7722 r7775  
    2626  /// Plugin class for HeuristicLab.Algorithms.ScatterSearch plugin.
    2727  /// </summary>
    28   [Plugin("HeuristicLab.Algorithms.ScatterSearch", "3.3.6.$WCREV$")]
     28  [Plugin("HeuristicLab.Algorithms.ScatterSearch", "3.3.6.7756")]
    2929  [PluginFile("HeuristicLab.Algorithms.ScatterSearch-3.3.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Analysis", "3.3")]
    … …  
    3333  [PluginDependency("HeuristicLab.Core", "3.3")]
    3434  [PluginDependency("HeuristicLab.Data", "3.3")]
     35  [PluginDependency("HeuristicLab.Encodings.BinaryVectorEncoding", "3.3")]
     36  [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
     37  [PluginDependency("HeuristicLab.Encodings.RealVectorEncoding", "3.3")]
    3538  [PluginDependency("HeuristicLab.Operators", "3.3")]
    3639  [PluginDependency("HeuristicLab.Optimization", "3.3")]
    … …  
    3841  [PluginDependency("HeuristicLab.Parameters", "3.3")]
    3942  [PluginDependency("HeuristicLab.Persistence", "3.3")]
     43  [PluginDependency("HeuristicLab.Problems.Knapsack", "3.3")]
     44  [PluginDependency("HeuristicLab.Problems.TestFunctions", "3.3")]
     45  [PluginDependency("HeuristicLab.Problems.TravelingSalesman", "3.3")]
    4046  [PluginDependency("HeuristicLab.Random", "3.3")]
    4147  [PluginDependency("HeuristicLab.Selection", "3.3")]

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/ReferenceSetUpdateMethod.cs

    r7744 r7775  
    9595      var population = new Dictionary<IScope, double>();
    9696      foreach (var pScope in CurrentScope.SubScopes[0].SubScopes) {
    97         int diversity = 0;
     97        double diversity = 0;
    9898        var pSol = pScope.Variables[TargetParameter.ActualName].Value;
    9999        foreach (var rScope in CurrentScope.SubScopes[1].SubScopes) {

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearch.cs

    r7756 r7775  
    306306      ICrossover defaultCrossover = Problem.Operators.OfType<ICrossover>().FirstOrDefault();
    307307
     308      CrossoverParameter.ValidValues.Add(new Knapsack.KnapsackPathRelinker());
     309      CrossoverParameter.ValidValues.Add(new Knapsack.KnapsackSimultaneousPathRelinker());
     310      CrossoverParameter.ValidValues.Add(new TestFunctions.TestFunctionsPathRelinker());
    308311      CrossoverParameter.ValidValues.Add(new TravelingSalesman.TravelingSalesmanPathRelinker());
    309       CrossoverParameter.ValidValues.Add(new Knapsack.KnapsackPathRelinker());
     312      CrossoverParameter.ValidValues.Add(new TravelingSalesman.TravelingSalesmanSimultaneousPathRelinker());
     313      CrossoverParameter.ValidValues.Add(new TravelingSalesman.TravelingSalesmanMultipleGuidesPathRelinker());
    310314
    311315      foreach (ICrossover crossover in Problem.Operators.OfType<ICrossover>().OrderBy(x => x.Name))
    … …  
    329333
    330334      DiversityCalculatorParameter.ValidValues.Add(new Knapsack.BinaryVectorDiversityCalculator());
     335      DiversityCalculatorParameter.ValidValues.Add(new TestFunctions.RealVectorDiversityCalculator());
    331336      DiversityCalculatorParameter.ValidValues.Add(new TravelingSalesman.PermutationDiversityCalculator());
    332337
    … …  
    348353
    349354      ImproverParameter.ValidValues.Add(new Knapsack.KnapsackImprovementOperator());
     355      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsAckleyImprovementOperator());
     356      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsBealeImprovementOperator());
     357      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsBoothImprovementOperator());
     358      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsGriewankImprovementOperator());
     359      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsLevyImprovementOperator());
     360      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsMatyasImprovementOperator());
     361      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsRosenbrockImprovementOperator());
     362      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsSchwefelImprovementOperator());
     363      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsSumSquaresImprovementOperator());
     364      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsZakharovImprovementOperator());
    350365      ImproverParameter.ValidValues.Add(new TravelingSalesman.TravelingSalesmanImprovementOperator());
    351366

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearchMainLoop.cs

    r7744 r7775  
    3333  /// An operator which represents a scatter search.
    3434  /// </summary>
    35   [Item("ScatterSearchMainLoop", "An operator which represents the main loop of a scatter search.")]
     35  [Item("ScatterSearchMainLoop", "An operator which represents a scatter search.")]
    3636  [StorableClass]
    3737  public sealed class ScatterSearchMainLoop : AlgorithmOperator {

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs

    r7744 r7775  
    123123      var worstParentQuality = (orderedParents.Last().Variables[QualityParameter.ActualName].Value as DoubleValue).Value;
    124124
    125       var Constraint = Maximization.Value ? (Func<IScope, bool>)(x => { return (x.Variables[QualityParameter.ActualName].Value as DoubleValue).Value > worstParentQuality; }) :
     125      var hasBetterQuality = Maximization.Value ? (Func<IScope, bool>)(x => { return (x.Variables[QualityParameter.ActualName].Value as DoubleValue).Value > worstParentQuality; }) :
    126126                                            (Func<IScope, bool>)(x => { return (x.Variables[QualityParameter.ActualName].Value as DoubleValue).Value < worstParentQuality; });
    127127
    128128      // is there any offspring better than the worst parent?
    129       if (orderedOffspring.Any(Constraint)) {
     129      if (orderedOffspring.Any(hasBetterQuality)) {
    130130        // produce the set union
    131131        // attention: distinction might cause a too small reference set! (e.g. reference set = {1, 2, 2, 2, ..., 2} -> union = {1, 2}
    132         var union = orderedParents.Union(orderedOffspring.Where(Constraint), new KeyEqualityComparer<IScope>(x => x.Variables[TargetParameter.ActualName].Value.ToString()));
    133         if (union.Count() > orderedParents./*Distinct(new KeyEqualityComparer<IScope>(x => x.Variables[TargetParameter.ActualName].Value.ToString())).*/Count()) {
     132        var union = orderedParents.Union(orderedOffspring.Where(hasBetterQuality), new KeyEqualityComparer<IScope>(x => x.Variables[TargetParameter.ActualName].Value.ToString()));
     133        if (union.Count() > orderedParents/*.Distinct(new KeyEqualityComparer<IScope>(x => x.Variables[TargetParameter.ActualName].Value.ToString()))*/.Count()) {
    134134          var orderedUnion = Maximization.Value ? union.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
    135135                                                  union.OrderBy(x => x.Variables[QualityParameter.ActualName].Value);

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/TravelingSalesman/PermutationDiversityCalculator.cs

    r7756 r7775  
    2020#endregion
    2121
     22using System;
    2223using System.Linq;
    2324using HeuristicLab.Common;
    … …  
    4243    }
    4344
    44     protected override int CalculateDiversity(IItem left, IItem right) {
     45    protected override double CalculateDiversity(IItem left, IItem right) {
     46      if (!(left is Permutation) || !(right is Permutation))
     47        throw new ArgumentException("Cannot calculate diversity because one of the provided objects or both have the wrong type.");
     48
    4549      var v1 = left as Permutation;
    4650      var v2 = right as Permutation;
    47       int diversity = 0;
    48       if (v1 != null && v2 != null)
    49         for (int i = 0; i < v1.Length; i++) {
    50           var node = v2.Select((x, index) => new { Value = x, ValueIndex = index }).First(x => x.Value == v1[i]);
    51           var pred = v2[(node.ValueIndex - 1 + v2.Length) % v2.Length];
    52           var succ = v2[(node.ValueIndex + 1 % v2.Length) % v2.Length];
    53           if (new[] { pred, succ }.All(x => x != v1[(i + 1) % v1.Length])) diversity++;
    54         }
     51      double diversity = 0.0;
     52      for (int i = 0; i < v1.Length; i++) {
     53        var node = v2.Select((x, index) => new { Value = x, ValueIndex = index }).First(x => x.Value == v1[i]);
     54        var pred = v2[(node.ValueIndex - 1 + v2.Length) % v2.Length];
     55        var succ = v2[(node.ValueIndex + 1) % v2.Length];
     56        if (new[] { pred, succ }.All(x => x != v1[(i + 1) % v1.Length])) diversity++;
     57      }
    5558      return diversity;
    5659    }

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/TravelingSalesman/TravelingSalesmanImprovementOperator.cs

    r7756 r7775  
    138138
    139139      for (int i = 0; i < ImprovementAttempts.Value; i++) {
    140         int a = Random.Next(currSol.Length - 1);
    141         int b = Random.Next(currSol.Length - 1);
     140        int a = Random.Next(currSol.Length);
     141        int b = Random.Next(currSol.Length);
    142142        Invert(currSol, a, b);
    143143        currLength = TSPEuclideanPathEvaluator.Apply(Evaluator as TSPCoordinatesPathEvaluator, Coordinates, currSol);
    144144        if (currLength < bestLength) {
    145145          bestLength = currLength;
    146           bestSol = (Permutation)currSol.Clone();
     146          bestSol = currSol.Clone() as Permutation;
    147147        }
    148148        Invert(currSol, a, b);
    … …  
    155155
    156156    private void Invert(Permutation sol, int i, int j) {
    157       if (i != j) {
    158         for (int a = 0; a < Math.Abs(i - j) / 2; a++) {
    159           int tmp = sol[(i + a) % sol.Length];
    160           sol[(i + a) % sol.Length] = sol[(j - a + sol.Length) % sol.Length];
    161           sol[(j - a + sol.Length) % sol.Length] = tmp;
    162         }
    163       }
     157      if (i != j)
     158        for (int a = 0; a < Math.Abs(i - j) / 2; a++)
     159          if (sol[(i + a) % sol.Length] != sol[(j - a + sol.Length) % sol.Length]) {
     160            // XOR swap
     161            sol[(i + a) % sol.Length] ^= sol[(j - a + sol.Length) % sol.Length];
     162            sol[(j - a + sol.Length) % sol.Length] ^= sol[(i + a) % sol.Length];
     163            sol[(i + a) % sol.Length] ^= sol[(j - a + sol.Length) % sol.Length];
     164          }
    164165    }
    165166  }

  • branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/TravelingSalesman/TravelingSalesmanPathRelinker.cs

    r7756 r7775  
    4949
    5050    public static ItemArray<IItem> Apply(IItem initiator, IItem guide, PercentValue n) {
     51      if (!(initiator is Permutation) || !(guide is Permutation))
     52        throw new ArgumentException("Cannot relink path because one of the provided solutions or both have the wrong type.");
     53      if (n.Value <= 0.0)
     54        throw new ArgumentException("RelinkingAccuracy must be greater than 0.");
     55
    5156      var v1 = initiator.Clone() as Permutation;
    5257      var v2 = guide as Permutation;
    5358
    5459      if (v1.Length != v2.Length)
    55         throw new ArgumentException("TravelingSalesmanPathRelinker: The solutions are of different length.");
    56       if (n.Value == 0.0)
    57         throw new ArgumentException("TravelingSalesmanPathRelinker: RelinkingAccuracy is 0.");
     60        throw new ArgumentException("The solutions are of different length.");
    5861
    5962      var solutions = new List<Permutation>();
    60       for (int i = 0; i < v1.Length; i++) {
     63      for (int i = 0; i < v1.Length; i++)
    6164        if (v1[i] != v2[i]) {
    6265          var target = v1.Select((x, index) => new { Value = x, ValueIndex = index }).First(x => x.Value == v2[i]);
    63           // XOR swap
    64           v1[i] ^= v1[target.ValueIndex];
    65           v1[target.ValueIndex] ^= v1[i];
    66           v1[i] ^= v1[target.ValueIndex];
    67           solutions.Add((Permutation)v1.Clone());
     66          if (v1[i] != v1[target.ValueIndex]) {
     67            // XOR swap
     68            v1[i] ^= v1[target.ValueIndex];
     69            v1[target.ValueIndex] ^= v1[i];
     70            v1[i] ^= v1[target.ValueIndex];
     71            solutions.Add(v1.Clone() as Permutation);
     72          }
    6873        }
    69       }
    7074
    71       var stepSize = 1 / n.Value;
    7275      var selection = new List<IItem>();
    73       for (int i = 0; i < solutions.Count; i = (int)Math.Round(i + stepSize)) {
    74         selection.Add(solutions.ElementAt(i));
     76      if (solutions.Count > 0) {
     77        var noSol = (int)Math.Round(solutions.Count * n.Value);
     78        if (noSol <= 0) noSol++;
     79        var stepSize = (double)solutions.Count / (double)noSol;
     80        for (int i = 0; i < noSol; i++)
     81          selection.Add(solutions.ElementAt((int)Math.Round((i + 1) * stepSize - stepSize * 0.5)));
    7582      }
    7683
    … …  
    7986
    8087    protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
    81       if (parents.Length != 2) throw new ArgumentException("TravelingSalesmanPathRelinker: The number of parents is not equal to 2.");
     88      if (parents.Length != 2)
     89        throw new ArgumentException("The number of parents is not equal to 2.");
    8290      return Apply(parents[0], parents[1], n);
    8391    }
Note: See TracChangeset for help on using the changeset viewer.