#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.Random; using HeuristicLab.Selection; namespace HeuristicLab.Algorithms.ScatterSearch { /// /// A scatter search algorithm. /// [Item("Scatter Search", "A scatter search algorithm.")] [Creatable("Algorithms")] [StorableClass] public sealed class ScatterSearch : HeuristicOptimizationEngineAlgorithm, IStorableContent { 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 public IValueParameter AnalyzerParameter { get { return (IValueParameter)Parameters["Analyzer"]; } } public ConstrainedValueParameter CrossoverParameter { get { return (ConstrainedValueParameter)Parameters["Crossover"]; } } public IValueParameter ImproverParameter { get { return (IValueParameter)Parameters["Improver"]; } } public IValueParameter MaximumIterationsParameter { get { return (IValueParameter)Parameters["MaximumIterations"]; } } public IValueParameter NumberOfHighQualitySolutionsParameter { get { return (IValueParameter)Parameters["NumberOfHighQualitySolutions"]; } } public IValueParameter PopulationSizeParameter { get { return (IValueParameter)Parameters["PopulationSize"]; } } public IValueParameter ReferenceSetSizeParameter { get { return (IValueParameter)Parameters["ReferenceSetSize"]; } } public IValueParameter SeedParameter { get { return (IValueParameter)Parameters["Seed"]; } } public IValueParameter SetSeedRandomlyParameter { get { return (IValueParameter)Parameters["SetSeedRandomly"]; } } #endregion #region Properties private MultiAnalyzer Analyzer { get { return AnalyzerParameter.Value; } set { AnalyzerParameter.Value = value; } } private ICrossover Crossover { get { return CrossoverParameter.Value; } set { CrossoverParameter.Value = value; } } private ILocalImprovementOperator Improver { get { return ImproverParameter.Value; } set { ImproverParameter.Value = value; } } private IntValue MaximumIterations { get { return MaximumIterationsParameter.Value; } set { MaximumIterationsParameter.Value = value; } } private IntValue NumberOfHighQualitySolutions { get { return NumberOfHighQualitySolutionsParameter.Value; } set { NumberOfHighQualitySolutionsParameter.Value = value; } } private IntValue PopulationSize { get { return PopulationSizeParameter.Value; } set { PopulationSizeParameter.Value = value; } } private IntValue ReferenceSetSize { get { return ReferenceSetSizeParameter.Value; } set { ReferenceSetSizeParameter.Value = value; } } private IntValue Seed { get { return SeedParameter.Value; } set { SeedParameter.Value = value; } } private BoolValue SetSeedRandomly { get { return SetSeedRandomlyParameter.Value; } set { SetSeedRandomlyParameter.Value = value; } } public RandomCreator RandomCreator { get { return (RandomCreator)OperatorGraph.InitialOperator; } } public SolutionsCreator SolutionsCreator { get { return (SolutionsCreator)RandomCreator.Successor; } } public ScatterSearchMainLoop MainLoop { get { return FindMainLoop(SolutionsCreator.Successor); } } [Storable] private BestAverageWorstQualityAnalyzer qualityAnalyzer; #endregion [StorableConstructor] private ScatterSearch(bool deserializing) : base(deserializing) { } [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { Initialize(); } private ScatterSearch(ScatterSearch original, Cloner cloner) : base(original, cloner) { qualityAnalyzer = cloner.Clone(original.qualityAnalyzer); Initialize(); } public override IDeepCloneable Clone(Cloner cloner) { return new ScatterSearch(this, cloner); } public ScatterSearch() : base() { #region Create parameters Parameters.Add(new ValueParameter("Analyzer", "The operator used to analyze the solution and moves.", new MultiAnalyzer())); Parameters.Add(new ConstrainedValueParameter("Crossover", "The operator used to combine solutions.")); Parameters.Add(new ValueParameter("Improver", "The operator used to improve solutions.", new ScatterSearchImprovementOperator())); Parameters.Add(new ValueParameter("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000))); Parameters.Add(new ValueParameter("NumberOfHighQualitySolutions", "The number of high quality solutions that should be added to the reference set.", new IntValue(5))); Parameters.Add(new ValueParameter("PopulationSize", "The size of the population.", new IntValue(30))); Parameters.Add(new ValueParameter("ReferenceSetSize", "The size of the reference set.", new IntValue(10))); Parameters.Add(new ValueParameter("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0))); Parameters.Add(new ValueParameter("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true))); #endregion #region Create operators RandomCreator randomCreator = new RandomCreator(); SolutionsCreator solutionsCreator = new SolutionsCreator(); UniformSubScopesProcessor uniformSubScopesProcessor = new UniformSubScopesProcessor(); Placeholder solutionEvaluator = new Placeholder(); Placeholder solutionImprover = new Placeholder(); BestSelector bestSelector = new BestSelector(); VariableCreator variableCreator = new VariableCreator(); ResultsCollector resultsCollector = new ResultsCollector(); ScatterSearchMainLoop mainLoop = new ScatterSearchMainLoop(); #endregion #region Create operator graph OperatorGraph.InitialOperator = randomCreator; randomCreator.RandomParameter.ActualName = "Random"; randomCreator.SeedParameter.ActualName = SeedParameter.Name; randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name; randomCreator.Successor = solutionsCreator; solutionsCreator.Name = "DiversificationGenerationMethod"; solutionsCreator.NumberOfSolutionsParameter.ActualName = "PopulationSize"; solutionsCreator.Successor = uniformSubScopesProcessor; uniformSubScopesProcessor.Operator = solutionImprover; uniformSubScopesProcessor.Successor = bestSelector; solutionImprover.Name = "SolutionImprover"; solutionImprover.OperatorParameter.ActualName = "Improver"; solutionImprover.Successor = solutionEvaluator; solutionEvaluator.Name = "SolutionEvaluator"; solutionEvaluator.OperatorParameter.ActualName = "Evaluator"; solutionEvaluator.Successor = null; bestSelector.NumberOfSelectedSubScopesParameter.ActualName = NumberOfHighQualitySolutionsParameter.Name; bestSelector.CopySelected = new BoolValue(false); bestSelector.Successor = variableCreator; variableCreator.CollectedValues.Add(new ValueParameter("Iterations", new IntValue(0))); variableCreator.CollectedValues.Add(new ValueParameter("NewSolutions", new BoolValue(false))); variableCreator.Successor = resultsCollector; resultsCollector.CollectedValues.Add(new LookupParameter("Iterations")); resultsCollector.ResultsParameter.ActualName = "Results"; resultsCollector.Successor = mainLoop; mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name; mainLoop.RandomParameter.ActualName = randomCreator.RandomParameter.ActualName; mainLoop.ResultsParameter.ActualName = "Results"; mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name; mainLoop.IterationsParameter.ActualName = "Iterations"; mainLoop.CrossoverParameter.ActualName = CrossoverParameter.Name; mainLoop.PopulationSizeParameter.ActualName = PopulationSizeParameter.Name; mainLoop.NumberOfHighQualitySolutionsParameter.ActualName = NumberOfHighQualitySolutionsParameter.Name; mainLoop.Successor = null; #endregion qualityAnalyzer = new BestAverageWorstQualityAnalyzer(); ParameterizeAnalyzers(); UpdateAnalyzers(); Initialize(); } public override void Prepare() { base.Prepare(); } #region Events protected override void OnProblemChanged() { ParameterizeStochasticOperator(Problem.SolutionCreator); ParameterizeStochasticOperator(Problem.Evaluator); foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op); ParameterizeAnalyzers(); ParameterizeMainLoop(); ParameterizeSolutionsCreator(); UpdateAnalyzers(); UpdateCrossovers(); Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged); base.OnProblemChanged(); } protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) { ParameterizeStochasticOperator(Problem.SolutionCreator); ParameterizeSolutionsCreator(); base.Problem_SolutionCreatorChanged(sender, e); } protected override void Problem_EvaluatorChanged(object sender, EventArgs e) { ParameterizeStochasticOperator(Problem.Evaluator); ParameterizeSolutionsCreator(); ParameterizeMainLoop(); ParameterizeAnalyzers(); Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged); base.Problem_EvaluatorChanged(sender, e); } protected override void Problem_OperatorsChanged(object sender, EventArgs e) { foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op); UpdateAnalyzers(); UpdateCrossovers(); ParameterizeMainLoop(); ParameterizeAnalyzers(); base.Problem_OperatorsChanged(sender, e); } private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) { ParameterizeMainLoop(); ParameterizeAnalyzers(); } #endregion #region Helpers private void Initialize() { if (Problem != null) { Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged); } } private void UpdateAnalyzers() { Analyzer.Operators.Clear(); if (Problem != null) { foreach (IAnalyzer analyzer in Problem.Operators.OfType()) { foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType()) param.Depth = 1; Analyzer.Operators.Add(analyzer, analyzer.EnabledByDefault); } } Analyzer.Operators.Add(qualityAnalyzer, qualityAnalyzer.EnabledByDefault); } private void UpdateCrossovers() { ICrossover oldCrossover = CrossoverParameter.Value; CrossoverParameter.ValidValues.Clear(); ICrossover defaultCrossover = Problem.Operators.OfType().FirstOrDefault(); foreach (ICrossover crossover in Problem.Operators.OfType().OrderBy(x => x.Name)) CrossoverParameter.ValidValues.Add(crossover); foreach (var crossover in CrossoverParameter.ValidValues.OfType()) crossover.ParentsParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem if (oldCrossover != null) { ICrossover crossover = CrossoverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldCrossover.GetType()); if (crossover != null) CrossoverParameter.Value = crossover; else oldCrossover = null; } if (oldCrossover == null && defaultCrossover != null) CrossoverParameter.Value = defaultCrossover; } private void ParameterizeSolutionsCreator() { SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name; SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name; } private void ParameterizeMainLoop() { if (Problem != null) { MainLoop.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name; MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name; MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName; } } private void ParameterizeStochasticOperator(IOperator op) { if (op is IStochasticOperator) { IStochasticOperator stOp = (IStochasticOperator)op; stOp.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName; stOp.RandomParameter.Hidden = true; } } private void ParameterizeAnalyzers() { qualityAnalyzer.ResultsParameter.ActualName = "Results"; qualityAnalyzer.ResultsParameter.Hidden = true; if (Problem != null) { qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name; qualityAnalyzer.MaximizationParameter.Hidden = true; qualityAnalyzer.QualityParameter.Hidden = false; qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name; qualityAnalyzer.BestKnownQualityParameter.Hidden = true; } else { qualityAnalyzer.MaximizationParameter.Hidden = false; qualityAnalyzer.BestKnownQualityParameter.Hidden = false; } } private ScatterSearchMainLoop FindMainLoop(IOperator start) { IOperator mainLoop = start; while (mainLoop != null && !(mainLoop is ScatterSearchMainLoop)) mainLoop = ((SingleSuccessorOperator)mainLoop).Successor; if (mainLoop == null) return null; else return (ScatterSearchMainLoop)mainLoop; } #endregion } }