Changeset 11666
- Timestamp:
- 12/05/14 18:25:03 (10 years ago)
- Location:
- branches/Parameter-less Population Pyramid
- Files:
-
- 4 added
- 1 deleted
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/HeuristicLab.Algorithms.ParameterlessPopulationPyramid-3.3.csproj
r11664 r11666 37 37 </PropertyGroup> 38 38 <ItemGroup> 39 <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL"> 40 <SpecificVersion>False</SpecificVersion> 41 <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Analysis-3.3.dll</HintPath> 42 </Reference> 39 43 <Reference Include="HeuristicLab.Collections-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL"> 40 44 <SpecificVersion>False</SpecificVersion> … … 101 105 <Compile Include="AlgorithmBase.cs" /> 102 106 <Compile Include="LinkageCrossover.cs" /> 103 <Compile Include=" DeceptiveTrapProblem.cs" />107 <Compile Include="Problems\DeceptiveTrapProblem.cs" /> 104 108 <Compile Include="HillClimber.cs" /> 105 109 <Compile Include="LinkageTree.cs" /> … … 108 112 <Compile Include="Problems\BinaryVectorProblem.cs" /> 109 113 <Compile Include="Plugin.cs" /> 114 <Compile Include="Problems\EvaluationTracker.cs" /> 115 <Compile Include="Problems\HIFFProblem.cs" /> 116 <Compile Include="Problems\IBinaryVectorProblem.cs" /> 110 117 <Compile Include="Problems\OneMaxProblem.cs" /> 111 118 <Compile Include="Properties\AssemblyInfo.cs" /> -
branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/HillClimber.cs
r11664 r11666 82 82 } 83 83 } 84 public static double ImproveToLocalOptimum( BinaryVectorProblem problem, bool[] solution, double fitness, IRandom rand) {84 public static double ImproveToLocalOptimum(IBinaryVectorProblem problem, bool[] solution, double fitness, IRandom rand) { 85 85 var tried = new HashSet<int>(); 86 86 do { -
branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageCrossover.cs
r11663 r11666 30 30 public static class LinkageCrossover { 31 31 32 public static double ImproveUsingTree(LinkageTree tree, IList<bool[]> donors, bool[] solution, double fitness, BinaryVectorProblem problem, IRandom rand) {32 public static double ImproveUsingTree(LinkageTree tree, IList<bool[]> donors, bool[] solution, double fitness, IBinaryVectorProblem problem, IRandom rand) { 33 33 var options = Enumerable.Range(0, donors.Count).ToArray(); 34 34 foreach (var cluster in tree.Clusters) { … … 36 36 // from the current solution for this cluster of genes 37 37 bool donorFound = false; 38 foreach (var donorIndex in options.Shuffle (rand)) {38 foreach (var donorIndex in options.ShuffleList(rand)) { 39 39 // Attempt the donation 40 40 fitness = Donate(solution, fitness, donors[donorIndex], cluster, problem, out donorFound); … … 45 45 } 46 46 47 private static double Donate(bool[] solution, double fitness, bool[] source, IEnumerable<int> cluster, BinaryVectorProblem problem, out bool changed) {47 private static double Donate(bool[] solution, double fitness, bool[] source, IEnumerable<int> cluster, IBinaryVectorProblem problem, out bool changed) { 48 48 // keep track of which bits flipped to make the donation 49 49 List<int> flipped = new List<int>(); -
branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageTree.cs
r11663 r11666 35 35 } 36 36 public static IList<T> ShuffleInPlace<T>(this IList<T> list, IRandom random) { 37 return list.ShuffleInPlace(random, 0, list.Count );37 return list.ShuffleInPlace(random, 0, list.Count - 1); 38 38 } 39 39 public static IList<T> ShuffleInPlace<T>(this IList<T> list, IRandom random, int maxIndex) { … … 41 41 } 42 42 public static IList<T> ShuffleInPlace<T>(this IList<T> list, IRandom random, int minIndex, int maxIndex) { 43 for (int i = list.Count - 1; i > 0; i--) {44 int swapIndex = random.Next( i + 1);43 for (int i = maxIndex; i > minIndex; i--) { 44 int swapIndex = random.Next(minIndex, i + 1); 45 45 list.Swap(i, swapIndex); 46 46 } … … 48 48 } 49 49 50 public static IEnumerable<T> Shuffle <T>(this IList<T> source, IRandom random) {50 public static IEnumerable<T> ShuffleList<T>(this IList<T> source, IRandom random) { 51 51 for (int i = source.Count - 1; i > 0; i--) { 52 52 // Swap element "i" with a random earlier element (including itself) … … 166 166 for (int index = length; index < clusters.Length; index++) { 167 167 // Shuffle everything not yet in the path 168 topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count );168 topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count-1); 169 169 170 170 // if nothing in the path, just add a random usable node -
branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/ParameterlessPopulationPyramid.cs
r11664 r11666 25 25 using System.Text; 26 26 using System.Threading.Tasks; 27 using HeuristicLab.Analysis; 27 28 using HeuristicLab.Common; 28 29 using HeuristicLab.Core; 29 30 using HeuristicLab.Data; 31 using HeuristicLab.Encodings.BinaryVectorEncoding; 30 32 using HeuristicLab.Optimization; 31 33 using HeuristicLab.Parameters; … … 39 41 40 42 public class ParameterlessPopulationPyramid : AlgorithmBase { 41 [Storable] 42 private IRandom random; 43 44 [Storable] 43 private readonly IRandom random = new MersenneTwister(); 45 44 private List<Population> pyramid; 45 private EvaluationTracker tracker; 46 46 47 47 // Tracks all solutions in Pyramid for quick membership checks 48 48 private readonly HashSet<bool[]> seen = new HashSet<bool[]>(); 49 49 50 private const string IterationsParameterName = "Iterations";51 52 public IFixedValueParameter<IntValue> IterationsParameter {53 get { return (IFixedValueParameter<IntValue>)Parameters[ IterationsParameterName]; }50 private const string MaximumIterationsParameterName = "Maximum Iterations"; 51 52 public IFixedValueParameter<IntValue> MaximumIterationsParameter { 53 get { return (IFixedValueParameter<IntValue>)Parameters[MaximumIterationsParameterName]; } 54 54 } 55 55 56 public int Iterations { 57 get { return IterationsParameter.Value.Value; } 58 set { IterationsParameter.Value.Value = value; } 59 } 56 public int MaximumIterations { 57 get { return MaximumIterationsParameter.Value.Value; } 58 set { MaximumIterationsParameter.Value.Value = value; } 59 } 60 61 private const string MaximumEvaluationsParameterName = "Maximum Evaluations"; 62 63 public IFixedValueParameter<IntValue> MaximumEvaluationsParameter { 64 get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; } 65 } 66 67 public int MaximumEvaluations { 68 get { return MaximumEvaluationsParameter.Value.Value; } 69 set { MaximumEvaluationsParameter.Value.Value = value; } 70 } 71 72 73 private const string SeedParameterName = "Seed"; 74 75 public IFixedValueParameter<IntValue> SeedParameter { 76 get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; } 77 } 78 79 public int Seed { 80 get { return SeedParameter.Value.Value; } 81 set { SeedParameter.Value.Value = value; } 82 } 83 84 private const string SetSeedRandomlyParameterName = "SetSeedRandomly"; 85 86 public FixedValueParameter<BoolValue> SetSeedRandomlyParameter { 87 get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; } 88 } 89 90 public bool SetSeedRandomly { 91 get { return SetSeedRandomlyParameter.Value.Value; } 92 set { SetSeedRandomlyParameter.Value.Value = value; } 93 } 94 95 #region ResultsProperties 96 private double ResultsBestQuality { 97 get { return ((DoubleValue)Results["Best Quality"].Value).Value; } 98 set { ((DoubleValue)Results["Best Quality"].Value).Value = value; } 99 } 100 101 private BinaryVector ResultsBestSolution { 102 get { return (BinaryVector)Results["Best Solution"].Value; } 103 set { Results["Best Solution"].Value = value; } 104 } 105 106 private int ResultsBestFoundOnEvaluation { 107 get { return ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value; } 108 set { ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value = value; } 109 } 110 111 private int ResultsEvaluations { 112 get { return ((IntValue)Results["Evaluations"].Value).Value; } 113 set { ((IntValue)Results["Evaluations"].Value).Value = value; } 114 } 115 private int ResultsIterations { 116 get { return ((IntValue)Results["Iterations"].Value).Value; } 117 set { ((IntValue)Results["Iterations"].Value).Value = value; } 118 } 119 120 private DataTable ResultsQualities { 121 get { return ((DataTable)Results["Qualities"].Value); } 122 } 123 private DataRow ResultsQualitiesBest { 124 get { return ResultsQualities.Rows["Best Quality"]; } 125 } 126 127 private DataRow ResultsQualitiesIteration { 128 get { return ResultsQualities.Rows["Iteration Quality"]; } 129 } 130 131 #endregion 132 60 133 [StorableConstructor] 61 134 protected ParameterlessPopulationPyramid(bool deserializing) : base(deserializing) { } … … 70 143 71 144 public ParameterlessPopulationPyramid() { 72 Parameters.Add(new FixedValueParameter<IntValue>(IterationsParameterName, "", new IntValue(100))); 145 Parameters.Add(new FixedValueParameter<IntValue>(MaximumIterationsParameterName, "", new IntValue(100))); 146 Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(1000))); 147 Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0))); 148 Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true))); 73 149 } 74 150 … … 78 154 if (seen.Contains(solution)) return; 79 155 if (level == pyramid.Count) { 80 pyramid.Add(new Population( Problem.Length, random));156 pyramid.Add(new Population(tracker.Length, random)); 81 157 } 82 158 pyramid[level].Add(solution); … … 86 162 private double iterate() { 87 163 // Create a random solution 88 bool[] solution = new bool[ Problem.Length];164 bool[] solution = new bool[tracker.Length]; 89 165 for (int i = 0; i < solution.Length; i++) { 90 166 solution[i] = random.Next(2) == 1; 91 167 } 92 double fitness = Problem.Evaluate(solution);93 fitness = HillClimber.ImproveToLocalOptimum( Problem, solution, fitness, random);168 double fitness = tracker.Evaluate(solution); 169 fitness = HillClimber.ImproveToLocalOptimum(tracker, solution, fitness, random); 94 170 AddIfUnique(solution, 0); 95 171 for (int level = 0; level < pyramid.Count; level++) { 96 172 var current = pyramid[level]; 97 double newFitness = LinkageCrossover.ImproveUsingTree(current.Tree, current.Solutions, solution, fitness, Problem, random);173 double newFitness = LinkageCrossover.ImproveUsingTree(current.Tree, current.Solutions, solution, fitness, tracker, random); 98 174 // add it to the next level if its a strict fitness improvement 99 if ( Problem.IsBetter(newFitness, fitness)) {175 if (tracker.IsBetter(newFitness, fitness)) { 100 176 fitness = newFitness; 101 177 AddIfUnique(solution, level + 1); … … 106 182 107 183 protected override void Run() { 184 if (SetSeedRandomly) Seed = new System.Random().Next(); 108 185 pyramid = new List<Population>(); 109 random = new MersenneTwister(); 110 var BestQuality = new DoubleValue(double.NaN); 111 Results.Add(new Result("Best quality", BestQuality)); 112 for (int iteration = 0; iteration < Iterations; iteration++) { 113 var fitness = iterate(); 114 if (double.IsNaN(BestQuality.Value) || Problem.IsBetter(fitness, BestQuality.Value)) { 115 BestQuality.Value = fitness; 186 random.Reset(Seed); 187 tracker = new EvaluationTracker(Problem, MaximumEvaluations); 188 Results.Add(new Result("Iterations", new IntValue(0))); 189 Results.Add(new Result("Evaluations", new IntValue(0))); 190 Results.Add(new Result("Best Solution", new BinaryVector(tracker.BestSolution))); 191 Results.Add(new Result("Best Quality", new DoubleValue(tracker.BestQuality))); 192 Results.Add(new Result("Evaluation Best Solution Was Found", new IntValue(tracker.BestFoundOnEvaluation))); 193 var table = new DataTable("Qualities"); 194 table.Rows.Add(new DataRow("Best Quality")); 195 var iterationRows = new DataRow("Iteration Quality"); 196 iterationRows.VisualProperties.LineStyle = DataRowVisualProperties.DataRowLineStyle.Dot; 197 table.Rows.Add(iterationRows); 198 Results.Add(new Result("Qualities", table)); 199 for (ResultsIterations = 0; ResultsIterations < MaximumIterations; ResultsIterations++) { 200 double fitness = double.NaN; 201 202 try { 203 fitness = iterate(); 116 204 } 205 catch (OperationCanceledException) { 206 throw; 207 } 208 finally { 209 ResultsEvaluations = tracker.Evaluations; 210 ResultsBestSolution = new BinaryVector(tracker.BestSolution); 211 ResultsBestQuality = tracker.BestQuality; 212 ResultsBestFoundOnEvaluation = tracker.BestFoundOnEvaluation; 213 ResultsQualitiesBest.Values.Add(tracker.BestQuality); 214 ResultsQualitiesIteration.Values.Add(fitness); 215 } 117 216 } 118 217 } -
branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/Problems/BinaryVectorProblem.cs
r11640 r11666 29 29 namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid { 30 30 [StorableClass] 31 public abstract class BinaryVectorProblem : Problem {31 public abstract class BinaryVectorProblem : Problem, IBinaryVectorProblem { 32 32 private const string LengthParameterName = "Length"; 33 33 -
branches/Parameter-less Population Pyramid/ParameterlessPopulationPyramid.Test/LinkageTreeTest.cs
r11663 r11666 21 21 // These are the clusters that should be built using "solutions" and the seed 123 22 22 private static int[][] correctClusters = new int[][] { 23 new int[] { 4, 5 }, 23 24 new int[] { 2, 3 }, 24 new int[] { 4, 5 },25 25 new int[] { 0, 1 }, 26 26 new int[] { 6, 7, 8 },
Note: See TracChangeset
for help on using the changeset viewer.