Changeset 9086

Timestamp:

12/20/12 22:51:59 (11 years ago)

Author:

abeham

Message:

#1836: Changed reheating strategy

Location:

trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4

Files:

• HeuristicLab.Algorithms.SimulatedAnnealing-3.4.csproj (modified) (1 diff)
• SimulatedAnnealing.cs (modified) (5 diffs)
• SimulatedAnnealingMainLoop.cs (modified) (6 diffs)
• TemperatureController.cs (modified) (6 diffs)

trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/HeuristicLab.Algorithms.SimulatedAnnealing-3.4.csproj

@@ -94 +94 @@
   <ItemGroup>
     <Reference Include="System" />
-    <Reference Include="System.Core">
-      <RequiredTargetFramework>3.5</RequiredTargetFramework>
-    </Reference>
     <Reference Include="System.Drawing" />
     <Reference Include="System.Xml.Linq">

trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/SimulatedAnnealing.cs

@@ -62 +62 @@
     private const string TemperatureChartName = "Temperature Chart";
     private const string TemperatureAnalyzerName = "Temperature Analyzer";
-    private const string ChangeInertiaName = "ChangeInertia";
+    private const string ThresholdName = "Threshold";
+    private const string MemorySizeName = "MemorySize";
     #endregion
 
@@ -99 +100 @@
       get { return (OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters[HeatingOperatorName]; }
     }
-    private ValueParameter<IntValue> ChangeInertiaParameter {
-      get { return (ValueParameter<IntValue>) Parameters[ChangeInertiaName]; }
+    private ValueParameter<DoubleRange> ThresholdParameter {
+      get { return (ValueParameter<DoubleRange>) Parameters[ThresholdName]; }
+    }
+    private ValueParameter<IntValue> MemorySizeParameter {
+      get { return (ValueParameter<IntValue>) Parameters[MemorySizeName]; }
     } 
     private ValueParameter<IntValue> MaximumIterationsParameter {
@@ -161 +165 @@
       set { AnalyzerParameter.Value = value; }
     }
-    public IntValue ChangeInertia {
-      get { return ChangeInertiaParameter.Value; }
-      set { ChangeInertiaParameter.Value = value; }
+    public DoubleRange AcceptanceThreshold {
+      get { return ThresholdParameter.Value; }
+      set { ThresholdParameter.Value = value; }
+    }
+    public IntValue AcceptanceMemorySize {
+      get { return MemorySizeParameter.Value; }
+      set { MemorySizeParameter.Value = value; }
     }
     private RandomCreator RandomCreator {
@@ -195 +203 @@
       Parameters.Add(new ValueParameter<DoubleValue>(LowerTemperatureName, "The lower bound for the temperature.", new DoubleValue(1e-6)));
       Parameters.Add(new ValueParameter<MultiAnalyzer>(AnalyzerName, "The operator used to analyze each iteration.", new MultiAnalyzer()));
-      Parameters.Add(new ValueParameter<IntValue>(ChangeInertiaName, "The inertia (= number of iterations) that the process spends before switching between heating and cooling.", new IntValue(10)));
+      Parameters.Add(new ValueParameter<IntValue>(MemorySizeName, "The maximum size of the acceptance memory.", new IntValue(100)));
+      Parameters.Add(new ValueParameter<DoubleRange>(ThresholdName, "The threshold controls the temperature in case a heating operator is specified. 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.05, 0.2)));
 
       var randomCreator = new RandomCreator();
@@ -247 +256 @@
       mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
       mainLoop.AnnealingOperatorParameter.ActualName = AnnealingOperatorParameter.Name;
-      mainLoop.ChangeInertiaParameter.ActualName = ChangeInertiaParameter.Name;
+      mainLoop.MemorySizeParameter.ActualName = MemorySizeParameter.Name;
+      mainLoop.ThresholdParameter.ActualName = ThresholdParameter.Name;
       mainLoop.CoolingParameter.ActualName = CoolingName;
       mainLoop.EndTemperatureParameter.ActualName = EndTemperatureName;

trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/SimulatedAnnealingMainLoop.cs

@@ -57 +57 @@
     private const string IsAcceptedName = "IsAccepted";
     private const string TerminateName = "Terminate";
-    private const string ChangeInertiaName = "ChangeInertia";
+    private const string ThresholdName = "Threshold";
+    private const string MemorySizeName = "MemorySize";
+    private const string AcceptanceMemoryName = "AcceptanceMemory";
     #endregion
 
@@ -127 +129 @@
       get { return (ILookupParameter<BoolValue>)Parameters[CoolingName]; }
     }
-    public IValueLookupParameter<IntValue> ChangeInertiaParameter {
-      get { return (IValueLookupParameter<IntValue>)Parameters[ChangeInertiaName]; }
+    public IValueLookupParameter<DoubleRange> ThresholdParameter {
+      get { return (IValueLookupParameter<DoubleRange>)Parameters[ThresholdName]; }
+    }
+    public IValueLookupParameter<IntValue> MemorySizeParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters[MemorySizeName]; }
     }
     #endregion
@@ -172 +177 @@
       Parameters.Add(new LookupParameter<DoubleValue>(StartTemperatureName, "The temperature from which cooling or reheating should occur."));
       Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
-      Parameters.Add(new ValueLookupParameter<IntValue>(ChangeInertiaName, "The minimum iterations that need to be passed, before the process can change between heating and cooling."));
+      Parameters.Add(new ValueLookupParameter<DoubleRange>(ThresholdName, "The threshold controls the temperature in case a heating operator is specified. 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."));
+      Parameters.Add(new ValueLookupParameter<IntValue>(MemorySizeName, "The maximum size of the acceptance memory."));
       #endregion
 
       #region Create operators
+      var variableCreator = new VariableCreator();
       var ssp1 = new SubScopesProcessor();
       var analyzer1 = new Placeholder();
@@ -196 +203 @@
       var iterationsTermination = new ConditionalBranch();
 
+      variableCreator.Name = "Initialize Memory";
+      variableCreator.CollectedValues.Add(new ValueParameter<ItemList<BoolValue>>(AcceptanceMemoryName, new ItemList<BoolValue>()));
+
       analyzer1.Name = "Analyzer";
       analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
@@ -220 +230 @@
 
       temperatureController.AnnealingOperatorParameter.ActualName = AnnealingOperatorParameter.Name;
-      temperatureController.ChangeInertiaParameter.ActualName = ChangeInertiaParameter.Name;
+      temperatureController.ThresholdParameter.ActualName = ThresholdParameter.Name;
+      temperatureController.AcceptanceMemoryParameter.ActualName = AcceptanceMemoryName;
+      temperatureController.MemorySizeParameter.ActualName = MemorySizeParameter.Name;
       temperatureController.CoolingParameter.ActualName = CoolingParameter.Name;
       temperatureController.EndTemperatureParameter.ActualName = EndTemperatureParameter.Name;
@@ -253 +265 @@
 
       #region Create operator graph
-      OperatorGraph.InitialOperator = ssp1;
+      OperatorGraph.InitialOperator = variableCreator;
+      variableCreator.Successor = ssp1;
       ssp1.Operators.Add(analyzer1);
       ssp1.Successor = ssp2;

trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/TemperatureController.cs

@@ -23 +23 @@
 
 using System;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -47 +48 @@
     private const string TemperatureName = "Temperature";
     private const string IsAcceptedName = "IsAccepted";
-    private const string ChangeInertiaName = "ChangeInertia";
+    private const string ThresholdName = "Threshold";
+    private const string AcceptanceMemoryName = "AcceptanceMemory";
+    private const string MemorySizeName = "MemorySize";
     #endregion
 
@@ -87 +90 @@
       get { return (ILookupParameter<BoolValue>)Parameters[IsAcceptedName]; }
     }
-    public IValueLookupParameter<IntValue> ChangeInertiaParameter {
-      get { return (IValueLookupParameter<IntValue>) Parameters[ChangeInertiaName]; }
+    public IValueLookupParameter<DoubleRange> ThresholdParameter {
+      get { return (IValueLookupParameter<DoubleRange>)Parameters[ThresholdName]; }
+    }
+    public ILookupParameter<ItemList<BoolValue>> AcceptanceMemoryParameter {
+      get { return (ILookupParameter<ItemList<BoolValue>>)Parameters[AcceptanceMemoryName]; }
+    }
+    public IValueLookupParameter<IntValue> MemorySizeParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters[MemorySizeName]; }
     }
     #endregion
@@ -109 +118 @@
       Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
       Parameters.Add(new LookupParameter<BoolValue>(IsAcceptedName, "Whether the move was accepted or not."));
-      Parameters.Add(new ValueLookupParameter<IntValue>(ChangeInertiaName, "The minimum iterations that need to be passed, before the process can change between heating and cooling."));
+      Parameters.Add(new ValueLookupParameter<DoubleRange>(ThresholdName, "The threshold controls the temperature in case a heating operator is specified. 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."));
+      Parameters.Add(new LookupParameter<ItemList<BoolValue>>(AcceptanceMemoryName, "Memorizes the last N acceptance decisions."));
+      Parameters.Add(new ValueLookupParameter<IntValue>(MemorySizeName, "The maximum size of the acceptance memory."));
     }
 
