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