Changeset 14429 for branches/ScopedAlgorithms

Timestamp:

11/29/16 15:46:48 (8 years ago)

Author:

abeham

Message:

#2701, #2708: Made a new branch from ProblemRefactoring and removed ScopedBasicAlgorithm branch (which becomes MemPR branch)

Location:

branches/ScopedAlgorithms

Files:

• . (copied) (copied from branches/ProblemRefactoring)
• HeuristicLab 3.3.sln (modified) (2 diffs)
• HeuristicLab.Algorithms.GeneticAlgorithm/3.3/BinaryCanonicalGeneticAlgorithm.cs (added)
• HeuristicLab.Algorithms.GeneticAlgorithm/3.3/CanonicalGeneticAlgorithm.cs (added)
• HeuristicLab.Algorithms.GeneticAlgorithm/3.3/EvolutionaryAlgorithmContext.cs (added)
• HeuristicLab.Algorithms.GeneticAlgorithm/3.3/HeuristicLab.Algorithms.GeneticAlgorithm-3.3.csproj (modified) (2 diffs)
• HeuristicLab.Algorithms.LocalSearch/3.3/BinaryIteratedLocalSearch.cs (added)
• HeuristicLab.Algorithms.LocalSearch/3.3/HeuristicLab.Algorithms.LocalSearch-3.3.csproj (modified) (2 diffs)
• HeuristicLab.Algorithms.LocalSearch/3.3/IteratedLocalSearch.cs (added)
• HeuristicLab.Algorithms.LocalSearch/3.3/LocalSearchContext.cs (added)
• HeuristicLab.Core/3.3/Attributes/ItemAttribute.cs (modified) (2 diffs)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Crossovers/NPointCrossover.cs (modified) (4 diffs)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Crossovers/SinglePointCrossover.cs (modified) (1 diff)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/HeuristicLab.Encodings.BinaryVectorEncoding-3.3.csproj (modified) (3 diffs)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Interfaces/IBinaryLocalSearch.cs (added)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Interfaces/IBinaryVectorCrossover.cs (modified) (2 diffs)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/LocalSearch (added)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/LocalSearch/ExhaustiveBitflip.cs (added)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Manipulators/BitflipManipulator.cs (added)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Manipulators/MultiBitflipManipulator.cs (added)
• HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Manipulators/SingleBitflipManipulator.cs (added)
• HeuristicLab.Optimization/3.3/Algorithms/AlgorithmContext.cs (added)
• HeuristicLab.Optimization/3.3/Algorithms/SingleObjective (added)
• HeuristicLab.Optimization/3.3/Algorithms/SingleObjective/HeuristicAlgorithm.cs (added)
• HeuristicLab.Optimization/3.3/Algorithms/SingleObjective/HeuristicAlgorithmContext.cs (added)
• HeuristicLab.Optimization/3.3/Algorithms/SingleObjective/SingleObjectiveSolutionScope.cs (added)
• HeuristicLab.Optimization/3.3/BasicProblems/Problem.cs (modified) (1 diff)
• HeuristicLab.Optimization/3.3/HeuristicLab.Optimization-3.3.csproj (modified) (3 diffs)
• HeuristicLab.Optimization/3.3/NewInfrastructure (added)
• HeuristicLab.Optimization/3.3/NewInfrastructure/Interfaces.cs (added)
• HeuristicLab.Problems.Knapsack/3.3/Analyzers/BestKnapsackSolutionAnalyzer.cs (modified) (2 diffs)
• HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs (modified) (5 diffs)
• HeuristicLab.Selection/3.3/TournamentSelector.cs (modified) (2 diffs)

branches/ScopedAlgorithms/HeuristicLab 3.3.sln

@@ -1 +1 @@
 
 Microsoft Visual Studio Solution File, Format Version 12.00
-# Visual Studio 2013
-VisualStudioVersion = 12.0.31101.0
+# Visual Studio 14
+VisualStudioVersion = 14.0.25420.1
 MinimumVisualStudioVersion = 10.0.40219.1
 Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "Solution Items", "Solution Items", "{96396439-A764-4022-A8D2-BE021449B8D1}"
@@ -451 +451 @@
 EndProject
 Global
