Free cookie consent management tool by TermsFeed Policy Generator

source: branches/1836_jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/SimulatedAnnealingMainLoop.cs @ 17481

Last change on this file since 17481 was 15333, checked in by jschiess, 7 years ago

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