@@ -119 +130 @@
       var accepted = IsAcceptedParameter.ActualValue;
       var heatingOperator = HeatingOperatorParameter.ActualValue;
-      if (accepted == null || heatingOperator == null) { // annealing in case no heating operator is given
+      if (accepted == null || heatingOperator == null) { // perform only annealing in case no heating operator is given
         return new OperationCollection {
           ExecutionContext.CreateOperation(AnnealingOperatorParameter.ActualValue),
@@ -127 +138 @@
 
       var cooling = CoolingParameter.ActualValue.Value;
-      var lastChange = TemperatureStartIndexParameter.ActualValue.Value;
       var iterations = IterationsParameter.ActualValue.Value;
-      var inertia = ChangeInertiaParameter.ActualValue.Value;
+      var ratioStart = ThresholdParameter.ActualValue.Start;
+      var ratioEnd = ThresholdParameter.ActualValue.End;
 
-      if (accepted.Value && !cooling && (iterations - (lastChange+1)) > inertia) { // temperature is heated, but should be cooled
+      var acceptances = AcceptanceMemoryParameter.ActualValue;
+      acceptances.Add(new BoolValue(accepted.Value));
+      if (acceptances.Count > MemorySizeParameter.ActualValue.Value) acceptances.RemoveAt(0);
+      var ratio = acceptances.Average(x => x.Value ? 1.0 : 0.0);
+      
+
+      if (!cooling && ratio >= ratioEnd) { // temperature is heated, but should be cooled
         cooling = true;
         TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, iterations - 1);
         StartTemperatureParameter.ActualValue.Value = TemperatureParameter.ActualValue.Value;
         EndTemperatureParameter.ActualValue.Value = LowerTemperatureParameter.ActualValue.Value;
-      } else if (!accepted.Value && cooling && (iterations - (lastChange+1)) > inertia) {  // temperature is cooled, but should be heated
+      } else if (cooling && ratio <= ratioStart) {  // temperature is cooled, but should be heated
         cooling = false;
         TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, iterations - 1);