Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GeneralizedQAP/HeuristicLab/3.3/Tests/SamplesTest.cs @ 6843

Last change on this file since 6843 was 6609, checked in by svonolfe, 13 years ago

Adapted VRP unit test (#1561)
File size: 57.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using System.Threading;
25using HeuristicLab.Algorithms.EvolutionStrategy;
26using HeuristicLab.Algorithms.GeneticAlgorithm;
27using HeuristicLab.Algorithms.LocalSearch;
28using HeuristicLab.Algorithms.ParticleSwarmOptimization;
29using HeuristicLab.Algorithms.SimulatedAnnealing;
30using HeuristicLab.Algorithms.TabuSearch;
31using HeuristicLab.Algorithms.VariableNeighborhoodSearch;
32using HeuristicLab.Data;
33using HeuristicLab.Encodings.BinaryVectorEncoding;
34using HeuristicLab.Encodings.PermutationEncoding;
35using HeuristicLab.Encodings.RealVectorEncoding;
36using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
37using HeuristicLab.Optimization;
38using HeuristicLab.Optimization.Operators;
39using HeuristicLab.ParallelEngine;
40using HeuristicLab.Persistence.Default.Xml;
41using HeuristicLab.Problems.ArtificialAnt;
42using HeuristicLab.Problems.DataAnalysis;
43using HeuristicLab.Problems.DataAnalysis.Symbolic;
44using HeuristicLab.Problems.DataAnalysis.Symbolic.Classification;
45using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
46using HeuristicLab.Problems.Knapsack;
47using HeuristicLab.Problems.TestFunctions;
48using HeuristicLab.Problems.TravelingSalesman;
49using HeuristicLab.Problems.VehicleRouting;
50using HeuristicLab.Problems.VehicleRouting.Encodings.General;
51using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
52using HeuristicLab.Selection;
53using Microsoft.VisualStudio.TestTools.UnitTesting;
54
55namespace HeuristicLab_33.Tests {
56  [TestClass]
57  [DeploymentItem(@"Resources/C101.opt.txt")]
58  [DeploymentItem(@"Resources/C101.txt")]
59  [DeploymentItem(@"Resources/ch130.tsp")]
60  [DeploymentItem(@"Resources/ch130.opt.tour")]
61  [DeploymentItem(@"Resources/mammographic_masses.txt")]
62  [DeploymentItem(@"Resources/towerData.txt")]
63  public class SamplesTest {
64    #region GA
65    #region TSP
66    [TestMethod]
67    public void CreateGaTspSampleTest() {
68      var ga = CreateGaTspSample();
69      XmlGenerator.Serialize(ga, "../../GA_TSP.hl");
70    }
71    [TestMethod]
72    public void RunGaTspSampleTest() {
73      var ga = CreateGaTspSample();
74      ga.SetSeedRandomly.Value = false;
75      RunAlgorithm(ga);
76      Assert.AreEqual(12332, GetDoubleResult(ga, "BestQuality"));
77      Assert.AreEqual(13123.2, GetDoubleResult(ga, "CurrentAverageQuality"));
78      Assert.AreEqual(14538, GetDoubleResult(ga, "CurrentWorstQuality"));
79      Assert.AreEqual(99100, GetIntResult(ga, "EvaluatedSolutions"));
80    }
81
82    private GeneticAlgorithm CreateGaTspSample() {
83      GeneticAlgorithm ga = new GeneticAlgorithm();
84      #region Problem Configuration
85      TravelingSalesmanProblem tspProblem = new TravelingSalesmanProblem();
86      tspProblem.ImportFromTSPLIB("ch130.tsp", "ch130.opt.tour", 6110);
87      tspProblem.Evaluator = new TSPRoundedEuclideanPathEvaluator();
88      tspProblem.SolutionCreator = new RandomPermutationCreator();
89      tspProblem.UseDistanceMatrix.Value = true;
90      tspProblem.Name = "ch130 TSP (imported from TSPLIB)";
91      tspProblem.Description = "130 city problem (Churritz)";
92      #endregion
93      #region Algorithm Configuration
94      ga.Name = "Genetic Algorithm - TSP";
95      ga.Description = "A genetic algorithm which solves the \"ch130\" traveling salesman problem (imported from TSPLIB)";
96      ga.Problem = tspProblem;
97      ConfigureGeneticAlgorithmParameters<ProportionalSelector, OrderCrossover2, InversionManipulator>(
98        ga, 100, 1, 1000, 0.05);
99
100      ga.Analyzer.Operators.SetItemCheckedState(ga.Analyzer.Operators
101        .OfType<TSPAlleleFrequencyAnalyzer>()
102        .Single(), false);
103      ga.Analyzer.Operators.SetItemCheckedState(ga.Analyzer.Operators
104        .OfType<TSPPopulationDiversityAnalyzer>()
105        .Single(), false);
106      #endregion
107      return ga;
108    }
109    #endregion
110    #region VRP
111    [TestMethod]
112    public void CreateGaVrpSampleTest() {
113      var ga = CreateGaVrpSample();
114      XmlGenerator.Serialize(ga, "../../GA_VRP.hl");
115    }
116
117    [TestMethod]
118    public void RunGaVrpSampleTest() {
119      var ga = CreateGaVrpSample();
120      ga.SetSeedRandomly.Value = false;
121      RunAlgorithm(ga);
122      Assert.AreEqual(1828.9368669428336, GetDoubleResult(ga, "BestQuality"));
123      Assert.AreEqual(1831.5504074358635, GetDoubleResult(ga, "CurrentAverageQuality"));
124      Assert.AreEqual(1895.8980772167054, GetDoubleResult(ga, "CurrentWorstQuality"));
125      Assert.AreEqual(99100, GetIntResult(ga, "EvaluatedSolutions"));
126    }
127
128    private GeneticAlgorithm CreateGaVrpSample() {
129      GeneticAlgorithm ga = new GeneticAlgorithm();
130      #region Problem Configuration
131      VehicleRoutingProblem vrpProblem = new VehicleRoutingProblem();
132
133      vrpProblem.ImportFromSolomon("C101.txt");
134      vrpProblem.ImportSolution("C101.opt.txt");
135      vrpProblem.Name = "C101 VRP (imported from Solomon)";
136      vrpProblem.Description = "Represents a Vehicle Routing Problem.";
137      vrpProblem.DistanceFactorParameter.Value.Value = 1;
138      vrpProblem.FleetUsageFactorParameter.Value.Value = 100;
139      vrpProblem.OverloadPenaltyParameter.Value.Value = 100;
140      vrpProblem.TardinessPenaltyParameter.Value.Value = 100;
141      vrpProblem.TimeFactorParameter.Value.Value = 0;
142      vrpProblem.Evaluator = new VRPEvaluator();
143      vrpProblem.MaximizationParameter.Value.Value = false;
144      vrpProblem.SolutionCreator = new RandomCreator();
145      vrpProblem.UseDistanceMatrix.Value = true;
146      vrpProblem.Vehicles.Value = 25;
147      #endregion
148      #region Algorithm Configuration
149      ga.Name = "Genetic Algorithm - VRP";
150      ga.Description = "A genetic algorithm which solves the \"C101\" vehicle routing problem (imported from Solomon)";
151      ga.Problem = vrpProblem;
152      ConfigureGeneticAlgorithmParameters<TournamentSelector, MultiVRPSolutionCrossover, MultiVRPSolutionManipulator>(
153        ga, 100, 1, 1000, 0.05, 3);
154
155      var xOver = (MultiVRPSolutionCrossover)ga.Crossover;
156      foreach (var op in xOver.Operators) {
157        xOver.Operators.SetItemCheckedState(op, false);
158      }
159      xOver.Operators.SetItemCheckedState(xOver.Operators
160        .OfType<PotvinRouteBasedCrossover>()
161        .Single(), true);
162      xOver.Operators.SetItemCheckedState(xOver.Operators
163        .OfType<PotvinSequenceBasedCrossover>()
164        .Single(), true);
165
166      var manipulator = (MultiVRPSolutionManipulator)ga.Mutator;
167      foreach (var op in manipulator.Operators) {
168        manipulator.Operators.SetItemCheckedState(op, false);
169      }
170      manipulator.Operators.SetItemCheckedState(manipulator.Operators
171        .OfType<PotvinOneLevelExchangeMainpulator>()
172        .Single(), true);
173      manipulator.Operators.SetItemCheckedState(manipulator.Operators
174        .OfType<PotvinTwoLevelExchangeManipulator>()
175        .Single(), true);
176      #endregion
177      return ga;
178    }
179    #endregion
180    #region ArtificialAnt
181    [TestMethod]
182    public void CreateGpArtificialAntSampleTest() {
183      var ga = CreateGpArtificialAntSample();
184      XmlGenerator.Serialize(ga, "../../SGP_SantaFe.hl");
185    }
186
187    [TestMethod]
188    public void RunGpArtificialAntSampleTest() {
189      var ga = CreateGpArtificialAntSample();
190      ga.SetSeedRandomly.Value = false;
191      RunAlgorithm(ga);
192      if (!Environment.Is64BitProcess) {
193        Assert.AreEqual(89, GetDoubleResult(ga, "BestQuality"));
194        Assert.AreEqual(68.635, GetDoubleResult(ga, "CurrentAverageQuality"));
195        Assert.AreEqual(0, GetDoubleResult(ga, "CurrentWorstQuality"));
196        Assert.AreEqual(50950, GetIntResult(ga, "EvaluatedSolutions"));
197      } else {
198        Assert.AreEqual(82, GetDoubleResult(ga, "BestQuality"));
199        Assert.AreEqual(65.594, GetDoubleResult(ga, "CurrentAverageQuality"));
200        Assert.AreEqual(0, GetDoubleResult(ga, "CurrentWorstQuality"));
201        Assert.AreEqual(50950, GetIntResult(ga, "EvaluatedSolutions"));
202      }
203    }
204
205    public GeneticAlgorithm CreateGpArtificialAntSample() {
206      GeneticAlgorithm ga = new GeneticAlgorithm();
207      #region Problem Configuration
208      ArtificialAntProblem antProblem = new ArtificialAntProblem();
209      antProblem.BestKnownQuality.Value = 89;
210      antProblem.MaxExpressionDepth.Value = 10;
211      antProblem.MaxExpressionLength.Value = 100;
212      antProblem.MaxFunctionArguments.Value = 3;
213      antProblem.MaxFunctionDefinitions.Value = 3;
214      antProblem.MaxTimeSteps.Value = 600;
215      #endregion
216      #region Algorithm Configuration
217      ga.Name = "Genetic Programming - Artificial Ant";
218      ga.Description = "A standard genetic programming algorithm to solve the artificial ant problem (Santa-Fe trail)";
219      ga.Problem = antProblem;
220      ConfigureGeneticAlgorithmParameters<TournamentSelector, SubtreeCrossover, MultiSymbolicExpressionTreeArchitectureManipulator>(
221        ga, 1000, 1, 50, 0.15, 5);
222      var mutator = (MultiSymbolicExpressionTreeArchitectureManipulator)ga.Mutator;
223      mutator.Operators.SetItemCheckedState(mutator.Operators
224        .OfType<FullTreeShaker>()
225        .Single(), false);
226      mutator.Operators.SetItemCheckedState(mutator.Operators
227        .OfType<OnePointShaker>()
228        .Single(), false);
229      mutator.Operators.SetItemCheckedState(mutator.Operators
230        .OfType<ArgumentDeleter>()
231        .Single(), false);
232      mutator.Operators.SetItemCheckedState(mutator.Operators
233        .OfType<SubroutineDeleter>()
234        .Single(), false);
235      #endregion
236      return ga;
237    }
238    #endregion
239    #region Symbolic Regression
240    [TestMethod]
241    public void CreateGpSymbolicRegressionSampleTest() {
242      var ga = CreateGpSymbolicRegressionSample();
243      XmlGenerator.Serialize(ga, "../../SGP_SymbReg.hl");
244    }
245    [TestMethod]
246    public void RunGpSymbolicRegressionSampleTest() {
247      var ga = CreateGpSymbolicRegressionSample();
248      ga.SetSeedRandomly.Value = false;
249      RunAlgorithm(ga);
250      if (!Environment.Is64BitProcess) {
251        Assert.AreEqual(0.82895806566669916, GetDoubleResult(ga, "BestQuality"));
252        Assert.AreEqual(0.50808259256341926, GetDoubleResult(ga, "CurrentAverageQuality"));
253        Assert.AreEqual(0, GetDoubleResult(ga, "CurrentWorstQuality"));
254        Assert.AreEqual(50950, GetIntResult(ga, "EvaluatedSolutions"));
255      } else {
256        Assert.AreEqual(0.80376816256837447, GetDoubleResult(ga, "BestQuality"));
257        Assert.AreEqual(0.56912229251001056, GetDoubleResult(ga, "CurrentAverageQuality"));
258        Assert.AreEqual(0, GetDoubleResult(ga, "CurrentWorstQuality"));
259        Assert.AreEqual(50950, GetIntResult(ga, "EvaluatedSolutions"));
260      }
261    }
262
263    private GeneticAlgorithm CreateGpSymbolicRegressionSample() {
264      GeneticAlgorithm ga = new GeneticAlgorithm();
265      #region Problem Configuration
266      SymbolicRegressionSingleObjectiveProblem symbRegProblem = new SymbolicRegressionSingleObjectiveProblem();
267      symbRegProblem.Name = "Tower Symbolic Regression Problem";
268      symbRegProblem.Description = "Tower Dataset (downloaded from: http://vanillamodeling.com/realproblems.html)";
269      var towerProblemData = RegressionProblemData.ImportFromFile("towerData.txt");
270      towerProblemData.TargetVariableParameter.Value = towerProblemData.TargetVariableParameter.ValidValues
271        .First(v => v.Value == "towerResponse");
272      towerProblemData.InputVariables.SetItemCheckedState(
273        towerProblemData.InputVariables.Single(x => x.Value == "x1"), true);
274      towerProblemData.InputVariables.SetItemCheckedState(
275        towerProblemData.InputVariables.Single(x => x.Value == "x7"), false);
276      towerProblemData.InputVariables.SetItemCheckedState(
277        towerProblemData.InputVariables.Single(x => x.Value == "x11"), false);
278      towerProblemData.InputVariables.SetItemCheckedState(
279        towerProblemData.InputVariables.Single(x => x.Value == "x16"), false);
280      towerProblemData.InputVariables.SetItemCheckedState(
281        towerProblemData.InputVariables.Single(x => x.Value == "x21"), false);
282      towerProblemData.InputVariables.SetItemCheckedState(
283        towerProblemData.InputVariables.Single(x => x.Value == "x25"), false);
284      towerProblemData.InputVariables.SetItemCheckedState(
285        towerProblemData.InputVariables.Single(x => x.Value == "towerResponse"), false);
286      towerProblemData.TrainingPartition.Start = 0;
287      towerProblemData.TrainingPartition.End = 4000;
288      towerProblemData.TestPartition.Start = 4000;
289      towerProblemData.TestPartition.End = 4999;
290      towerProblemData.Name = "Data imported from towerData.txt";
291      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";
292      symbRegProblem.ProblemData = towerProblemData;
293
294      // configure grammar
295      var grammar = new TypeCoherentExpressionGrammar();
296      grammar.Symbols.OfType<Sine>().Single().InitialFrequency = 0.0;
297      grammar.Symbols.OfType<Cosine>().Single().InitialFrequency = 0.0;
298      grammar.Symbols.OfType<Tangent>().Single().InitialFrequency = 0.0;
299      grammar.Symbols.OfType<IfThenElse>().Single().InitialFrequency = 0.0;
300      grammar.Symbols.OfType<GreaterThan>().Single().InitialFrequency = 0.0;
301      grammar.Symbols.OfType<LessThan>().Single().InitialFrequency = 0.0;
302      grammar.Symbols.OfType<And>().Single().InitialFrequency = 0.0;
303      grammar.Symbols.OfType<Or>().Single().InitialFrequency = 0.0;
304      grammar.Symbols.OfType<Not>().Single().InitialFrequency = 0.0;
305      grammar.Symbols.OfType<TimeLag>().Single().InitialFrequency = 0.0;
306      grammar.Symbols.OfType<Integral>().Single().InitialFrequency = 0.0;
307      grammar.Symbols.OfType<Derivative>().Single().InitialFrequency = 0.0;
308      grammar.Symbols.OfType<LaggedVariable>().Single().InitialFrequency = 0.0;
309      grammar.Symbols.OfType<VariableCondition>().Single().InitialFrequency = 0.0;
310      var varSymbol = grammar.Symbols.OfType<Variable>().Where(x => !(x is LaggedVariable)).Single();
311      varSymbol.WeightMu = 1.0;
312      varSymbol.WeightSigma = 1.0;
313      varSymbol.WeightManipulatorMu = 0.0;
314      varSymbol.WeightManipulatorSigma = 0.05;
315      varSymbol.MultiplicativeWeightManipulatorSigma = 0.03;
316      var constSymbol = grammar.Symbols.OfType<Constant>().Single();
317      constSymbol.MaxValue = 20;
318      constSymbol.MinValue = -20;
319      constSymbol.ManipulatorMu = 0.0;
320      constSymbol.ManipulatorSigma = 1;
321      constSymbol.MultiplicativeManipulatorSigma = 0.03;
322      symbRegProblem.SymbolicExpressionTreeGrammar = grammar;
323
324      // configure remaining problem parameters
325      symbRegProblem.BestKnownQuality.Value = 0.97;
326      symbRegProblem.FitnessCalculationPartition.Start = 0;
327      symbRegProblem.FitnessCalculationPartition.End = 2800;
328      symbRegProblem.ValidationPartition.Start = 2800;
329      symbRegProblem.ValidationPartition.End = 4000;
330      symbRegProblem.RelativeNumberOfEvaluatedSamples.Value = 1;
331      symbRegProblem.MaximumSymbolicExpressionTreeLength.Value = 150;
332      symbRegProblem.MaximumSymbolicExpressionTreeDepth.Value = 12;
333      symbRegProblem.MaximumFunctionDefinitions.Value = 0;
334      symbRegProblem.MaximumFunctionArguments.Value = 0;
335
336      symbRegProblem.EvaluatorParameter.Value = new SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator();
337      #endregion
338      #region Algorithm Configuration
339      ga.Problem = symbRegProblem;
340      ga.Name = "Genetic Programming - Symbolic Regression";
341      ga.Description = "A standard genetic programming algorithm to solve a symbolic regression problem (tower dataset)";
342      ConfigureGeneticAlgorithmParameters<TournamentSelector, SubtreeCrossover, MultiSymbolicExpressionTreeManipulator>(
343        ga, 1000, 1, 50, 0.15, 5);
344      var mutator = (MultiSymbolicExpressionTreeManipulator)ga.Mutator;
345      mutator.Operators.OfType<FullTreeShaker>().Single().ShakingFactor = 0.1;
346      mutator.Operators.OfType<OnePointShaker>().Single().ShakingFactor = 1.0;
347
348      ga.Analyzer.Operators.SetItemCheckedState(
349        ga.Analyzer.Operators
350        .OfType<SymbolicRegressionSingleObjectiveOverfittingAnalyzer>()
351        .Single(), false);
352      ga.Analyzer.Operators.SetItemCheckedState(
353        ga.Analyzer.Operators
354        .OfType<SymbolicDataAnalysisAlleleFrequencyAnalyzer>()
355        .First(), false);
356      #endregion
357      return ga;
358    }
359    #endregion
360    #region Symbolic Classification
361    [TestMethod]
362    public void CreateGpSymbolicClassificationSampleTest() {
363      var ga = CreateGpSymbolicClassificationSample();
364      XmlGenerator.Serialize(ga, "../../SGP_SymbClass.hl");
365    }
366
367    [TestMethod]
368    public void RunGpSymbolicClassificationSampleTest() {
369      var ga = CreateGpSymbolicClassificationSample();
370      ga.SetSeedRandomly.Value = false;
371      RunAlgorithm(ga);
372      if (!Environment.Is64BitProcess) {
373        Assert.AreEqual(0.13607488888377872, GetDoubleResult(ga, "BestQuality"));
374        Assert.AreEqual(2.1634701155600293, GetDoubleResult(ga, "CurrentAverageQuality"));
375        Assert.AreEqual(100.62175156249987, GetDoubleResult(ga, "CurrentWorstQuality"));
376        Assert.AreEqual(100900, GetIntResult(ga, "EvaluatedSolutions"));
377      } else {
378        Assert.AreEqual(0.1343874434023121, GetDoubleResult(ga, "BestQuality"));
379        Assert.AreEqual(5.1125971846526053, GetDoubleResult(ga, "CurrentAverageQuality"));
380        Assert.AreEqual(100.62175156249987, GetDoubleResult(ga, "CurrentWorstQuality"));
381        Assert.AreEqual(100900, GetIntResult(ga, "EvaluatedSolutions"));
382      }
383    }
384
385    private GeneticAlgorithm CreateGpSymbolicClassificationSample() {
386      GeneticAlgorithm ga = new GeneticAlgorithm();
387      #region Problem Configuration
388      SymbolicClassificationSingleObjectiveProblem symbClassProblem = new SymbolicClassificationSingleObjectiveProblem();
389      symbClassProblem.Name = "Mammography Classification Problem";
390      symbClassProblem.Description = "Mammography dataset imported from the UCI machine learning repository (http://archive.ics.uci.edu/ml/datasets/Mammographic+Mass)";
391      var mammoData = ClassificationProblemData.ImportFromFile("mammographic_masses.txt");
392      mammoData.TargetVariableParameter.Value = mammoData.TargetVariableParameter.ValidValues
393        .First(v => v.Value == "Severity");
394      mammoData.InputVariables.SetItemCheckedState(
395        mammoData.InputVariables.Single(x => x.Value == "BI-RADS"), false);
396      mammoData.InputVariables.SetItemCheckedState(
397        mammoData.InputVariables.Single(x => x.Value == "Age"), true);
398      mammoData.InputVariables.SetItemCheckedState(
399        mammoData.InputVariables.Single(x => x.Value == "Shape"), true);
400      mammoData.InputVariables.SetItemCheckedState(
401        mammoData.InputVariables.Single(x => x.Value == "Margin"), true);
402      mammoData.InputVariables.SetItemCheckedState(
403        mammoData.InputVariables.Single(x => x.Value == "Density"), true);
404      mammoData.InputVariables.SetItemCheckedState(
405        mammoData.InputVariables.Single(x => x.Value == "Severity"), false);
406      mammoData.TrainingPartition.Start = 0;
407      mammoData.TrainingPartition.End = 800;
408      mammoData.TestPartition.Start = 800;
409      mammoData.TestPartition.End = 961;
410      mammoData.Name = "Data imported from mammographic_masses.csv";
411      mammoData.Description = "Original dataset: http://archive.ics.uci.edu/ml/datasets/Mammographic+Mass, missing values have been replaced with median values.";
412      symbClassProblem.ProblemData = mammoData;
413
414      // configure grammar
415      var grammar = new TypeCoherentExpressionGrammar();
416      grammar.Symbols.OfType<Sine>().Single().InitialFrequency = 0.0;
417      grammar.Symbols.OfType<Cosine>().Single().InitialFrequency = 0.0;
418      grammar.Symbols.OfType<Tangent>().Single().InitialFrequency = 0.0;
419      grammar.Symbols.OfType<Power>().Single().InitialFrequency = 0.0;
420      grammar.Symbols.OfType<Root>().Single().InitialFrequency = 0.0;
421      grammar.Symbols.OfType<TimeLag>().Single().InitialFrequency = 0.0;
422      grammar.Symbols.OfType<Integral>().Single().InitialFrequency = 0.0;
423      grammar.Symbols.OfType<Derivative>().Single().InitialFrequency = 0.0;
424      grammar.Symbols.OfType<LaggedVariable>().Single().InitialFrequency = 0.0;
425      grammar.Symbols.OfType<VariableCondition>().Single().InitialFrequency = 0.0;
426      var varSymbol = grammar.Symbols.OfType<Variable>().Where(x => !(x is LaggedVariable)).Single();
427      varSymbol.WeightMu = 1.0;
428      varSymbol.WeightSigma = 1.0;
429      varSymbol.WeightManipulatorMu = 0.0;
430      varSymbol.WeightManipulatorSigma = 0.05;
431      varSymbol.MultiplicativeWeightManipulatorSigma = 0.03;
432      var constSymbol = grammar.Symbols.OfType<Constant>().Single();
433      constSymbol.MaxValue = 20;
434      constSymbol.MinValue = -20;
435      constSymbol.ManipulatorMu = 0.0;
436      constSymbol.ManipulatorSigma = 1;
437      constSymbol.MultiplicativeManipulatorSigma = 0.03;
438      symbClassProblem.SymbolicExpressionTreeGrammar = grammar;
439
440      // configure remaining problem parameters
441      symbClassProblem.BestKnownQuality.Value = 0.0;
442      symbClassProblem.FitnessCalculationPartition.Start = 0;
443      symbClassProblem.FitnessCalculationPartition.End = 400;
444      symbClassProblem.ValidationPartition.Start = 400;
445      symbClassProblem.ValidationPartition.End = 800;
446      symbClassProblem.RelativeNumberOfEvaluatedSamples.Value = 1;
447      symbClassProblem.MaximumSymbolicExpressionTreeLength.Value = 100;
448      symbClassProblem.MaximumSymbolicExpressionTreeDepth.Value = 10;
449      symbClassProblem.MaximumFunctionDefinitions.Value = 0;
450      symbClassProblem.MaximumFunctionArguments.Value = 0;
451      symbClassProblem.EvaluatorParameter.Value = new SymbolicClassificationSingleObjectiveMeanSquaredErrorEvaluator();
452      #endregion
453      #region Algorithm Configuration
454      ga.Problem = symbClassProblem;
455      ga.Name = "Genetic Programming - Symbolic Classification";
456      ga.Description = "A standard genetic programming algorithm to solve a classification problem (Mammographic+Mass dataset)";
457      ConfigureGeneticAlgorithmParameters<TournamentSelector, SubtreeCrossover, MultiSymbolicExpressionTreeManipulator>(
458        ga, 1000, 1, 100, 0.15, 5
459        );
460
461      var mutator = (MultiSymbolicExpressionTreeManipulator)ga.Mutator;
462      mutator.Operators.OfType<FullTreeShaker>().Single().ShakingFactor = 0.1;
463      mutator.Operators.OfType<OnePointShaker>().Single().ShakingFactor = 1.0;
464
465      ga.Analyzer.Operators.SetItemCheckedState(
466        ga.Analyzer.Operators
467        .OfType<SymbolicClassificationSingleObjectiveOverfittingAnalyzer>()
468        .Single(), false);
469      ga.Analyzer.Operators.SetItemCheckedState(
470        ga.Analyzer.Operators
471        .OfType<SymbolicDataAnalysisAlleleFrequencyAnalyzer>()
472        .First(), false);
473      #endregion
474      return ga;
475    }
476    #endregion
477    #endregion
478
479    #region ES
480    #region Griewank
481    [TestMethod]
482    public void CreateEsGriewankSampleTest() {
483      var es = CreateEsGriewankSample();
484      XmlGenerator.Serialize(es, "../../ES_Griewank.hl");
485    }
486    [TestMethod]
487    public void RunEsGriewankSampleTest() {
488      var es = CreateEsGriewankSample();
489      es.SetSeedRandomly.Value = false;
490      RunAlgorithm(es);
491      Assert.AreEqual(0, GetDoubleResult(es, "BestQuality"));
492      Assert.AreEqual(0, GetDoubleResult(es, "CurrentAverageQuality"));
493      Assert.AreEqual(0, GetDoubleResult(es, "CurrentWorstQuality"));
494      Assert.AreEqual(100020, GetIntResult(es, "EvaluatedSolutions"));
495    }
496
497    private EvolutionStrategy CreateEsGriewankSample() {
498      EvolutionStrategy es = new EvolutionStrategy();
499      #region Problem Configuration
500      SingleObjectiveTestFunctionProblem problem = new SingleObjectiveTestFunctionProblem();
501
502      problem.ProblemSize.Value = 10;
503      problem.Evaluator = new GriewankEvaluator();
504      problem.SolutionCreator = new UniformRandomRealVectorCreator();
505      problem.Maximization.Value = false;
506      problem.Bounds = new DoubleMatrix(new double[,] { { -600, 600 } });
507      problem.BestKnownQuality.Value = 0;
508      problem.BestKnownSolutionParameter.Value = new RealVector(10);
509      problem.Name = "Single Objective Test Function";
510      problem.Description = "Test function with real valued inputs and a single objective.";
511      #endregion
512      #region Algorithm Configuration
513      es.Name = "Evolution Strategy - Griewank";
514      es.Description = "An evolution strategy which solves the 10-dimensional Griewank test function";
515      es.Problem = problem;
516      ConfigureEvolutionStrategyParameters<AverageCrossover, NormalAllPositionsManipulator,
517        StdDevStrategyVectorCreator, StdDevStrategyVectorCrossover, StdDevStrategyVectorManipulator>(
518        es, 20, 500, 2, 200, false);
519
520      StdDevStrategyVectorCreator strategyCreator = (StdDevStrategyVectorCreator)es.StrategyParameterCreator;
521      strategyCreator.BoundsParameter.Value = new DoubleMatrix(new double[,] { { 1, 20 } });
522
523      StdDevStrategyVectorManipulator strategyManipulator = (StdDevStrategyVectorManipulator)es.StrategyParameterManipulator;
524      strategyManipulator.BoundsParameter.Value = new DoubleMatrix(new double[,] { { 1E-12, 30 } });
525      strategyManipulator.GeneralLearningRateParameter.Value = new DoubleValue(0.22360679774997896);
526      strategyManipulator.LearningRateParameter.Value = new DoubleValue(0.39763536438352531);
527      #endregion
528      return es;
529    }
530    #endregion
531    #endregion
532
533    #region Island GA
534    #region TSP
535    [TestMethod]
536    public void CreateIslandGaTspSampleTest() {
537      var ga = CreateIslandGaTspSample();
538      XmlGenerator.Serialize(ga, "../../IslandGA_TSP.hl");
539    }
540    [TestMethod]
541    public void RunIslandGaTspSampleTest() {
542      var ga = CreateIslandGaTspSample();
543      ga.SetSeedRandomly.Value = false;
544      RunAlgorithm(ga);
545      Assert.AreEqual(10469, GetDoubleResult(ga, "BestQuality"));
546      Assert.AreEqual(11184.87, GetDoubleResult(ga, "CurrentAverageQuality"));
547      Assert.AreEqual(13420, GetDoubleResult(ga, "CurrentWorstQuality"));
548      Assert.AreEqual(495500, GetIntResult(ga, "EvaluatedSolutions"));
549    }
550
551    private IslandGeneticAlgorithm CreateIslandGaTspSample() {
552      IslandGeneticAlgorithm ga = new IslandGeneticAlgorithm();
553      #region Problem Configuration
554      TravelingSalesmanProblem tspProblem = new TravelingSalesmanProblem();
555      tspProblem.ImportFromTSPLIB("ch130.tsp", "ch130.opt.tour", 6110);
556      tspProblem.Evaluator = new TSPRoundedEuclideanPathEvaluator();
557      tspProblem.SolutionCreator = new RandomPermutationCreator();
558      tspProblem.UseDistanceMatrix.Value = true;
559      tspProblem.Name = "ch130 TSP (imported from TSPLIB)";
560      tspProblem.Description = "130 city problem (Churritz)";
561      #endregion
562      #region Algorithm Configuration
563      ga.Name = "Island Genetic Algorithm - TSP";
564      ga.Description = "An island genetic algorithm which solves the \"ch130\" traveling salesman problem (imported from TSPLIB)";
565      ga.Problem = tspProblem;
566      ConfigureIslandGeneticAlgorithmParameters<ProportionalSelector, OrderCrossover2, InversionManipulator,
567        UnidirectionalRingMigrator, BestSelector, WorstReplacer>(
568        ga, 100, 1, 1000, 0.05, 5, 50, 0.25);
569
570      ga.Analyzer.Operators.SetItemCheckedState(ga.Analyzer.Operators
571        .OfType<TSPAlleleFrequencyAnalyzer>()
572        .Single(), false);
573      ga.Analyzer.Operators.SetItemCheckedState(ga.Analyzer.Operators
574        .OfType<TSPPopulationDiversityAnalyzer>()
575        .Single(), false);
576      #endregion
577      return ga;
578    }
579    #endregion
580    #endregion
581
582    #region LS
583    #region Knapsack
584    [TestMethod]
585    public void CreateLocalSearchKnapsackSampleTest() {
586      var ls = CreateLocalSearchKnapsackSample();
587      XmlGenerator.Serialize(ls, "../../LS_Knapsack.hl");
588    }
589    [TestMethod]
590    public void RunLocalSearchKnapsackSampleTest() {
591      var ls = CreateLocalSearchKnapsackSample();
592      ls.SetSeedRandomly.Value = false;
593      RunAlgorithm(ls);
594      Assert.AreEqual(345, GetDoubleResult(ls, "BestQuality"));
595      Assert.AreEqual(340.70731707317071, GetDoubleResult(ls, "CurrentAverageQuality"));
596      Assert.AreEqual(337, GetDoubleResult(ls, "CurrentWorstQuality"));
597      Assert.AreEqual(82000, GetIntResult(ls, "EvaluatedMoves"));
598    }
599
600    private LocalSearch CreateLocalSearchKnapsackSample() {
601      LocalSearch ls = new LocalSearch();
602      #region Problem Configuration
603      KnapsackProblem problem = new KnapsackProblem();
604      problem.BestKnownQuality = new DoubleValue(362);
605      problem.BestKnownSolution = new HeuristicLab.Encodings.BinaryVectorEncoding.BinaryVector(new bool[] {
606       true , false, false, true , true , true , true , true , false, true , true , true , true , true , true , false, true , false, true , true , false, true , true , false, true , false, true , true , true , false, true , true , false, true , true , false, true , false, true , true , true , true , true , true , true , true , true , true , true , true , true , false, true , false, false, true , true , false, true , true , true , true , true , true , true , true , false, true , false, true , true , true , true , false, true , true , true , true , true , true , true , true});
607      problem.Evaluator = new KnapsackEvaluator();
608      problem.SolutionCreator = new RandomBinaryVectorCreator();
609      problem.KnapsackCapacity.Value = 297;
610      problem.Maximization.Value = true;
611      problem.Penalty.Value = 1;
612      problem.Values = new IntArray(new int[] {
613  6, 1, 1, 6, 7, 8, 7, 4, 2, 5, 2, 6, 7, 8, 7, 1, 7, 1, 9, 4, 2, 6, 5,  3, 5, 3, 3, 6, 5, 2, 4, 9, 4, 5, 7, 1, 4, 3, 5, 5, 8, 3, 6, 7, 3, 9, 7, 7, 5, 5, 7, 1, 4, 4, 3, 9, 5, 1, 6, 2, 2, 6, 1, 6, 5, 4, 4, 7, 1,  8, 9, 9, 7, 4, 3, 8, 7, 5, 7, 4, 4, 5});
614      problem.Weights = new IntArray(new int[] {
615 1, 9, 3, 6, 5, 3, 8, 1, 7, 4, 2, 1, 2, 7, 9, 9, 8, 4, 9, 2, 4, 8, 3, 7, 5, 7, 5, 5, 1, 9, 8, 7, 8, 9, 1, 3, 3, 8, 8, 5, 1, 2, 4, 3, 6, 9, 4, 4, 9, 7, 4, 5, 1, 9, 7, 6, 7, 4, 7, 1, 2, 1, 2, 9, 8, 6, 8, 4, 7, 6, 7, 5, 3, 9, 4, 7, 4, 6, 1, 2, 5, 4});
616      problem.Name = "Knapsack Problem";
617      problem.Description = "Represents a Knapsack problem.";
618      #endregion
619      #region Algorithm Configuration
620      ls.Name = "Local Search - Knapsack";
621      ls.Description = "A local search algorithm that solves a randomly generated Knapsack problem";
622      ls.Problem = problem;
623      ls.MaximumIterations.Value = 1000;
624      ls.MoveEvaluator = ls.MoveEvaluatorParameter.ValidValues
625        .OfType<KnapsackOneBitflipMoveEvaluator>()
626        .Single();
627      ls.MoveGenerator = ls.MoveGeneratorParameter.ValidValues
628        .OfType<ExhaustiveOneBitflipMoveGenerator>()
629        .Single();
630      ls.MoveMaker = ls.MoveMakerParameter.ValidValues
631        .OfType<OneBitflipMoveMaker>()
632        .Single();
633      ls.SampleSize.Value = 100;
634      ls.Seed.Value = 0;
635      ls.SetSeedRandomly.Value = true;
636      #endregion
637      ls.Engine = new ParallelEngine();
638      return ls;
639    }
640    #endregion
641    #endregion
642
643    #region PSO
644    #region Schwefel
645    [TestMethod]
646    public void CreatePsoSchwefelSampleTest() {
647      var pso = CreatePsoSchwefelSample();
648      XmlGenerator.Serialize(pso, "../../PSO_Schwefel.hl");
649    }
650    [TestMethod]
651    public void RunPsoSchwefelSampleTest() {
652      var pso = CreatePsoSchwefelSample();
653      pso.SetSeedRandomly.Value = false;
654      RunAlgorithm(pso);
655      if (!Environment.Is64BitProcess) {
656        Assert.AreEqual(119.30888659302838, GetDoubleResult(pso, "BestQuality"));
657        Assert.AreEqual(140.71570105946438, GetDoubleResult(pso, "CurrentAverageQuality"));
658        Assert.AreEqual(220.956806502853, GetDoubleResult(pso, "CurrentWorstQuality"));
659        Assert.AreEqual(1000, GetIntResult(pso, "Iterations"));
660      } else {
661        Assert.AreEqual(118.58396881972624, GetDoubleResult(pso, "BestQuality"));
662        Assert.AreEqual(139.43946864779372, GetDoubleResult(pso, "CurrentAverageQuality"));
663        Assert.AreEqual(217.14654589055152, GetDoubleResult(pso, "CurrentWorstQuality"));
664        Assert.AreEqual(1000, GetIntResult(pso, "Iterations"));
665      }
666    }
667    private ParticleSwarmOptimization CreatePsoSchwefelSample() {
668      ParticleSwarmOptimization pso = new ParticleSwarmOptimization();
669      #region Problem Configuration
670      var problem = new SingleObjectiveTestFunctionProblem();
671      problem.BestKnownQuality.Value = 0.0;
672      problem.BestKnownSolutionParameter.Value = new RealVector(new double[] { 420.968746, 420.968746 });
673      problem.Bounds = new DoubleMatrix(new double[,] { { -500, 500 } });
674      problem.Evaluator = new SchwefelEvaluator();
675      problem.Maximization.Value = false;
676      problem.ProblemSize.Value = 2;
677      problem.SolutionCreator = new UniformRandomRealVectorCreator();
678      #endregion
679      #region Algorithm Configuration
680      pso.Name = "Particle Swarm Optimization - Schwefel";
681      pso.Description = "A particle swarm optimization algorithm which solves the 2-dimensional Schwefel test function (based on the description in Pedersen, M.E.H. (2010). PhD thesis. University of Southampton)";
682      pso.Problem = problem;
683      pso.Inertia.Value = 10;
684      pso.MaxIterations.Value = 1000;
685      pso.NeighborBestAttraction.Value = 0.5;
686      pso.PersonalBestAttraction.Value = -0.01;
687      pso.SwarmSize.Value = 50;
688
689      var inertiaUpdater = pso.InertiaUpdaterParameter.ValidValues
690        .OfType<ExponentialDiscreteDoubleValueModifier>()
691        .Single();
692      inertiaUpdater.StartValueParameter.Value = new DoubleValue(10);
693      inertiaUpdater.EndValueParameter.Value = new DoubleValue(1);
694      pso.InertiaUpdater = inertiaUpdater;
695
696      pso.ParticleCreator = pso.ParticleCreatorParameter.ValidValues
697        .OfType<RealVectorParticleCreator>()
698        .Single();
699      var swarmUpdater = pso.SwarmUpdaterParameter.ValidValues
700        .OfType<RealVectorSwarmUpdater>()
701        .Single();
702      swarmUpdater.VelocityBoundsIndexParameter.ActualName = "Iterations";
703      swarmUpdater.VelocityBoundsParameter.Value = new DoubleMatrix(new double[,] { { -10, 10 } });
704      swarmUpdater.VelocityBoundsStartValueParameter.Value = new DoubleValue(10.0);
705      swarmUpdater.VelocityBoundsEndValueParameter.Value = new DoubleValue(1.0);
706      swarmUpdater.VelocityBoundsScalingOperatorParameter.Value = swarmUpdater.VelocityBoundsScalingOperatorParameter.ValidValues
707        .OfType<ExponentialDiscreteDoubleValueModifier>()
708        .Single();
709
710      pso.TopologyInitializer = null;
711      pso.TopologyUpdater = null;
712      pso.SwarmUpdater = swarmUpdater;
713      pso.Seed.Value = 0;
714      pso.SetSeedRandomly.Value = true;
715      #endregion
716      pso.Engine = new ParallelEngine();
717      return pso;
718    }
719    #endregion
720    #endregion
721
722    #region SA
723    #region Rastrigin
724    [TestMethod]
725    public void CreateSimulatedAnnealingRastriginSampleTest() {
726      var sa = CreateSimulatedAnnealingRastriginSample();
727      XmlGenerator.Serialize(sa, "../../SA_Rastrigin.hl");
728    }
729    [TestMethod]
730    public void RunSimulatedAnnealingRastriginSampleTest() {
731      var sa = CreateSimulatedAnnealingRastriginSample();
732      sa.SetSeedRandomly.Value = false;
733      RunAlgorithm(sa);
734      Assert.AreEqual(0.00014039606034543795, GetDoubleResult(sa, "BestQuality"));
735      Assert.AreEqual(5000, GetIntResult(sa, "EvaluatedMoves"));
736    }
737    private SimulatedAnnealing CreateSimulatedAnnealingRastriginSample() {
738      SimulatedAnnealing sa = new SimulatedAnnealing();
739      #region Problem Configuration
740      var problem = new SingleObjectiveTestFunctionProblem();
741      problem.BestKnownQuality.Value = 0.0;
742      problem.BestKnownSolutionParameter.Value = new RealVector(new double[] { 0, 0 });
743      problem.Bounds = new DoubleMatrix(new double[,] { { -5.12, 5.12 } });
744      problem.Evaluator = new RastriginEvaluator();
745      problem.Maximization.Value = false;
746      problem.ProblemSize.Value = 2;
747      problem.SolutionCreator = new UniformRandomRealVectorCreator();
748      #endregion
749      #region Algorithm Configuration
750      sa.Name = "Simulated Annealing - Rastrigin";
751      sa.Description = "A simulated annealing algorithm that solves the 2-dimensional Rastrigin test function";
752      sa.Problem = problem;
753      var annealingOperator = sa.AnnealingOperatorParameter.ValidValues
754        .OfType<ExponentialDiscreteDoubleValueModifier>()
755        .Single();
756      annealingOperator.StartIndexParameter.Value = new IntValue(0);
757      sa.AnnealingOperator = annealingOperator;
758
759      sa.EndTemperature.Value = 1E-6;
760      sa.InnerIterations.Value = 50;
761      sa.MaximumIterations.Value = 100;
762      var moveEvaluator = sa.MoveEvaluatorParameter.ValidValues
763        .OfType<RastriginAdditiveMoveEvaluator>()
764        .Single();
765      moveEvaluator.A.Value = 10;
766      sa.MoveEvaluator = moveEvaluator;
767
768      var moveGenerator = sa.MoveGeneratorParameter.ValidValues
769        .OfType<StochasticNormalMultiMoveGenerator>()
770        .Single();
771      moveGenerator.SigmaParameter.Value = new DoubleValue(1);
772      sa.MoveGenerator = moveGenerator;
773
774      sa.MoveMaker = sa.MoveMakerParameter.ValidValues
775        .OfType<AdditiveMoveMaker>()
776        .Single();
777
778      sa.Seed.Value = 0;
779      sa.SetSeedRandomly.Value = true;
780      sa.StartTemperature.Value = 1;
781      #endregion
782      sa.Engine = new ParallelEngine();
783      return sa;
784    }
785    #endregion
786    #endregion
787
788    #region TS
789    #region TSP
790    [TestMethod]
791    public void CreateTabuSearchTspSampleTest() {
792      var ts = CreateTabuSearchTspSample();
793      XmlGenerator.Serialize(ts, "../../TS_TSP.hl");
794    }
795    [TestMethod]
796    public void RunTabuSearchTspSampleTest() {
797      var ts = CreateTabuSearchTspSample();
798      ts.SetSeedRandomly.Value = false;
799      RunAlgorithm(ts);
800      Assert.AreEqual(6441, GetDoubleResult(ts, "BestQuality"));
801      Assert.AreEqual(7401.666666666667, GetDoubleResult(ts, "CurrentAverageQuality"));
802      Assert.AreEqual(8418, GetDoubleResult(ts, "CurrentWorstQuality"));
803      Assert.AreEqual(750000, GetIntResult(ts, "EvaluatedMoves"));
804    }
805
806    private TabuSearch CreateTabuSearchTspSample() {
807      TabuSearch ts = new TabuSearch();
808      #region Problem Configuration
809      var tspProblem = new TravelingSalesmanProblem();
810      tspProblem.ImportFromTSPLIB("ch130.tsp", "ch130.opt.tour", 6110);
811      tspProblem.Evaluator = new TSPRoundedEuclideanPathEvaluator();
812      tspProblem.SolutionCreator = new RandomPermutationCreator();
813      tspProblem.UseDistanceMatrix.Value = true;
814      tspProblem.Name = "ch130 TSP (imported from TSPLIB)";
815      tspProblem.Description = "130 city problem (Churritz)";
816      #endregion
817      #region Algorithm Configuration
818      ts.Name = "Tabu Search - TSP";
819      ts.Description = "A tabu search algorithm that solves the \"ch130\" TSP (imported from TSPLIB)";
820      ts.Problem = tspProblem;
821
822      ts.MaximumIterations.Value = 1000;
823      // move generator has to be set first
824      var moveGenerator = ts.MoveGeneratorParameter.ValidValues
825        .OfType<StochasticInversionMultiMoveGenerator>()
826        .Single();
827      ts.MoveGenerator = moveGenerator;
828      var moveEvaluator = ts.MoveEvaluatorParameter.ValidValues
829        .OfType<TSPInversionMoveRoundedEuclideanPathEvaluator>()
830        .Single();
831      ts.MoveEvaluator = moveEvaluator;
832      var moveMaker = ts.MoveMakerParameter.ValidValues
833        .OfType<InversionMoveMaker>()
834        .Single();
835      ts.MoveMaker = moveMaker;
836      ts.SampleSize.Value = 750;
837      ts.Seed.Value = 0;
838      ts.SetSeedRandomly.Value = true;
839
840      var tabuChecker = ts.TabuCheckerParameter.ValidValues
841        .OfType<InversionMoveSoftTabuCriterion>()
842        .Single();
843      tabuChecker.UseAspirationCriterion.Value = true;
844      ts.TabuChecker = tabuChecker;
845
846      var tabuMaker = ts.TabuMakerParameter.ValidValues
847        .OfType<InversionMoveTabuMaker>()
848        .Single();
849      ts.TabuMaker = tabuMaker;
850      ts.TabuTenure.Value = 60;
851
852      ts.Analyzer.Operators.SetItemCheckedState(ts.Analyzer.Operators
853        .OfType<TSPAlleleFrequencyAnalyzer>()
854        .Single(), false);
855      ts.Analyzer.Operators.SetItemCheckedState(ts.Analyzer.Operators
856        .OfType<TSPPopulationDiversityAnalyzer>()
857        .Single(), false);
858      #endregion
859      ts.Engine = new ParallelEngine();
860      return ts;
861    }
862    #endregion
863    #endregion
864
865    #region VNS
866    #region TSP
867    [TestMethod]
868    public void CreateVnsTspSampleTest() {
869      var vns = CreateVnsTspSample();
870      XmlGenerator.Serialize(vns, "../../VNS_TSP.hl");
871    }
872    [TestMethod]
873    public void RunVnsTspSampleTest() {
874      var vns = CreateVnsTspSample();
875      vns.SetSeedRandomly = false;
876      RunAlgorithm(vns);
877      Assert.AreEqual(867, GetDoubleResult(vns, "BestQuality"));
878      Assert.AreEqual(867, GetDoubleResult(vns, "CurrentAverageQuality"));
879      Assert.AreEqual(867, GetDoubleResult(vns, "CurrentWorstQuality"));
880      Assert.AreEqual(12975173, GetIntResult(vns, "EvaluatedSolutions"));
881    }
882
883    private VariableNeighborhoodSearch CreateVnsTspSample() {
884      VariableNeighborhoodSearch vns = new VariableNeighborhoodSearch();
885      #region Problem Configuration
886      TravelingSalesmanProblem tspProblem = new TravelingSalesmanProblem();
887      tspProblem.BestKnownSolution = new Permutation(PermutationTypes.Absolute, new int[] {
888117, 65, 73, 74, 75, 76, 82, 86, 87, 94, 100, 106, 115, 120, 124, 107, 101, 108, 109, 102, 97, 90, 96, 95, 88, 89, 84, 78, 69, 57, 68, 56, 44, 55, 45, 36, 46, 37, 38, 47, 48, 59, 49, 58, 70, 77, 83, 79, 50, 80, 85, 98, 103, 110, 116, 121, 125, 133, 132, 138, 139, 146, 147, 159, 168, 169, 175, 182, 188, 201, 213, 189, 214, 221, 230, 246, 262, 276, 284, 275, 274, 261, 245, 229, 220, 228, 243, 259, 273, 282, 272, 258, 242, 257, 293, 292, 302, 310, 319, 320, 327, 326, 333, 340, 346, 339, 345, 344, 337, 338, 332, 325, 318, 309, 301, 291, 271, 251, 270, 233, 250, 269, 268, 280, 290, 300, 415, 440, 416, 417, 441, 458, 479, 418, 419, 395, 420, 442, 421, 396, 397, 422, 423, 461, 481, 502, 460, 501, 459, 480, 500, 517, 531, 516, 530, 499, 478, 457, 439, 414, 413, 412, 438, 456, 477, 498, 515, 529, 538, 547, 558, 559, 560, 548, 539, 549, 561, 562, 551, 550, 532, 540, 533, 541, 518, 534, 542, 552, 553, 554, 555, 535, 543, 556, 544, 536, 522, 505, 521, 520, 504, 519, 503, 482, 462, 463, 464, 483, 443, 465, 484, 506, 485, 507, 508, 487, 467, 486, 466, 445, 428, 444, 424, 425, 426, 427, 398, 399, 400, 381, 382, 371, 372, 401, 429, 446, 430, 402, 383, 366, 356, 357, 352, 385, 384, 403, 431, 447, 469, 468, 488, 489, 490, 470, 471, 448, 432, 433, 404, 405, 386, 373, 374, 367, 376, 375, 387, 491, 509, 537, 510, 492, 472, 449, 388, 389, 406, 450, 407, 377, 368, 359, 354, 350, 335, 324, 330, 390, 434, 451, 473, 493, 511, 523, 545, 563, 565, 567, 570, 569, 578, 577, 576, 575, 574, 573, 572, 580, 584, 583, 582, 587, 586, 585, 581, 579, 571, 568, 566, 564, 557, 546, 527, 513, 526, 525, 524, 512, 495, 494, 474, 452, 436, 409, 435, 453, 475, 496, 514, 528, 497, 455, 476, 454, 437, 411, 410, 394, 393, 392, 380, 370, 379, 408, 391, 378, 369, 364, 365, 361, 355, 351, 343, 336, 331, 317, 299, 286, 287, 278, 263, 264, 265, 223, 202, 248, 266, 279, 288, 289, 281, 267, 249, 232, 224, 216, 215, 204, 192, 193, 194, 186, 179, 185, 203, 191, 190, 177, 171, 161, 128, 135, 140, 149, 162, 150, 163, 172, 178, 173, 164, 152, 151, 141, 153, 165, 154, 142, 155, 143, 137, 136, 130, 129, 118, 114, 113, 105, 119, 123, 131, 144, 156, 157, 145, 158, 166, 167, 174, 180, 181, 187, 195, 205, 217, 226, 236, 225, 234, 252, 235, 253, 254, 255, 238, 239, 240, 241, 256, 237, 206, 207, 208, 196, 197, 198, 209, 199, 200, 211, 212, 219, 210, 218, 227, 244, 260, 283, 294, 295, 303, 296, 311, 304, 297, 298, 305, 285, 306, 314, 329, 321, 313, 312, 328, 334, 341, 347, 348, 353, 358, 362, 363, 360, 349, 342, 322, 323, 315, 316, 308, 307, 277, 247, 231, 222, 184, 183, 176, 170, 160, 148, 134, 127, 126, 111, 104, 92, 91, 71, 60, 51, 52, 40, 32, 23, 21, 20, 18, 17, 16, 14, 13, 11, 10, 7, 6, 5, 2, 1, 0, 3, 4, 31, 39, 25, 30, 35, 34, 33, 43, 54, 42, 27, 28, 29, 9, 8, 12, 15, 19, 22, 24, 26, 41, 67, 66, 64, 63, 53, 62, 61, 72, 81, 93, 99, 112, 122,
889      });
890      tspProblem.Coordinates = new DoubleMatrix(new double[,] {
891{48, 71}, {49, 71}, {50, 71}, {44, 70}, {45, 70}, {52, 70}, {53, 70}, {54, 70}, {41, 69}, {42, 69}, {55, 69}, {56, 69}, {40, 68}, {56, 68}, {57, 68}, {39, 67}, {57, 67}, {58, 67}, {59, 67}, {38, 66}, {59, 66}, {60, 66}, {37, 65}, {60, 65}, {36, 64}, {43, 64}, {35, 63}, {37, 63}, {41, 63}, {42, 63}, {43, 63}, {47, 63}, {61, 63}, {40, 62}, {41, 62}, {42, 62}, {43, 62}, {45, 62}, {46, 62}, {47, 62}, {62, 62}, {34, 61}, {38, 61}, {39, 61}, {42, 61}, {43, 61}, {44, 61}, {45, 61}, {46, 61}, {47, 61}, {52, 61}, {62, 61}, {63, 61}, {26, 60}, {38, 60}, {42, 60}, {43, 60}, {44, 60}, {46, 60}, {47, 60}, {63, 60}, {23, 59}, {24, 59}, {27, 59}, {29, 59}, {30, 59}, {31, 59}, {33, 59}, {42, 59}, {46, 59}, {47, 59}, {63, 59}, {21, 58}, {32, 58}, {33, 58}, {34, 58}, {35, 58}, {46, 58}, {47, 58}, {48, 58}, {53, 58}, {21, 57}, {35, 57}, {47, 57}, {48, 57}, {53, 57}, {36, 56}, {37, 56}, {46, 56}, {47, 56}, {48, 56}, {64, 56}, {65, 56}, {20, 55}, {38, 55}, {46, 55}, {47, 55}, {48, 55}, {52, 55}, {21, 54}, {40, 54}, {47, 54}, {48, 54}, {52, 54}, {65, 54}, {30, 53}, {41, 53}, {46, 53}, {47, 53}, {48, 53}, {52, 53}, {65, 53}, {21, 52}, {32, 52}, {33, 52}, {42, 52}, {51, 52}, {21, 51}, {33, 51}, {34, 51}, {43, 51}, {51, 51}, {21, 50}, {35, 50}, {44, 50}, {50, 50}, {66, 50}, {67, 50}, {21, 49}, {34, 49}, {36, 49}, {37, 49}, {46, 49}, {49, 49}, {67, 49}, {22, 48}, {36, 48}, {37, 48}, {46, 48}, {47, 48}, {22, 47}, {30, 47}, {34, 47}, {37, 47}, {38, 47}, {39, 47}, {47, 47}, {48, 47}, {67, 47}, {23, 46}, {28, 46}, {29, 46}, {30, 46}, {31, 46}, {32, 46}, {35, 46}, {37, 46}, {38, 46}, {39, 46}, {49, 46}, {67, 46}, {23, 45}, {28, 45}, {29, 45}, {31, 45}, {32, 45}, {40, 45}, {41, 45}, {49, 45}, {50, 45}, {68, 45}, {24, 44}, {29, 44}, {32, 44}, {41, 44}, {51, 44}, {68, 44}, {25, 43}, {30, 43}, {32, 43}, {42, 43}, {43, 43}, {51, 43}, {68, 43}, {69, 43}, {31, 42}, {32, 42}, {43, 42}, {52, 42}, {55, 42}, {26, 41}, {27, 41}, {31, 41}, {32, 41}, {33, 41}, {44, 41}, {45, 41}, {46, 41}, {47, 41}, {48, 41}, {49, 41}, {53, 41}, {25, 40}, {27, 40}, {32, 40}, {43, 40}, {44, 40}, {45, 40}, {46, 40}, {48, 40}, {49, 40}, {50, 40}, {51, 40}, {53, 40}, {56, 40}, {32, 39}, {33, 39}, {43, 39}, {50, 39}, {51, 39}, {54, 39}, {56, 39}, {69, 39}, {24, 38}, {32, 38}, {41, 38}, {42, 38}, {51, 38}, {52, 38}, {54, 38}, {57, 38}, {69, 38}, {31, 37}, {32, 37}, {40, 37}, {41, 37}, {42, 37}, {43, 37}, {44, 37}, {45, 37}, {46, 37}, {47, 37}, {48, 37}, {51, 37}, {52, 37}, {55, 37}, {57, 37}, {69, 37}, {24, 36}, {31, 36}, {32, 36}, {39, 36}, {40, 36}, {41, 36}, {42, 36}, {43, 36}, {45, 36}, {48, 36}, {49, 36}, {51, 36}, {53, 36}, {55, 36}, {58, 36}, {22, 35}, {23, 35}, {24, 35}, {25, 35}, {30, 35}, {31, 35}, {32, 35}, {39, 35}, {41, 35}, {49, 35}, {51, 35}, {55, 35}, {56, 35}, {58, 35}, {71, 35}, {20, 34}, {27, 34}, {30, 34}, {31, 34}, {51, 34}, {53, 34}, {57, 34}, {60, 34}, {18, 33}, {19, 33}, {29, 33}, {30, 33}, {31, 33}, {45, 33}, {46, 33}, {47, 33}, {52, 33}, {53, 33}, {55, 33}, {57, 33}, {58, 33}, {17, 32}, {30, 32}, {44, 32}, {47, 32}, {54, 32}, {57, 32}, {59, 32}, {61, 32}, {71, 32}, {72, 32}, {43, 31}, {47, 31}, {56, 31}, {58, 31}, {59, 31}, {61, 31}, {72, 31}, {74, 31}, {16, 30}, {43, 30}, {46, 30}, {47, 30}, {59, 30}, {63, 30}, {71, 30}, {75, 30}, {43, 29}, {46, 29}, {47, 29}, {59, 29}, {60, 29}, {75, 29}, {15, 28}, {43, 28}, {46, 28}, {61, 28}, {76, 28}, {15, 27}, {43, 27}, {44, 27}, {45, 27}, {46, 27}, {60, 27}, {62, 27}, {15, 26}, {43, 26}, {44, 26}, {46, 26}, {59, 26}, {60, 26}, {64, 26}, {77, 26}, {15, 25}, {58, 25}, {61, 25}, {77, 25}, {15, 24}, {53, 24}, {55, 24}, {61, 24}, {77, 24}, {62, 23}, {16, 22}, {61, 22}, {62, 22}, {15, 21}, {16, 21}, {52, 21}, {63, 21}, {77, 21}, {16, 20}, {17, 20}, {46, 20}, {47, 20}, {60, 20}, {62, 20}, {63, 20}, {65, 20}, {76, 20}, {15, 19}, {17, 19}, {18, 19}, {44, 19}, {45, 19}, {48, 19}, {53, 19}, {56, 19}, {60, 19}, {62, 19}, {67, 19}, {68, 19}, {76, 19}, {15, 18}, {18, 18}, {19, 18}, {20, 18}, {32, 18}, {33, 18}, {34, 18}, {41, 18}, {42, 18}, {43, 18}, {46, 18}, {48, 18}, {53, 18}, {59, 18}, {60, 18}, {69, 18}, {75, 18}, {16, 17}, {17, 17}, {20, 17}, {21, 17}, {22, 17}, {23, 17}, {24, 17}, {26, 17}, {28, 17}, {29, 17}, {30, 17}, {31, 17}, {32, 17}, {34, 17}, {35, 17}, {36, 17}, {37, 17}, {38, 17}, {39, 17}, {40, 17}, {44, 17}, {46, 17}, {48, 17}, {53, 17}, {56, 17}, {58, 17}, {75, 17}, {17, 16}, {18, 16}, {20, 16}, {24, 16}, {26, 16}, {27, 16}, {29, 16}, {33, 16}, {41, 16}, {42, 16}, {44, 16}, {47, 16}, {52, 16}, {57, 16}, {70, 16}, {73, 16}, {74, 16}, {17, 15}, {18, 15}, {20, 15}, {22, 15}, {24, 15}, {27, 15}, {29, 15}, {31, 15}, {33, 15}, {35, 15}, {36, 15}, {38, 15}, {39, 15}, {42, 15}, {45, 15}, {47, 15}, {52, 15}, {53, 15}, {55, 15}, {56, 15}, {70, 15}, {73, 15}, {17, 14}, {19, 14}, {21, 14}, {24, 14}, {26, 14}, {29, 14}, {31, 14}, {34, 14}, {37, 14}, {40, 14}, {42, 14}, {44, 14}, {46, 14}, {47, 14}, {53, 14}, {54, 14}, {55, 14}, {62, 14}, {70, 14}, {72, 14}, {17, 13}, {19, 13}, {21, 13}, {23, 13}, {25, 13}, {27, 13}, {30, 13}, {32, 13}, {34, 13}, {36, 13}, {38, 13}, {41, 13}, {43, 13}, {44, 13}, {45, 13}, {60, 13}, {70, 13}, {71, 13}, {18, 12}, {21, 12}, {23, 12}, {26, 12}, {28, 12}, {31, 12}, {34, 12}, {37, 12}, {39, 12}, {41, 12}, {42, 12}, {70, 12}, {18, 11}, {19, 11}, {20, 11}, {21, 11}, {24, 11}, {25, 11}, {27, 11}, {29, 11}, {31, 11}, {33, 11}, {35, 11}, {38, 11}, {41, 11}, {59, 11}, {26, 10}, {29, 10}, {32, 10}, {34, 10}, {36, 10}, {39, 10}, {40, 10}, {69, 10}, {21, 9}, {26, 9}, {28, 9}, {30, 9}, {32, 9}, {33, 9}, {35, 9}, {36, 9}, {37, 9}, {38, 9}, {39, 9}, {22, 8}, {27, 8}, {28, 8}, {29, 8}, {30, 8}, {31, 8}, {68, 8}, {23, 7}, {66, 7}, {24, 6}, {65, 6}, {25, 5}, {62, 5}, {63, 5}, {26, 4}, {55, 4}, {56, 4}, {57, 4}, {58, 4}, {59, 4}, {60, 4}, {61, 4}, {28, 3}, {53, 3}, {29, 2}, {50, 2}, {51, 2}, {52, 2}, {31, 1}, {32, 1}, {48, 1}
892      });
893      tspProblem.BestKnownQuality = new DoubleValue(867);
894
895      tspProblem.Evaluator = new TSPRoundedEuclideanPathEvaluator();
896      tspProblem.SolutionCreator = new RandomPermutationCreator();
897      tspProblem.UseDistanceMatrix.Value = true;
898      tspProblem.Name = "Funny TSP";
899      tspProblem.Description = "Represents a symmetric Traveling Salesman Problem.";
900      #endregion
901      #region Algorithm Configuration
902      vns.Name = "Variable Neighborhood Search - TSP";
903      vns.Description = "A variable neighborhood search algorithm which solves a funny TSP instance";
904      vns.Problem = tspProblem;
905
906      var localImprovement = vns.LocalImprovementParameter.ValidValues
907        .OfType<LocalSearchImprovementOperator>()
908        .Single();
909      // move generator has to be set first
910      localImprovement.MoveGenerator = localImprovement.MoveGeneratorParameter.ValidValues
911        .OfType<StochasticInversionMultiMoveGenerator>()
912        .Single();
913      localImprovement.MoveEvaluator = localImprovement.MoveEvaluatorParameter.ValidValues
914        .OfType<TSPInversionMoveRoundedEuclideanPathEvaluator>()
915        .Single();
916      localImprovement.MoveMaker = localImprovement.MoveMakerParameter.ValidValues
917        .OfType<InversionMoveMaker>()
918        .Single();
919      localImprovement.SampleSizeParameter.Value = new IntValue(500);
920      vns.LocalImprovement = localImprovement;
921
922      vns.LocalImprovementMaximumIterations = 150;
923      vns.MaximumIterations = 25;
924      vns.Seed = 0;
925      vns.SetSeedRandomly = true;
926      var shakingOperator = vns.ShakingOperatorParameter.ValidValues
927        .OfType<PermutationShakingOperator>()
928        .Single();
929      shakingOperator.Operators.SetItemCheckedState(shakingOperator.Operators
930        .OfType<Swap2Manipulator>()
931        .Single(), false);
932      shakingOperator.Operators.SetItemCheckedState(shakingOperator.Operators
933        .OfType<Swap3Manipulator>()
934        .Single(), false);
935      vns.ShakingOperator = shakingOperator;
936      vns.Analyzer.Operators.SetItemCheckedState(vns.Analyzer.Operators
937        .OfType<TSPAlleleFrequencyAnalyzer>()
938        .Single(), false);
939      vns.Analyzer.Operators.SetItemCheckedState(vns.Analyzer.Operators
940        .OfType<TSPPopulationDiversityAnalyzer>()
941        .Single(), false);
942      #endregion
943      vns.Engine = new ParallelEngine();
944      return vns;
945    }
946    #endregion
947    #endregion
948
949    #region Helpers
950    private void ConfigureEvolutionStrategyParameters<R, M, SC, SR, SM>(EvolutionStrategy es, int popSize, int children, int parentsPerChild, int maxGens, bool plusSelection)
951      where R : ICrossover
952      where M : IManipulator
953      where SC : IStrategyParameterCreator
954      where SR : IStrategyParameterCrossover
955      where SM : IStrategyParameterManipulator {
956      es.PopulationSize.Value = popSize;
957      es.Children.Value = children;
958      es.ParentsPerChild.Value = parentsPerChild;
959      es.MaximumGenerations.Value = maxGens;
960      es.PlusSelection.Value = false;
961
962      es.Seed.Value = 0;
963      es.SetSeedRandomly.Value = true;
964
965      es.Recombinator = es.RecombinatorParameter.ValidValues
966        .OfType<R>()
967        .Single();
968
969      es.Mutator = es.MutatorParameter.ValidValues
970        .OfType<M>()
971        .Single();
972
973      es.StrategyParameterCreator = es.StrategyParameterCreatorParameter.ValidValues
974        .OfType<SC>()
975        .Single();
976      es.StrategyParameterCrossover = es.StrategyParameterCrossoverParameter.ValidValues
977        .OfType<SR>()
978        .Single();
979      es.StrategyParameterManipulator = es.StrategyParameterManipulatorParameter.ValidValues
980        .OfType<SM>()
981        .Single();
982      es.Engine = new ParallelEngine();
983    }
984
985    private void ConfigureGeneticAlgorithmParameters<S, C, M>(GeneticAlgorithm ga, int popSize, int elites, int maxGens, double mutationRate, int tournGroupSize = 0)
986      where S : ISelector
987      where C : ICrossover
988      where M : IManipulator {
989      ga.Elites.Value = elites;
990      ga.MaximumGenerations.Value = maxGens;
991      ga.MutationProbability.Value = mutationRate;
992      ga.PopulationSize.Value = popSize;
993      ga.Seed.Value = 0;
994      ga.SetSeedRandomly.Value = true;
995      ga.Selector = ga.SelectorParameter.ValidValues
996        .OfType<S>()
997        .Single();
998
999      ga.Crossover = ga.CrossoverParameter.ValidValues
1000        .OfType<C>()
1001        .Single();
1002
1003      ga.Mutator = ga.MutatorParameter.ValidValues
1004        .OfType<M>()
1005        .Single();
1006
1007      var tSelector = ga.Selector as TournamentSelector;
1008      if (tSelector != null) {
1009        tSelector.GroupSizeParameter.Value.Value = tournGroupSize;
1010      }
1011      ga.Engine = new ParallelEngine();
1012    }
1013
1014    private void ConfigureIslandGeneticAlgorithmParameters<S, C, M, Mi, MiS, MiR>(IslandGeneticAlgorithm ga, int popSize, int elites, int maxGens, double mutationRate, int numberOfIslands, int migrationInterval, double migrationRate)
1015      where S : ISelector
1016      where C : ICrossover
1017      where M : IManipulator
1018      where Mi : IMigrator
1019      where MiS : ISelector
1020      where MiR : IReplacer {
1021      ga.Elites.Value = elites;
1022      ga.MaximumGenerations.Value = maxGens;
1023      ga.MutationProbability.Value = mutationRate;
1024      ga.PopulationSize.Value = popSize;
1025      ga.NumberOfIslands.Value = numberOfIslands;
1026      ga.MigrationInterval.Value = migrationInterval;
1027      ga.MigrationRate.Value = migrationRate;
1028      ga.Seed.Value = 0;
1029      ga.SetSeedRandomly.Value = true;
1030      ga.Selector = ga.SelectorParameter.ValidValues
1031        .OfType<S>()
1032        .Single();
1033
1034      ga.Crossover = ga.CrossoverParameter.ValidValues
1035        .OfType<C>()
1036        .Single();
1037
1038      ga.Mutator = ga.MutatorParameter.ValidValues
1039        .OfType<M>()
1040        .Single();
1041      ga.Migrator = ga.MigratorParameter.ValidValues
1042        .OfType<Mi>()
1043        .Single();
1044      ga.EmigrantsSelector = ga.EmigrantsSelectorParameter.ValidValues
1045        .OfType<MiS>()
1046        .Single();
1047      ga.ImmigrationReplacer = ga.ImmigrationReplacerParameter.ValidValues
1048        .OfType<MiR>()
1049        .Single();
1050      ga.Engine = new ParallelEngine();
1051    }
1052
1053
1054    private void RunAlgorithm(IAlgorithm a) {
1055      var trigger = new EventWaitHandle(false, EventResetMode.ManualReset);
1056      Exception ex = null;
1057      a.Stopped += (src, e) => { trigger.Set(); };
1058      a.ExceptionOccurred += (src, e) => { ex = e.Value; trigger.Set(); };
1059      a.Prepare();
1060      a.Start();
1061      trigger.WaitOne();
1062
1063      Assert.AreEqual(ex, null);
1064    }
1065
1066    private double GetDoubleResult(IAlgorithm a, string resultName) {
1067      return ((DoubleValue)a.Results[resultName].Value).Value;
1068    }
1069    private int GetIntResult(IAlgorithm a, string resultName) {
1070      return ((IntValue)a.Results[resultName].Value).Value;
1071    }
1072    #endregion
1073  }
1074}
Note: See TracBrowser for help on using the repository browser.