Changeset 15001 for branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/TemperatureController.cs

Timestamp:

05/30/17 07:50:37 (7 years ago)

Author:

jschiess

Message:

#1836 SA reheating strategies: Newest version of reheating

File:

• branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/TemperatureController.cs (modified) (8 diffs)

branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/TemperatureController.cs

@@ -30 +30 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Optimization;
 
 namespace HeuristicLab.Algorithms.SimulatedAnnealing
@@ -41 +42 @@
         private const string AnnealingOperatorName = "AnnealingOperator";
         private const string MaximumIterationsName = "MaximumIterations";
+        private const string InitialTemperatureName = "InitialTemperature";
         private const string LowerTemperatureName = "LowerTemperature";
         private const string IterationsName = "Iterations";
@@ -49 +51 @@
         private const string TemperatureName = "Temperature";
         private const string IsAcceptedName = "IsAccepted";
+        private const string ConsecutiveRejectedSolutionsCountName = "ConsecutiveRejectedSolutions";
+        private const string AverageAcceptanceRatioName = "AverageAcceptanceRatio";
         private const string AcceptanceMemoryName = "AcceptanceMemory";
-        private const string ReheatCountName = "ReheatCount";
+        private const string LastQualityName = "LastQuality";
+        private const string UphillMovesMemoryName = "UphillMovesMemory";
+        private const string MaximizationName = "Maximization";
+        private const string MoveQualityName = "MoveQuality";
+        private const string InitialAcceptanceRateName = "InitialAcceptanceRate";
+        private const string ResultsName = "Results";
+        private const string CalculatedInitialTemperatureName = "CalculatedInitialTemperature";
+
         #endregion
 
@@ -58 +69 @@
             get { return (ILookupParameter<DoubleValue>)Parameters[TemperatureName]; }
         }
+        public ILookupParameter<DoubleValue> InitialTemperatureParameter
+        {
+            get { return (ILookupParameter<DoubleValue>)Parameters[InitialTemperatureName]; }
+        }
         public IValueLookupParameter<DoubleValue> LowerTemperatureParameter
         {
@@ -102 +117 @@
             get { return (ILookupParameter<ItemList<BoolValue>>)Parameters[AcceptanceMemoryName]; }
         }
-        public ILookupParameter<IntValue> ReheatCountParameter
-        {
-            get { return (ILookupParameter<IntValue>)Parameters[ReheatCountName]; }
+        public ILookupParameter<ItemList<DoubleValue>> UphillMovesMemoryParameter
+        {
+            get { return (ILookupParameter<ItemList<DoubleValue>>)Parameters[UphillMovesMemoryName]; }
+        }
+        public ILookupParameter<DoubleValue> MoveQualityParameter
+        {
+            get { return (ILookupParameter<DoubleValue>)Parameters[MoveQualityName]; }
+        }
+        public ILookupParameter<DoubleValue> LastQualityParameter
+        {
+            get { return (ILookupParameter<DoubleValue>)Parameters[LastQualityName]; }
+        }
+        public IValueLookupParameter<BoolValue> MaximizationParameter
+        {
+            get { return (IValueLookupParameter<BoolValue>)Parameters[MaximizationName]; }
+        }
+        public ILookupParameter<DoubleValue> InitialAcceptanceRateParameter
+        {
+            get { return (ILookupParameter<DoubleValue>)Parameters[InitialAcceptanceRateName]; }
+        }
+        public ILookupParameter<IntValue> ConsecutiveRejectedSolutionsCountParameter
+        {
+            get { return (ILookupParameter<IntValue>)Parameters[ConsecutiveRejectedSolutionsCountName]; }
+        }
+        public ILookupParameter<DoubleValue> AverageAcceptanceRatioParameter
+        {
+            get { return (ILookupParameter<DoubleValue>)Parameters[AverageAcceptanceRatioName]; }
         }
         #endregion
@@ -118 +157 @@
             Parameters.Add(new LookupParameter<IntValue>(IterationsName, "The number of iterations."));
             Parameters.Add(new ValueLookupParameter<IntValue>(MaximumIterationsName, "The maximum number of iterations which should be processed."));
+            Parameters.Add(new ValueLookupParameter<BoolValue>(MaximizationName, "True if the problem is a maximization problem, otherwise false."));
             Parameters.Add(new ValueLookupParameter<IOperator>(AnnealingOperatorName, "The operator that cools the temperature."));
             Parameters.Add(new ValueLookupParameter<IReheatingOperator>(ReheatingOperatorName, "The operator that reheats the temperature if necessary."));
@@ -126 +166 @@
             Parameters.Add(new LookupParameter<BoolValue>(IsAcceptedName, "Whether the move was accepted or not."));
             Parameters.Add(new LookupParameter<ItemList<BoolValue>>(AcceptanceMemoryName, "Memorizes the last N acceptance decisions."));
-            Parameters.Add(new LookupParameter<IntValue>(ReheatCountName, "The number of reheats."));
+            Parameters.Add(new LookupParameter<DoubleValue>(InitialTemperatureName, "The initial temperature."));
+
+            Parameters.Add(new LookupParameter<ItemList<DoubleValue>>(UphillMovesMemoryName, "Memorizes the last 100 uphill moves."));
+            Parameters.Add(new LookupParameter<DoubleValue>(MoveQualityName, "The value which represents the quality of a move."));
+            Parameters.Add(new LookupParameter<DoubleValue>(LastQualityName, "The value which represents the quality of the last move."));
+            Parameters.Add(new LookupParameter<DoubleValue>(InitialAcceptanceRateName, "The initial acceptance rate of average-sized hills used to calculate the initial temperature."));
+            Parameters.Add(new LookupParameter<IntValue>(ConsecutiveRejectedSolutionsCountName, "Amount of consecutive rejected solutions."));
+            Parameters.Add(new LookupParameter<DoubleValue>(AverageAcceptanceRatioName, "Average acceptance over full acceptance memory."));
+
         }
 