+  GlobalSection(Performance) = preSolution
+    HasPerformanceSessions = true
+  EndGlobalSection
   GlobalSection(SolutionConfigurationPlatforms) = preSolution
     Debug|Any CPU = Debug|Any CPU

branches/ScopedAlgorithms/HeuristicLab.Algorithms.GeneticAlgorithm/3.3/HeuristicLab.Algorithms.GeneticAlgorithm-3.3.csproj

@@ -115 +115 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="BinaryCanonicalGeneticAlgorithm.cs" />
+    <Compile Include="CanonicalGeneticAlgorithm.cs" />
+    <Compile Include="EvolutionaryAlgorithmContext.cs" />
     <Compile Include="GeneticAlgorithm.cs" />
     <Compile Include="GeneticAlgorithmMainLoop.cs" />
@@ -147 +150 @@
       <Name>HeuristicLab.Data-3.3</Name>
       <Private>False</Private>
+    </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Encodings.BinaryVectorEncoding\3.3\HeuristicLab.Encodings.BinaryVectorEncoding-3.3.csproj">
+      <Project>{66D249C3-A01D-42A8-82A2-919BC8EC3D83}</Project>
+      <Name>HeuristicLab.Encodings.BinaryVectorEncoding-3.3</Name>
     </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj">

branches/ScopedAlgorithms/HeuristicLab.Algorithms.LocalSearch/3.3/HeuristicLab.Algorithms.LocalSearch-3.3.csproj

@@ -114 +114 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="BinaryIteratedLocalSearch.cs" />
+    <Compile Include="IteratedLocalSearch.cs" />
+    <Compile Include="LocalSearchContext.cs" />
     <Compile Include="LocalSearchImprovementOperator.cs" />
     <Compile Include="LocalSearchMainLoop.cs" />
@@ -150 +153 @@
       <Name>HeuristicLab.Data-3.3</Name>
       <Private>False</Private>
+    </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Encodings.BinaryVectorEncoding\3.3\HeuristicLab.Encodings.BinaryVectorEncoding-3.3.csproj">
+      <Project>{66D249C3-A01D-42A8-82A2-919BC8EC3D83}</Project>
+      <Name>HeuristicLab.Encodings.BinaryVectorEncoding-3.3</Name>
     </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj">

branches/ScopedAlgorithms/HeuristicLab.Core/3.3/Attributes/ItemAttribute.cs

@@ -39 +39 @@
       set { description = value == null ? string.Empty : value; }
     }
+    public bool ExcludeGenericTypeInfo { get; set; }
 
