source: trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.3/RandomWalkReheatingOperator.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: 14.7 KB
Line 
1using HeuristicLab.Operators;
2using System;
3using System.Collections.Generic;
4using System.Linq;
5using System.Text;
6using System.Threading.Tasks;
7using HeuristicLab.Common;
8using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
9using HeuristicLab.Core;
10using HeuristicLab.Data;
11using HeuristicLab.Parameters;
12using HeuristicLab.Optimization;
13using HeuristicLab.PluginInfrastructure;
14using HeuristicLab.Analysis;
15
16namespace HeuristicLab.Algorithms.SimulatedAnnealing
17{
18    [Item("RandomWalkReheatingOperator", "Performs a randomwalk with the lenght of n after x consecutive solutions were rejected.")]
19    [StorableClass]
20    public class RandomWalkReheatingOperator : SingleSuccessorOperator, IReheatingOperator
21    {
22        #region Strings
23        private const string AnnealingOperatorName = "AnnealingOperator";
24        private const string LowerTemperatureName = "LowerTemperature";
25        private const string IterationsName = "Iterations";
26        private const string TemperatureStartIndexName = "TemperatureStartIndex";
27        private const string StartTemperatureName = "StartTemperature";
28        private const string EndTemperatureName = "EndTemperature";
29        private const string TemperatureName = "Temperature";
30        private const string MaximumIterationsName = "MaximumIterations";
31
32        private const string TemperatureBeforeReheatName = "TemperatureBeforeReheat";
33        private const string CurrentRandomWalkStepName = "CurrentRandomWalkStep";
34        private const string RandomWalkLengthName = "RandomWalkLength";
35        private const string ThresholdName = "Threshold";
36        private const string IsAcceptedName = "IsAccepted";
37        private const string ConsecutiveRejectedSolutionsCountName = "ConsecutiveRejectedSolutions";
38        private const string QualitiesBeforeReheatingName = "QualitiesBeforeReheating";
39        private const string AmountOfReheatsName = "AmountOfReheats";
40        private const string RetrappedName = "Retrapped";
41        private const string LastAcceptedQualityName = "LastAcceptedQuality";
42        private const string ResultsName = "Results";
43        private const string MoveQualityName = "MoveQuality";
44        private const string CoolingName = "Cooling";
45        private const string TabuListActiveName = "TabuListActive";
46
47
48        #endregion
49
50        #region Parameters
51        public ILookupParameter<DoubleValue> TemperatureParameter
52        {
53            get { return (ILookupParameter<DoubleValue>)Parameters[TemperatureName]; }
54        }
55        public ILookupParameter<DoubleValue> LowerTemperatureParameter
56        {
57            get { return (ILookupParameter<DoubleValue>)Parameters[LowerTemperatureName]; }
58        }
59        public ILookupParameter<DoubleValue> StartTemperatureParameter
60        {
61            get { return (ILookupParameter<DoubleValue>)Parameters[StartTemperatureName]; }
62        }
63        public ILookupParameter<DoubleValue> EndTemperatureParameter
64        {
65            get { return (ILookupParameter<DoubleValue>)Parameters[EndTemperatureName]; }
66        }
67        public ILookupParameter<IntValue> TemperatureStartIndexParameter
68        {
69            get { return (ILookupParameter<IntValue>)Parameters[TemperatureStartIndexName]; }
70        }
71        public ILookupParameter<IntValue> IterationsParameter
72        {
73            get { return (ILookupParameter<IntValue>)Parameters[IterationsName]; }
74        }
75        public ILookupParameter<IOperator> AnnealingOperatorParameter
76        {
77            get { return (ILookupParameter<IOperator>)Parameters[AnnealingOperatorName]; }
78        }
79        public ILookupParameter<IntValue> MaximumIterationsParameter
80        {
81            get { return (ILookupParameter<IntValue>)Parameters[MaximumIterationsName]; }
82        }
83        private ValueParameter<IntValue> ThresholdParameter
84        {
85            get { return (ValueParameter<IntValue>)Parameters[ThresholdName]; }
86        }
87        private ValueParameter<IntValue> RandomWalkLengthParameter
88        {
89            get { return (ValueParameter<IntValue>)Parameters[RandomWalkLengthName]; }
90        }
91        public ILookupParameter<BoolValue> IsAcceptedParameter
92        {
93            get { return (ILookupParameter<BoolValue>)Parameters[IsAcceptedName]; }
94        }
95        public ILookupParameter<IntValue> ConsecutiveRejectedSolutionsCountParameter
96        {
97            get { return (ILookupParameter<IntValue>)Parameters[ConsecutiveRejectedSolutionsCountName]; }
98        }
99        public ILookupParameter<IntValue> RandomWalkLengthNameParameter
100        {
101            get { return (ILookupParameter<IntValue>)Parameters[RandomWalkLengthName]; }
102        }
103        public ILookupParameter<IntValue> CurrentRandomWalkStepParameter
104        {
105            get { return (ILookupParameter<IntValue>)Parameters[CurrentRandomWalkStepName]; }
106        }
107        public ILookupParameter<DoubleValue> TemperatureBeforeReheatParameter
108        {
109            get { return (ILookupParameter<DoubleValue>)Parameters[TemperatureBeforeReheatName]; }
110        }
111        private LookupParameter<ItemList<DoubleValue>> QualitiesBeforeReheatingParameter
112        {
113            get { return (LookupParameter<ItemList<DoubleValue>>)Parameters[QualitiesBeforeReheatingName]; }
114        }
115        public ILookupParameter<BoolValue> CoolingParameter
116        {
117            get { return (ILookupParameter<BoolValue>)Parameters[CoolingName]; }
118        }
119        public ILookupParameter<DoubleValue> MoveQualityParameter
120        {
121            get { return (ILookupParameter<DoubleValue>)Parameters[MoveQualityName]; }
122        }
123        public ILookupParameter<DoubleValue> LastAcceptedQualityParameter
124        {
125            get { return (ILookupParameter<DoubleValue>)Parameters[LastAcceptedQualityName]; }
126        }
127        public IValueParameter<BoolValue> TabuListActiveParameter
128        {
129            get { return (IValueParameter<BoolValue>)Parameters[TabuListActiveName];  }
130        }
131
132        #endregion
133
134        public RandomWalkReheatingOperator() : base()
135        {
136            #region Create parameters
137            Parameters.Add(new LookupParameter<DoubleValue>(TemperatureName, "The current temperature."));
138            Parameters.Add(new LookupParameter<DoubleValue>(LowerTemperatureName, "The lower bound of the temperature."));
139            Parameters.Add(new LookupParameter<IntValue>(IterationsName, "The number of iterations."));
140            Parameters.Add(new LookupParameter<IOperator>(AnnealingOperatorName, "The operator that cools the temperature."));
141            Parameters.Add(new LookupParameter<IntValue>(TemperatureStartIndexName, "The index where the annealing or heating was last changed."));
142            Parameters.Add(new LookupParameter<DoubleValue>(StartTemperatureName, "The temperature from which cooling or reheating should occur."));
143            Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
144            Parameters.Add(new LookupParameter<IntValue>(MaximumIterationsName, "The maximum number of iterations which should be processed."));
145            Parameters.Add(new LookupParameter<BoolValue>(IsAcceptedName, "Whether the move was accepted or not."));
146            Parameters.Add(new LookupParameter<IntValue>(ConsecutiveRejectedSolutionsCountName, "Amount of consecutive rejected solutions."));
147            Parameters.Add(new ValueParameter<IntValue>(ThresholdName, "How many consecutive rejected solutions must occur to trigger a reheat.", new IntValue(10)));
148            Parameters.Add(new ValueParameter<IntValue>(RandomWalkLengthName, "Amount of randomly accepted moves upon reheat.", new IntValue(2)));
149            Parameters.Add(new LookupParameter<IntValue>(CurrentRandomWalkStepName, "Current random walk step."));
150            Parameters.Add(new LookupParameter<DoubleValue>(TemperatureBeforeReheatName, "Temperature before the reheat occured."));
151            Parameters.Add(new LookupParameter<ItemList<DoubleValue>>(QualitiesBeforeReheatingName, "Quality of last optimum."));
152            Parameters.Add(new LookupParameter<DoubleValue>(MoveQualityName, "The value which represents the quality of a move."));
153            Parameters.Add(new LookupParameter<BoolValue>(CoolingName, "True when the temperature should be cooled, false otherwise."));
154            Parameters.Add(new LookupParameter<DoubleValue>(LastAcceptedQualityName, "Quality of last accepted solution."));
155            Parameters.Add(new ValueParameter<BoolValue>(TabuListActiveName, "Determines whether visiting a 'frozen' quality instantly triggers a reheat or not", new BoolValue(true)));
156
157            #endregion
158
159            Parameterize();
160        }
161
162        [StorableConstructor]
163        protected RandomWalkReheatingOperator(bool deserializing) : base(deserializing) { }
164        protected RandomWalkReheatingOperator(RandomWalkReheatingOperator original, Cloner cloner) : base(original, cloner) { }
165
166
167        public override IDeepCloneable Clone(Cloner cloner)
168        {
169            return new RandomWalkReheatingOperator(this, cloner);
170        }
171
172        public void Parameterize()
173        {
174        }
175
176        public override IOperation Apply()
177        {
178            var isAccepted = IsAcceptedParameter.ActualValue.Value;
179            var consecutiveRejectedCount = ConsecutiveRejectedSolutionsCountParameter.ActualValue;
180            var cooling = CoolingParameter.ActualValue.Value;
181            var frozenSolutions = QualitiesBeforeReheatingParameter.ActualValue;
182            var quality = MoveQualityParameter.ActualValue;
183            var lastAcceptedQuality = LastAcceptedQualityParameter.ActualValue;
184            var tabuListActive = TabuListActiveParameter.Value.Value;
185
186            if(isAccepted)
187            {
188                LastAcceptedQualityParameter.ActualValue.Value = quality.Value;
189            }
190
191            if (cooling)
192            { 
193                // check if we are re-trapped
194                if (isAccepted && frozenSolutions.Any(frozen => frozen.Value.Equals(quality.Value)) && tabuListActive)
195                {
196                   cooling = false;
197
198                    IntValue retrapped = new IntValue(0);
199                    IResult retrappedAmount;
200                    var results = (ResultCollection)ExecutionContext.Parent.Parent.Scope.Variables[ResultsName].Value;
201                    if (results.TryGetValue(RetrappedName, out retrappedAmount))
202                    {
203                        retrapped = (IntValue)retrappedAmount.Value;
204                        retrapped.Value += 1;
205                    }
206                    else
207                    {
208                        retrapped.Value += 1;
209                        results.Add(new Result(RetrappedName, retrapped));
210                    }
211                    // remember local optimum
212                    frozenSolutions.Add(new DoubleValue(lastAcceptedQuality.Value));
213                }
214                else
215                {
216                    // add acceptance value to consecutive rejected solutions count
217                    consecutiveRejectedCount.Value = !IsAcceptedParameter.ActualValue.Value ? consecutiveRejectedCount.Value + 1 : 0;
218
219                    // check if we are trapped in a new local optimum
220                    if (consecutiveRejectedCount.Value == ThresholdParameter.Value.Value)
221                    {
222                        cooling = false;
223                        consecutiveRejectedCount.Value = 0;
224                        // remember local optimum
225                        frozenSolutions.Add(new DoubleValue(lastAcceptedQuality.Value));
226                    }
227                }
228            }
229            else
230            {
231                // random walk not yet finished
232                if (RandomWalkLengthParameter.Value.Value != CurrentRandomWalkStepParameter.ActualValue.Value)
233                {
234                    if (CurrentRandomWalkStepParameter.ActualValue.Value == 0)
235                    {
236                        DebugIncreaseReheatCounter();
237                    }
238                    CurrentRandomWalkStepParameter.ActualValue.Value++;
239                }
240                else
241                {
242                    // random walk finished start cooling again
243                    cooling = true;
244                    TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, IterationsParameter.ActualValue.Value - 1);
245                    StartTemperatureParameter.ActualValue.Value = TemperatureBeforeReheatParameter.ActualValue.Value;
246                    EndTemperatureParameter.ActualValue.Value = LowerTemperatureParameter.ActualValue.Value;
247                    consecutiveRejectedCount.Value = isAccepted ? 0 : 1;
248                    CurrentRandomWalkStepParameter.ActualValue.Value = 0;
249
250                }
251            }
252            CoolingParameter.ActualValue.Value = cooling;
253            return cooling ? Cool() : Heat();
254        }
255
256        private void DebugIncreaseReheatCounter()
257        {
258            var reheats = new IntValue(0);
259            var frozen = new ItemList<DoubleValue>();
260            var results = (ResultCollection)ExecutionContext.Parent.Parent.Scope.Variables[ResultsName].Value;
261            IResult amountOfReheats;
262            IResult frozenSolutions;
263            if (results.TryGetValue(AmountOfReheatsName, out amountOfReheats))
264            {
265                reheats = (IntValue)amountOfReheats.Value;
266                reheats.Value += 1;
267            }
268            else
269            {
270                reheats.Value += 1;
271                results.Add(new Result(AmountOfReheatsName, reheats));
272            }
273
274            if (results.TryGetValue(QualitiesBeforeReheatingName, out frozenSolutions))
275            {
276               
277                frozen = (ItemList<DoubleValue>) frozenSolutions.Value;
278                frozen.Add(new DoubleValue(LastAcceptedQualityParameter.ActualValue.Value));
279            }
280            else
281            {
282                frozen.Add(new DoubleValue(LastAcceptedQualityParameter.ActualValue.Value));
283                results.Add(new Result(QualitiesBeforeReheatingName, frozen));
284            }
285        }
286
287        private IOperation Heat()
288        {
289            TemperatureParameter.ActualValue.Value = Double.PositiveInfinity;
290            return base.Apply();
291        }
292
293        private IOperation Cool()
294        {
295            TemperatureBeforeReheatParameter.ActualValue.Value = TemperatureParameter.ActualValue.Value;
296            return new OperationCollection {
297                    ExecutionContext.CreateOperation(AnnealingOperatorParameter.ActualValue),
298                    base.Apply()
299                };
300        }
301    }
302}
Note: See TracBrowser for help on using the repository browser.