Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.MetaOptimization/HeuristicLab.MetaOptimization.Test/Program.cs @ 5111

Last change on this file since 5111 was 5111, checked in by cneumuel, 13 years ago

#1215

  • improved exchangeability of crossover and mutation operators for parameter values
File size: 20.7 KB
Line 
1using System.Collections.Generic;
2using System.Diagnostics;
3using System.Linq;
4using HeuristicLab.Algorithms.GeneticAlgorithm;
5using HeuristicLab.Core;
6using HeuristicLab.PluginInfrastructure;
7using HeuristicLab.Parameters;
8using HeuristicLab.Problems.MetaOptimization;
9using HeuristicLab.Data;
10using System;
11using System.Threading;
12using HeuristicLab.Random;
13using HeuristicLab.Optimization;
14using HeuristicLab.Common;
15using System.IO;
16using HeuristicLab.Problems.TestFunctions;
17using System.Text;
18using HeuristicLab.Selection;
19using HeuristicLab.Algorithms.EvolutionStrategy;
20using HeuristicLab.PluginInfrastructure.Manager;
21
22namespace HeuristicLab.MetaOptimization.Test {
23  class Program {
24    private static int metaAlgorithmPopulationSize = 50;
25    private static int metaAlgorithmMaxGenerations = 30;
26    private static int metaProblemRepetitions = 6;
27
28    private static int baseAlgorithmMaxGenerations = 250;
29
30    static void Main(string[] args) {
31      //TestShorten();
32
33      //TestIntSampling();
34      //TestDoubleSampling();
35      //TestTypeDiscovery();
36      //TestOperators();
37     
38      GeneticAlgorithm baseLevelAlgorithm = new GeneticAlgorithm();
39
40      MetaOptimizationProblem metaOptimizationProblem = new MetaOptimizationProblem();
41      metaOptimizationProblem.Repetitions = new IntValue(metaProblemRepetitions);
42      GeneticAlgorithm metaLevelAlgorithm = GetMetaGA(metaOptimizationProblem);
43      //EvolutionStrategy metaLevelAlgorithm = GetMetaES(metaOptimizationProblem);
44
45      IValueConfiguration algorithmVc = SetupGAAlgorithm(baseLevelAlgorithm, metaOptimizationProblem);
46
47      //Console.WriteLine("Press enter to start");
48      //Console.ReadLine();
49      //TestConfiguration(algorithmVc, baseLevelAlgorithm);
50     
51      //Console.WriteLine("Press enter to start");
52      //Console.ReadLine();
53      TestOptimization(metaLevelAlgorithm);
54
55      //TestMemoryLeak(metaLevelAlgorithm);
56
57      Console.ReadLine();
58    }
59
60    private static void TestOperators() {
61      IRandom random = new MersenneTwister();
62      ParameterConfigurationManipulator manip = new ParameterConfigurationManipulator();
63
64      manip.IntValueManipulatorParameter.ActualValue = new UniformIntValueManipulator();
65      manip.DoubleValueManipulatorParameter.ActualValue = new NormalDoubleValueManipulator();
66     
67      var doubleRange = new DoubleValueRange(new DoubleValue(0), new DoubleValue(100), new DoubleValue(0.1));
68      using (var sw = new StreamWriter("out-DoubleValue.txt")) {
69        for (int i = 0; i < 10000; i++) {
70          var val = new DoubleValue(50);
71          NormalDoubleValueManipulator.ApplyStatic(random, val, doubleRange);
72         
73          sw.WriteLine(val);
74        }
75      }
76
77      var percentRange = new PercentValueRange(new PercentValue(0), new PercentValue(1), new PercentValue(0.001));
78      using (var sw = new StreamWriter("out-PercentValue.txt")) {
79        for (int i = 0; i < 10000; i++) {
80          var val = new PercentValue(0.5);
81          NormalDoubleValueManipulator.ApplyStatic(random, val, percentRange.AsDoubleValueRange());
82          sw.WriteLine(val);
83        }
84      }
85
86      var intRange = new IntValueRange(new IntValue(0), new IntValue(100), new IntValue(1));
87      using (var sw = new StreamWriter("out-IntValue.txt")) {
88        for (int i = 0; i < 10000; i++) {
89          var val = new IntValue(50);
90          UniformIntValueManipulator.ApplyStatic(random, val, intRange);
91          sw.WriteLine(val);
92        }
93      }
94
95      Console.ReadLine();
96    }
97
98    private static void TestTypeDiscovery() {
99      PluginLoader.pluginAssemblies.Any();
100     
101      var items = ApplicationManager.Manager.GetInstances(typeof(DoubleArray)).ToArray();
102
103      foreach (var item in items) {
104        Console.WriteLine(item.ToString());
105      }
106    }
107
108    private static void TestMemoryLeak(GeneticAlgorithm metaLevelAlgorithm) {
109      IValueConfiguration algorithmVc = ((MetaOptimizationProblem)metaLevelAlgorithm.Problem).AlgorithmParameterConfiguration;
110
111      Console.WriteLine("Starting Memory Test...");
112      Console.ReadLine();
113
114      var clones = new List<object>();
115      for (int i = 0; i < 1000; i++) {
116        var clone = algorithmVc.Clone();
117        clones.Add(clone);
118      }
119
120      Console.WriteLine("Finished. Now GC...");
121      Console.ReadLine();
122
123      GC.Collect();
124
125      Console.WriteLine("Finished!");
126      Console.ReadLine();
127    }
128
129    private static GeneticAlgorithm GetMetaGA(MetaOptimizationProblem metaOptimizationProblem) {
130      GeneticAlgorithm metaLevelAlgorithm = new GeneticAlgorithm();
131      metaLevelAlgorithm.PopulationSize.Value = metaAlgorithmPopulationSize;
132      metaLevelAlgorithm.MaximumGenerations.Value = metaAlgorithmMaxGenerations;
133
134      metaLevelAlgorithm.Problem = metaOptimizationProblem;
135      metaLevelAlgorithm.Engine = new SequentialEngine.SequentialEngine();
136
137      metaLevelAlgorithm.Mutator = new ParameterConfigurationManipulator();
138      metaLevelAlgorithm.MutationProbability.Value = 0.15;
139
140      return metaLevelAlgorithm;
141    }
142
143    private static EvolutionStrategy GetMetaES(MetaOptimizationProblem metaOptimizationProblem) {
144      EvolutionStrategy metaLevelAlgorithm = new EvolutionStrategy();
145      metaLevelAlgorithm.PopulationSize.Value = metaAlgorithmPopulationSize;
146      metaLevelAlgorithm.MaximumGenerations.Value = metaAlgorithmMaxGenerations;
147
148      metaLevelAlgorithm.Problem = metaOptimizationProblem;
149      metaLevelAlgorithm.Engine = new SequentialEngine.SequentialEngine();
150
151      metaLevelAlgorithm.Mutator = new ParameterConfigurationManipulator();
152      //metaLevelAlgorithm.MutationProbability.Value = 0.15;
153
154      return metaLevelAlgorithm;
155    }
156
157    private static IValueConfiguration SetupGAAlgorithm(GeneticAlgorithm baseLevelAlgorithm, MetaOptimizationProblem metaOptimizationProblem) {
158      baseLevelAlgorithm.Problem = new HeuristicLab.Problems.TestFunctions.SingleObjectiveTestFunctionProblem();
159      baseLevelAlgorithm.MaximumGenerations.Value = baseAlgorithmMaxGenerations;
160
161      metaOptimizationProblem.Algorithm = baseLevelAlgorithm;
162      IValueConfiguration algorithmVc = metaOptimizationProblem.AlgorithmParameterConfiguration;
163
164      metaOptimizationProblem.Problems.Add(new HeuristicLab.Problems.TestFunctions.SingleObjectiveTestFunctionProblem() {
165        Evaluator = new GriewankEvaluator(),
166        ProblemSize = new IntValue(500)
167      });
168      metaOptimizationProblem.Problems.Add(new HeuristicLab.Problems.TestFunctions.SingleObjectiveTestFunctionProblem() {
169        Evaluator = new GriewankEvaluator(),
170        ProblemSize = new IntValue(1000)
171      });
172
173      ConfigurePopulationSize(algorithmVc);
174      ConfigureMutationRate(algorithmVc);
175      ConfigureMutationOperator(algorithmVc);
176      ConfigureElites(algorithmVc);
177      ConfigureSelectionOperator(algorithmVc);
178      return algorithmVc;
179    }
180
181    private static void TestConfiguration(IValueConfiguration algorithmVc, GeneticAlgorithm baseLevelAlgorithm) {
182      IRandom rand = new FastRandom(0);
183      // set random values
184      for (int i = 0; i < 10; i++) {
185        IValueConfiguration clonedVc = (IValueConfiguration)algorithmVc.Clone();
186        GeneticAlgorithm newAlg = (GeneticAlgorithm)baseLevelAlgorithm.Clone();
187        clonedVc.Randomize(rand);
188        clonedVc.Parameterize(newAlg);
189        Console.WriteLine(string.Format("PopSize: original: {0}, randomized: {1}", baseLevelAlgorithm.PopulationSize, newAlg.PopulationSize));
190        Console.WriteLine(string.Format("MutRate: original: {0}, randomized: {1}", baseLevelAlgorithm.MutationProbability, newAlg.MutationProbability));
191        Console.WriteLine(string.Format("MutOp: original: {0}, randomized: {1}", baseLevelAlgorithm.Mutator, newAlg.Mutator));
192        Console.WriteLine(string.Format("SelOp: original: {0}, randomized: {1}", baseLevelAlgorithm.Selector, newAlg.Selector));
193        //Console.WriteLine(string.Format("GrSi: original: {0}, randomized: {1}", "?", ((TournamentSelector)newAlg.Selector).GroupSizeParameter.Value));
194        Console.WriteLine("---");
195      }
196
197      Console.WriteLine("=======================");
198      algorithmVc.Randomize(rand);
199      algorithmVc.Parameterize(baseLevelAlgorithm);
200      // mutate
201      for (int i = 0; i < 10; i++) {
202        IValueConfiguration clonedVc = (IValueConfiguration)algorithmVc.Clone();
203        GeneticAlgorithm newAlg = (GeneticAlgorithm)baseLevelAlgorithm.Clone();
204        //clonedVc.Mutate(rand);
205       
206        //.Apply(rand, clonedVc); todo
207        clonedVc.Parameterize(newAlg);
208        Console.WriteLine(string.Format("PopSize: original: {0}, mutated: {1}", baseLevelAlgorithm.PopulationSize, newAlg.PopulationSize));
209        Console.WriteLine(string.Format("MutRate: original: {0}, mutated: {1}", baseLevelAlgorithm.MutationProbability, newAlg.MutationProbability));
210        Console.WriteLine(string.Format("MutOp: original: {0}, mutated: {1}", baseLevelAlgorithm.Mutator, newAlg.Mutator));
211        Console.WriteLine(string.Format("SelOp: original: {0}, mutated: {1}", baseLevelAlgorithm.Selector, newAlg.Selector));
212        //Console.WriteLine(string.Format("GrSi: original: {0}, mutated: {1}", ((TournamentSelector)baseLevelAlgorithm.Selector).GroupSizeParameter.Value, ((TournamentSelector)newAlg.Selector).GroupSizeParameter.Value));
213        Console.WriteLine("---");
214      }
215
216      Console.WriteLine("=======================");
217      // cross
218      for (int i = 0; i < 10; i++) {
219        IValueConfiguration clonedVc1 = (IValueConfiguration)algorithmVc.Clone();
220        IValueConfiguration clonedVc2 = (IValueConfiguration)algorithmVc.Clone();
221
222        GeneticAlgorithm first = (GeneticAlgorithm)baseLevelAlgorithm.Clone();
223        GeneticAlgorithm second = (GeneticAlgorithm)baseLevelAlgorithm.Clone();
224
225        clonedVc1.Randomize(rand);
226        clonedVc1.Parameterize(first);
227
228        clonedVc2.Randomize(rand);
229        clonedVc2.Parameterize(second);
230
231        var popSizeBefore = first.PopulationSize.Value;
232        var mutRateBefore = first.MutationProbability.Value;
233        var mutOpBefore = first.Mutator;
234        var selOpBefore = first.Selector;
235        //var groupSizeBefore = ((TournamentSelector)first.Selector).GroupSizeParameter.Value.Value;
236
237        //clonedVc1.Cross(clonedVc2, rand); todo
238        clonedVc1.Parameterize(first);
239
240        Console.WriteLine(string.Format("PopSize: first: {0}, second: {1}, crossed: {2}", popSizeBefore, second.PopulationSize, first.PopulationSize));
241        Console.WriteLine(string.Format("MutRate: first: {0}, second: {1}, crossed: {2}", mutRateBefore, second.MutationProbability, first.MutationProbability));
242        Console.WriteLine(string.Format("MutOp: first: {0}, second: {1}, crossed: {2}", mutOpBefore, second.Mutator, first.Mutator));
243        Console.WriteLine(string.Format("SelOp: first: {0}, second: {1}, crossed: {2}", selOpBefore, second.Selector, first.Selector));
244        //Console.WriteLine(string.Format("GrSi: first: {0}, second: {1}, crossed: {2}", groupSizeBefore, ((TournamentSelector)second.Selector).GroupSizeParameter.Value, ((TournamentSelector)first.Selector).GroupSizeParameter.Value));
245        Console.WriteLine("---");
246      }
247      Console.WriteLine("=======================");
248    }
249
250    private static void ConfigureMutationOperator(IValueConfiguration algorithmVc) {
251      var mutationOperator = algorithmVc.ParameterConfigurations.Where(x => x.Name == "Mutator").SingleOrDefault();
252      mutationOperator.Optimize = true;
253
254      // uncheck multiMutator to avoid Michalewicz issue
255      var multiMutator = mutationOperator.ValueConfigurations.Where(x => x.ActualValue.Value != null && x.ActualValue.Value.ItemName.StartsWith("Multi")).SingleOrDefault();
256      if (multiMutator != null) {
257        mutationOperator.ValueConfigurations.SetItemCheckedState(multiMutator, false);
258      }
259    }
260
261    private static void ConfigureSelectionOperator(IValueConfiguration algorithmVc) {
262      var selectionOperatorPc = algorithmVc.ParameterConfigurations.Where(x => x.Name == "Selector").SingleOrDefault();
263      selectionOperatorPc.Optimize = true;
264
265      foreach (var vc in selectionOperatorPc.ValueConfigurations) {
266        if (vc.ActualValue.ValueDataType == typeof(TournamentSelector)) {
267          selectionOperatorPc.ValueConfigurations.SetItemCheckedState(vc, true);
268          vc.Optimize = true;
269          ConfigureTournamentGroupSize(vc);
270        } else if (vc.ActualValue.ValueDataType == typeof(RandomSelector)) {
271          selectionOperatorPc.ValueConfigurations.SetItemCheckedState(vc, true);
272        } else {
273          selectionOperatorPc.ValueConfigurations.SetItemCheckedState(vc, true);
274        }
275      }
276    }
277
278    private static void ConfigureTournamentGroupSize(IValueConfiguration tournamentVc) {
279      var groupSizePc = tournamentVc.ParameterConfigurations.Where(x => x.ParameterName == "GroupSize").SingleOrDefault();
280      groupSizePc.Optimize = true;
281
282      groupSizePc.ValueConfigurations.First().Optimize = true;
283      groupSizePc.ValueConfigurations.First().RangeConstraint.LowerBound = new IntValue(0);
284      groupSizePc.ValueConfigurations.First().RangeConstraint.UpperBound = new IntValue(100);
285      groupSizePc.ValueConfigurations.First().RangeConstraint.StepSize = new IntValue(1);
286    }
287
288    private static void ConfigurePopulationSize(IValueConfiguration algorithmVc) {
289      var populationSizePc = algorithmVc.ParameterConfigurations.Where(x => x.Name == "PopulationSize").SingleOrDefault();
290      populationSizePc.Optimize = true;
291      var populationSizeVc = populationSizePc.ValueConfigurations.First();
292      populationSizeVc.Optimize = true;
293      populationSizeVc.RangeConstraint.LowerBound = new IntValue(20);
294      populationSizeVc.RangeConstraint.UpperBound = new IntValue(100);
295      populationSizeVc.RangeConstraint.StepSize = new IntValue(1);
296    }
297
298    private static void ConfigureMutationRate(IValueConfiguration algorithmVc) {
299      var mutationRatePc = algorithmVc.ParameterConfigurations.Where(x => x.Name == "MutationProbability").SingleOrDefault();
300      mutationRatePc.Optimize = true;
301      var mutationRateVc = mutationRatePc.ValueConfigurations.First();
302      mutationRateVc.Optimize = true;
303      mutationRateVc.RangeConstraint.LowerBound = new PercentValue(0.0);
304      mutationRateVc.RangeConstraint.UpperBound = new PercentValue(1.0);
305      mutationRateVc.RangeConstraint.StepSize = new PercentValue(0.01);
306    }
307
308    private static void ConfigureElites(IValueConfiguration algorithmVc) {
309      var elitesPc = algorithmVc.ParameterConfigurations.Where(x => x.Name == "Elites").SingleOrDefault();
310      elitesPc.Optimize = true;
311      var elitesVc = elitesPc.ValueConfigurations.First();
312      elitesVc.Optimize = true;
313      elitesVc.RangeConstraint.LowerBound = new IntValue(0);
314      elitesVc.RangeConstraint.UpperBound = new IntValue(20);
315      elitesVc.RangeConstraint.StepSize = new IntValue(1);
316    }
317
318    private static void TestOptimization(EngineAlgorithm metaLevelAlgorithm) {
319      ContentManager.Initialize(new PersistenceContentManager());
320      string path = Path.Combine(AppDomain.CurrentDomain.BaseDirectory, "Results");
321      if (!Directory.Exists(path))
322        Directory.CreateDirectory(path);
323      string id = DateTime.Now.ToString("yyyy.MM.dd - HH;mm;ss,ffff");
324      string resultPath = Path.Combine(path, string.Format("{0} - Result.hl", id));
325      string outputPath = Path.Combine(path, string.Format("{0} - Console.txt", id));
326
327      using (var sw = new StreamWriter(outputPath)) {
328        sw.AutoFlush = true;
329
330        StringBuilder sb1 = new StringBuilder();
331        sb1.AppendLine(string.Format("Meta.PopulationSize: {0}", metaAlgorithmPopulationSize));
332        sb1.AppendLine(string.Format("Meta.MaxGenerations: {0}", metaAlgorithmMaxGenerations));
333        sb1.AppendLine(string.Format("Meta.Repetitions   : {0}", metaProblemRepetitions));
334        sb1.AppendLine(string.Format("Base.MaxGenerations: {0}", baseAlgorithmMaxGenerations));
335        sw.WriteLine(sb1.ToString());
336        Console.WriteLine(sb1.ToString());
337
338        metaLevelAlgorithm.Start();
339        int i = 0;
340        int currentGeneration = -1;
341        do {
342          Thread.Sleep(500);
343          if (metaLevelAlgorithm.Results.ContainsKey("Generations") && ((IntValue)metaLevelAlgorithm.Results["Generations"].Value).Value != currentGeneration) {
344            while (metaLevelAlgorithm.Results.Count < 3) Thread.Sleep(100);
345            StringBuilder sb = new StringBuilder();
346            sb.AppendLine(DateTime.Now.ToLongTimeString());
347            sb.AppendLine("=================================");
348
349            sb.AppendLine(metaLevelAlgorithm.ExecutionState.ToString());
350            foreach (var result in metaLevelAlgorithm.Results) {
351              sb.AppendLine(result.ToString());
352              if (result.Name == "Population") {
353                RunCollection rc = (RunCollection)result.Value;
354                var orderedRuns = rc.OrderBy(x => x.Results["RunsAverageQuality"]);
355
356                sb.AppendLine("Qual.  PoSi MutRa Eli SelOp MutOp");
357                foreach (IRun run in orderedRuns) {
358                  string selector;
359                  if (run.Parameters["Selector"] is TournamentSelector) {
360                    selector = string.Format("{0} ({1})", run.Parameters["Selector"].ToString(), ((TournamentSelector)run.Parameters["Selector"]).GroupSizeParameter.Value.ToString());
361                  } else {
362                    selector = string.Format("{0}", run.Parameters["Selector"].ToString());
363                  }
364
365                  sb.AppendLine(string.Format("{0} {1} {2} {3} {4} {5}",
366                    ((DoubleValue)run.Results["RunsAverageQuality"]).Value.ToString("#0.00").PadLeft(7, ' '),
367                    ((IntValue)run.Parameters["PopulationSize"]).Value.ToString().PadLeft(3, ' ').PadRight(3, ' '),
368                    ((DoubleValue)run.Parameters["MutationProbability"]).Value.ToString("0.00").PadLeft(5, ' '),
369                    ((IntValue)run.Parameters["Elites"]).Value.ToString().PadLeft(3, ' '),
370                    Shorten(selector, 20).PadRight(20, ' '),
371                    run.Parameters.ContainsKey("Mutator") ? run.Parameters["Mutator"].ToString() : "null"));
372                }
373              }
374            } // foreach
375            Console.Clear();
376            Console.WriteLine(sb.ToString());
377            sw.WriteLine(sb.ToString());
378            currentGeneration = ((IntValue)metaLevelAlgorithm.Results["Generations"].Value).Value;
379          } // if
380          if (i % 30 == 0) GC.Collect();
381          i++;
382        } while (metaLevelAlgorithm.ExecutionState != ExecutionState.Stopped);
383      }
384
385      Console.WriteLine();
386      Console.WriteLine("Storing...");
387
388      ContentManager.Save((IStorableContent)metaLevelAlgorithm, resultPath, true);
389      Console.WriteLine("Finished");
390    }
391
392    private static void TestShorten() {
393      int n = 8;
394      Console.WriteLine(Shorten("1", n));
395      Console.WriteLine(Shorten("12", n));
396      Console.WriteLine(Shorten("123", n));
397      Console.WriteLine(Shorten("1234", n));
398      Console.WriteLine(Shorten("12345", n));
399      Console.WriteLine(Shorten("123456", n));
400      Console.WriteLine(Shorten("1234567", n));
401      Console.WriteLine(Shorten("12345678", n));
402      Console.WriteLine(Shorten("123456789", n));
403      Console.WriteLine(Shorten("1234567890", n));
404      Console.WriteLine(Shorten("12345678901", n));
405    }
406
407    private static string Shorten(string s, int n) {
408      string placeholder = "..";
409      if (s.Length <= n) return s;
410      int len = n / 2 - placeholder.Length / 2;
411      string start = s.Substring(0, len);
412      string end = s.Substring(s.Length - len, len);
413      return start + placeholder + end;
414    }
415
416    private static void TestIntSampling() {
417      System.Random rand = new System.Random();
418      int lower = 10;
419      int upper = 20;
420      int stepsize = 7;
421      for (int i = 0; i < 100; i++) {
422        int val;
423        do {
424          val = rand.Next(lower / stepsize, upper / stepsize + 1) * stepsize;
425        } while (val < lower || val > upper);
426        Console.WriteLine(val);
427      }
428    }
429
430    private static void TestDoubleSampling() {
431      System.Random rand = new System.Random();
432      double lower = 2;
433      double upper = 3;
434      double stepsize = 0.6;
435      for (int i = 0; i < 100; i++) {
436        double val;
437        do {
438          val = Math.Round((rand.NextDouble() * (upper - lower) + lower) / stepsize, 0) * stepsize;
439        } while (val < lower || val > upper);
440        Console.WriteLine(val);
441      }
442    }
443
444    private static IEnumerable<IItem> GetValidValues(IValueParameter valueParameter) {
445      return ApplicationManager.Manager.GetInstances(valueParameter.DataType).Select(x => (IItem)x).OrderBy(x => x.ItemName);
446    }
447  }
448}
Note: See TracBrowser for help on using the repository browser.