Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15315


Ignore:
Timestamp:
08/09/17 10:37:45 (7 years ago)
Author:
jschiess
Message:

#1836 SA reheating strategies:
+ Finalized strategies
+ Added temperature initializer mechanism

Location:
branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4
Files:
4 added
5 edited

Legend:

Unmodified
Added
Removed

  • branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/AcceptanceRatioReheatingOperator.cs

    r15001 r15315  
    1616namespace HeuristicLab.Algorithms.SimulatedAnnealing
    1717{
    18     [Item("AcceptanceRatioReheatingOperator", "Reheats the temperature if the acceptance is below a threshold.")]
     18    [Item("AcceptanceRatioReheatingOperator", "Reheats the temperature if the acceptance is below a threshold until it is above another one.")]
    1919    [StorableClass]
    2020    public class AcceptanceRatioReheatingOperator : SingleSuccessorOperator, IReheatingOperator
    … …  
    3838        private const string AcceptanceMemoryName = "AcceptanceMemory";
    3939        private const string AverageAcceptanceRatioName = "AverageAcceptanceRatio";
     40        private const string ReheatWindowSizeName = "ReheatWindowSize";
    4041
    4142
    … …  
    105106        {
    106107            get { return (ILookupParameter<DoubleValue>)Parameters[AverageAcceptanceRatioName]; }
     108        }
     109        public IValueParameter<IntValue> ReheatWindowSizeParameter
     110        {
     111            get { return (IValueParameter<IntValue>)Parameters[ReheatWindowSizeName]; }
    107112        }
    108113
    … …  
    128133            Parameters.Add(new ValueParameter<IntValue>(MemorySizeName, "The maximum size of the acceptance memory.", new IntValue(100)));
    129134            Parameters.Add(new LookupParameter<DoubleValue>(AverageAcceptanceRatioName, "Average acceptance over full acceptance memory."));
     135            Parameters.Add(new ValueParameter<IntValue>(ReheatWindowSizeName, "The amount of iterations each reheat needs to heat the current temperature to upper temperature.", new IntValue(10000)));
    130136            #endregion
    131137
    … …  
    204210                    StartTemperatureParameter.ActualValue.Value = TemperatureParameter.ActualValue.Value;
    205211                    EndTemperatureParameter.ActualValue.Value = UpperTemperatureParameter.ActualValue.Value;
     212                    ReheatingOperatorParameter.Value.EndIndexParameter.Value = new IntValue(
     213                        Math.Min(MaximumIterationsParameter.ActualValue.Value, IterationsParameter.ActualValue.Value + ReheatWindowSizeParameter.Value.Value));
    206214                }
    207215

  • branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/ConsecutiveRejectionTemperatureResetOperator.cs

    r15001 r15315  
    1616namespace HeuristicLab.Algorithms.SimulatedAnnealing
    1717{
    18     [Item("ConsecutiveRejectionTemperatureResetOperator", "The operator resets the temperature to X when N consecutive solutions are rejected. X is calculated by BaseResetTemperature * (MultiplyWithEachReheat to the power of the current number of reheats).")]
     18    [Item("ConsecutiveRejectionTemperatureResetOperator", "The operator resets the temperature to the ResetTemperature when N consecutive solutions are rejected.")]
    1919    [StorableClass]
    2020    public class ConsecutiveRejectionTemperatureResetOperator : SingleSuccessorOperator, IReheatingOperator
    … …  
    3434        private const string IsAcceptedName = "IsAccepted";
    3535        private const string ConsecutiveRejectedSolutionsCountName = "ConsecutiveRejectedSolutions";
    36         private const string BaseResetTemperatureName = "BaseResetTemperature";
     36        private const string ResetTemperatureName = "ResetTemperature";
    3737        #endregion
    3838
    3939        #region Parameters
    40         private ValueLookupParameter<DoubleValue> BaseResetTemperatureParameter
     40        private ValueLookupParameter<DoubleValue> ResetTemperatureParameter
    4141        {
    42             get { return (ValueLookupParameter<DoubleValue>)Parameters[BaseResetTemperatureName]; }
     42            get { return (ValueLookupParameter<DoubleValue>)Parameters[ResetTemperatureName]; }
    4343        }
    4444        public ILookupParameter<DoubleValue> TemperatureParameter
    … …  
    102102            Parameters.Add(new LookupParameter<IntValue>(ConsecutiveRejectedSolutionsCountName, "Amount of consecutive rejected solutions."));
    103103            Parameters.Add(new ValueParameter<IntValue>(ThresholdName, "How many consecutive rejected solutions must occur to trigger a reheat.", new IntValue(10)));
    104             Parameters.Add(new ValueLookupParameter<DoubleValue>(BaseResetTemperatureName, "The base reset temperature.", InitialTemperatureName));
     104            Parameters.Add(new ValueLookupParameter<DoubleValue>(ResetTemperatureName, "The base reset temperature.", InitialTemperatureName));
    105105         
    106106            #endregion
    … …  
    138138        private IOperation Heat()
    139139        {
    140             var temperature = Math.Max(BaseResetTemperatureParameter.ActualValue.Value, TemperatureParameter.ActualValue.Value);
     140            var temperature = Math.Max(ResetTemperatureParameter.ActualValue.Value, TemperatureParameter.ActualValue.Value);
    141141
    142142            TemperatureParameter.ActualValue.Value = temperature;

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

    r15001 r15315  
    5151        private const string MaximumIterationsName = "MaximumIterations";
    5252        private const string InitialTemperatureName = "InitialTemperature";
    53         private const string InitialAcceptanceRateName = "InitialAcceptanceRate";
    5453        private const string LowerTemperatureName = "LowerTemperature";
    5554        private const string AnalyzerName = "Analyzer";
    … …  
    6564        private const string TemperatureChartName = "Temperature Chart";
    6665        private const string TemperatureAnalyzerName = "Temperature Analyzer";
     66        private const string TemperatureInitializerName = "TemperatureInitializer";
    6767        #endregion
    6868
    … …  
    111111            get { return (IConstrainedValueParameter<IReheatingOperator>)Parameters[ReheatingOperatorName]; }
    112112        }
     113        public IConstrainedValueParameter<ITemperatureInitializer> TemperatureInitializerParameter
     114        {
     115            get { return (IConstrainedValueParameter<ITemperatureInitializer>)Parameters[TemperatureInitializerName]; }
     116        }
    113117
    114118        private ValueParameter<IntValue> MaximumIterationsParameter
    115119        {
    116120            get { return (ValueParameter<IntValue>)Parameters[MaximumIterationsName]; }
    117         }
    118         private ValueParameter<DoubleValue> InitialAcceptanceRateParameter
    119         {
    120             get { return (ValueParameter<DoubleValue>)Parameters[InitialAcceptanceRateName]; }
    121121        }
    122122        private ValueParameter<DoubleValue> LowerTemperatureParameter
    … …  
    167167            set { ReheatingOperatorParameter.Value = value; }
    168168        }
     169        public ITemperatureInitializer TemperatureInitializer
     170        {
     171            get { return TemperatureInitializerParameter.Value; }
     172            set { TemperatureInitializerParameter.Value = value; }
     173        }
    169174
    170175        public IntValue MaximumIterations
    … …  
    172177            get { return MaximumIterationsParameter.Value; }
    173178            set { MaximumIterationsParameter.Value = value; }
    174         }
    175         public DoubleValue InitialAcceptanceRate
    176         {
    177             get { return InitialAcceptanceRateParameter.Value; }
    178             set { InitialAcceptanceRateParameter.Value = value; }
    179179        }
    180180        public DoubleValue LowerTemperature
    … …  
    219219            Parameters.Add(new ConstrainedValueParameter<IDiscreteDoubleValueModifier>(AnnealingOperatorName, "The operator used to cool the temperature."));
    220220            Parameters.Add(new ConstrainedValueParameter<IReheatingOperator>(ReheatingOperatorName, "The operator used to reheat the temperature, if necessary."));
     221            Parameters.Add(new ConstrainedValueParameter<ITemperatureInitializer>(TemperatureInitializerName, "The operator used to initialize the temperature."));
    221222            Parameters.Add(new ValueParameter<IntValue>(MaximumIterationsName, "The maximum number of generations which should be processed.", new IntValue(10000)));
    222             Parameters.Add(new ValueParameter<DoubleValue>(InitialAcceptanceRateName, "The initial acceptance rate of average-sized hills used to calculate the initial temperature", new DoubleValue(0.4)));
    223223            Parameters.Add(new ValueParameter<DoubleValue>(LowerTemperatureName, "The lower bound for the temperature.", new DoubleValue(1e-6)));
    224224            Parameters.Add(new ValueParameter<MultiAnalyzer>(AnalyzerName, "The operator used to analyze each iteration.", new MultiAnalyzer()));
    … …  
    300300            {
    301301                AnnealingOperatorParameter.ValidValues.Add(op);
     302            }
     303
     304            foreach(var op in ApplicationManager.Manager.GetInstances<ITemperatureInitializer>().OrderBy(x => x.Name))
     305            {
     306                TemperatureInitializerParameter.ValidValues.Add(op);
    302307            }
    303308

  • branches/jschiess/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/SimulatedAnnealingMainLoop.cs

    r15001 r15315  
    4949        private const string CoolingName = "Cooling";
    5050        private const string InitialTemperatureName = "InitialTemperature";
    51         private const string InitialAcceptanceRateName = "InitialAcceptanceRate";
    5251        private const string StartTemperatureName = "StartTemperature";
    5352        private const string EndTemperatureName = "EndTemperature";
    … …  
    6564        private const string LastQualityName = "LastQuality";
    6665        private const string UphillMovesMemoryName = "UphillMovesMemory";
     66        private const string TemperatureBeforeReheatName = "TemperatureBeforeReheat";
     67        private const string CurrentRandomWalkStepName = "CurrentRandomWalkStep";
     68        private const string QualitiesBeforeReheatingName = "QualitiesBeforeReheating";
     69        private const string LastAcceptedQualityName = "LastAcceptedQuality";
     70        private const string TemperatureInitializerName = "TemperatureInitializer";
     71        private const string TemperatureInitializedName = "TemperatureInitialized";
     72
    6773        #endregion
    6874
    … …  
    9197        {
    9298            get { return (ILookupParameter<DoubleValue>)Parameters[InitialTemperatureName]; }
    93         }
    94         public ILookupParameter<DoubleValue> InitialAcceptanceRateParameter
    95         {
    96             get { return (ILookupParameter<DoubleValue>)Parameters[InitialAcceptanceRateName]; }
    9799        }
    98100        public ILookupParameter<DoubleValue> MoveQualityParameter
    … …  
    200202            Parameters.Add(new ValueLookupParameter<IOperator>(AnnealingOperatorName, "The operator that cools the temperature."));
    201203            Parameters.Add(new ValueLookupParameter<IOperator>(ReheatingOperatorName, "The operator that reheats the temperature if necessary."));
     204            Parameters.Add(new ValueLookupParameter<IOperator>(TemperatureInitializerName, "The operator that initialized the temperature."));
    202205
    203206            Parameters.Add(new ValueLookupParameter<IOperator>(AnalyzerName, "The operator used to analyze each generation."));
    … …  
    206209
    207210            Parameters.Add(new LookupParameter<DoubleValue>(InitialTemperatureName, "The initial temperature."));
    208             Parameters.Add(new LookupParameter<DoubleValue>(InitialAcceptanceRateName, "The initial acceptance rate of average-sized hills used to calculate the initial temperature."));
    209211            Parameters.Add(new LookupParameter<IntValue>(TemperatureStartIndexName, "The index where the annealing or heating was last changed."));
    210212            Parameters.Add(new LookupParameter<BoolValue>(CoolingName, "True when the temperature should be cooled, false otherwise."));
    211213            Parameters.Add(new LookupParameter<DoubleValue>(StartTemperatureName, "The temperature from which cooling or reheating should occur."));
    212214            Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
     215
    213216
    214217            #endregion
    … …  
    237240
    238241            variableCreator.Name = "Initialize Memory";
     242            variableCreator.CollectedValues.Add(new ValueParameter<BoolValue>(TemperatureInitializedName, new BoolValue(false)));
    239243            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(AverageAcceptanceRatioName, new DoubleValue(0d)));
    240244            variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(ConsecutiveRejectedSolutionsCountName, new IntValue(0)));
    … …  
    242246            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(LastQualityName, new DoubleValue(-1)));
    243247            variableCreator.CollectedValues.Add(new ValueParameter<ItemList<DoubleValue>>(UphillMovesMemoryName, new ItemList<DoubleValue>()));
     248            variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(CurrentRandomWalkStepName, new IntValue(0)));
     249            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(TemperatureBeforeReheatName, new DoubleValue(0)));
     250            variableCreator.CollectedValues.Add(new ValueParameter<ItemList<DoubleValue>>(QualitiesBeforeReheatingName, new ItemList<DoubleValue>()));
     251            variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(LastAcceptedQualityName, new DoubleValue(-1)));
    244252
    245253            analyzer1.Name = "Analyzer";
    … …  
    267275
    268276           
    269 
    270277            subScopesRemover.RemoveAllSubScopes = true;
    271278

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

    r15001 r15315  
    3434namespace HeuristicLab.Algorithms.SimulatedAnnealing
    3535{
    36     [Item("TemperatureController", "Decides based on information from the heatingoperator, whether to use cooling or heating and calls the appropriate operator.")]
     36    [Item("TemperatureController", "Responsible to first initialize the temperature and then control the temperature.")]
    3737    [StorableClass]
    3838    public class TemperatureController : SingleSuccessorOperator
    … …  
    5858        private const string MaximizationName = "Maximization";
    5959        private const string MoveQualityName = "MoveQuality";
    60         private const string InitialAcceptanceRateName = "InitialAcceptanceRate";
    61         private const string ResultsName = "Results";
    62         private const string CalculatedInitialTemperatureName = "CalculatedInitialTemperature";
    63 
     60        private const string TemperatureBeforeReheatName = "TemperatureBeforeReheat";
     61        private const string CurrentRandomWalkStepName = "CurrentRandomWalkStep";
     62        private const string QualitiesBeforeReheatingName = "QualitiesBeforeReheating";
     63        private const string LastAcceptedQualityName = "LastAcceptedQuality";
     64        private const string TemperatureInitializerName = "TemperatureInitializer";
     65        private const string TemperatureInitializedName = "TemperatureInitialized";
    6466        #endregion
    6567
    6668        #region Parameter Properties
    67         public ILookupParameter<DoubleValue> TemperatureParameter
    68         {
    69             get { return (ILookupParameter<DoubleValue>)Parameters[TemperatureName]; }
    70         }
    71         public ILookupParameter<DoubleValue> InitialTemperatureParameter
    72         {
    73             get { return (ILookupParameter<DoubleValue>)Parameters[InitialTemperatureName]; }
    74         }
    75         public IValueLookupParameter<DoubleValue> LowerTemperatureParameter
    76         {
    77             get { return (IValueLookupParameter<DoubleValue>)Parameters[LowerTemperatureName]; }
    78         }
    79         public ILookupParameter<DoubleValue> StartTemperatureParameter
    80         {
    81             get { return (ILookupParameter<DoubleValue>)Parameters[StartTemperatureName]; }
    82         }
    83         public ILookupParameter<DoubleValue> EndTemperatureParameter
    84         {
    85             get { return (ILookupParameter<DoubleValue>)Parameters[EndTemperatureName]; }
    86         }
    87         public ILookupParameter<IntValue> TemperatureStartIndexParameter
    88         {
    89             get { return (ILookupParameter<IntValue>)Parameters[TemperatureStartIndexName]; }
    90         }
    91         public ILookupParameter<BoolValue> CoolingParameter
    92         {
    93             get { return (ILookupParameter<BoolValue>)Parameters[CoolingName]; }
    94         }
    95         public ILookupParameter<IntValue> IterationsParameter
    96         {
    97             get { return (ILookupParameter<IntValue>)Parameters[IterationsName]; }
    98         }
    99         public IValueLookupParameter<IntValue> MaximumIterationsParameter
    100         {
    101             get { return (IValueLookupParameter<IntValue>)Parameters[MaximumIterationsName]; }
    102         }
    103         public IValueLookupParameter<IOperator> AnnealingOperatorParameter
    104         {
    105             get { return (IValueLookupParameter<IOperator>)Parameters[AnnealingOperatorName]; }
    106         }
    10769        public IValueLookupParameter<IReheatingOperator> ReheatingOperatorParameter
    10870        {
    10971            get { return (IValueLookupParameter<IReheatingOperator>)Parameters[ReheatingOperatorName]; }
    11072        }
    111         public ILookupParameter<BoolValue> IsAcceptedParameter
     73        public IValueLookupParameter<ITemperatureInitializer> TemperatureInitializerParameter
    11274        {
    113             get { return (ILookupParameter<BoolValue>)Parameters[IsAcceptedName]; }
     75            get { return (IValueLookupParameter<ITemperatureInitializer>)Parameters[TemperatureInitializerName]; }
    11476        }
    115         public ILookupParameter<ItemList<BoolValue>> AcceptanceMemoryParameter
     77        public ILookupParameter<BoolValue> TemperatureInitializedParameter
    11678        {
    117             get { return (ILookupParameter<ItemList<BoolValue>>)Parameters[AcceptanceMemoryName]; }
    118         }
    119         public ILookupParameter<ItemList<DoubleValue>> UphillMovesMemoryParameter
    120         {
    121             get { return (ILookupParameter<ItemList<DoubleValue>>)Parameters[UphillMovesMemoryName]; }
    122         }
    123         public ILookupParameter<DoubleValue> MoveQualityParameter
    124         {
    125             get { return (ILookupParameter<DoubleValue>)Parameters[MoveQualityName]; }
    126         }
    127         public ILookupParameter<DoubleValue> LastQualityParameter
    128         {
    129             get { return (ILookupParameter<DoubleValue>)Parameters[LastQualityName]; }
    130         }
    131         public IValueLookupParameter<BoolValue> MaximizationParameter
    132         {
    133             get { return (IValueLookupParameter<BoolValue>)Parameters[MaximizationName]; }
    134         }
    135         public ILookupParameter<DoubleValue> InitialAcceptanceRateParameter
    136         {
    137             get { return (ILookupParameter<DoubleValue>)Parameters[InitialAcceptanceRateName]; }
    138         }
    139         public ILookupParameter<IntValue> ConsecutiveRejectedSolutionsCountParameter
    140         {
    141             get { return (ILookupParameter<IntValue>)Parameters[ConsecutiveRejectedSolutionsCountName]; }
    142         }
    143         public ILookupParameter<DoubleValue> AverageAcceptanceRatioParameter
    144         {
    145             get { return (ILookupParameter<DoubleValue>)Parameters[AverageAcceptanceRatioName]; }
     79            get { return (ILookupParameter<BoolValue>)Parameters[TemperatureInitializedName]; }
    14680        }
    14781        #endregion
    … …  
    171105            Parameters.Add(new LookupParameter<DoubleValue>(MoveQualityName, "The value which represents the quality of a move."));
    172106            Parameters.Add(new LookupParameter<DoubleValue>(LastQualityName, "The value which represents the quality of the last move."));
    173             Parameters.Add(new LookupParameter<DoubleValue>(InitialAcceptanceRateName, "The initial acceptance rate of average-sized hills used to calculate the initial temperature."));
    174107            Parameters.Add(new LookupParameter<IntValue>(ConsecutiveRejectedSolutionsCountName, "Amount of consecutive rejected solutions."));
    175108            Parameters.Add(new LookupParameter<DoubleValue>(AverageAcceptanceRatioName, "Average acceptance over full acceptance memory."));
     109            Parameters.Add(new LookupParameter<IntValue>(CurrentRandomWalkStepName, "Current random walk step."));
     110            Parameters.Add(new LookupParameter<DoubleValue>(TemperatureBeforeReheatName, "Temperature before the reheat occured."));
     111            Parameters.Add(new LookupParameter<ItemList<DoubleValue>>(QualitiesBeforeReheatingName, "List of qualities where the algorithm has been stuck."));
     112            Parameters.Add(new LookupParameter<DoubleValue>(LastAcceptedQualityName, "Quality of last accepted solution."));
     113
     114            Parameters.Add(new ValueLookupParameter<ITemperatureInitializer>(TemperatureInitializerName, "The operator that initilized the temperature."));
     115            Parameters.Add(new LookupParameter<BoolValue>(TemperatureInitializedName, "True, if the temperature has already been initialized."));
    176116
    177117        }
    … …  
    184124        public override IOperation Apply()
    185125        {
    186             var uphillMoves = UphillMovesMemoryParameter.ActualValue;
    187             if (!InitialTemperatureFound())
     126
     127            if (!TemperatureInitializedParameter.ActualValue.Value)
    188128            {
    189                 return findInitialTemperature();
    190             }else
     129                return new OperationCollection
     130                {
     131                    ExecutionContext.CreateOperation(TemperatureInitializerParameter.ActualValue),
     132                    base.Apply()
     133                };
     134            }
     135            else
    191136            {
    192137                return new OperationCollection {
    … …  
    196141            }
    197142        }
    198 
    199         private IOperation findInitialTemperature()
    200         {
    201             var currentQuality = MoveQualityParameter.ActualValue.Value;
    202             var lastQuality = LastQualityParameter.ActualValue.Value;
    203             var isMaximation = MaximizationParameter.ActualValue.Value;
    204             var hillMemory = UphillMovesMemoryParameter.ActualValue;
    205            
    206             if(lastQuality != -1)
    207             {
    208                 double hillSize = CalculateHillSize(lastQuality, currentQuality, isMaximation);
    209                
    210                 if(hillSize > 0)
    211                 {
    212                     hillMemory.Add(new DoubleValue(hillSize));
    213                     if(InitialTemperatureFound())
    214                     {
    215                         var results = (ResultCollection)ExecutionContext.Parent.Scope.Variables[ResultsName].Value;
    216                         var initialTemperature = CalculateInitialTemperatureBasedOnAverageHillSize(hillMemory);
    217                         InitialTemperatureParameter.ActualValue.Value = initialTemperature;
    218                         TemperatureParameter.ActualValue.Value = initialTemperature;
    219                         TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, IterationsParameter.ActualValue.Value - 1);
    220                         StartTemperatureParameter.ActualValue.Value = TemperatureParameter.ActualValue.Value;
    221                         results.Add(new Result(CalculatedInitialTemperatureName, new DoubleValue(initialTemperature)));
    222                     }
    223                 }
    224             }
    225 
    226             LastQualityParameter.ActualValue.Value = currentQuality;
    227             return base.Apply();
    228         }
    229 
    230         private double CalculateInitialTemperatureBasedOnAverageHillSize(ItemList<DoubleValue> hillMemory)
    231         {
    232             var averageHillSize = hillMemory.Average(x => x.Value);
    233             return -(averageHillSize / Math.Log(InitialAcceptanceRateParameter.ActualValue.Value));
    234 
    235         }
    236 
    237         private double CalculateHillSize(double lastQuality, double currentQuality, bool isMaximation)
    238         {
    239             return isMaximation ? lastQuality - currentQuality : currentQuality - lastQuality;
    240         }
    241 
    242         private bool InitialTemperatureFound()
    243         {
    244             return UphillMovesMemoryParameter.ActualValue.Count == 100;
    245         }
    246143    }
    247144}
Note: See TracChangeset for help on using the changeset viewer.