Changeset 15333 for branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/RandomWalkReheatingOperator.cs

Timestamp:

08/21/17 11:17:24 (7 years ago)

Author:

jschiess

Message:

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

File:

• branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/RandomWalkReheatingOperator.cs (modified) (7 diffs)

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

@@ -29 +29 @@
         private const string TemperatureName = "Temperature";
         private const string MaximumIterationsName = "MaximumIterations";
-
-        private const string TemperatureBeforeReheatName = "TemperatureBeforeReheat";
         private const string CurrentRandomWalkStepName = "CurrentRandomWalkStep";
         private const string RandomWalkLengthName = "RandomWalkLength";
@@ -36 +34 @@
         private const string IsAcceptedName = "IsAccepted";
         private const string ConsecutiveRejectedSolutionsCountName = "ConsecutiveRejectedSolutions";
-        private const string QualitiesBeforeReheatingName = "QualitiesBeforeReheating";
-        private const string AmountOfReheatsName = "AmountOfReheats";
-        private const string RetrappedName = "Retrapped";
         private const string LastAcceptedQualityName = "LastAcceptedQuality";
-        private const string ResultsName = "Results";
         private const string MoveQualityName = "MoveQuality";
         private const string CoolingName = "Cooling";
-        private const string TabuListActiveName = "TabuListActive";
 
 
@@ -105 +98 @@
             get { return (ILookupParameter<IntValue>)Parameters[CurrentRandomWalkStepName]; }
         }
-        public ILookupParameter<DoubleValue> TemperatureBeforeReheatParameter
-        {
-            get { return (ILookupParameter<DoubleValue>)Parameters[TemperatureBeforeReheatName]; }
-        }
-        private LookupParameter<ItemList<DoubleValue>> QualitiesBeforeReheatingParameter
-        {
-            get { return (LookupParameter<ItemList<DoubleValue>>)Parameters[QualitiesBeforeReheatingName]; }
-        }
         public ILookupParameter<BoolValue> CoolingParameter
         {
@@ -124 +109 @@
         {
             get { return (ILookupParameter<DoubleValue>)Parameters[LastAcceptedQualityName]; }
-        }
-        public IValueParameter<BoolValue> TabuListActiveParameter
-        {
-            get { return (IValueParameter<BoolValue>)Parameters[TabuListActiveName];  }
         }
 
@@ -145 +126 @@
             Parameters.Add(new LookupParameter<BoolValue>(IsAcceptedName, "Whether the move was accepted or not."));
             Parameters.Add(new LookupParameter<IntValue>(ConsecutiveRejectedSolutionsCountName, "Amount of consecutive rejected solutions."));
-            Parameters.Add(new ValueParameter<IntValue>(ThresholdName, "How many consecutive rejected solutions must occur to trigger a reheat.", new IntValue(10)));
-            Parameters.Add(new ValueParameter<IntValue>(RandomWalkLengthName, "Amount of randomly accepted moves upon reheat.", new IntValue(2)));
+            Parameters.Add(new ValueParameter<IntValue>(ThresholdName, "How many consecutive rejected solutions must occur to trigger a reheat.", new IntValue(10000)));
+            Parameters.Add(new ValueParameter<IntValue>(RandomWalkLengthName, "Amount of randomly accepted moves upon reheat.", new IntValue(1)));
             Parameters.Add(new LookupParameter<IntValue>(CurrentRandomWalkStepName, "Current random walk step."));
-            Parameters.Add(new LookupParameter<DoubleValue>(TemperatureBeforeReheatName, "Temperature before the reheat occured."));
-            Parameters.Add(new LookupParameter<ItemList<DoubleValue>>(QualitiesBeforeReheatingName, "Quality of last optimum."));
             Parameters.Add(new LookupParameter<DoubleValue>(MoveQualityName, "The value which represents the quality of a move."));
             Parameters.Add(new LookupParameter<BoolValue>(CoolingName, "True when the temperature should be cooled, false otherwise."));
             Parameters.Add(new LookupParameter<DoubleValue>(LastAcceptedQualityName, "Quality of last accepted solution."));
-            Parameters.Add(new ValueParameter<BoolValue>(TabuListActiveName, "Determines whether visiting a 'frozen' quality instantly triggers a reheat or not", new BoolValue(true)));
-
             #endregion
 
@@ -176 +153 @@
         public override IOperation Apply()
         {
-            var isAccepted = IsAcceptedParameter.ActualValue.Value;
-            var consecutiveRejectedCount = ConsecutiveRejectedSolutionsCountParameter.ActualValue;
             var cooling = CoolingParameter.ActualValue.Value;
-            var frozenSolutions = QualitiesBeforeReheatingParameter.ActualValue;
             var quality = MoveQualityParameter.ActualValue;
             var lastAcceptedQuality = LastAcceptedQualityParameter.ActualValue;
-            var tabuListActive = TabuListActiveParameter.Value.Value;
-
-            if(isAccepted)
+            var isAccepted = IsAcceptedParameter.ActualValue.Value;
+            var consecutiveRejectedSolutionsCount = ConsecutiveRejectedSolutionsCountParameter.ActualValue;
+
+            if (cooling)
+            {
+                // add acceptance value to consecutive rejected solutions count
+                // if quality hasnt changed, we might be stuck on a plateau
+                if (!isAccepted || quality.Value.Equals(lastAcceptedQuality.Value))
+                {
+                    consecutiveRejectedSolutionsCount.Value++;
+                }
+                else
+                {
+                    consecutiveRejectedSolutionsCount.Value = 0;
+                }
+
+                // check if we are trapped in a local optimum
+                if (consecutiveRejectedSolutionsCount.Value >= ThresholdParameter.Value.Value)
+                {
+                    cooling = false;
+                    consecutiveRejectedSolutionsCount.Value = 0;
+                }
+            }
+
+
+            if (!cooling)
+            {
+                // random walk finished, start cooling again
+                if (RandomWalkLengthParameter.Value.Value <= CurrentRandomWalkStepParameter.ActualValue.Value)
+                {
+                    cooling = true;
+                    CurrentRandomWalkStepParameter.ActualValue.Value = 0;
+                }
+                else
+                {
+                    CurrentRandomWalkStepParameter.ActualValue.Value++;
+                }
+            }
+
+            if (isAccepted)
             {
                 LastAcceptedQualityParameter.ActualValue.Value = quality.Value;
             }
 
-            if (cooling)
-            { 
-                // check if we are re-trapped
-                if (isAccepted && frozenSolutions.Any(frozen => frozen.Value.Equals(quality.Value)) && tabuListActive)
-                {
-                   cooling = false;
-
-                    IntValue retrapped = new IntValue(0);
-                    IResult retrappedAmount;
-                    var results = (ResultCollection)ExecutionContext.Parent.Parent.Scope.Variables[ResultsName].Value;
-                    if (results.TryGetValue(RetrappedName, out retrappedAmount))
-                    {
-                        retrapped = (IntValue)retrappedAmount.Value;
-                        retrapped.Value += 1;
-                    }
-                    else
-                    {
-                        retrapped.Value += 1;
-                        results.Add(new Result(RetrappedName, retrapped));
-                    }
-                    // remember local optimum
-                    frozenSolutions.Add(new DoubleValue(lastAcceptedQuality.Value));
-                }
-                else
-                {
-                    // add acceptance value to consecutive rejected solutions count
-                    consecutiveRejectedCount.Value = !IsAcceptedParameter.ActualValue.Value ? consecutiveRejectedCount.Value + 1 : 0;
-
-                    // check if we are trapped in a new local optimum
-                    if (consecutiveRejectedCount.Value == ThresholdParameter.Value.Value)
-                    {
-                        cooling = false;
-                        consecutiveRejectedCount.Value = 0;
-                        // remember local optimum
-                        frozenSolutions.Add(new DoubleValue(lastAcceptedQuality.Value));
-                    }
-                }
-            }
-            else
-            {
-                // random walk not yet finished
-                if (RandomWalkLengthParameter.Value.Value != CurrentRandomWalkStepParameter.ActualValue.Value)
-                {
-                    if (CurrentRandomWalkStepParameter.ActualValue.Value == 0)
-                    {
-                        DebugIncreaseReheatCounter();
-                    }
-                    CurrentRandomWalkStepParameter.ActualValue.Value++;
-                }
-                else
-                {
-                    // random walk finished start cooling again
-                    cooling = true;
-                    TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, IterationsParameter.ActualValue.Value - 1);
-                    StartTemperatureParameter.ActualValue.Value = TemperatureBeforeReheatParameter.ActualValue.Value;
-                    EndTemperatureParameter.ActualValue.Value = LowerTemperatureParameter.ActualValue.Value;
-                    consecutiveRejectedCount.Value = isAccepted ? 0 : 1;
-                    CurrentRandomWalkStepParameter.ActualValue.Value = 0;
-
-                }
-            }
             CoolingParameter.ActualValue.Value = cooling;
             return cooling ? Cool() : Heat();
         }
 
