Free cookie consent management tool by TermsFeed Policy Generator

source: branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/RandomWalkReheatingOperator.cs @ 15333

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

#1836 SA reheating strategies
+ added an adaptive temperature control strategy
+ some refactorings

File size: 10.1 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        private const string CurrentRandomWalkStepName = "CurrentRandomWalkStep";
32        private const string RandomWalkLengthName = "RandomWalkLength";
33        private const string ThresholdName = "Threshold";
34        private const string IsAcceptedName = "IsAccepted";
35        private const string ConsecutiveRejectedSolutionsCountName = "ConsecutiveRejectedSolutions";
36        private const string LastAcceptedQualityName = "LastAcceptedQuality";
37        private const string MoveQualityName = "MoveQuality";
38        private const string CoolingName = "Cooling";
39
40
41        #endregion
42
43        #region Parameters
44        public ILookupParameter<DoubleValue> TemperatureParameter
45        {
46            get { return (ILookupParameter<DoubleValue>)Parameters[TemperatureName]; }
47        }
48        public ILookupParameter<DoubleValue> LowerTemperatureParameter
49        {
50            get { return (ILookupParameter<DoubleValue>)Parameters[LowerTemperatureName]; }
51        }
52        public ILookupParameter<DoubleValue> StartTemperatureParameter
53        {
54            get { return (ILookupParameter<DoubleValue>)Parameters[StartTemperatureName]; }
55        }
56        public ILookupParameter<DoubleValue> EndTemperatureParameter
57        {
58            get { return (ILookupParameter<DoubleValue>)Parameters[EndTemperatureName]; }
59        }
60        public ILookupParameter<IntValue> TemperatureStartIndexParameter
61        {
62            get { return (ILookupParameter<IntValue>)Parameters[TemperatureStartIndexName]; }
63        }
64        public ILookupParameter<IntValue> IterationsParameter
65        {
66            get { return (ILookupParameter<IntValue>)Parameters[IterationsName]; }
67        }
68        public ILookupParameter<IOperator> AnnealingOperatorParameter
69        {
70            get { return (ILookupParameter<IOperator>)Parameters[AnnealingOperatorName]; }
71        }
72        public ILookupParameter<IntValue> MaximumIterationsParameter
73        {
74            get { return (ILookupParameter<IntValue>)Parameters[MaximumIterationsName]; }
75        }
76        private ValueParameter<IntValue> ThresholdParameter
77        {
78            get { return (ValueParameter<IntValue>)Parameters[ThresholdName]; }
79        }
80        private ValueParameter<IntValue> RandomWalkLengthParameter
81        {
82            get { return (ValueParameter<IntValue>)Parameters[RandomWalkLengthName]; }
83        }
84        public ILookupParameter<BoolValue> IsAcceptedParameter
85        {
86            get { return (ILookupParameter<BoolValue>)Parameters[IsAcceptedName]; }
87        }
88        public ILookupParameter<IntValue> ConsecutiveRejectedSolutionsCountParameter
89        {
90            get { return (ILookupParameter<IntValue>)Parameters[ConsecutiveRejectedSolutionsCountName]; }
91        }
92        public ILookupParameter<IntValue> RandomWalkLengthNameParameter
93        {
94            get { return (ILookupParameter<IntValue>)Parameters[RandomWalkLengthName]; }
95        }
96        public ILookupParameter<IntValue> CurrentRandomWalkStepParameter
97        {
98            get { return (ILookupParameter<IntValue>)Parameters[CurrentRandomWalkStepName]; }
99        }
100        public ILookupParameter<BoolValue> CoolingParameter
101        {
102            get { return (ILookupParameter<BoolValue>)Parameters[CoolingName]; }
103        }
104        public ILookupParameter<DoubleValue> MoveQualityParameter
105        {
106            get { return (ILookupParameter<DoubleValue>)Parameters[MoveQualityName]; }
107        }
108        public ILookupParameter<DoubleValue> LastAcceptedQualityParameter
109        {
110            get { return (ILookupParameter<DoubleValue>)Parameters[LastAcceptedQualityName]; }
111        }
112
113        #endregion
114
115        public RandomWalkReheatingOperator() : base()
116        {
117            #region Create parameters
118            Parameters.Add(new LookupParameter<DoubleValue>(TemperatureName, "The current temperature."));
119            Parameters.Add(new LookupParameter<DoubleValue>(LowerTemperatureName, "The lower bound of the temperature."));
120            Parameters.Add(new LookupParameter<IntValue>(IterationsName, "The number of iterations."));
121            Parameters.Add(new LookupParameter<IOperator>(AnnealingOperatorName, "The operator that cools the temperature."));
122            Parameters.Add(new LookupParameter<IntValue>(TemperatureStartIndexName, "The index where the annealing or heating was last changed."));
123            Parameters.Add(new LookupParameter<DoubleValue>(StartTemperatureName, "The temperature from which cooling or reheating should occur."));
124            Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
125            Parameters.Add(new LookupParameter<IntValue>(MaximumIterationsName, "The maximum number of iterations which should be processed."));
126            Parameters.Add(new LookupParameter<BoolValue>(IsAcceptedName, "Whether the move was accepted or not."));
127            Parameters.Add(new LookupParameter<IntValue>(ConsecutiveRejectedSolutionsCountName, "Amount of consecutive rejected solutions."));
128            Parameters.Add(new ValueParameter<IntValue>(ThresholdName, "How many consecutive rejected solutions must occur to trigger a reheat.", new IntValue(10000)));
129            Parameters.Add(new ValueParameter<IntValue>(RandomWalkLengthName, "Amount of randomly accepted moves upon reheat.", new IntValue(1)));
130            Parameters.Add(new LookupParameter<IntValue>(CurrentRandomWalkStepName, "Current random walk step."));
131            Parameters.Add(new LookupParameter<DoubleValue>(MoveQualityName, "The value which represents the quality of a move."));
132            Parameters.Add(new LookupParameter<BoolValue>(CoolingName, "True when the temperature should be cooled, false otherwise."));
133            Parameters.Add(new LookupParameter<DoubleValue>(LastAcceptedQualityName, "Quality of last accepted solution."));
134            #endregion
135
136            Parameterize();
137        }
138
139        [StorableConstructor]
140        protected RandomWalkReheatingOperator(bool deserializing) : base(deserializing) { }
141        protected RandomWalkReheatingOperator(RandomWalkReheatingOperator original, Cloner cloner) : base(original, cloner) { }
142
143
144        public override IDeepCloneable Clone(Cloner cloner)
145        {
146            return new RandomWalkReheatingOperator(this, cloner);
147        }
148
149        public void Parameterize()
150        {
151        }
152
153        public override IOperation Apply()
154        {
155            var cooling = CoolingParameter.ActualValue.Value;
156            var quality = MoveQualityParameter.ActualValue;
157            var lastAcceptedQuality = LastAcceptedQualityParameter.ActualValue;
158            var isAccepted = IsAcceptedParameter.ActualValue.Value;
159            var consecutiveRejectedSolutionsCount = ConsecutiveRejectedSolutionsCountParameter.ActualValue;
160
161            if (cooling)
162            {
163                // add acceptance value to consecutive rejected solutions count
164                // if quality hasnt changed, we might be stuck on a plateau
165                if (!isAccepted || quality.Value.Equals(lastAcceptedQuality.Value))
166                {
167                    consecutiveRejectedSolutionsCount.Value++;
168                }
169                else
170                {
171                    consecutiveRejectedSolutionsCount.Value = 0;
172                }
173
174                // check if we are trapped in a local optimum
175                if (consecutiveRejectedSolutionsCount.Value >= ThresholdParameter.Value.Value)
176                {
177                    cooling = false;
178                    consecutiveRejectedSolutionsCount.Value = 0;
179                }
180            }
181
182
183            if (!cooling)
184            {
185                // random walk finished, start cooling again
186                if (RandomWalkLengthParameter.Value.Value <= CurrentRandomWalkStepParameter.ActualValue.Value)
187                {
188                    cooling = true;
189                    CurrentRandomWalkStepParameter.ActualValue.Value = 0;
190                }
191                else
192                {
193                    CurrentRandomWalkStepParameter.ActualValue.Value++;
194                }
195            }
196
197            if (isAccepted)
198            {
199                LastAcceptedQualityParameter.ActualValue.Value = quality.Value;
200            }
201
202            CoolingParameter.ActualValue.Value = cooling;
203            return cooling ? Cool() : Heat();
204        }
205
206        private IOperation Heat()
207        {
208            TemperatureParameter.ActualValue.Value = Double.PositiveInfinity;
209            return base.Apply();
210        }
211
212        private IOperation Cool()
213        {
214            return new OperationCollection {
215                    ExecutionContext.CreateOperation(AnnealingOperatorParameter.ActualValue),
216                    base.Apply()
217                };
218        }
219    }
220}
Note: See TracBrowser for help on using the repository browser.