Changeset 9086


Ignore:
Timestamp:
12/20/12 22:51:59 (6 years ago)
Author:
abeham
Message:

#1836: Changed reheating strategy

Location:
trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/HeuristicLab.Algorithms.SimulatedAnnealing-3.4.csproj

    r9085 r9086  
    9494  <ItemGroup>
    9595    <Reference Include="System" />
    96     <Reference Include="System.Core">
    97       <RequiredTargetFramework>3.5</RequiredTargetFramework>
    98     </Reference>
    9996    <Reference Include="System.Drawing" />
    10097    <Reference Include="System.Xml.Linq">
  • trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/SimulatedAnnealing.cs

    r9085 r9086  
    6262    private const string TemperatureChartName = "Temperature Chart";
    6363    private const string TemperatureAnalyzerName = "Temperature Analyzer";
    64     private const string ChangeInertiaName = "ChangeInertia";
     64    private const string ThresholdName = "Threshold";
     65    private const string MemorySizeName = "MemorySize";
    6566    #endregion
    6667
     
    99100      get { return (OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters[HeatingOperatorName]; }
    100101    }
    101     private ValueParameter<IntValue> ChangeInertiaParameter {
    102       get { return (ValueParameter<IntValue>) Parameters[ChangeInertiaName]; }
     102    private ValueParameter<DoubleRange> ThresholdParameter {
     103      get { return (ValueParameter<DoubleRange>) Parameters[ThresholdName]; }
     104    }
     105    private ValueParameter<IntValue> MemorySizeParameter {
     106      get { return (ValueParameter<IntValue>) Parameters[MemorySizeName]; }
    103107    }
    104108    private ValueParameter<IntValue> MaximumIterationsParameter {
     
    161165      set { AnalyzerParameter.Value = value; }
    162166    }
    163     public IntValue ChangeInertia {
    164       get { return ChangeInertiaParameter.Value; }
    165       set { ChangeInertiaParameter.Value = value; }
     167    public DoubleRange AcceptanceThreshold {
     168      get { return ThresholdParameter.Value; }
     169      set { ThresholdParameter.Value = value; }
     170    }
     171    public IntValue AcceptanceMemorySize {
     172      get { return MemorySizeParameter.Value; }
     173      set { MemorySizeParameter.Value = value; }
    166174    }
    167175    private RandomCreator RandomCreator {
     
    195203      Parameters.Add(new ValueParameter<DoubleValue>(LowerTemperatureName, "The lower bound for the temperature.", new DoubleValue(1e-6)));
    196204      Parameters.Add(new ValueParameter<MultiAnalyzer>(AnalyzerName, "The operator used to analyze each iteration.", new MultiAnalyzer()));
    197       Parameters.Add(new ValueParameter<IntValue>(ChangeInertiaName, "The inertia (= number of iterations) that the process spends before switching between heating and cooling.", new IntValue(10)));
     205      Parameters.Add(new ValueParameter<IntValue>(MemorySizeName, "The maximum size of the acceptance memory.", new IntValue(100)));
     206      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)));
    198207
    199208      var randomCreator = new RandomCreator();
     
    247256      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
    248257      mainLoop.AnnealingOperatorParameter.ActualName = AnnealingOperatorParameter.Name;
    249       mainLoop.ChangeInertiaParameter.ActualName = ChangeInertiaParameter.Name;
     258      mainLoop.MemorySizeParameter.ActualName = MemorySizeParameter.Name;
     259      mainLoop.ThresholdParameter.ActualName = ThresholdParameter.Name;
    250260      mainLoop.CoolingParameter.ActualName = CoolingName;
    251261      mainLoop.EndTemperatureParameter.ActualName = EndTemperatureName;
  • trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/SimulatedAnnealingMainLoop.cs

    r9085 r9086  
    5757    private const string IsAcceptedName = "IsAccepted";
    5858    private const string TerminateName = "Terminate";
    59     private const string ChangeInertiaName = "ChangeInertia";
     59    private const string ThresholdName = "Threshold";
     60    private const string MemorySizeName = "MemorySize";
     61    private const string AcceptanceMemoryName = "AcceptanceMemory";
    6062    #endregion
    6163
     
    127129      get { return (ILookupParameter<BoolValue>)Parameters[CoolingName]; }
    128130    }
    129     public IValueLookupParameter<IntValue> ChangeInertiaParameter {
    130       get { return (IValueLookupParameter<IntValue>)Parameters[ChangeInertiaName]; }
     131    public IValueLookupParameter<DoubleRange> ThresholdParameter {
     132      get { return (IValueLookupParameter<DoubleRange>)Parameters[ThresholdName]; }
     133    }
     134    public IValueLookupParameter<IntValue> MemorySizeParameter {
     135      get { return (IValueLookupParameter<IntValue>)Parameters[MemorySizeName]; }
    131136    }
    132137    #endregion
     
    172177      Parameters.Add(new LookupParameter<DoubleValue>(StartTemperatureName, "The temperature from which cooling or reheating should occur."));
    173178      Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
    174       Parameters.Add(new ValueLookupParameter<IntValue>(ChangeInertiaName, "The minimum iterations that need to be passed, before the process can change between heating and cooling."));
     179      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."));
     180      Parameters.Add(new ValueLookupParameter<IntValue>(MemorySizeName, "The maximum size of the acceptance memory."));
    175181      #endregion
    176182
    177183      #region Create operators
     184      var variableCreator = new VariableCreator();
    178185      var ssp1 = new SubScopesProcessor();
    179186      var analyzer1 = new Placeholder();
     
    196203      var iterationsTermination = new ConditionalBranch();
    197204
     205      variableCreator.Name = "Initialize Memory";
     206      variableCreator.CollectedValues.Add(new ValueParameter<ItemList<BoolValue>>(AcceptanceMemoryName, new ItemList<BoolValue>()));
     207
    198208      analyzer1.Name = "Analyzer";
    199209      analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
     
    220230
    221231      temperatureController.AnnealingOperatorParameter.ActualName = AnnealingOperatorParameter.Name;
    222       temperatureController.ChangeInertiaParameter.ActualName = ChangeInertiaParameter.Name;
     232      temperatureController.ThresholdParameter.ActualName = ThresholdParameter.Name;
     233      temperatureController.AcceptanceMemoryParameter.ActualName = AcceptanceMemoryName;
     234      temperatureController.MemorySizeParameter.ActualName = MemorySizeParameter.Name;
    223235      temperatureController.CoolingParameter.ActualName = CoolingParameter.Name;
    224236      temperatureController.EndTemperatureParameter.ActualName = EndTemperatureParameter.Name;
     
    253265
    254266      #region Create operator graph
    255       OperatorGraph.InitialOperator = ssp1;
     267      OperatorGraph.InitialOperator = variableCreator;
     268      variableCreator.Successor = ssp1;
    256269      ssp1.Operators.Add(analyzer1);
    257270      ssp1.Successor = ssp2;
  • trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.4/TemperatureController.cs

    r9085 r9086  
    2323
    2424using System;
     25using System.Linq;
    2526using HeuristicLab.Common;
    2627using HeuristicLab.Core;
     
    4748    private const string TemperatureName = "Temperature";
    4849    private const string IsAcceptedName = "IsAccepted";
    49     private const string ChangeInertiaName = "ChangeInertia";
     50    private const string ThresholdName = "Threshold";
     51    private const string AcceptanceMemoryName = "AcceptanceMemory";
     52    private const string MemorySizeName = "MemorySize";
    5053    #endregion
    5154
     
    8790      get { return (ILookupParameter<BoolValue>)Parameters[IsAcceptedName]; }
    8891    }
    89     public IValueLookupParameter<IntValue> ChangeInertiaParameter {
    90       get { return (IValueLookupParameter<IntValue>) Parameters[ChangeInertiaName]; }
     92    public IValueLookupParameter<DoubleRange> ThresholdParameter {
     93      get { return (IValueLookupParameter<DoubleRange>)Parameters[ThresholdName]; }
     94    }
     95    public ILookupParameter<ItemList<BoolValue>> AcceptanceMemoryParameter {
     96      get { return (ILookupParameter<ItemList<BoolValue>>)Parameters[AcceptanceMemoryName]; }
     97    }
     98    public IValueLookupParameter<IntValue> MemorySizeParameter {
     99      get { return (IValueLookupParameter<IntValue>)Parameters[MemorySizeName]; }
    91100    }
    92101    #endregion
     
    109118      Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
    110119      Parameters.Add(new LookupParameter<BoolValue>(IsAcceptedName, "Whether the move was accepted or not."));
    111       Parameters.Add(new ValueLookupParameter<IntValue>(ChangeInertiaName, "The minimum iterations that need to be passed, before the process can change between heating and cooling."));
     120      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."));
     121      Parameters.Add(new LookupParameter<ItemList<BoolValue>>(AcceptanceMemoryName, "Memorizes the last N acceptance decisions."));
     122      Parameters.Add(new ValueLookupParameter<IntValue>(MemorySizeName, "The maximum size of the acceptance memory."));
    112123    }
    113124
     
    119130      var accepted = IsAcceptedParameter.ActualValue;
    120131      var heatingOperator = HeatingOperatorParameter.ActualValue;
    121       if (accepted == null || heatingOperator == null) { // annealing in case no heating operator is given
     132      if (accepted == null || heatingOperator == null) { // perform only annealing in case no heating operator is given
    122133        return new OperationCollection {
    123134          ExecutionContext.CreateOperation(AnnealingOperatorParameter.ActualValue),
     
    127138
    128139      var cooling = CoolingParameter.ActualValue.Value;
    129       var lastChange = TemperatureStartIndexParameter.ActualValue.Value;
    130140      var iterations = IterationsParameter.ActualValue.Value;
    131       var inertia = ChangeInertiaParameter.ActualValue.Value;
     141      var ratioStart = ThresholdParameter.ActualValue.Start;
     142      var ratioEnd = ThresholdParameter.ActualValue.End;
    132143
    133       if (accepted.Value && !cooling && (iterations - (lastChange+1)) > inertia) { // temperature is heated, but should be cooled
     144      var acceptances = AcceptanceMemoryParameter.ActualValue;
     145      acceptances.Add(new BoolValue(accepted.Value));
     146      if (acceptances.Count > MemorySizeParameter.ActualValue.Value) acceptances.RemoveAt(0);
     147      var ratio = acceptances.Average(x => x.Value ? 1.0 : 0.0);
     148     
     149
     150      if (!cooling && ratio >= ratioEnd) { // temperature is heated, but should be cooled
    134151        cooling = true;
    135152        TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, iterations - 1);
    136153        StartTemperatureParameter.ActualValue.Value = TemperatureParameter.ActualValue.Value;
    137154        EndTemperatureParameter.ActualValue.Value = LowerTemperatureParameter.ActualValue.Value;
    138       } else if (!accepted.Value && cooling && (iterations - (lastChange+1)) > inertia) {  // temperature is cooled, but should be heated
     155      } else if (cooling && ratio <= ratioStart) {  // temperature is cooled, but should be heated
    139156        cooling = false;
    140157        TemperatureStartIndexParameter.ActualValue.Value = Math.Max(0, iterations - 1);
Note: See TracChangeset for help on using the changeset viewer.