-        private void DebugIncreaseReheatCounter()
-        {
-            var reheats = new IntValue(0);
-            var frozen = new ItemList<DoubleValue>();
-            var results = (ResultCollection)ExecutionContext.Parent.Parent.Scope.Variables[ResultsName].Value;
-            IResult amountOfReheats;
-            IResult frozenSolutions;
-            if (results.TryGetValue(AmountOfReheatsName, out amountOfReheats))
-            {
-                reheats = (IntValue)amountOfReheats.Value;
-                reheats.Value += 1;
-            }
-            else
-            {
-                reheats.Value += 1;
-                results.Add(new Result(AmountOfReheatsName, reheats));
-            }
-
-            if (results.TryGetValue(QualitiesBeforeReheatingName, out frozenSolutions))
-            {
-                
-                frozen = (ItemList<DoubleValue>) frozenSolutions.Value;
-                frozen.Add(new DoubleValue(LastAcceptedQualityParameter.ActualValue.Value));
-            }
-            else
-            {
-                frozen.Add(new DoubleValue(LastAcceptedQualityParameter.ActualValue.Value));
-                results.Add(new Result(QualitiesBeforeReheatingName, frozen));
-            }
-        }
-
         private IOperation Heat()
         {
@@ -293 +212 @@
         private IOperation Cool()
         {
-            TemperatureBeforeReheatParameter.ActualValue.Value = TemperatureParameter.ActualValue.Value;
             return new OperationCollection {
                     ExecutionContext.CreateOperation(AnnealingOperatorParameter.ActualValue),