source: branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/SimulatedAnnealingMainLoop.cs @ 15001

Last change on this file since 15001 was 15001, checked in by jschiess, 5 years ago

#1836 SA reheating strategies: Newest version of reheating

File size: 17.4 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 InitialAcceptanceRateName = "InitialAcceptanceRate";
52        private const string StartTemperatureName = "StartTemperature";
53        private const string EndTemperatureName = "EndTemperature";
54        private const string TemperatureName = "Temperature";
55        private const string ResultsName = "Results";
56        private const string MaximizationName = "Maximization";
57        private const string QualityName = "Quality";
58        private const string BestKnownQualityName = "BestKnownQuality";
59        private const string MoveQualityName = "MoveQuality";
60        private const string IsAcceptedName = "IsAccepted";
61        private const string TerminateName = "Terminate";
62        private const string AcceptanceMemoryName = "AcceptanceMemory";
63        private const string ConsecutiveRejectedSolutionsCountName = "ConsecutiveRejectedSolutions";
64        private const string AverageAcceptanceRatioName = "AverageAcceptanceRatio";
65        private const string LastQualityName = "LastQuality";
66        private const string UphillMovesMemoryName = "UphillMovesMemory";
67        #endregion
68
69        #region Parameter properties
70        public IValueLookupParameter<IRandom> RandomParameter
71        {
72            get { return (IValueLookupParameter<IRandom>)Parameters[RandomName]; }
73        }
74        public IValueLookupParameter<BoolValue> MaximizationParameter
75        {
76            get { return (IValueLookupParameter<BoolValue>)Parameters[MaximizationName]; }
77        }
78        public ILookupParameter<DoubleValue> QualityParameter
79        {
80            get { return (ILookupParameter<DoubleValue>)Parameters[QualityName]; }
81        }
82        public IValueLookupParameter<DoubleValue> BestKnownQualityParameter
83        {
84            get { return (IValueLookupParameter<DoubleValue>)Parameters[BestKnownQualityName]; }
85        }
86        public IValueLookupParameter<DoubleValue> LastQualityParameter
87        {
88            get { return (IValueLookupParameter<DoubleValue>)Parameters[LastQualityName]; }
89        }
90        public ILookupParameter<DoubleValue> InitialTemperatureParameter
91        {
92            get { return (ILookupParameter<DoubleValue>)Parameters[InitialTemperatureName]; }
93        }
94        public ILookupParameter<DoubleValue> InitialAcceptanceRateParameter
95        {
96            get { return (ILookupParameter<DoubleValue>)Parameters[InitialAcceptanceRateName]; }
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
203            Parameters.Add(new ValueLookupParameter<IOperator>(AnalyzerName, "The operator used to analyze each generation."));
204            Parameters.Add(new ValueLookupParameter<VariableCollection>(ResultsName, "The variable collection where results should be stored."));
205            Parameters.Add(new LookupParameter<IntValue>(EvaluatedMovesName, "The number of evaluated moves."));
206
207            Parameters.Add(new LookupParameter<DoubleValue>(InitialTemperatureName, "The initial temperature."));
208            Parameters.Add(new LookupParameter<DoubleValue>(InitialAcceptanceRateName, "The initial acceptance rate of average-sized hills used to calculate 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            #endregion
215
216            #region Create operators
217            var variableCreator = new VariableCreator();
218            var ssp1 = new SubScopesProcessor();
219            var analyzer1 = new Placeholder();
220            var ssp2 = new SubScopesProcessor();
221            var resultsCollector = new ResultsCollector();
222            var mainProcessor = new SubScopesProcessor();
223            var moveGenerator = new Placeholder();
224            var moveEvaluationProcessor = new SubScopesProcessor();
225            var moveEvaluator = new Placeholder();
226            var evaluatedMovesCounter = new IntCounter();
227            var qualityComparator = new ProbabilisticQualityComparator();
228            var acceptsQualityBranch = new ConditionalBranch();
229            var moveMaker = new Placeholder();
230            var temperatureController = new TemperatureController();
231            var subScopesRemover = new SubScopesRemover();
232            var iterationsCounter = new IntCounter();
233            var iterationsComparator = new Comparator();
234            var ssp3 = new SubScopesProcessor();
235            var analyzer2 = new Placeholder();
236            var iterationsTermination = new ConditionalBranch();
237
238            variableCreator.Name = "Initialize Memory";
239            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(AverageAcceptanceRatioName, new DoubleValue(0d)));
240            variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(ConsecutiveRejectedSolutionsCountName, new IntValue(0)));
241            variableCreator.CollectedValues.Add(new ValueParameter<ItemList<BoolValue>>(AcceptanceMemoryName, new ItemList<BoolValue>()));
242            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(LastQualityName, new DoubleValue(-1)));
243            variableCreator.CollectedValues.Add(new ValueParameter<ItemList<DoubleValue>>(UphillMovesMemoryName, new ItemList<DoubleValue>()));
244
245            analyzer1.Name = "Analyzer";
246            analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
247
248            moveGenerator.Name = "Move generator";
249            moveGenerator.OperatorParameter.ActualName = MoveGeneratorParameter.Name;
250
251            moveEvaluator.Name = "Move evaluator";
252            moveEvaluator.OperatorParameter.ActualName = MoveEvaluatorParameter.Name;
253
254            evaluatedMovesCounter.Name = "EvaluatedMoves++";
255            evaluatedMovesCounter.ValueParameter.ActualName = EvaluatedMovesParameter.Name;
256            evaluatedMovesCounter.Increment = new IntValue(1);
257
258            qualityComparator.LeftSideParameter.ActualName = MoveQualityParameter.Name;
259            qualityComparator.RightSideParameter.ActualName = QualityParameter.Name;
260            qualityComparator.ResultParameter.ActualName = IsAcceptedName;
261            qualityComparator.DampeningParameter.ActualName = TemperatureParameter.Name;
262
263            acceptsQualityBranch.ConditionParameter.ActualName = IsAcceptedName;
264
265            moveMaker.Name = "Move maker";
266            moveMaker.OperatorParameter.ActualName = MoveMakerParameter.Name;
267
268           
269
270            subScopesRemover.RemoveAllSubScopes = true;
271
272            iterationsCounter.Name = "Iterations++";
273            iterationsCounter.Increment = new IntValue(1);
274            iterationsCounter.ValueParameter.ActualName = IterationsParameter.Name;
275
276            iterationsComparator.Name = "Iterations >= MaximumIterations";
277            iterationsComparator.LeftSideParameter.ActualName = IterationsParameter.Name;
278            iterationsComparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
279            iterationsComparator.ResultParameter.ActualName = TerminateName;
280            iterationsComparator.Comparison.Value = ComparisonType.GreaterOrEqual;
281
282            analyzer2.Name = "Analyzer (placeholder)";
283            analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
284
285            iterationsTermination.Name = "Iterations termination condition";
286            iterationsTermination.ConditionParameter.ActualName = TerminateName;
287            #endregion
288
289            #region Create operator graph
290            OperatorGraph.InitialOperator = variableCreator;
291            variableCreator.Successor = ssp1;
292            ssp1.Operators.Add(analyzer1);
293            ssp1.Successor = ssp2;
294            analyzer1.Successor = null;
295            ssp2.Operators.Add(resultsCollector);
296            ssp2.Successor = mainProcessor;
297            resultsCollector.Successor = null;
298            mainProcessor.Operators.Add(moveGenerator);
299            mainProcessor.Successor = iterationsCounter;
300            moveGenerator.Successor = moveEvaluationProcessor;
301            moveEvaluationProcessor.Operators.Add(moveEvaluator);
302            moveEvaluationProcessor.Successor = evaluatedMovesCounter;
303            moveEvaluator.Successor = qualityComparator;
304            qualityComparator.Successor = acceptsQualityBranch;
305            acceptsQualityBranch.TrueBranch = moveMaker;
306            acceptsQualityBranch.FalseBranch = null;
307            acceptsQualityBranch.Successor = temperatureController;
308            moveMaker.Successor = null;
309            temperatureController.Successor = null;
310            evaluatedMovesCounter.Successor = subScopesRemover;
311            subScopesRemover.Successor = null;
312            iterationsCounter.Successor = iterationsComparator;
313            iterationsComparator.Successor = ssp3;
314            ssp3.Operators.Add(analyzer2);
315            ssp3.Successor = iterationsTermination;
316            iterationsTermination.TrueBranch = null;
317            iterationsTermination.FalseBranch = mainProcessor;
318            #endregion
319        }
320
321        public override IOperation Apply()
322        {
323            if (MoveGeneratorParameter.ActualValue == null || MoveEvaluatorParameter.ActualValue == null || MoveMakerParameter.ActualValue == null)
324                return null;
325            return base.Apply();
326        }
327    }
328}
Note: See TracBrowser for help on using the repository browser.