source: trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.3/SimulatedAnnealingMainLoop.cs @ 15295

Last change on this file since 15295 was 15295, checked in by jschiess, 2 years ago

#1836 SA reheating strategies: Refactoring

File size: 18.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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 HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Operators;
26using HeuristicLab.Optimization.Operators;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Algorithms.SimulatedAnnealing
31{
32    [Item("SimulatedAnnealingMainLoop", "An operator which represents the main loop of a simulated annealing algorithm.")]
33    [StorableClass]
34    public sealed class SimulatedAnnealingMainLoop : AlgorithmOperator
35    {
36        #region Strings
37        private const string MoveGeneratorName = "MoveGenerator";
38        private const string MoveEvaluatorName = "MoveEvaluator";
39        private const string MoveMakerName = "MoveMaker";
40        private const string AnnealingOperatorName = "AnnealingOperator";
41        private const string ReheatingOperatorName = "ReheatingOperator";
42        private const string MaximumIterationsName = "MaximumIterations";
43        private const string LowerTemperatureName = "LowerTemperature";
44        private const string AnalyzerName = "Analyzer";
45        private const string RandomName = "Random";
46        private const string EvaluatedMovesName = "EvaluatedMoves";
47        private const string IterationsName = "Iterations";
48        private const string TemperatureStartIndexName = "TemperatureStartIndex";
49        private const string CoolingName = "Cooling";
50        private const string InitialTemperatureName = "InitialTemperature";
51        private const string StartTemperatureName = "StartTemperature";
52        private const string EndTemperatureName = "EndTemperature";
53        private const string TemperatureName = "Temperature";
54        private const string ResultsName = "Results";
55        private const string MaximizationName = "Maximization";
56        private const string QualityName = "Quality";
57        private const string BestKnownQualityName = "BestKnownQuality";
58        private const string MoveQualityName = "MoveQuality";
59        private const string IsAcceptedName = "IsAccepted";
60        private const string TerminateName = "Terminate";
61        private const string AcceptanceMemoryName = "AcceptanceMemory";
62        private const string ConsecutiveRejectedSolutionsCountName = "ConsecutiveRejectedSolutions";
63        private const string AverageAcceptanceRatioName = "AverageAcceptanceRatio";
64        private const string LastQualityName = "LastQuality";
65        private const string UphillMovesMemoryName = "UphillMovesMemory";
66        private const string TemperatureBeforeReheatName = "TemperatureBeforeReheat";
67        private const string CurrentRandomWalkStepName = "CurrentRandomWalkStep";
68        private const string QualitiesBeforeReheatingName = "QualitiesBeforeReheating";
69        private const string LastAcceptedQualityName = "LastAcceptedQuality";
70        private const string TemperatureInitializerName = "TemperatureInitializer";
71        private const string TemperatureInitializedName = "TemperatureInitialized";
72
73        #endregion
74
75        #region Parameter properties
76        public IValueLookupParameter<IRandom> RandomParameter
77        {
78            get { return (IValueLookupParameter<IRandom>)Parameters[RandomName]; }
79        }
80        public IValueLookupParameter<BoolValue> MaximizationParameter
81        {
82            get { return (IValueLookupParameter<BoolValue>)Parameters[MaximizationName]; }
83        }
84        public ILookupParameter<DoubleValue> QualityParameter
85        {
86            get { return (ILookupParameter<DoubleValue>)Parameters[QualityName]; }
87        }
88        public IValueLookupParameter<DoubleValue> BestKnownQualityParameter
89        {
90            get { return (IValueLookupParameter<DoubleValue>)Parameters[BestKnownQualityName]; }
91        }
92        public IValueLookupParameter<DoubleValue> LastQualityParameter
93        {
94            get { return (IValueLookupParameter<DoubleValue>)Parameters[LastQualityName]; }
95        }
96        public ILookupParameter<DoubleValue> InitialTemperatureParameter
97        {
98            get { return (ILookupParameter<DoubleValue>)Parameters[InitialTemperatureName]; }
99        }
100        public ILookupParameter<DoubleValue> MoveQualityParameter
101        {
102            get { return (ILookupParameter<DoubleValue>)Parameters[MoveQualityName]; }
103        }
104        public ILookupParameter<DoubleValue> TemperatureParameter
105        {
106            get { return (ILookupParameter<DoubleValue>)Parameters[TemperatureName]; }
107        }
108        public IValueLookupParameter<DoubleValue> LowerTemperatureParameter
109        {
110            get { return (IValueLookupParameter<DoubleValue>)Parameters[LowerTemperatureName]; }
111        }
112        public ILookupParameter<IntValue> IterationsParameter
113        {
114            get { return (ILookupParameter<IntValue>)Parameters[IterationsName]; }
115        }
116        public IValueLookupParameter<IntValue> MaximumIterationsParameter
117        {
118            get { return (IValueLookupParameter<IntValue>)Parameters[MaximumIterationsName]; }
119        }
120        public IValueLookupParameter<IOperator> MoveGeneratorParameter
121        {
122            get { return (IValueLookupParameter<IOperator>)Parameters[MoveGeneratorName]; }
123        }
124        public IValueLookupParameter<IOperator> MoveEvaluatorParameter
125        {
126            get { return (IValueLookupParameter<IOperator>)Parameters[MoveEvaluatorName]; }
127        }
128        public IValueLookupParameter<IOperator> MoveMakerParameter
129        {
130            get { return (IValueLookupParameter<IOperator>)Parameters[MoveMakerName]; }
131        }
132        public IValueLookupParameter<IOperator> AnnealingOperatorParameter
133        {
134            get { return (IValueLookupParameter<IOperator>)Parameters[AnnealingOperatorName]; }
135        }
136        public IValueLookupParameter<IOperator> ReheatingOperatorParameter
137        {
138            get { return (IValueLookupParameter<IOperator>)Parameters[ReheatingOperatorName]; }
139        }
140        public IValueLookupParameter<IOperator> AnalyzerParameter
141        {
142            get { return (IValueLookupParameter<IOperator>)Parameters[AnalyzerName]; }
143        }
144        public IValueLookupParameter<VariableCollection> ResultsParameter
145        {
146            get { return (IValueLookupParameter<VariableCollection>)Parameters[ResultsName]; }
147        }
148        public ILookupParameter<IntValue> EvaluatedMovesParameter
149        {
150            get { return (ILookupParameter<IntValue>)Parameters[EvaluatedMovesName]; }
151        }
152        public ILookupParameter<DoubleValue> StartTemperatureParameter
153        {
154            get { return (ILookupParameter<DoubleValue>)Parameters[StartTemperatureName]; }
155        }
156        public ILookupParameter<DoubleValue> EndTemperatureParameter
157        {
158            get { return (ILookupParameter<DoubleValue>)Parameters[EndTemperatureName]; }
159        }
160        public ILookupParameter<IntValue> TemperatureStartIndexParameter
161        {
162            get { return (ILookupParameter<IntValue>)Parameters[TemperatureStartIndexName]; }
163        }
164        public ILookupParameter<BoolValue> CoolingParameter
165        {
166            get { return (ILookupParameter<BoolValue>)Parameters[CoolingName]; }
167        }
168        #endregion
169
170        [StorableConstructor]
171        private SimulatedAnnealingMainLoop(bool deserializing) : base(deserializing) { }
172        private SimulatedAnnealingMainLoop(SimulatedAnnealingMainLoop original, Cloner cloner)
173          : base(original, cloner)
174        {
175        }
176        public override IDeepCloneable Clone(Cloner cloner)
177        {
178            return new SimulatedAnnealingMainLoop(this, cloner);
179        }
180        public SimulatedAnnealingMainLoop()
181          : base()
182        {
183            Initialize();
184        }
185
186        private void Initialize()
187        {
188            #region Create parameters
189            Parameters.Add(new ValueLookupParameter<IRandom>(RandomName, "A pseudo random number generator."));
190            Parameters.Add(new ValueLookupParameter<BoolValue>(MaximizationName, "True if the problem is a maximization problem, otherwise false."));
191            Parameters.Add(new LookupParameter<DoubleValue>(QualityName, "The value which represents the quality of a solution."));
192            Parameters.Add(new ValueLookupParameter<DoubleValue>(BestKnownQualityName, "The best known quality value found so far."));
193            Parameters.Add(new LookupParameter<DoubleValue>(MoveQualityName, "The value which represents the quality of a move."));
194            Parameters.Add(new LookupParameter<DoubleValue>(TemperatureName, "The current temperature."));
195            Parameters.Add(new ValueLookupParameter<DoubleValue>(LowerTemperatureName, "The lower bound of the temperature."));
196            Parameters.Add(new LookupParameter<IntValue>(IterationsName, "The number of iterations."));
197            Parameters.Add(new ValueLookupParameter<IntValue>(MaximumIterationsName, "The maximum number of iterations which should be processed."));
198
199            Parameters.Add(new ValueLookupParameter<IOperator>(MoveGeneratorName, "The operator that generates the moves."));
200            Parameters.Add(new ValueLookupParameter<IOperator>(MoveEvaluatorName, "The operator that evaluates a move."));
201            Parameters.Add(new ValueLookupParameter<IOperator>(MoveMakerName, "The operator that performs a move and updates the quality."));
202            Parameters.Add(new ValueLookupParameter<IOperator>(AnnealingOperatorName, "The operator that cools the temperature."));
203            Parameters.Add(new ValueLookupParameter<IOperator>(ReheatingOperatorName, "The operator that reheats the temperature if necessary."));
204            Parameters.Add(new ValueLookupParameter<IOperator>(TemperatureInitializerName, "The operator that initialized the temperature."));
205
206            Parameters.Add(new ValueLookupParameter<IOperator>(AnalyzerName, "The operator used to analyze each generation."));
207            Parameters.Add(new ValueLookupParameter<VariableCollection>(ResultsName, "The variable collection where results should be stored."));
208            Parameters.Add(new LookupParameter<IntValue>(EvaluatedMovesName, "The number of evaluated moves."));
209
210            Parameters.Add(new LookupParameter<DoubleValue>(InitialTemperatureName, "The initial temperature."));
211            Parameters.Add(new LookupParameter<IntValue>(TemperatureStartIndexName, "The index where the annealing or heating was last changed."));
212            Parameters.Add(new LookupParameter<BoolValue>(CoolingName, "True when the temperature should be cooled, false otherwise."));
213            Parameters.Add(new LookupParameter<DoubleValue>(StartTemperatureName, "The temperature from which cooling or reheating should occur."));
214            Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
215
216
217            #endregion
218
219            #region Create operators
220            var variableCreator = new VariableCreator();
221            var ssp1 = new SubScopesProcessor();
222            var analyzer1 = new Placeholder();
223            var ssp2 = new SubScopesProcessor();
224            var resultsCollector = new ResultsCollector();
225            var mainProcessor = new SubScopesProcessor();
226            var moveGenerator = new Placeholder();
227            var moveEvaluationProcessor = new SubScopesProcessor();
228            var moveEvaluator = new Placeholder();
229            var evaluatedMovesCounter = new IntCounter();
230            var qualityComparator = new ProbabilisticQualityComparator();
231            var acceptsQualityBranch = new ConditionalBranch();
232            var moveMaker = new Placeholder();
233            var temperatureController = new TemperatureController();
234            var subScopesRemover = new SubScopesRemover();
235            var iterationsCounter = new IntCounter();
236            var iterationsComparator = new Comparator();
237            var ssp3 = new SubScopesProcessor();
238            var analyzer2 = new Placeholder();
239            var iterationsTermination = new ConditionalBranch();
240
241            variableCreator.Name = "Initialize Memory";
242            variableCreator.CollectedValues.Add(new ValueParameter<BoolValue>(TemperatureInitializedName, new BoolValue(false)));
243            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(AverageAcceptanceRatioName, new DoubleValue(0d)));
244            variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(ConsecutiveRejectedSolutionsCountName, new IntValue(0)));
245            variableCreator.CollectedValues.Add(new ValueParameter<ItemList<BoolValue>>(AcceptanceMemoryName, new ItemList<BoolValue>()));
246            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(LastQualityName, new DoubleValue(-1)));
247            variableCreator.CollectedValues.Add(new ValueParameter<ItemList<DoubleValue>>(UphillMovesMemoryName, new ItemList<DoubleValue>()));
248            variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(CurrentRandomWalkStepName, new IntValue(0)));
249            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(TemperatureBeforeReheatName, new DoubleValue(0)));
250            variableCreator.CollectedValues.Add(new ValueParameter<ItemList<DoubleValue>>(QualitiesBeforeReheatingName, new ItemList<DoubleValue>()));
251            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(LastAcceptedQualityName, new DoubleValue(-1)));
252
253            analyzer1.Name = "Analyzer";
254            analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
255
256            moveGenerator.Name = "Move generator";
257            moveGenerator.OperatorParameter.ActualName = MoveGeneratorParameter.Name;
258
259            moveEvaluator.Name = "Move evaluator";
260            moveEvaluator.OperatorParameter.ActualName = MoveEvaluatorParameter.Name;
261
262            evaluatedMovesCounter.Name = "EvaluatedMoves++";
263            evaluatedMovesCounter.ValueParameter.ActualName = EvaluatedMovesParameter.Name;
264            evaluatedMovesCounter.Increment = new IntValue(1);
265
266            qualityComparator.LeftSideParameter.ActualName = MoveQualityParameter.Name;
267            qualityComparator.RightSideParameter.ActualName = QualityParameter.Name;
268            qualityComparator.ResultParameter.ActualName = IsAcceptedName;
269            qualityComparator.DampeningParameter.ActualName = TemperatureParameter.Name;
270
271            acceptsQualityBranch.ConditionParameter.ActualName = IsAcceptedName;
272
273            moveMaker.Name = "Move maker";
274            moveMaker.OperatorParameter.ActualName = MoveMakerParameter.Name;
275
276           
277            subScopesRemover.RemoveAllSubScopes = true;
278
279            iterationsCounter.Name = "Iterations++";
280            iterationsCounter.Increment = new IntValue(1);
281            iterationsCounter.ValueParameter.ActualName = IterationsParameter.Name;
282
283            iterationsComparator.Name = "Iterations >= MaximumIterations";
284            iterationsComparator.LeftSideParameter.ActualName = IterationsParameter.Name;
285            iterationsComparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
286            iterationsComparator.ResultParameter.ActualName = TerminateName;
287            iterationsComparator.Comparison.Value = ComparisonType.GreaterOrEqual;
288
289            analyzer2.Name = "Analyzer (placeholder)";
290            analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
291
292            iterationsTermination.Name = "Iterations termination condition";
293            iterationsTermination.ConditionParameter.ActualName = TerminateName;
294            #endregion
295
296            #region Create operator graph
297            OperatorGraph.InitialOperator = variableCreator;
298            variableCreator.Successor = ssp1;
299            ssp1.Operators.Add(analyzer1);
300            ssp1.Successor = ssp2;
301            analyzer1.Successor = null;
302            ssp2.Operators.Add(resultsCollector);
303            ssp2.Successor = mainProcessor;
304            resultsCollector.Successor = null;
305            mainProcessor.Operators.Add(moveGenerator);
306            mainProcessor.Successor = iterationsCounter;
307            moveGenerator.Successor = moveEvaluationProcessor;
308            moveEvaluationProcessor.Operators.Add(moveEvaluator);
309            moveEvaluationProcessor.Successor = evaluatedMovesCounter;
310            moveEvaluator.Successor = qualityComparator;
311            qualityComparator.Successor = acceptsQualityBranch;
312            acceptsQualityBranch.TrueBranch = moveMaker;
313            acceptsQualityBranch.FalseBranch = null;
314            acceptsQualityBranch.Successor = temperatureController;
315            moveMaker.Successor = null;
316            temperatureController.Successor = null;
317            evaluatedMovesCounter.Successor = subScopesRemover;
318            subScopesRemover.Successor = null;
319            iterationsCounter.Successor = iterationsComparator;
320            iterationsComparator.Successor = ssp3;
321            ssp3.Operators.Add(analyzer2);
322            ssp3.Successor = iterationsTermination;
323            iterationsTermination.TrueBranch = null;
324            iterationsTermination.FalseBranch = mainProcessor;
325            #endregion
326        }
327
328        public override IOperation Apply()
329        {
330            if (MoveGeneratorParameter.ActualValue == null || MoveEvaluatorParameter.ActualValue == null || MoveMakerParameter.ActualValue == null)
331                return null;
332            return base.Apply();
333        }
334    }
335}
Note: See TracBrowser for help on using the repository browser.