Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab/3.3/Tests/GeneticAlgorithmSamplesTest.cs @ 6441

Last change on this file since 6441 was 6441, checked in by gkronber, 13 years ago

#1553: implemented unit test to create and run the GA VRP sample.
File size: 19.9 KB
Line 
1using System;
2using System.Text;
3using System.Collections.Generic;
4using System.Linq;
5using Microsoft.VisualStudio.TestTools.UnitTesting;
6using HeuristicLab.Algorithms.GeneticAlgorithm;
7using HeuristicLab.Problems.ArtificialAnt;
8using HeuristicLab.Selection;
9using HeuristicLab.Data;
10using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
11using HeuristicLab.Persistence.Default.Xml;
12using HeuristicLab.Optimization;
13using System.Threading;
14using HeuristicLab.ParallelEngine;
15using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
16using HeuristicLab.Problems.DataAnalysis;
17using HeuristicLab.Problems.DataAnalysis.Symbolic;
18using System.IO;
19using HeuristicLab.Problems.DataAnalysis.Symbolic.Classification;
20using HeuristicLab.Problems.TravelingSalesman;
21using HeuristicLab.Encodings.PermutationEncoding;
22using HeuristicLab.Problems.VehicleRouting;
23using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
24using HeuristicLab.Problems.VehicleRouting.Encodings;
25using HeuristicLab.Problems.VehicleRouting.Encodings.General;
26
27namespace HeuristicLab_33.Tests {
28  [TestClass]
29  public class GeneticAlgorithmSamplesTest {
30    [TestMethod]
31    public void CreateTSPSample() {
32      GeneticAlgorithm ga = new GeneticAlgorithm();
33      #region problem configuration
34      TravelingSalesmanProblem tspProblem = new TravelingSalesmanProblem();
35      // import and configure TSP data
36      string ch130FileName = Path.GetTempFileName() + ".tsp";// for silly parser constraints
37      using (var writer = File.CreateText(ch130FileName)) {
38        writer.Write(HeuristicLab_33.Tests.Properties.Resources.ch130);
39      }
40      string ch130OptTourFileName = Path.GetTempFileName() + ".opt.tour"; // for silly parser constraints
41      using (var writer = File.CreateText(ch130OptTourFileName)) {
42        writer.Write(HeuristicLab_33.Tests.Properties.Resources.ch130_opt);
43      }
44
45      tspProblem.ImportFromTSPLIB(ch130FileName, ch130OptTourFileName, 6110);
46      tspProblem.Evaluator = new TSPRoundedEuclideanPathEvaluator();
47      tspProblem.SolutionCreator = new RandomPermutationCreator();
48      tspProblem.UseDistanceMatrix.Value = true;
49      tspProblem.Name = "ch130 TSP (imported from TSPLIB)";
50      tspProblem.Description = "130 city problem (Churritz)";
51      #endregion
52      #region algorithm configuration
53      ga.Name = "Genetic Algorithm - TSP";
54      ga.Description = "A genetic algorithm which solves the \"ch130\" traveling salesman problem (imported from TSPLIB)";
55      ga.Problem = tspProblem;
56      ConfigureGeneticAlgorithmParameters<ProportionalSelector, OrderCrossover2, InversionManipulator>(
57        ga, 100, 1, 1000, 0.05);
58
59      ga.Analyzer.Operators.SetItemCheckedState(ga.Analyzer.Operators
60        .OfType<TSPAlleleFrequencyAnalyzer>()
61        .Single(), false);
62      ga.Analyzer.Operators.SetItemCheckedState(ga.Analyzer.Operators
63        .OfType<TSPPopulationDiversityAnalyzer>()
64        .Single(), false);
65      #endregion
66
67      XmlGenerator.Serialize(ga, "../../GA_TSP.hl");
68
69      RunAlgorithm(ga);
70    }
71    [TestMethod]
72    public void CreateVRPSample() {
73      GeneticAlgorithm ga = new GeneticAlgorithm();
74      #region problem configuration
75      VehicleRoutingProblem vrpProblem = new VehicleRoutingProblem();
76      // import and configure VRP data
77      string c101FileName = Path.GetTempFileName();
78      using (var writer = File.CreateText(c101FileName)) {
79        writer.Write(HeuristicLab_33.Tests.Properties.Resources.C101);
80      }
81      // import and configure VRP data
82      string c101BestSolutionFileName = Path.GetTempFileName();
83      using (var writer = File.CreateText(c101BestSolutionFileName)) {
84        writer.Write(HeuristicLab_33.Tests.Properties.Resources.C101_opt);
85      }
86
87      vrpProblem.ImportFromSolomon(c101FileName);
88      vrpProblem.ImportSolution(c101BestSolutionFileName);
89      vrpProblem.Name = "C101 VRP (imported from Solomon)";
90      vrpProblem.Description = "Represents a Vehicle Routing Problem.";
91      vrpProblem.DistanceFactorParameter.Value.Value = 1;
92      vrpProblem.FleetUsageFactorParameter.Value.Value = 100;
93      vrpProblem.OverloadPenaltyParameter.Value.Value = 100;
94      vrpProblem.TardinessPenaltyParameter.Value.Value = 100;
95      vrpProblem.TimeFactorParameter.Value.Value = 0;
96      vrpProblem.Evaluator = new VRPEvaluator();
97      vrpProblem.MaximizationParameter.Value.Value = false;
98      vrpProblem.SolutionCreator = new RandomCreator();
99      vrpProblem.UseDistanceMatrix.Value = true;
100      vrpProblem.Vehicles.Value = 25;
101      #endregion
102      #region algorithm configuration
103      ga.Name = "Genetic Algorithm - VRP";
104      ga.Description = "A genetic algorithm which solves the \"C101\" vehicle routing problem (imported from Solomon)";
105      ga.Problem = vrpProblem;
106      ConfigureGeneticAlgorithmParameters<TournamentSelector, MultiVRPSolutionCrossover, MultiVRPSolutionManipulator>(
107        ga, 100, 1, 1000, 0.05, 3);
108
109      var xOver = (MultiVRPSolutionCrossover)ga.Crossover;
110      foreach (var op in xOver.Operators) {
111        xOver.Operators.SetItemCheckedState(op, false);
112      }
113      xOver.Operators.SetItemCheckedState(xOver.Operators
114        .OfType<PotvinRouteBasedCrossover>()
115        .Single(), true);
116      xOver.Operators.SetItemCheckedState(xOver.Operators
117        .OfType<PotvinSequenceBasedCrossover>()
118        .Single(), true);
119
120      var manipulator = (MultiVRPSolutionManipulator)ga.Mutator;
121      foreach (var op in manipulator.Operators) {
122        manipulator.Operators.SetItemCheckedState(op, false);
123      }
124      manipulator.Operators.SetItemCheckedState(manipulator.Operators
125        .OfType<PotvinOneLevelExchangeMainpulator>()
126        .Single(), true);
127      manipulator.Operators.SetItemCheckedState(manipulator.Operators
128        .OfType<PotvinTwoLevelExchangeManipulator>()
129        .Single(), true);
130      #endregion
131
132      XmlGenerator.Serialize(ga, "../../GA_VRP.hl");
133
134      RunAlgorithm(ga);
135    }
136
137    [TestMethod]
138    public void CreateArtificialAntSample() {
139      GeneticAlgorithm ga = new GeneticAlgorithm();
140      #region problem configuration
141      ArtificialAntProblem antProblem = new ArtificialAntProblem();
142      antProblem.BestKnownQuality.Value = 89;
143      antProblem.MaxExpressionDepth.Value = 10;
144      antProblem.MaxExpressionLength.Value = 100;
145      antProblem.MaxFunctionArguments.Value = 3;
146      antProblem.MaxFunctionDefinitions.Value = 3;
147      antProblem.MaxTimeSteps.Value = 600;
148      #endregion
149      #region algorithm configuration
150      ga.Name = "Genetic Programming - Artificial Ant";
151      ga.Description = "A standard genetic programming algorithm to solve the artificial ant problem (Santa-Fe trail)";
152      ga.Problem = antProblem;
153      ConfigureGeneticAlgorithmParameters<TournamentSelector, SubtreeCrossover, MultiSymbolicExpressionTreeArchitectureManipulator>(
154        ga, 1000, 1, 100, 0.15, 5);
155      var mutator = (MultiSymbolicExpressionTreeArchitectureManipulator)ga.Mutator;
156      mutator.Operators.SetItemCheckedState(mutator.Operators
157        .OfType<FullTreeShaker>()
158        .Single(), false);
159      mutator.Operators.SetItemCheckedState(mutator.Operators
160        .OfType<OnePointShaker>()
161        .Single(), false);
162      #endregion
163
164      XmlGenerator.Serialize(ga, "../../SGP_SantaFe.hl");
165
166      RunAlgorithm(ga);
167    }
168
169    [TestMethod]
170    public void CreateSymbolicRegressionSample() {
171      GeneticAlgorithm ga = new GeneticAlgorithm();
172      #region problem configuration
173      SymbolicRegressionSingleObjectiveProblem symbRegProblem = new SymbolicRegressionSingleObjectiveProblem();
174      symbRegProblem.Name = "Tower Symbolic Regression Problem";
175      symbRegProblem.Description = "Tower Dataset (downloaded from: http://vanillamodeling.com/realproblems.html)";
176      // import and configure problem data
177      string filename = Path.GetTempFileName();
178      using (var writer = File.CreateText(filename)) {
179        writer.Write(HeuristicLab_33.Tests.Properties.Resources.TowerData);
180      }
181      var towerProblemData = RegressionProblemData.ImportFromFile(filename);
182      towerProblemData.TargetVariableParameter.Value = towerProblemData.TargetVariableParameter.ValidValues
183        .First(v => v.Value == "towerResponse");
184      towerProblemData.InputVariables.SetItemCheckedState(
185        towerProblemData.InputVariables.Single(x => x.Value == "x1"), true);
186      towerProblemData.InputVariables.SetItemCheckedState(
187        towerProblemData.InputVariables.Single(x => x.Value == "x7"), false);
188      towerProblemData.InputVariables.SetItemCheckedState(
189        towerProblemData.InputVariables.Single(x => x.Value == "x11"), false);
190      towerProblemData.InputVariables.SetItemCheckedState(
191        towerProblemData.InputVariables.Single(x => x.Value == "x16"), false);
192      towerProblemData.InputVariables.SetItemCheckedState(
193        towerProblemData.InputVariables.Single(x => x.Value == "x21"), false);
194      towerProblemData.InputVariables.SetItemCheckedState(
195        towerProblemData.InputVariables.Single(x => x.Value == "x25"), false);
196      towerProblemData.InputVariables.SetItemCheckedState(
197        towerProblemData.InputVariables.Single(x => x.Value == "towerResponse"), false);
198      towerProblemData.TrainingPartition.Start = 0;
199      towerProblemData.TrainingPartition.End = 4000;
200      towerProblemData.TestPartition.Start = 4000;
201      towerProblemData.TestPartition.End = 4999;
202      towerProblemData.Name = "Data imported from towerData.txt";
203      towerProblemData.Description = "Chemical concentration at top of distillation tower, dataset downloaded from: http://vanillamodeling.com/realproblems.html, best R² achieved with nu-SVR = 0.97";
204      symbRegProblem.ProblemData = towerProblemData;
205
206      // configure grammar
207      var grammar = new TypeCoherentExpressionGrammar();
208      grammar.Symbols.OfType<Sine>().Single().InitialFrequency = 0.0;
209      grammar.Symbols.OfType<Cosine>().Single().InitialFrequency = 0.0;
210      grammar.Symbols.OfType<Tangent>().Single().InitialFrequency = 0.0;
211      grammar.Symbols.OfType<IfThenElse>().Single().InitialFrequency = 0.0;
212      grammar.Symbols.OfType<GreaterThan>().Single().InitialFrequency = 0.0;
213      grammar.Symbols.OfType<LessThan>().Single().InitialFrequency = 0.0;
214      grammar.Symbols.OfType<And>().Single().InitialFrequency = 0.0;
215      grammar.Symbols.OfType<Or>().Single().InitialFrequency = 0.0;
216      grammar.Symbols.OfType<Not>().Single().InitialFrequency = 0.0;
217      grammar.Symbols.OfType<TimeLag>().Single().InitialFrequency = 0.0;
218      grammar.Symbols.OfType<Integral>().Single().InitialFrequency = 0.0;
219      grammar.Symbols.OfType<Derivative>().Single().InitialFrequency = 0.0;
220      grammar.Symbols.OfType<LaggedVariable>().Single().InitialFrequency = 0.0;
221      grammar.Symbols.OfType<VariableCondition>().Single().InitialFrequency = 0.0;
222      var varSymbol = grammar.Symbols.OfType<Variable>().Where(x => !(x is LaggedVariable)).Single();
223      varSymbol.WeightMu = 1.0;
224      varSymbol.WeightSigma = 1.0;
225      varSymbol.WeightManipulatorMu = 0.0;
226      varSymbol.WeightManipulatorSigma = 0.05;
227      varSymbol.MultiplicativeWeightManipulatorSigma = 0.03;
228      var constSymbol = grammar.Symbols.OfType<Constant>().Single();
229      constSymbol.MaxValue = 20;
230      constSymbol.MinValue = -20;
231      constSymbol.ManipulatorMu = 0.0;
232      constSymbol.ManipulatorSigma = 1;
233      constSymbol.MultiplicativeManipulatorSigma = 0.03;
234      symbRegProblem.SymbolicExpressionTreeGrammar = grammar;
235
236      // configure remaining problem parameters
237      symbRegProblem.BestKnownQuality.Value = 0.97;
238      symbRegProblem.FitnessCalculationPartition.Start = 0;
239      symbRegProblem.FitnessCalculationPartition.End = 2800;
240      symbRegProblem.ValidationPartition.Start = 2800;
241      symbRegProblem.ValidationPartition.End = 4000;
242      symbRegProblem.RelativeNumberOfEvaluatedSamples.Value = 0.3;
243      symbRegProblem.MaximumSymbolicExpressionTreeLength.Value = 150;
244      symbRegProblem.MaximumSymbolicExpressionTreeDepth.Value = 12;
245      symbRegProblem.MaximumFunctionDefinitions.Value = 0;
246      symbRegProblem.MaximumFunctionArguments.Value = 0;
247
248      symbRegProblem.EvaluatorParameter.Value = new SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator();
249      #endregion
250      #region algorithm configuration
251      ga.Problem = symbRegProblem;
252      ga.Name = "Genetic Programming - Symbolic Regression";
253      ga.Description = "A standard genetic programming algorithm to solve a symbolic regression problem (tower dataset)";
254      ConfigureGeneticAlgorithmParameters<TournamentSelector, SubtreeCrossover, MultiSymbolicExpressionTreeManipulator>(
255        ga, 1000, 1, 100, 0.15, 5);
256      var mutator = (MultiSymbolicExpressionTreeManipulator)ga.Mutator;
257      mutator.Operators.OfType<FullTreeShaker>().Single().ShakingFactor = 0.1;
258      mutator.Operators.OfType<OnePointShaker>().Single().ShakingFactor = 1.0;
259
260      ga.Analyzer.Operators.SetItemCheckedState(
261        ga.Analyzer.Operators
262        .OfType<SymbolicRegressionSingleObjectiveOverfittingAnalyzer>()
263        .Single(), false);
264      #endregion
265
266      XmlGenerator.Serialize(ga, "../../SGP_SymbReg.hl");
267
268      RunAlgorithm(ga);
269    }
270
271    [TestMethod]
272    public void CreateSymbolicClassificationSample() {
273      GeneticAlgorithm ga = new GeneticAlgorithm();
274      #region problem configuration
275      SymbolicClassificationSingleObjectiveProblem symbClassProblem = new SymbolicClassificationSingleObjectiveProblem();
276      symbClassProblem.Name = "Mammography Classification Problem";
277      symbClassProblem.Description = "Mammography dataset imported from the UCI machine learning repository (http://archive.ics.uci.edu/ml/datasets/Mammographic+Mass)";
278      // import and configure problem data
279      string filename = Path.GetTempFileName();
280      using (var writer = File.CreateText(filename)) {
281        writer.Write(HeuristicLab_33.Tests.Properties.Resources.MammographicMasses);
282      }
283      var mammoData = ClassificationProblemData.ImportFromFile(filename);
284      mammoData.TargetVariableParameter.Value = mammoData.TargetVariableParameter.ValidValues
285        .First(v => v.Value == "Severity");
286      mammoData.InputVariables.SetItemCheckedState(
287        mammoData.InputVariables.Single(x => x.Value == "BI-RADS"), false);
288      mammoData.InputVariables.SetItemCheckedState(
289        mammoData.InputVariables.Single(x => x.Value == "Age"), true);
290      mammoData.InputVariables.SetItemCheckedState(
291        mammoData.InputVariables.Single(x => x.Value == "Shape"), true);
292      mammoData.InputVariables.SetItemCheckedState(
293        mammoData.InputVariables.Single(x => x.Value == "Margin"), true);
294      mammoData.InputVariables.SetItemCheckedState(
295        mammoData.InputVariables.Single(x => x.Value == "Density"), true);
296      mammoData.InputVariables.SetItemCheckedState(
297        mammoData.InputVariables.Single(x => x.Value == "Severity"), false);
298      mammoData.TrainingPartition.Start = 0;
299      mammoData.TrainingPartition.End = 800;
300      mammoData.TestPartition.Start = 800;
301      mammoData.TestPartition.End = 961;
302      mammoData.Name = "Data imported from mammographic_masses.csv";
303      mammoData.Description = "Original dataset: http://archive.ics.uci.edu/ml/datasets/Mammographic+Mass, missing values have been replaced with median values.";
304      symbClassProblem.ProblemData = mammoData;
305
306      // configure grammar
307      var grammar = new TypeCoherentExpressionGrammar();
308      grammar.Symbols.OfType<Sine>().Single().InitialFrequency = 0.0;
309      grammar.Symbols.OfType<Cosine>().Single().InitialFrequency = 0.0;
310      grammar.Symbols.OfType<Tangent>().Single().InitialFrequency = 0.0;
311      grammar.Symbols.OfType<Power>().Single().InitialFrequency = 0.0;
312      grammar.Symbols.OfType<Root>().Single().InitialFrequency = 0.0;
313      grammar.Symbols.OfType<TimeLag>().Single().InitialFrequency = 0.0;
314      grammar.Symbols.OfType<Integral>().Single().InitialFrequency = 0.0;
315      grammar.Symbols.OfType<Derivative>().Single().InitialFrequency = 0.0;
316      grammar.Symbols.OfType<LaggedVariable>().Single().InitialFrequency = 0.0;
317      grammar.Symbols.OfType<VariableCondition>().Single().InitialFrequency = 0.0;
318      var varSymbol = grammar.Symbols.OfType<Variable>().Where(x => !(x is LaggedVariable)).Single();
319      varSymbol.WeightMu = 1.0;
320      varSymbol.WeightSigma = 1.0;
321      varSymbol.WeightManipulatorMu = 0.0;
322      varSymbol.WeightManipulatorSigma = 0.05;
323      varSymbol.MultiplicativeWeightManipulatorSigma = 0.03;
324      var constSymbol = grammar.Symbols.OfType<Constant>().Single();
325      constSymbol.MaxValue = 20;
326      constSymbol.MinValue = -20;
327      constSymbol.ManipulatorMu = 0.0;
328      constSymbol.ManipulatorSigma = 1;
329      constSymbol.MultiplicativeManipulatorSigma = 0.03;
330      symbClassProblem.SymbolicExpressionTreeGrammar = grammar;
331
332      // configure remaining problem parameters
333      symbClassProblem.BestKnownQuality.Value = 0.0;
334      symbClassProblem.FitnessCalculationPartition.Start = 0;
335      symbClassProblem.FitnessCalculationPartition.End = 400;
336      symbClassProblem.ValidationPartition.Start = 400;
337      symbClassProblem.ValidationPartition.End = 800;
338      symbClassProblem.RelativeNumberOfEvaluatedSamples.Value = 1;
339      symbClassProblem.MaximumSymbolicExpressionTreeLength.Value = 100;
340      symbClassProblem.MaximumSymbolicExpressionTreeDepth.Value = 10;
341      symbClassProblem.MaximumFunctionDefinitions.Value = 0;
342      symbClassProblem.MaximumFunctionArguments.Value = 0;
343      symbClassProblem.EvaluatorParameter.Value = new SymbolicClassificationSingleObjectiveMeanSquaredErrorEvaluator();
344      #endregion
345      #region algorithm configuration
346      ga.Problem = symbClassProblem;
347      ga.Name = "Genetic Programming - Symbolic Classification";
348      ga.Description = "A standard genetic programming algorithm to solve a classification problem (Mammographic+Mass dataset)";
349      ConfigureGeneticAlgorithmParameters<TournamentSelector, SubtreeCrossover, MultiSymbolicExpressionTreeManipulator>(
350        ga, 1000, 1, 100, 0.15, 5
351        );
352
353      var mutator = (MultiSymbolicExpressionTreeManipulator)ga.Mutator;
354      mutator.Operators.OfType<FullTreeShaker>().Single().ShakingFactor = 0.1;
355      mutator.Operators.OfType<OnePointShaker>().Single().ShakingFactor = 1.0;
356
357      ga.Analyzer.Operators.SetItemCheckedState(
358        ga.Analyzer.Operators
359        .OfType<SymbolicClassificationSingleObjectiveOverfittingAnalyzer>()
360        .Single(), false);
361      #endregion
362
363      XmlGenerator.Serialize(ga, "../../SGP_SymbClass.hl");
364
365      RunAlgorithm(ga);
366    }
367
368    private void ConfigureGeneticAlgorithmParameters<S, C, M>(GeneticAlgorithm ga, int popSize, int elites, int maxGens, double mutationRate, int tournGroupSize = 0)
369      where S : ISelector
370      where C : ICrossover
371      where M : IManipulator {
372      ga.Elites.Value = elites;
373      ga.MaximumGenerations.Value = maxGens;
374      ga.MutationProbability.Value = mutationRate;
375      ga.PopulationSize.Value = popSize;
376      ga.Seed.Value = 0;
377      ga.SetSeedRandomly.Value = true;
378      ga.Selector = ga.SelectorParameter.ValidValues
379        .OfType<S>()
380        .Single();
381
382      ga.Crossover = ga.CrossoverParameter.ValidValues
383        .OfType<C>()
384        .Single();
385
386      ga.Mutator = ga.MutatorParameter.ValidValues
387        .OfType<M>()
388        .Single();
389
390      var tSelector = ga.Selector as TournamentSelector;
391      if (tSelector != null) {
392        tSelector.GroupSizeParameter.Value.Value = 5;
393      }
394      ga.Engine = new ParallelEngine();
395    }
396
397
398    private void RunAlgorithm(IAlgorithm a) {
399      var trigger = new EventWaitHandle(false, EventResetMode.ManualReset);
400      Exception ex = null;
401      a.Stopped += (src, e) => { trigger.Set(); };
402      a.ExceptionOccurred += (src, e) => { ex = e.Value; };
403      a.Prepare();
404      a.Start();
405      trigger.WaitOne();
406
407      Assert.AreEqual(ex, null);
408    }
409  }
410}
Note: See TracBrowser for help on using the repository browser.