#region License Information /* HeuristicLab * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Linq; using HeuristicLab.Analysis; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Operators; using HeuristicLab.Optimization; using HeuristicLab.Optimization.Operators; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.PluginInfrastructure; using HeuristicLab.Random; namespace HeuristicLab.Algorithms.SimulatedAnnealing { [Item("Simulated Annealing", "An advanced simulated annealing algorithm.")] [Creatable("Algorithms")] [StorableClass] public sealed class SimulatedAnnealing : HeuristicOptimizationEngineAlgorithm, IStorableContent { #region Strings private const string SeedName = "Seed"; private const string SetSeedRandomlyName = "SetSeedRandomly"; private const string MoveGeneratorName = "MoveGenerator"; private const string MoveEvaluatorName = "MoveEvaluator"; private const string MoveMakerName = "MoveMaker"; private const string AnnealingOperatorName = "AnnealingOperator"; private const string HeatingOperatorName = "HeatingOperator"; private const string MaximumIterationsName = "MaximumIterations"; private const string UpperTemperatureName = "UpperTemperature"; private const string LowerTemperatureName = "LowerTemperature"; private const string AnalyzerName = "Analyzer"; private const string RandomName = "Random"; private const string EvaluatedMovesName = "EvaluatedMoves"; private const string IterationsName = "Iterations"; private const string TemperatureStartIndexName = "TemperatureStartIndex"; private const string CoolingName = "Cooling"; private const string StartTemperatureName = "StartTemperature"; private const string EndTemperatureName = "EndTemperature"; private const string TemperatureName = "Temperature"; private const string ResultsName = "Results"; private const string TemperatureChartName = "Temperature Chart"; private const string TemperatureAnalyzerName = "Temperature Analyzer"; private const string ThresholdName = "Threshold"; private const string MemorySizeName = "MemorySize"; #endregion public string Filename { get; set; } #region Problem Properties public override Type ProblemType { get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); } } public new ISingleObjectiveHeuristicOptimizationProblem Problem { get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; } set { base.Problem = value; } } #endregion #region Parameter Properties private ValueParameter SeedParameter { get { return (ValueParameter)Parameters[SeedName]; } } private ValueParameter SetSeedRandomlyParameter { get { return (ValueParameter)Parameters[SetSeedRandomlyName]; } } public IConstrainedValueParameter MoveGeneratorParameter { get { return (IConstrainedValueParameter)Parameters[MoveGeneratorName]; } } public IConstrainedValueParameter MoveMakerParameter { get { return (IConstrainedValueParameter)Parameters[MoveMakerName]; } } public IConstrainedValueParameter MoveEvaluatorParameter { get { return (IConstrainedValueParameter)Parameters[MoveEvaluatorName]; } } public IConstrainedValueParameter AnnealingOperatorParameter { get { return (IConstrainedValueParameter)Parameters[AnnealingOperatorName]; } } public OptionalConstrainedValueParameter HeatingOperatorParameter { get { return (OptionalConstrainedValueParameter)Parameters[HeatingOperatorName]; } } private ValueParameter ThresholdParameter { get { return (ValueParameter) Parameters[ThresholdName]; } } private ValueParameter MemorySizeParameter { get { return (ValueParameter) Parameters[MemorySizeName]; } } private ValueParameter MaximumIterationsParameter { get { return (ValueParameter)Parameters[MaximumIterationsName]; } } private ValueParameter UpperTemperatureParameter { get { return (ValueParameter)Parameters[UpperTemperatureName]; } } private ValueParameter LowerTemperatureParameter { get { return (ValueParameter)Parameters[LowerTemperatureName]; } } private ValueParameter AnalyzerParameter { get { return (ValueParameter)Parameters[AnalyzerName]; } } #endregion #region Properties public IntValue Seed { get { return SeedParameter.Value; } set { SeedParameter.Value = value; } } public BoolValue SetSeedRandomly { get { return SetSeedRandomlyParameter.Value; } set { SetSeedRandomlyParameter.Value = value; } } public IMultiMoveGenerator MoveGenerator { get { return MoveGeneratorParameter.Value; } set { MoveGeneratorParameter.Value = value; } } public IMoveMaker MoveMaker { get { return MoveMakerParameter.Value; } set { MoveMakerParameter.Value = value; } } public ISingleObjectiveMoveEvaluator MoveEvaluator { get { return MoveEvaluatorParameter.Value; } set { MoveEvaluatorParameter.Value = value; } } public IDiscreteDoubleValueModifier AnnealingOperator { get { return AnnealingOperatorParameter.Value; } set { AnnealingOperatorParameter.Value = value; } } public IDiscreteDoubleValueModifier HeatingOperator { get { return HeatingOperatorParameter.Value; } set { HeatingOperatorParameter.Value = value; } } public IntValue MaximumIterations { get { return MaximumIterationsParameter.Value; } set { MaximumIterationsParameter.Value = value; } } public DoubleValue UpperTemperature { get { return UpperTemperatureParameter.Value; } set { UpperTemperatureParameter.Value = value; } } public DoubleValue LowerTemperature { get { return LowerTemperatureParameter.Value; } set { LowerTemperatureParameter.Value = value; } } public MultiAnalyzer Analyzer { get { return AnalyzerParameter.Value; } set { AnalyzerParameter.Value = value; } } public DoubleRange AcceptanceThreshold { get { return ThresholdParameter.Value; } set { ThresholdParameter.Value = value; } } public IntValue AcceptanceMemorySize { get { return MemorySizeParameter.Value; } set { MemorySizeParameter.Value = value; } } private RandomCreator RandomCreator { get { return (RandomCreator)OperatorGraph.InitialOperator; } } private SolutionsCreator SolutionsCreator { get { return (SolutionsCreator)RandomCreator.Successor; } } private SimulatedAnnealingMainLoop MainLoop { get { return OperatorGraph.Iterate().OfType().First(); } } #endregion [StorableConstructor] private SimulatedAnnealing(bool deserializing) : base(deserializing) { } private SimulatedAnnealing(SimulatedAnnealing original, Cloner cloner) : base(original, cloner) { RegisterEventHandlers(); } public SimulatedAnnealing() : base() { Parameters.Add(new ValueParameter(SeedName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0))); Parameters.Add(new ValueParameter(SetSeedRandomlyName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true))); Parameters.Add(new ConstrainedValueParameter(MoveGeneratorName, "The operator used to generate moves to the neighborhood of the current solution.")); Parameters.Add(new ConstrainedValueParameter(MoveEvaluatorName, "The operator used to evaluate a move.")); Parameters.Add(new ConstrainedValueParameter(MoveMakerName, "The operator used to perform a move.")); Parameters.Add(new ConstrainedValueParameter(AnnealingOperatorName, "The operator used to cool the temperature.")); Parameters.Add(new OptionalConstrainedValueParameter(HeatingOperatorName, "The operator used to heat the temperature.")); Parameters.Add(new ValueParameter(MaximumIterationsName, "The maximum number of generations which should be processed.", new IntValue(10000))); Parameters.Add(new ValueParameter(UpperTemperatureName, "The upper bound for the temperature.", new DoubleValue(100))); Parameters.Add(new ValueParameter(LowerTemperatureName, "The lower bound for the temperature.", new DoubleValue(1e-6))); Parameters.Add(new ValueParameter(AnalyzerName, "The operator used to analyze each iteration.", new MultiAnalyzer())); Parameters.Add(new ValueParameter(MemorySizeName, "The maximum size of the acceptance memory.", new IntValue(100))); Parameters.Add(new ValueParameter(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))); var randomCreator = new RandomCreator(); var solutionsCreator = new SolutionsCreator(); var variableCreator = new VariableCreator(); var startTemperatureAssigner = new Assigner(); var endTemperatureAssigner = new Assigner(); var temperatureAssigner = new Assigner(); var resultsCollector = new ResultsCollector(); var mainLoop = new SimulatedAnnealingMainLoop(); OperatorGraph.InitialOperator = randomCreator; randomCreator.RandomParameter.ActualName = RandomName; randomCreator.SeedParameter.ActualName = SeedParameter.Name; randomCreator.SeedParameter.Value = null; randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name; randomCreator.SetSeedRandomlyParameter.Value = null; randomCreator.Successor = solutionsCreator; solutionsCreator.NumberOfSolutions = new IntValue(1); solutionsCreator.Successor = variableCreator; variableCreator.Name = "Initialize Variables"; variableCreator.CollectedValues.Add(new ValueParameter(EvaluatedMovesName, new IntValue())); variableCreator.CollectedValues.Add(new ValueParameter(IterationsName, new IntValue(0))); variableCreator.CollectedValues.Add(new ValueParameter(TemperatureStartIndexName, new IntValue(0))); variableCreator.CollectedValues.Add(new ValueParameter(CoolingName, new BoolValue(true))); variableCreator.Successor = startTemperatureAssigner; startTemperatureAssigner.Name = "Assign Start Temperature"; startTemperatureAssigner.LeftSideParameter.ActualName = StartTemperatureName; startTemperatureAssigner.RightSideParameter.ActualName = UpperTemperatureParameter.Name; startTemperatureAssigner.Successor = endTemperatureAssigner; endTemperatureAssigner.Name = "Assign End Temperature"; endTemperatureAssigner.LeftSideParameter.ActualName = EndTemperatureName; endTemperatureAssigner.RightSideParameter.ActualName = LowerTemperatureParameter.Name; endTemperatureAssigner.Successor = temperatureAssigner; temperatureAssigner.Name = "Initialize Temperature"; temperatureAssigner.LeftSideParameter.ActualName = TemperatureName; temperatureAssigner.RightSideParameter.ActualName = StartTemperatureName; temperatureAssigner.Successor = resultsCollector; resultsCollector.CopyValue = new BoolValue(false); resultsCollector.CollectedValues.Add(new LookupParameter(EvaluatedMovesName, null)); resultsCollector.CollectedValues.Add(new LookupParameter(IterationsName, null)); resultsCollector.ResultsParameter.ActualName = ResultsName; resultsCollector.Successor = mainLoop; mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name; mainLoop.AnnealingOperatorParameter.ActualName = AnnealingOperatorParameter.Name; mainLoop.MemorySizeParameter.ActualName = MemorySizeParameter.Name; mainLoop.ThresholdParameter.ActualName = ThresholdParameter.Name; mainLoop.CoolingParameter.ActualName = CoolingName; mainLoop.EndTemperatureParameter.ActualName = EndTemperatureName; mainLoop.EvaluatedMovesParameter.ActualName = EvaluatedMovesName; mainLoop.HeatingOperatorParameter.ActualName = HeatingOperatorParameter.Name; mainLoop.IterationsParameter.ActualName = IterationsName; mainLoop.LowerTemperatureParameter.ActualName = LowerTemperatureParameter.Name; mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name; mainLoop.MoveEvaluatorParameter.ActualName = MoveEvaluatorParameter.Name; mainLoop.MoveGeneratorParameter.ActualName = MoveGeneratorParameter.Name; mainLoop.MoveMakerParameter.ActualName = MoveMakerParameter.Name; mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName; mainLoop.ResultsParameter.ActualName = ResultsName; mainLoop.StartTemperatureParameter.ActualName = StartTemperatureName; mainLoop.TemperatureStartIndexParameter.ActualName = TemperatureStartIndexName; mainLoop.TemperatureParameter.ActualName = TemperatureName; mainLoop.UpperTemperatureParameter.ActualName = UpperTemperatureParameter.Name; foreach (var op in ApplicationManager.Manager.GetInstances().OrderBy(x => x.Name)) { AnnealingOperatorParameter.ValidValues.Add(op); HeatingOperatorParameter.ValidValues.Add((IDiscreteDoubleValueModifier)op.Clone()); } UpdateAnalyzers(); Parameterize(); RegisterEventHandlers(); } public override IDeepCloneable Clone(Cloner cloner) { return new SimulatedAnnealing(this, cloner); } [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { RegisterEventHandlers(); } private void RegisterEventHandlers() { if (Problem != null) { Problem.Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged; foreach (var op in Problem.Operators.OfType()) { op.MoveQualityParameter.ActualNameChanged += MoveEvaluator_MoveQualityParameter_ActualNameChanged; } } MoveGeneratorParameter.ValueChanged += MoveGeneratorParameter_ValueChanged; MoveEvaluatorParameter.ValueChanged += MoveEvaluatorParameter_ValueChanged; } public override void Prepare() { if (Problem != null && MoveGenerator != null && MoveMaker != null && MoveEvaluator != null) base.Prepare(); } #region Events protected override void OnProblemChanged() { foreach (var op in Problem.Operators.OfType()) { op.MoveQualityParameter.ActualNameChanged += MoveEvaluator_MoveQualityParameter_ActualNameChanged; } UpdateMoveGenerator(); UpdateMoveOperators(); UpdateAnalyzers(); Parameterize(); Problem.Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged; base.OnProblemChanged(); } protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) { Parameterize(); base.Problem_SolutionCreatorChanged(sender, e); } protected override void Problem_EvaluatorChanged(object sender, EventArgs e) { Parameterize(); Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged); base.Problem_EvaluatorChanged(sender, e); } protected override void Problem_OperatorsChanged(object sender, EventArgs e) { foreach (var op in Problem.Operators.OfType()) { op.MoveQualityParameter.ActualNameChanged -= MoveEvaluator_MoveQualityParameter_ActualNameChanged; op.MoveQualityParameter.ActualNameChanged += MoveEvaluator_MoveQualityParameter_ActualNameChanged; } UpdateMoveGenerator(); UpdateMoveOperators(); UpdateAnalyzers(); Parameterize(); base.Problem_OperatorsChanged(sender, e); } private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) { Parameterize(); } private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) { UpdateMoveOperators(); } private void MoveEvaluatorParameter_ValueChanged(object sender, EventArgs e) { Parameterize(); } private void MoveEvaluator_MoveQualityParameter_ActualNameChanged(object sender, EventArgs e) { if (sender == MoveEvaluator) Parameterize(); } #endregion #region Helpers private void UpdateMoveGenerator() { var oldMoveGenerator = MoveGenerator; var defaultMoveGenerator = Problem.Operators.OfType().FirstOrDefault(); MoveGeneratorParameter.ValidValues.Clear(); if (Problem != null) { foreach (var generator in Problem.Operators.OfType().OrderBy(x => x.Name)) MoveGeneratorParameter.ValidValues.Add(generator); } if (oldMoveGenerator != null) { var newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType()); if (newMoveGenerator != null) MoveGenerator = newMoveGenerator; else oldMoveGenerator = null; } if (oldMoveGenerator == null && defaultMoveGenerator != null) MoveGenerator = defaultMoveGenerator; UpdateMoveOperators(); } private void UpdateMoveOperators() { var oldMoveMaker = MoveMaker; var oldMoveEvaluator = MoveEvaluator; MoveMakerParameter.ValidValues.Clear(); MoveEvaluatorParameter.ValidValues.Clear(); if (MoveGenerator != null) { var moveTypes = MoveGenerator.GetType().GetInterfaces().Where(x => typeof(IMoveOperator).IsAssignableFrom(x)).ToList(); foreach (var type in moveTypes.ToList()) { if (moveTypes.Any(t => t != type && type.IsAssignableFrom(t))) moveTypes.Remove(type); } var operators = Problem.Operators.Where(op => moveTypes.Any(m => m.IsInstanceOfType(op))).ToList(); var defaultMoveMaker = operators.OfType().FirstOrDefault(); var defaultMoveEvaluator = operators.OfType().FirstOrDefault(); foreach (var moveMaker in operators.OfType().OrderBy(op => op.Name)) MoveMakerParameter.ValidValues.Add(moveMaker); foreach (var moveEvaluator in operators.OfType().OrderBy(op => op.Name)) MoveEvaluatorParameter.ValidValues.Add(moveEvaluator); if (oldMoveMaker != null) { var mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType()); if (mm != null) MoveMaker = mm; else oldMoveMaker = null; } if (oldMoveMaker == null && defaultMoveMaker != null) MoveMaker = defaultMoveMaker; if (oldMoveEvaluator != null) { var me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType()); if (me != null) MoveEvaluator = me; else oldMoveEvaluator = null; } if (oldMoveEvaluator == null & defaultMoveEvaluator != null) MoveEvaluator = defaultMoveEvaluator; } } private void UpdateAnalyzers() { Analyzer.Operators.Clear(); if (Problem != null) { foreach (var analyzer in Problem.Operators.OfType()) { foreach (var param in analyzer.Parameters.OfType()) param.Depth = 0; Analyzer.Operators.Add(analyzer, analyzer.EnabledByDefault); } } var qualityAnalyzer = new QualityAnalyzer(); var temperatureAnalyzer = new SingleValueAnalyzer { Name = TemperatureAnalyzerName }; Analyzer.Operators.Add(qualityAnalyzer, qualityAnalyzer.EnabledByDefault); Analyzer.Operators.Add(temperatureAnalyzer, temperatureAnalyzer.EnabledByDefault); } private void Parameterize() { #region IStochasticOperator if (Problem != null) { foreach (var op in Problem.Operators.OfType()) { op.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName; op.RandomParameter.Hidden = true; } } #endregion #region IIterationBasedOperator if (Problem != null) { foreach (var op in Problem.Operators.OfType()) { op.IterationsParameter.ActualName = IterationsName; op.IterationsParameter.Hidden = true; op.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name; op.MaximumIterationsParameter.Hidden = true; } } #endregion #region Analyzers foreach (var qualityAnalyzer in Analyzer.Operators.OfType()) { qualityAnalyzer.ResultsParameter.ActualName = ResultsName; if (Problem != null) { qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name; qualityAnalyzer.MaximizationParameter.Hidden = true; qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName; qualityAnalyzer.QualityParameter.Depth = 0; qualityAnalyzer.QualityParameter.Hidden = true; qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name; qualityAnalyzer.BestKnownQualityParameter.Hidden = true; } else { qualityAnalyzer.MaximizationParameter.Hidden = false; qualityAnalyzer.QualityParameter.Hidden = false; qualityAnalyzer.BestKnownQualityParameter.Hidden = false; } } var temperatureAnalyzer = Analyzer.Operators.OfType().FirstOrDefault(x => x.Name == TemperatureAnalyzerName); if (temperatureAnalyzer != null) { temperatureAnalyzer.ResultsParameter.ActualName = ResultsName; temperatureAnalyzer.ResultsParameter.Hidden = true; temperatureAnalyzer.ValueParameter.ActualName = TemperatureName; temperatureAnalyzer.ValueParameter.Hidden = true; temperatureAnalyzer.ValuesParameter.ActualName = TemperatureChartName; temperatureAnalyzer.ValuesParameter.Hidden = true; } #endregion #region SolutionCreator if (Problem != null) { SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name; SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name; } #endregion #region Annealing/Reheating Operators foreach (var op in AnnealingOperatorParameter.ValidValues) { op.IndexParameter.ActualName = IterationsName; op.IndexParameter.Hidden = true; op.StartIndexParameter.Value = null; op.StartIndexParameter.ActualName = TemperatureStartIndexName; op.EndIndexParameter.ActualName = MaximumIterationsParameter.Name; op.ValueParameter.ActualName = TemperatureName; op.ValueParameter.Hidden = true; op.StartValueParameter.ActualName = StartTemperatureName; op.StartValueParameter.Hidden = true; op.EndValueParameter.ActualName = LowerTemperatureParameter.Name; op.EndValueParameter.Hidden = true; } foreach (var op in HeatingOperatorParameter.ValidValues) { op.IndexParameter.ActualName = IterationsName; op.IndexParameter.Hidden = true; op.StartIndexParameter.Value = null; op.StartIndexParameter.ActualName = TemperatureStartIndexName; op.EndIndexParameter.ActualName = MaximumIterationsParameter.Name; op.ValueParameter.ActualName = TemperatureName; op.ValueParameter.Hidden = true; op.StartValueParameter.ActualName = StartTemperatureName; op.StartValueParameter.Hidden = true; op.EndValueParameter.ActualName = UpperTemperatureParameter.Name; op.EndValueParameter.Hidden = true; } #endregion #region Move Operators if (Problem != null) { foreach (var op in Problem.Operators.OfType()) { op.SampleSizeParameter.Value = new IntValue(1); op.SampleSizeParameter.Hidden = true; } foreach (var op in Problem.Operators.OfType()) { op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName; op.QualityParameter.Hidden = true; if (MoveEvaluator != null) { op.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName; op.MoveQualityParameter.Hidden = true; } else { op.MoveQualityParameter.Hidden = false; } } foreach (var op in Problem.Operators.OfType()) { op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName; op.QualityParameter.Hidden = true; } } #endregion #region MainLoop if (Problem != null) { MainLoop.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name; MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name; MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName; if (MoveEvaluator != null) MainLoop.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName; } #endregion } #endregion } }