-    public ItemAttribute() {
-      Name = string.Empty;
-      Description = string.Empty;
-    }
-    public ItemAttribute(string name, string description) {
+    public ItemAttribute() : this(string.Empty, string.Empty, false) { }
+    public ItemAttribute(string name, string description) : this(name, description, false) { }
+    public ItemAttribute(string name, string description, bool excludeGenericTypeInfo) {
       Name = name;
       Description = description;
+      ExcludeGenericTypeInfo = excludeGenericTypeInfo;
     }
 
@@ -52 +52 @@
       object[] attribs = type.GetCustomAttributes(typeof(ItemAttribute), false);
       if (attribs.Length > 0) {
-        string name = ((ItemAttribute)attribs[0]).Name;
-        if (type.IsGenericType) {
+        var attribute = (ItemAttribute)attribs[0];
+        string name = attribute.Name;
+        if (!attribute.ExcludeGenericTypeInfo && type.IsGenericType) {
           name += "<";
           Type[] typeParams = type.GetGenericArguments();

branches/ScopedAlgorithms/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Crossovers/NPointCrossover.cs

@@ -25 +25 @@
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -70 +71 @@
     /// <param name="n">Number of crossover points.</param>
     /// <returns>The newly created binary vector, resulting from the N point crossover.</returns>
-    public static BinaryVector Apply(IRandom random, BinaryVector parent1, BinaryVector parent2, IntValue n) {
+    public static BinaryVector Apply(IRandom random, BinaryVector parent1, BinaryVector parent2, int n) {
       if (parent1.Length != parent2.Length)
         throw new ArgumentException("NPointCrossover: The parents are of different length.");
 
-      if (n.Value > parent1.Length)
+      if (n > parent1.Length)
         throw new ArgumentException("NPointCrossover: There cannot be more breakpoints than the size of the parents.");
 
-      if (n.Value < 1)
+      if (n < 1)
         throw new ArgumentException("NPointCrossover: N cannot be < 1.");
 
       int length = parent1.Length;
       bool[] result = new bool[length];
-      int[] breakpoints = new int[n.Value];
+      int[] breakpoints = new int[n];
 
       //choose break points
@@ -90 +91 @@
         breakpointPool.Add(i);
 
-      for (int i = 0; i < n.Value; i++) {
+      for (int i = 0; i < n; i++) {
         int index = random.Next(breakpointPool.Count);
         breakpoints[i] = breakpointPool[index];
@@ -137 +138 @@
       if (NParameter.ActualValue == null) throw new InvalidOperationException("NPointCrossover: Parameter " + NParameter.ActualName + " could not be found.");
 
-      return Apply(random, parents[0], parents[1], NParameter.ActualValue);
+      return Apply(random, parents[0], parents[1], NParameter.ActualValue.Value);
+    }
+  }
+
+  [Item("N-point Crossover", "", ExcludeGenericTypeInfo = true)]
+  [StorableClass]
+  public sealed class NPointCrossover<TContext> : ParameterizedNamedItem, IBinaryCrossover<TContext>
+    where TContext : IMatingContext<BinaryVector>, IStochasticContext {
+
+    [Storable]
+    private IValueParameter<IntValue> nparameter;
+    public int N {
+      get { return nparameter.Value.Value; }
+      set {
+        if (value < 1) throw new ArgumentException("Cannot set N to less than 1.");
+        nparameter.Value.Value = value;
+      }
+    }
+
+    [StorableConstructor]
+    private NPointCrossover(bool deserializing) : base(deserializing) { }
+    private NPointCrossover(NPointCrossover<TContext> original, Cloner cloner)
+      : base(original, cloner) {
+      nparameter = cloner.Clone(original.nparameter);
+    }
+    public NPointCrossover() {
+      Parameters.Add(nparameter = new ValueParameter<IntValue>("N", "The number of crossover points.", new IntValue(1)));
+    }
+
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new NPointCrossover<TContext>(this, cloner);
+    }
+
+    public void Cross(TContext context) {
+      context.Child.Solution = NPointCrossover.Apply(context.Random, context.Parents.Item1.Solution, context.Parents.Item2.Solution, N);
     }
   }

branches/ScopedAlgorithms/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Crossovers/SinglePointCrossover.cs

@@ -57 +57 @@
       if (parents.Length != 2) throw new ArgumentException("ERROR in SinglePointCrossover: The number of parents is not equal to 2");
 
-      return NPointCrossover.Apply(random, parents[0], parents[1], new IntValue(1));
+      return NPointCrossover.Apply(random, parents[0], parents[1], 1);
     }
   }

branches/ScopedAlgorithms/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/HeuristicLab.Encodings.BinaryVectorEncoding-3.3.csproj

@@ -126 +126 @@
     <Compile Include="Crossovers\NPointCrossover.cs" />
     <Compile Include="BinaryVector.cs" />
+    <Compile Include="Interfaces\IBinaryLocalSearch.cs" />
     <Compile Include="Interfaces\IBinaryVectorMultiNeighborhoodShakingOperator.cs" />
     <Compile Include="Interfaces\IBinaryVectorSolutionsOperator.cs" />
@@ -139 +140 @@
     <Compile Include="BinaryVectorManipulator.cs" />
     <Compile Include="Interfaces\IBinaryVectorMoveOperator.cs" />
+    <Compile Include="LocalSearch\ExhaustiveBitflip.cs" />
+    <Compile Include="Manipulators\MultiBitflipManipulator.cs" />
+    <Compile Include="Manipulators\SingleBitflipManipulator.cs" />
+    <Compile Include="Manipulators\BitflipManipulator.cs" />
     <Compile Include="Manipulators\SomePositionsBitflipManipulator.cs" />
     <Compile Include="Manipulators\SinglePositionBitflipManipulator.cs" />
@@ -205 +210 @@
       <Name>HeuristicLab.PluginInfrastructure-3.3</Name>
       <Private>False</Private>
+    </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Random\3.3\HeuristicLab.Random-3.3.csproj">
+      <Project>{F4539FB6-4708-40C9-BE64-0A1390AEA197}</Project>
+      <Name>HeuristicLab.Random-3.3</Name>
     </ProjectReference>
   </ItemGroup>

branches/ScopedAlgorithms/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Interfaces/IBinaryVectorCrossover.cs

@@ -22 +22 @@
 using HeuristicLab.Core;
 using HeuristicLab.Optimization;
+using HeuristicLab.Optimization.Crossover;
 
 namespace HeuristicLab.Encodings.BinaryVectorEncoding {
@@ -31 +32 @@
     ILookupParameter<BinaryVector> ChildParameter { get; }
   }
+
+  // TODO: probably unecessary
+  public interface IBinaryCrossover<TContext> : ICrossover<TContext> { }
 }

branches/ScopedAlgorithms/HeuristicLab.Optimization/3.3/BasicProblems/Problem.cs

@@ -81 +81 @@
     }
 
-
+    // TODO: There is no way to access the Operators collection other than through OperatorParameter.Value
     protected override IEnumerable<IItem> GetOperators() {
       if (Encoding == null) return base.GetOperators();

branches/ScopedAlgorithms/HeuristicLab.Optimization/3.3/HeuristicLab.Optimization-3.3.csproj

@@ -120 +120 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="Algorithms\SingleObjective\HeuristicAlgorithmContext.cs" />
     <Compile Include="Algorithms\BasicAlgorithm.cs" />
+    <Compile Include="Algorithms\SingleObjective\HeuristicAlgorithm.cs" />
+    <Compile Include="Algorithms\AlgorithmContext.cs" />
+    <Compile Include="Algorithms\SingleObjective\SingleObjectiveSolutionScope.cs" />
     <Compile Include="BasicProblems\CombinedSolution.cs" />
     <Compile Include="BasicProblems\Interfaces\IMultiEncodingOperator.cs" />
@@ -170 +174 @@
     <Compile Include="MetaOptimizers\Experiment.cs" />
     <Compile Include="MetaOptimizers\TimeLimitRun.cs" />
+    <Compile Include="NewInfrastructure\Interfaces.cs" />
     <Compile Include="RunCollectionModification\RunCollectionRunRemover.cs" />
     <Compile Include="Plugin.cs" />
@@ -312 +317 @@
       <Private>False</Private>
     </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Random\3.3\HeuristicLab.Random-3.3.csproj">
+      <Project>{F4539FB6-4708-40C9-BE64-0A1390AEA197}</Project>
+      <Name>HeuristicLab.Random-3.3</Name>
+    </ProjectReference>
   </ItemGroup>
   <ItemGroup>

branches/ScopedAlgorithms/HeuristicLab.Problems.Knapsack/3.3/Analyzers/BestKnapsackSolutionAnalyzer.cs

@@ -60 +60 @@
     }
     public ILookupParameter<KnapsackSolution> BestSolutionParameter {
-      get { return (ILookupParameter<KnapsackSolution>)Parameters["BestSolution"]; }
+      get { return (ILookupParameter<KnapsackSolution>)Parameters["BestKnapsackSolution"]; }
     }
     public IValueLookupParameter<ResultCollection> ResultsParameter {
@@ -84 +84 @@
 
       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the Knapsack solutions which should be visualized."));
-      Parameters.Add(new LookupParameter<KnapsackSolution>("BestSolution", "The best Knapsack solution."));
+      Parameters.Add(new LookupParameter<KnapsackSolution>("BestKnapsackSolution", "The best Knapsack solution."));
       Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the knapsack solution should be stored."));
       Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution."));

branches/ScopedAlgorithms/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs

@@ -91 +91 @@
 
       InitializeRandomKnapsackInstance();
+      Encoding.Length = Weights.Length;
 
       InitializeOperators();
@@ -97 +98 @@
 
     public override double Evaluate(BinaryVector solution, IRandom random) {
+      var weights = Weights;
+      var values = Values;
       var totalWeight = 0.0;
       var totalValue = 0.0;
       for (var i = 0; i < solution.Length; i++) {
         if (!solution[i]) continue;
-        totalWeight += Weights[i];
-        totalValue += Values[i];
+        totalWeight += weights[i];
+        totalValue += values[i];
       }
       return totalWeight > KnapsackCapacity ? KnapsackCapacity - totalWeight : totalValue;
@@ -253 +256 @@
       var sysrand = new System.Random();
 
-      var itemCount = sysrand.Next(10, 100);
+      var power = sysrand.Next(5, 11);
+      var itemCount = (int)Math.Pow(2, power);
       Weights = new IntArray(itemCount);
       Values = new IntArray(itemCount);
@@ -260 +264 @@
 
       for (int i = 0; i < itemCount; i++) {
-        var value = sysrand.Next(1, 10);
-        var weight = sysrand.Next(1, 10);
+        var value = sysrand.Next(1, 30);
+        var weight = sysrand.Next(1, 30);
 
         Values[i] = value;
@@ -268 +272 @@
       }
 
-      KnapsackCapacity = (int)Math.Round(0.7 * totalWeight);
+      KnapsackCapacity = (int)Math.Round(0.5 * totalWeight);
     }
   }

branches/ScopedAlgorithms/HeuristicLab.Selection/3.3/TournamentSelector.cs

@@ -27 +27 @@
 using HeuristicLab.Data;
 using HeuristicLab.Optimization;
+using HeuristicLab.Optimization.Selection;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -90 +91 @@
     }
   }
