| 1 | #region License Information
|
|---|
| 2 | /* HeuristicLab
|
|---|
| 3 | * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
|---|
| 4 | *
|
|---|
| 5 | * This file is part of HeuristicLab.
|
|---|
| 6 | *
|
|---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
|---|
| 8 | * it under the terms of the GNU General Public License as published by
|
|---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
|---|
| 10 | * (at your option) any later version.
|
|---|
| 11 | *
|
|---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
|---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|---|
| 15 | * GNU General Public License for more details.
|
|---|
| 16 | *
|
|---|
| 17 | * You should have received a copy of the GNU General Public License
|
|---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
|---|
| 19 | */
|
|---|
| 20 | #endregion
|
|---|
| 21 |
|
|---|
| 22 | using HeuristicLab.Common;
|
|---|
| 23 | using HeuristicLab.Core;
|
|---|
| 24 | using HeuristicLab.Data;
|
|---|
| 25 | using HeuristicLab.Operators;
|
|---|
| 26 | using HeuristicLab.Optimization.Operators;
|
|---|
| 27 | using HeuristicLab.Parameters;
|
|---|
| 28 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
|---|
| 29 |
|
|---|
| 30 | namespace HeuristicLab.Algorithms.SimulatedAnnealing {
|
|---|
| 31 | [Item("SimulatedAnnealingMainLoop", "An operator which represents the main loop of a simulated annealing algorithm.")]
|
|---|
| 32 | [StorableClass]
|
|---|
| 33 | public sealed class SimulatedAnnealingMainLoop : AlgorithmOperator {
|
|---|
| 34 | #region Strings
|
|---|
| 35 | private const string MoveGeneratorName = "MoveGenerator";
|
|---|
| 36 | private const string MoveEvaluatorName = "MoveEvaluator";
|
|---|
| 37 | private const string MoveMakerName = "MoveMaker";
|
|---|
| 38 | private const string AnnealingOperatorName = "AnnealingOperator";
|
|---|
| 39 | private const string HeatingOperatorName = "HeatingOperator";
|
|---|
| 40 | private const string MaximumIterationsName = "MaximumIterations";
|
|---|
| 41 | private const string UpperTemperatureName = "UpperTemperature";
|
|---|
| 42 | private const string LowerTemperatureName = "LowerTemperature";
|
|---|
| 43 | private const string AnalyzerName = "Analyzer";
|
|---|
| 44 | private const string RandomName = "Random";
|
|---|
| 45 | private const string EvaluatedMovesName = "EvaluatedMoves";
|
|---|
| 46 | private const string IterationsName = "Iterations";
|
|---|
| 47 | private const string TemperatureStartIndexName = "TemperatureStartIndex";
|
|---|
| 48 | private const string CoolingName = "Cooling";
|
|---|
| 49 | private const string StartTemperatureName = "StartTemperature";
|
|---|
| 50 | private const string EndTemperatureName = "EndTemperature";
|
|---|
| 51 | private const string TemperatureName = "Temperature";
|
|---|
| 52 | private const string ResultsName = "Results";
|
|---|
| 53 | private const string MaximizationName = "Maximization";
|
|---|
| 54 | private const string QualityName = "Quality";
|
|---|
| 55 | private const string BestKnownQualityName = "BestKnownQuality";
|
|---|
| 56 | private const string MoveQualityName = "MoveQuality";
|
|---|
| 57 | private const string IsAcceptedName = "IsAccepted";
|
|---|
| 58 | private const string TerminateName = "Terminate";
|
|---|
| 59 | private const string ThresholdName = "Threshold";
|
|---|
| 60 | private const string MemorySizeName = "MemorySize";
|
|---|
| 61 | private const string AcceptanceMemoryName = "AcceptanceMemory";
|
|---|
| 62 | #endregion
|
|---|
| 63 |
|
|---|
| 64 | #region Parameter properties
|
|---|
| 65 | public IValueLookupParameter<IRandom> RandomParameter {
|
|---|
| 66 | get { return (IValueLookupParameter<IRandom>)Parameters[RandomName]; }
|
|---|
| 67 | }
|
|---|
| 68 | public IValueLookupParameter<BoolValue> MaximizationParameter {
|
|---|
| 69 | get { return (IValueLookupParameter<BoolValue>)Parameters[MaximizationName]; }
|
|---|
| 70 | }
|
|---|
| 71 | public ILookupParameter<DoubleValue> QualityParameter {
|
|---|
| 72 | get { return (ILookupParameter<DoubleValue>)Parameters[QualityName]; }
|
|---|
| 73 | }
|
|---|
| 74 | public IValueLookupParameter<DoubleValue> BestKnownQualityParameter {
|
|---|
| 75 | get { return (IValueLookupParameter<DoubleValue>)Parameters[BestKnownQualityName]; }
|
|---|
| 76 | }
|
|---|
| 77 | public ILookupParameter<DoubleValue> MoveQualityParameter {
|
|---|
| 78 | get { return (ILookupParameter<DoubleValue>)Parameters[MoveQualityName]; }
|
|---|
| 79 | }
|
|---|
| 80 | public ILookupParameter<DoubleValue> TemperatureParameter {
|
|---|
| 81 | get { return (ILookupParameter<DoubleValue>)Parameters[TemperatureName]; }
|
|---|
| 82 | }
|
|---|
| 83 | public IValueLookupParameter<DoubleValue> UpperTemperatureParameter {
|
|---|
| 84 | get { return (IValueLookupParameter<DoubleValue>)Parameters[UpperTemperatureName]; }
|
|---|
| 85 | }
|
|---|
| 86 | public IValueLookupParameter<DoubleValue> LowerTemperatureParameter {
|
|---|
| 87 | get { return (IValueLookupParameter<DoubleValue>)Parameters[LowerTemperatureName]; }
|
|---|
| 88 | }
|
|---|
| 89 | public ILookupParameter<IntValue> IterationsParameter {
|
|---|
| 90 | get { return (ILookupParameter<IntValue>)Parameters[IterationsName]; }
|
|---|
| 91 | }
|
|---|
| 92 | public IValueLookupParameter<IntValue> MaximumIterationsParameter {
|
|---|
| 93 | get { return (IValueLookupParameter<IntValue>)Parameters[MaximumIterationsName]; }
|
|---|
| 94 | }
|
|---|
| 95 | public IValueLookupParameter<IOperator> MoveGeneratorParameter {
|
|---|
| 96 | get { return (IValueLookupParameter<IOperator>)Parameters[MoveGeneratorName]; }
|
|---|
| 97 | }
|
|---|
| 98 | public IValueLookupParameter<IOperator> MoveEvaluatorParameter {
|
|---|
| 99 | get { return (IValueLookupParameter<IOperator>)Parameters[MoveEvaluatorName]; }
|
|---|
| 100 | }
|
|---|
| 101 | public IValueLookupParameter<IOperator> MoveMakerParameter {
|
|---|
| 102 | get { return (IValueLookupParameter<IOperator>)Parameters[MoveMakerName]; }
|
|---|
| 103 | }
|
|---|
| 104 | public IValueLookupParameter<IOperator> AnnealingOperatorParameter {
|
|---|
| 105 | get { return (IValueLookupParameter<IOperator>)Parameters[AnnealingOperatorName]; }
|
|---|
| 106 | }
|
|---|
| 107 | public IValueLookupParameter<IOperator> HeatingOperatorParameter {
|
|---|
| 108 | get { return (IValueLookupParameter<IOperator>)Parameters[HeatingOperatorName]; }
|
|---|
| 109 | }
|
|---|
| 110 | public IValueLookupParameter<IOperator> AnalyzerParameter {
|
|---|
| 111 | get { return (IValueLookupParameter<IOperator>)Parameters[AnalyzerName]; }
|
|---|
| 112 | }
|
|---|
| 113 | public IValueLookupParameter<VariableCollection> ResultsParameter {
|
|---|
| 114 | get { return (IValueLookupParameter<VariableCollection>)Parameters[ResultsName]; }
|
|---|
| 115 | }
|
|---|
| 116 | public ILookupParameter<IntValue> EvaluatedMovesParameter {
|
|---|
| 117 | get { return (ILookupParameter<IntValue>)Parameters[EvaluatedMovesName]; }
|
|---|
| 118 | }
|
|---|
| 119 | public ILookupParameter<DoubleValue> StartTemperatureParameter {
|
|---|
| 120 | get { return (ILookupParameter<DoubleValue>)Parameters[StartTemperatureName]; }
|
|---|
| 121 | }
|
|---|
| 122 | public ILookupParameter<DoubleValue> EndTemperatureParameter {
|
|---|
| 123 | get { return (ILookupParameter<DoubleValue>)Parameters[EndTemperatureName]; }
|
|---|
| 124 | }
|
|---|
| 125 | public ILookupParameter<IntValue> TemperatureStartIndexParameter {
|
|---|
| 126 | get { return (ILookupParameter<IntValue>)Parameters[TemperatureStartIndexName]; }
|
|---|
| 127 | }
|
|---|
| 128 | public ILookupParameter<BoolValue> CoolingParameter {
|
|---|
| 129 | get { return (ILookupParameter<BoolValue>)Parameters[CoolingName]; }
|
|---|
| 130 | }
|
|---|
| 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]; }
|
|---|
| 136 | }
|
|---|
| 137 | #endregion
|
|---|
| 138 |
|
|---|
| 139 | [StorableConstructor]
|
|---|
| 140 | private SimulatedAnnealingMainLoop(bool deserializing) : base(deserializing) { }
|
|---|
| 141 | private SimulatedAnnealingMainLoop(SimulatedAnnealingMainLoop original, Cloner cloner)
|
|---|
| 142 | : base(original, cloner) {
|
|---|
| 143 | }
|
|---|
| 144 | public override IDeepCloneable Clone(Cloner cloner) {
|
|---|
| 145 | return new SimulatedAnnealingMainLoop(this, cloner);
|
|---|
| 146 | }
|
|---|
| 147 | public SimulatedAnnealingMainLoop()
|
|---|
| 148 | : base() {
|
|---|
| 149 | Initialize();
|
|---|
| 150 | }
|
|---|
| 151 |
|
|---|
| 152 | private void Initialize() {
|
|---|
| 153 | #region Create parameters
|
|---|
| 154 | Parameters.Add(new ValueLookupParameter<IRandom>(RandomName, "A pseudo random number generator."));
|
|---|
| 155 | Parameters.Add(new ValueLookupParameter<BoolValue>(MaximizationName, "True if the problem is a maximization problem, otherwise false."));
|
|---|
| 156 | Parameters.Add(new LookupParameter<DoubleValue>(QualityName, "The value which represents the quality of a solution."));
|
|---|
| 157 | Parameters.Add(new ValueLookupParameter<DoubleValue>(BestKnownQualityName, "The best known quality value found so far."));
|
|---|
| 158 | Parameters.Add(new LookupParameter<DoubleValue>(MoveQualityName, "The value which represents the quality of a move."));
|
|---|
| 159 | Parameters.Add(new LookupParameter<DoubleValue>(TemperatureName, "The current temperature."));
|
|---|
| 160 | Parameters.Add(new ValueLookupParameter<DoubleValue>(UpperTemperatureName, "The upper bound of the temperature."));
|
|---|
| 161 | Parameters.Add(new ValueLookupParameter<DoubleValue>(LowerTemperatureName, "The lower bound of the temperature."));
|
|---|
| 162 | Parameters.Add(new LookupParameter<IntValue>(IterationsName, "The number of iterations."));
|
|---|
| 163 | Parameters.Add(new ValueLookupParameter<IntValue>(MaximumIterationsName, "The maximum number of iterations which should be processed."));
|
|---|
| 164 |
|
|---|
| 165 | Parameters.Add(new ValueLookupParameter<IOperator>(MoveGeneratorName, "The operator that generates the moves."));
|
|---|
| 166 | Parameters.Add(new ValueLookupParameter<IOperator>(MoveEvaluatorName, "The operator that evaluates a move."));
|
|---|
| 167 | Parameters.Add(new ValueLookupParameter<IOperator>(MoveMakerName, "The operator that performs a move and updates the quality."));
|
|---|
| 168 | Parameters.Add(new ValueLookupParameter<IOperator>(AnnealingOperatorName, "The operator that cools the temperature."));
|
|---|
| 169 | Parameters.Add(new ValueLookupParameter<IOperator>(HeatingOperatorName, "The operator that heats the temperature."));
|
|---|
| 170 |
|
|---|
| 171 | Parameters.Add(new ValueLookupParameter<IOperator>(AnalyzerName, "The operator used to analyze each generation."));
|
|---|
| 172 | Parameters.Add(new ValueLookupParameter<VariableCollection>(ResultsName, "The variable collection where results should be stored."));
|
|---|
| 173 | Parameters.Add(new LookupParameter<IntValue>(EvaluatedMovesName, "The number of evaluated moves."));
|
|---|
| 174 |
|
|---|
| 175 | Parameters.Add(new LookupParameter<IntValue>(TemperatureStartIndexName, "The index where the annealing or heating was last changed."));
|
|---|
| 176 | Parameters.Add(new LookupParameter<BoolValue>(CoolingName, "True when the temperature should be cooled, false otherwise."));
|
|---|
| 177 | Parameters.Add(new LookupParameter<DoubleValue>(StartTemperatureName, "The temperature from which cooling or reheating should occur."));
|
|---|
| 178 | Parameters.Add(new LookupParameter<DoubleValue>(EndTemperatureName, "The temperature to which should be cooled or heated."));
|
|---|
| 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."));
|
|---|
| 181 | #endregion
|
|---|
| 182 |
|
|---|
| 183 | #region Create operators
|
|---|
| 184 | var variableCreator = new VariableCreator();
|
|---|
| 185 | var ssp1 = new SubScopesProcessor();
|
|---|
| 186 | var analyzer1 = new Placeholder();
|
|---|
| 187 | var ssp2 = new SubScopesProcessor();
|
|---|
| 188 | var resultsCollector = new ResultsCollector();
|
|---|
| 189 | var mainProcessor = new SubScopesProcessor();
|
|---|
| 190 | var moveGenerator = new Placeholder();
|
|---|
| 191 | var moveEvaluationProcessor = new SubScopesProcessor();
|
|---|
| 192 | var moveEvaluator = new Placeholder();
|
|---|
| 193 | var evaluatedMovesCounter = new IntCounter();
|
|---|
| 194 | var qualityComparator = new ProbabilisticQualityComparator();
|
|---|
| 195 | var acceptsQualityBranch = new ConditionalBranch();
|
|---|
| 196 | var moveMaker = new Placeholder();
|
|---|
| 197 | var temperatureController = new TemperatureController();
|
|---|
| 198 | var subScopesRemover = new SubScopesRemover();
|
|---|
| 199 | var iterationsCounter = new IntCounter();
|
|---|
| 200 | var iterationsComparator = new Comparator();
|
|---|
| 201 | var ssp3 = new SubScopesProcessor();
|
|---|
| 202 | var analyzer2 = new Placeholder();
|
|---|
| 203 | var iterationsTermination = new ConditionalBranch();
|
|---|
| 204 |
|
|---|
| 205 | variableCreator.Name = "Initialize Memory";
|
|---|
| 206 | variableCreator.CollectedValues.Add(new ValueParameter<ItemList<BoolValue>>(AcceptanceMemoryName, new ItemList<BoolValue>()));
|
|---|
| 207 |
|
|---|
| 208 | analyzer1.Name = "Analyzer";
|
|---|
| 209 | analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
|
|---|
| 210 |
|
|---|
| 211 | moveGenerator.Name = "Move generator";
|
|---|
| 212 | moveGenerator.OperatorParameter.ActualName = MoveGeneratorParameter.Name;
|
|---|
| 213 |
|
|---|
| 214 | moveEvaluator.Name = "Move evaluator";
|
|---|
| 215 | moveEvaluator.OperatorParameter.ActualName = MoveEvaluatorParameter.Name;
|
|---|
| 216 |
|
|---|
| 217 | evaluatedMovesCounter.Name = "EvaluatedMoves++";
|
|---|
| 218 | evaluatedMovesCounter.ValueParameter.ActualName = EvaluatedMovesParameter.Name;
|
|---|
| 219 | evaluatedMovesCounter.Increment = new IntValue(1);
|
|---|
| 220 |
|
|---|
| 221 | qualityComparator.LeftSideParameter.ActualName = MoveQualityParameter.Name;
|
|---|
| 222 | qualityComparator.RightSideParameter.ActualName = QualityParameter.Name;
|
|---|
| 223 | qualityComparator.ResultParameter.ActualName = IsAcceptedName;
|
|---|
| 224 | qualityComparator.DampeningParameter.ActualName = TemperatureParameter.Name;
|
|---|
| 225 |
|
|---|
| 226 | acceptsQualityBranch.ConditionParameter.ActualName = IsAcceptedName;
|
|---|
| 227 |
|
|---|
| 228 | moveMaker.Name = "Move maker";
|
|---|
| 229 | moveMaker.OperatorParameter.ActualName = MoveMakerParameter.Name;
|
|---|
| 230 |
|
|---|
| 231 | temperatureController.AnnealingOperatorParameter.ActualName = AnnealingOperatorParameter.Name;
|
|---|
| 232 | temperatureController.ThresholdParameter.ActualName = ThresholdParameter.Name;
|
|---|
| 233 | temperatureController.AcceptanceMemoryParameter.ActualName = AcceptanceMemoryName;
|
|---|
| 234 | temperatureController.MemorySizeParameter.ActualName = MemorySizeParameter.Name;
|
|---|
| 235 | temperatureController.CoolingParameter.ActualName = CoolingParameter.Name;
|
|---|
| 236 | temperatureController.EndTemperatureParameter.ActualName = EndTemperatureParameter.Name;
|
|---|
| 237 | temperatureController.HeatingOperatorParameter.ActualName = HeatingOperatorParameter.Name;
|
|---|
| 238 | temperatureController.IsAcceptedParameter.ActualName = IsAcceptedName;
|
|---|
| 239 | temperatureController.IterationsParameter.ActualName = IterationsParameter.Name;
|
|---|
| 240 | temperatureController.LowerTemperatureParameter.ActualName = LowerTemperatureParameter.Name;
|
|---|
| 241 | temperatureController.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
|
|---|
| 242 | temperatureController.StartTemperatureParameter.ActualName = StartTemperatureParameter.Name;
|
|---|
| 243 | temperatureController.TemperatureParameter.ActualName = TemperatureParameter.Name;
|
|---|
| 244 | temperatureController.TemperatureStartIndexParameter.ActualName = TemperatureStartIndexParameter.Name;
|
|---|
| 245 | temperatureController.UpperTemperatureParameter.ActualName = UpperTemperatureParameter.Name;
|
|---|
| 246 |
|
|---|
| 247 | subScopesRemover.RemoveAllSubScopes = true;
|
|---|
| 248 |
|
|---|
| 249 | iterationsCounter.Name = "Iterations++";
|
|---|
| 250 | iterationsCounter.Increment = new IntValue(1);
|
|---|
| 251 | iterationsCounter.ValueParameter.ActualName = IterationsParameter.Name;
|
|---|
| 252 |
|
|---|
| 253 | iterationsComparator.Name = "Iterations >= MaximumIterations";
|
|---|
| 254 | iterationsComparator.LeftSideParameter.ActualName = IterationsParameter.Name;
|
|---|
| 255 | iterationsComparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
|
|---|
| 256 | iterationsComparator.ResultParameter.ActualName = TerminateName;
|
|---|
| 257 | iterationsComparator.Comparison.Value = ComparisonType.GreaterOrEqual;
|
|---|
| 258 |
|
|---|
| 259 | analyzer2.Name = "Analyzer (placeholder)";
|
|---|
| 260 | analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
|
|---|
| 261 |
|
|---|
| 262 | iterationsTermination.Name = "Iterations termination condition";
|
|---|
| 263 | iterationsTermination.ConditionParameter.ActualName = TerminateName;
|
|---|
| 264 | #endregion
|
|---|
| 265 |
|
|---|
| 266 | #region Create operator graph
|
|---|
| 267 | OperatorGraph.InitialOperator = variableCreator;
|
|---|
| 268 | variableCreator.Successor = ssp1;
|
|---|
| 269 | ssp1.Operators.Add(analyzer1);
|
|---|
| 270 | ssp1.Successor = ssp2;
|
|---|
| 271 | analyzer1.Successor = null;
|
|---|
| 272 | ssp2.Operators.Add(resultsCollector);
|
|---|
| 273 | ssp2.Successor = mainProcessor;
|
|---|
| 274 | resultsCollector.Successor = null;
|
|---|
| 275 | mainProcessor.Operators.Add(moveGenerator);
|
|---|
| 276 | mainProcessor.Successor = iterationsCounter;
|
|---|
| 277 | moveGenerator.Successor = moveEvaluationProcessor;
|
|---|
| 278 | moveEvaluationProcessor.Operators.Add(moveEvaluator);
|
|---|
| 279 | moveEvaluationProcessor.Successor = evaluatedMovesCounter;
|
|---|
| 280 | moveEvaluator.Successor = qualityComparator;
|
|---|
| 281 | qualityComparator.Successor = acceptsQualityBranch;
|
|---|
| 282 | acceptsQualityBranch.TrueBranch = moveMaker;
|
|---|
| 283 | acceptsQualityBranch.FalseBranch = null;
|
|---|
| 284 | acceptsQualityBranch.Successor = temperatureController;
|
|---|
| 285 | moveMaker.Successor = null;
|
|---|
| 286 | temperatureController.Successor = null;
|
|---|
| 287 | evaluatedMovesCounter.Successor = subScopesRemover;
|
|---|
| 288 | subScopesRemover.Successor = null;
|
|---|
| 289 | iterationsCounter.Successor = iterationsComparator;
|
|---|
| 290 | iterationsComparator.Successor = ssp3;
|
|---|
| 291 | ssp3.Operators.Add(analyzer2);
|
|---|
| 292 | ssp3.Successor = iterationsTermination;
|
|---|
| 293 | iterationsTermination.TrueBranch = null;
|
|---|
| 294 | iterationsTermination.FalseBranch = mainProcessor;
|
|---|
| 295 | #endregion
|
|---|
| 296 | }
|
|---|
| 297 |
|
|---|
| 298 | public override IOperation Apply() {
|
|---|
| 299 | if (MoveGeneratorParameter.ActualValue == null || MoveEvaluatorParameter.ActualValue == null || MoveMakerParameter.ActualValue == null)
|
|---|
| 300 | return null;
|
|---|
| 301 | return base.Apply();
|
|---|
| 302 | }
|
|---|
| 303 | }
|
|---|
| 304 | }
|
|---|