@@ -136 +184 @@
         public override IOperation Apply()
         {
-            return new OperationCollection {
+            var uphillMoves = UphillMovesMemoryParameter.ActualValue;
+            if (!InitialTemperatureFound())
+            {
+                return findInitialTemperature();
+            }else
+            {
+                return new OperationCollection {
                     ExecutionContext.CreateOperation(ReheatingOperatorParameter.ActualValue),
                     base.Apply()
                 };
+            }
+        }
+
+        private IOperation findInitialTemperature()
+        {
+            var currentQuality = MoveQualityParameter.ActualValue.Value;
+            var lastQuality = LastQualityParameter.ActualValue.Value;
+            var isMaximation = MaximizationParameter.ActualValue.Value;
+            var hillMemory = UphillMovesMemoryParameter.ActualValue;
+            
+            if(lastQuality != -1)
+            {
+                double hillSize = CalculateHillSize(lastQuality, currentQuality, isMaximation);
+                
+                if(hillSize > 0)
+                {
+                    hillMemory.Add(new DoubleValue(hillSize));
+                    if(InitialTemperatureFound())
+                    {
+                        var results = (ResultCollection)ExecutionContext.Parent.Scope.Variables[ResultsName].Value;
+                        var initialTemperature = CalculateInitialTemperatureBasedOnAverageHillSize(hillMemory);
+                        InitialTemperatureParameter.ActualValue.Value = initialTemperature;
+                        TemperatureParameter.ActualValue.Value = initialTemperature;
+                        TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, IterationsParameter.ActualValue.Value - 1);
+                        StartTemperatureParameter.ActualValue.Value = TemperatureParameter.ActualValue.Value;
+                        results.Add(new Result(CalculatedInitialTemperatureName, new DoubleValue(initialTemperature)));
+                    }
+                }
+            }
+
+            LastQualityParameter.ActualValue.Value = currentQuality;
+            return base.Apply();
+        }
+
+        private double CalculateInitialTemperatureBasedOnAverageHillSize(ItemList<DoubleValue> hillMemory)
+        {
+            var averageHillSize = hillMemory.Average(x => x.Value);
+            return -(averageHillSize / Math.Log(InitialAcceptanceRateParameter.ActualValue.Value));
+
+        }
+
+        private double CalculateHillSize(double lastQuality, double currentQuality, bool isMaximation)
+        {
+            return isMaximation ? lastQuality - currentQuality : currentQuality - lastQuality;
+        }
+
+        private bool InitialTemperatureFound()
+        {
+            return UphillMovesMemoryParameter.ActualValue.Count == 100;
         }
     }