+
+  [Item("Tournament Selector", "", ExcludeGenericTypeInfo = true)]
+  [StorableClass]
+  public sealed class TournamentSelector<TContext, TProblem, TEncoding, TSolution> : ParameterizedNamedItem, ISelector<TContext>
+      where TContext : ISingleObjectivePopulationContext<TSolution>, IMatingpoolContext<TSolution>, IStochasticContext,
+                       IProblemContext<TProblem, TEncoding, TSolution>
+      where TProblem : class, ISingleObjectiveProblem<TEncoding, TSolution>, ISingleObjectiveProblemDefinition<TEncoding, TSolution>
+      where TEncoding : class, IEncoding<TSolution>
+      where TSolution : class, ISolution {
+
+    [Storable]
+    private IValueParameter<IntValue> groupSizeParameter;
+    public int GroupSize {
+      get { return groupSizeParameter.Value.Value; }
+      set {
+        if (value < 1) throw new ArgumentException("Cannot use a group size less than 1 in tournament selection.");
+        groupSizeParameter.Value.Value = value;
+      }
+    }
+    
+    [StorableConstructor]
+    private TournamentSelector(bool deserializing) : base(deserializing) { }
+    private TournamentSelector(TournamentSelector<TContext, TProblem, TEncoding, TSolution> original, Cloner cloner)
+      : base(original, cloner) {
+      groupSizeParameter = cloner.Clone(groupSizeParameter);
+    }
+    public TournamentSelector() {
+      Parameters.Add(groupSizeParameter = new ValueParameter<IntValue>("GroupSize", "The group size that competes in the tournament.", new IntValue(2)));
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new TournamentSelector<TContext, TProblem, TEncoding, TSolution>(this, cloner);
+    }
+
+    public void Select(TContext context, int n, bool withRepetition) {
+      context.MatingPool = Select(context.Random, context.Problem.IsBetter, context.Population, GroupSize, n, withRepetition);
+    }
+
+    public static IEnumerable<ISingleObjectiveSolutionScope<TSolution>> Select(IRandom random, Func<double, double, bool> isBetterFunc, IEnumerable<ISingleObjectiveSolutionScope<TSolution>> population, int groupSize, int n, bool withRepetition) {
+      var pop = population.Where(x => !double.IsNaN(x.Fitness)).ToList();
+
+      var i = n;
+      while (i > 0 && pop.Count > 0) {
+        var best = random.Next(pop.Count);
+        for (var j = 1; j < groupSize; j++) {
+          var index = random.Next(pop.Count);
+          if (isBetterFunc(pop[index].Fitness, pop[best].Fitness)) {
+            best = index;
+          }
+        }
+
+        yield return pop[best];
+        i--;
+        if (!withRepetition) {
+          pop.RemoveAt(i);
+        }
+      }
+    }
+  }
 }