1 | using HeuristicLab.Operators;
|
---|
2 | using System;
|
---|
3 | using System.Collections.Generic;
|
---|
4 | using System.Linq;
|
---|
5 | using System.Text;
|
---|
6 | using System.Threading.Tasks;
|
---|
7 | using HeuristicLab.Common;
|
---|
8 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
9 | using HeuristicLab.Core;
|
---|
10 | using HeuristicLab.Data;
|
---|
11 | using HeuristicLab.Parameters;
|
---|
12 | using HeuristicLab.Optimization;
|
---|
13 | using HeuristicLab.PluginInfrastructure;
|
---|
14 | using HeuristicLab.Analysis;
|
---|
15 |
|
---|
16 | namespace HeuristicLab.Algorithms.SimulatedAnnealing
|
---|
17 | {
|
---|
18 | [Item("AcceptanceRatioReheatingOperator", "Reheats the temperature if the acceptance is below a threshold.")]
|
---|
19 | [StorableClass]
|
---|
20 | public class AcceptanceRatioReheatingOperator : 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 UpperTemperatureName = "UpperTemperature";
|
---|
33 | private const string ReheatingOperatorName = "ReheatingOperator";
|
---|
34 | private const string ThresholdName = "Threshold";
|
---|
35 | private const string MemorySizeName = "MemorySize";
|
---|
36 | private const string CoolingName = "Cooling";
|
---|
37 | private const string IsAcceptedName = "IsAccepted";
|
---|
38 | private const string AcceptanceMemoryName = "AcceptanceMemory";
|
---|
39 | private const string AverageAcceptanceRatioName = "AverageAcceptanceRatio";
|
---|
40 |
|
---|
41 |
|
---|
42 | #endregion
|
---|
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 ValueLookupParameter<DoubleValue> UpperTemperatureParameter
|
---|
77 | {
|
---|
78 | get { return (ValueLookupParameter<DoubleValue>)Parameters[UpperTemperatureName]; }
|
---|
79 | }
|
---|
80 | private IConstrainedValueParameter<IDiscreteDoubleValueModifier> ReheatingOperatorParameter
|
---|
81 | {
|
---|
82 | get { return (IConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters[ReheatingOperatorName]; }
|
---|
83 | }
|
---|
84 | private ValueParameter<DoubleRange> ThresholdParameter
|
---|
85 | {
|
---|
86 | get { return (ValueParameter<DoubleRange>)Parameters[ThresholdName]; }
|
---|
87 | }
|
---|
88 | private ValueParameter<IntValue> MemorySizeParameter
|
---|
89 | {
|
---|
90 | get { return (ValueParameter<IntValue>)Parameters[MemorySizeName]; }
|
---|
91 | }
|
---|
92 | public ILookupParameter<BoolValue> CoolingParameter
|
---|
93 | {
|
---|
94 | get { return (ILookupParameter<BoolValue>)Parameters[CoolingName]; }
|
---|
95 | }
|
---|
96 | public ILookupParameter<BoolValue> IsAcceptedParameter
|
---|
97 | {
|
---|
98 | get { return (ILookupParameter<BoolValue>)Parameters[IsAcceptedName]; }
|
---|
99 | }
|
---|
100 | public ILookupParameter<ItemList<BoolValue>> AcceptanceMemoryParameter
|
---|
101 | {
|
---|
102 | get { return (ILookupParameter<ItemList<BoolValue>>)Parameters[AcceptanceMemoryName]; }
|
---|
103 | }
|
---|
104 | public ILookupParameter<DoubleValue> AverageAcceptanceRatioParameter
|
---|
105 | {
|
---|
106 | get { return (ILookupParameter<DoubleValue>)Parameters[AverageAcceptanceRatioName]; }
|
---|
107 | }
|
---|
108 |
|
---|
109 | #endregion
|
---|
110 |
|
---|
111 | public AcceptanceRatioReheatingOperator() : base()
|
---|
112 | {
|
---|
113 | #region Create parameters
|
---|
114 | Parameters.Add(new LookupParameter<DoubleValue>(TemperatureName, "The current temperature."));
|
---|
115 | Parameters.Add(new LookupParameter<DoubleValue>(LowerTemperatureName, "The lower bound of the temperature."));
|
---|
116 | Parameters.Add(new LookupParameter<IntValue>(IterationsName, "The number of iterations."));
|
---|
117 | Parameters.Add(new LookupParameter<IOperator>(AnnealingOperatorName, "The operator that cools the temperature."));
|
---|
118 | Parameters.Add(new LookupParameter<IntValue>(TemperatureStartIndexName, "The index where the annealing or heating was last changed."));
|
---|
119 | Parameters.Add(new LookupParameter<DoubleValue>(StartTemperatureName, "The temperature from which cooling or reheating should occur."));
|
---|
120 | Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
|
---|
121 | Parameters.Add(new LookupParameter<IntValue>(MaximumIterationsName, "The maximum number of iterations which should be processed."));
|
---|
122 | Parameters.Add(new LookupParameter<BoolValue>(IsAcceptedName, "Whether the move was accepted or not."));
|
---|
123 | Parameters.Add(new LookupParameter<ItemList<BoolValue>>(AcceptanceMemoryName, "Memorizes the last N acceptance decisions."));
|
---|
124 | Parameters.Add(new LookupParameter<BoolValue>(CoolingName, "True when the temperature should be cooled, false otherwise."));
|
---|
125 | Parameters.Add(new ValueLookupParameter<DoubleValue>(UpperTemperatureName, "The upper bound of the temperature.", "InitialTemperature"));
|
---|
126 | Parameters.Add(new ConstrainedValueParameter<IDiscreteDoubleValueModifier>(ReheatingOperatorName, "The operator that reheats the temperature."));
|
---|
127 | Parameters.Add(new ValueParameter<DoubleRange>(ThresholdName, "The threshold controls the temperature. If the average ratio of accepted moves goes below the start of the range the temperature is heated. If the the average ratio of accepted moves goes beyond the end of the range the temperature is cooled again.", new DoubleRange(0.01, 0.1)));
|
---|
128 | Parameters.Add(new ValueParameter<IntValue>(MemorySizeName, "The maximum size of the acceptance memory.", new IntValue(100)));
|
---|
129 | Parameters.Add(new LookupParameter<DoubleValue>(AverageAcceptanceRatioName, "Average acceptance over full acceptance memory."));
|
---|
130 | #endregion
|
---|
131 |
|
---|
132 | foreach (var op in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name))
|
---|
133 | {
|
---|
134 | ReheatingOperatorParameter.ValidValues.Add((IDiscreteDoubleValueModifier) op);
|
---|
135 | }
|
---|
136 | Parameterize();
|
---|
137 | }
|
---|
138 |
|
---|
139 | [StorableConstructor]
|
---|
140 | protected AcceptanceRatioReheatingOperator(bool deserializing) : base(deserializing) { }
|
---|
141 | protected AcceptanceRatioReheatingOperator(AcceptanceRatioReheatingOperator original, Cloner cloner) : base(original, cloner) { }
|
---|
142 |
|
---|
143 |
|
---|
144 | public override IDeepCloneable Clone(Cloner cloner)
|
---|
145 | {
|
---|
146 | return new AcceptanceRatioReheatingOperator(this, cloner);
|
---|
147 | }
|
---|
148 |
|
---|
149 | public void Parameterize()
|
---|
150 | {
|
---|
151 | foreach (var op in ReheatingOperatorParameter.ValidValues)
|
---|
152 | {
|
---|
153 | op.IndexParameter.ActualName = IterationsName;
|
---|
154 | op.IndexParameter.Hidden = true;
|
---|
155 | op.StartIndexParameter.Value = null;
|
---|
156 | op.StartIndexParameter.ActualName = TemperatureStartIndexName;
|
---|
157 | op.EndIndexParameter.ActualName = MaximumIterationsParameter.Name;
|
---|
158 | op.ValueParameter.ActualName = TemperatureName;
|
---|
159 | op.ValueParameter.Hidden = true;
|
---|
160 | op.StartValueParameter.ActualName = StartTemperatureName;
|
---|
161 | op.StartValueParameter.Hidden = true;
|
---|
162 | op.EndValueParameter.ActualName = EndTemperatureName;
|
---|
163 | op.EndValueParameter.Hidden = true;
|
---|
164 | }
|
---|
165 | }
|
---|
166 |
|
---|
167 | public override IOperation Apply()
|
---|
168 | {
|
---|
169 | var isAccepted = IsAcceptedParameter.ActualValue;
|
---|
170 | var acceptances = AcceptanceMemoryParameter.ActualValue;
|
---|
171 | var cooling = CoolingParameter.ActualValue.Value;
|
---|
172 | var ratioAmount = AverageAcceptanceRatioParameter.ActualValue;
|
---|
173 |
|
---|
174 | acceptances.Add(isAccepted);
|
---|
175 |
|
---|
176 | ratioAmount.Value += isAccepted.Value ? 1 : 0;
|
---|
177 |
|
---|
178 |
|
---|
179 | if (acceptances.Count > MemorySizeParameter.Value.Value) {
|
---|
180 | ratioAmount.Value -= acceptances.ElementAt(0).Value ? 1 : 0;
|
---|
181 | acceptances.RemoveAt(0);
|
---|
182 | }
|
---|
183 |
|
---|
184 | // only reheat when at least MemorySizeParameter.Value iterations have passed
|
---|
185 | if (acceptances.Count == MemorySizeParameter.Value.Value)
|
---|
186 | {
|
---|
187 | var ratio = ratioAmount.Value / MemorySizeParameter.Value.Value;
|
---|
188 | var ratioStart = ThresholdParameter.Value.Start;
|
---|
189 | var ratioEnd = ThresholdParameter.Value.End;
|
---|
190 |
|
---|
191 | if (!cooling && ratio >= ratioEnd)
|
---|
192 | {
|
---|
193 | // if we are heating, but should be cooling
|
---|
194 | cooling = true;
|
---|
195 | TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, IterationsParameter.ActualValue.Value - 1);
|
---|
196 | StartTemperatureParameter.ActualValue.Value = TemperatureParameter.ActualValue.Value;
|
---|
197 | EndTemperatureParameter.ActualValue.Value = LowerTemperatureParameter.ActualValue.Value;
|
---|
198 | }
|
---|
199 | else if (cooling && ratio <= ratioStart)
|
---|
200 | {
|
---|
201 | // if we are cooling but should be heating
|
---|
202 | cooling = false;
|
---|
203 | TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, IterationsParameter.ActualValue.Value - 1);
|
---|
204 | StartTemperatureParameter.ActualValue.Value = TemperatureParameter.ActualValue.Value;
|
---|
205 | EndTemperatureParameter.ActualValue.Value = UpperTemperatureParameter.ActualValue.Value;
|
---|
206 | }
|
---|
207 |
|
---|
208 | CoolingParameter.ActualValue.Value = cooling;
|
---|
209 | }
|
---|
210 | return cooling ? Cool() : Heat();
|
---|
211 | }
|
---|
212 |
|
---|
213 | private IOperation Heat()
|
---|
214 | {
|
---|
215 | return new OperationCollection {
|
---|
216 | ExecutionContext.CreateOperation(ReheatingOperatorParameter.Value),
|
---|
217 | base.Apply()
|
---|
218 | };
|
---|
219 | }
|
---|
220 |
|
---|
221 | private IOperation Cool()
|
---|
222 | {
|
---|
223 | return new OperationCollection {
|
---|
224 | ExecutionContext.CreateOperation(AnnealingOperatorParameter.ActualValue),
|
---|
225 | base.Apply()
|
---|
226 | };
|
---|
227 | }
|
---|
228 | }
|
---|
229 | }
|
---|