#region License Information
/* HeuristicLab
* Copyright (C) 2002-2010 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.Collections.Generic;
using System.Linq;
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;
using HeuristicLab.Analysis;
namespace HeuristicLab.Algorithms.EvolutionStrategy {
///
/// A standard genetic algorithm.
///
[Item("Evolution Strategy", "An evolution strategy.")]
[Creatable("Algorithms")]
[StorableClass]
public sealed class EvolutionStrategy : EngineAlgorithm {
#region Problem Properties
public override Type ProblemType {
get { return typeof(ISingleObjectiveProblem); }
}
public new ISingleObjectiveProblem Problem {
get { return (ISingleObjectiveProblem)base.Problem; }
set { base.Problem = value; }
}
#endregion
#region Parameter Properties
private ValueParameter SeedParameter {
get { return (ValueParameter)Parameters["Seed"]; }
}
private ValueParameter SetSeedRandomlyParameter {
get { return (ValueParameter)Parameters["SetSeedRandomly"]; }
}
private ValueParameter PopulationSizeParameter {
get { return (ValueParameter)Parameters["PopulationSize"]; }
}
private ValueParameter ParentsPerChildParameter {
get { return (ValueParameter)Parameters["ParentsPerChild"]; }
}
private ValueParameter ChildrenParameter {
get { return (ValueParameter)Parameters["Children"]; }
}
private ValueParameter MaximumGenerationsParameter {
get { return (ValueParameter)Parameters["MaximumGenerations"]; }
}
private ValueParameter PlusSelectionParameter {
get { return (ValueParameter)Parameters["PlusSelection"]; }
}
private ConstrainedValueParameter MutatorParameter {
get { return (ConstrainedValueParameter)Parameters["Mutator"]; }
}
private OptionalConstrainedValueParameter RecombinatorParameter {
get { return (OptionalConstrainedValueParameter)Parameters["Recombinator"]; }
}
private ValueParameter AnalyzerParameter {
get { return (ValueParameter)Parameters["Analyzer"]; }
}
private OptionalConstrainedValueParameter StrategyParameterCreatorParameter {
get { return (OptionalConstrainedValueParameter)Parameters["StrategyParameterCreator"]; }
}
private OptionalConstrainedValueParameter StrategyParameterCrossoverParameter {
get { return (OptionalConstrainedValueParameter)Parameters["StrategyParameterCrossover"]; }
}
private OptionalConstrainedValueParameter StrategyParameterManipulatorParameter {
get { return (OptionalConstrainedValueParameter)Parameters["StrategyParameterManipulator"]; }
}
#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 IntValue PopulationSize {
get { return PopulationSizeParameter.Value; }
set { PopulationSizeParameter.Value = value; }
}
public IntValue ParentsPerChild {
get { return ParentsPerChildParameter.Value; }
set { ParentsPerChildParameter.Value = value; }
}
public IntValue Children {
get { return ChildrenParameter.Value; }
set { ChildrenParameter.Value = value; }
}
public IntValue MaximumGenerations {
get { return MaximumGenerationsParameter.Value; }
set { MaximumGenerationsParameter.Value = value; }
}
private BoolValue PlusSelection {
get { return PlusSelectionParameter.Value; }
set { PlusSelectionParameter.Value = value; }
}
public IManipulator Mutator {
get { return MutatorParameter.Value; }
set { MutatorParameter.Value = value; }
}
public ICrossover Recombinator {
get { return RecombinatorParameter.Value; }
set { RecombinatorParameter.Value = value; }
}
public MultiAnalyzer Analyzer {
get { return AnalyzerParameter.Value; }
set { AnalyzerParameter.Value = value; }
}
public IStrategyParameterCreator StrategyParameterCreator {
get { return StrategyParameterCreatorParameter.Value; }
set { StrategyParameterCreatorParameter.Value = value; }
}
public IStrategyParameterCrossover StrategyParameterCrossover {
get { return StrategyParameterCrossoverParameter.Value; }
set { StrategyParameterCrossoverParameter.Value = value; }
}
public IStrategyParameterManipulator StrategyParameterManipulator {
get { return StrategyParameterManipulatorParameter.Value; }
set { StrategyParameterManipulatorParameter.Value = value; }
}
private RandomCreator RandomCreator {
get { return (RandomCreator)OperatorGraph.InitialOperator; }
}
private SolutionsCreator SolutionsCreator {
get { return (SolutionsCreator)RandomCreator.Successor; }
}
private EvolutionStrategyMainLoop MainLoop {
get { return (EvolutionStrategyMainLoop)((UniformSubScopesProcessor)SolutionsCreator.Successor).Successor; }
}
[Storable]
private BestAverageWorstQualityAnalyzer qualityAnalyzer;
#endregion
public EvolutionStrategy()
: base() {
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)));
Parameters.Add(new ValueParameter("PopulationSize", "µ (mu) - the size of the population.", new IntValue(5)));
Parameters.Add(new ValueParameter("ParentsPerChild", "ρ (rho) - how many parents should be recombined.", new IntValue(1)));
Parameters.Add(new ValueParameter("Children", "λ (lambda) - the size of the offspring population.", new IntValue(10)));
Parameters.Add(new ValueParameter("MaximumGenerations", "The maximum number of generations which should be processed.", new IntValue(1000)));
Parameters.Add(new ValueParameter("PlusSelection", "True for plus selection (elitist population), false for comma selection (non-elitist population).", new BoolValue(true)));
Parameters.Add(new OptionalConstrainedValueParameter("Recombinator", "The operator used to cross solutions."));
Parameters.Add(new ConstrainedValueParameter("Mutator", "The operator used to mutate solutions."));
Parameters.Add(new OptionalConstrainedValueParameter("StrategyParameterCreator", "The operator that creates the strategy parameters."));
Parameters.Add(new OptionalConstrainedValueParameter("StrategyParameterCrossover", "The operator that recombines the strategy parameters."));
Parameters.Add(new OptionalConstrainedValueParameter("StrategyParameterManipulator", "The operator that manipulates the strategy parameters."));
Parameters.Add(new ValueParameter("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
RandomCreator randomCreator = new RandomCreator();
SolutionsCreator solutionsCreator = new SolutionsCreator();
UniformSubScopesProcessor strategyVectorProcessor = new UniformSubScopesProcessor();
Placeholder strategyVectorCreator = new Placeholder();
EvolutionStrategyMainLoop mainLoop = new EvolutionStrategyMainLoop();
OperatorGraph.InitialOperator = randomCreator;
randomCreator.RandomParameter.ActualName = "Random";
randomCreator.SeedParameter.ActualName = SeedParameter.Name;
randomCreator.SeedParameter.Value = null;
randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
randomCreator.SetSeedRandomlyParameter.Value = null;
randomCreator.Successor = solutionsCreator;
solutionsCreator.NumberOfSolutionsParameter.ActualName = PopulationSizeParameter.Name;
solutionsCreator.Successor = strategyVectorProcessor;
strategyVectorProcessor.Operator = strategyVectorCreator;
strategyVectorProcessor.Successor = mainLoop;
strategyVectorCreator.OperatorParameter.ActualName = "StrategyParameterCreator";
mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
mainLoop.PopulationSizeParameter.ActualName = PopulationSizeParameter.Name;
mainLoop.ParentsPerChildParameter.ActualName = ParentsPerChildParameter.Name;
mainLoop.ChildrenParameter.ActualName = ChildrenParameter.Name;
mainLoop.MaximumGenerationsParameter.ActualName = MaximumGenerationsParameter.Name;
mainLoop.MutatorParameter.ActualName = MutatorParameter.Name;
mainLoop.RecombinatorParameter.ActualName = RecombinatorParameter.Name;
mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
mainLoop.ResultsParameter.ActualName = "Results";
qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
ParameterizeAnalyzers();
UpdateAnalyzers();
Initialize();
}
[StorableConstructor]
private EvolutionStrategy(bool deserializing) : base(deserializing) { }
public override IDeepCloneable Clone(Cloner cloner) {
EvolutionStrategy clone = (EvolutionStrategy)base.Clone(cloner);
clone.qualityAnalyzer = (BestAverageWorstQualityAnalyzer)cloner.Clone(qualityAnalyzer);
clone.Initialize();
return clone;
}
public override void Prepare() {
if (Problem != null) base.Prepare();
}
#region Events
protected override void OnProblemChanged() {
ParameterizeStochasticOperator(Problem.SolutionCreator);
ParameterizeStochasticOperator(Problem.Evaluator);
foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
ParameterizeSolutionsCreator();
ParameterizeMainLoop();
ParameterizeAnalyzers();
ParameterizeIterationBasedOperators();
UpdateRecombinators();
UpdateMutators();
UpdateAnalyzers();
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);
ParameterizeIterationBasedOperators();
UpdateRecombinators();
UpdateMutators();
UpdateAnalyzers();
base.Problem_OperatorsChanged(sender, e);
}
private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
ParameterizeMainLoop();
ParameterizeAnalyzers();
}
private void PopulationSizeParameter_ValueChanged(object sender, EventArgs e) {
PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
PopulationSize_ValueChanged(null, EventArgs.Empty);
}
private void PopulationSize_ValueChanged(object sender, EventArgs e) {
if (PopulationSize.Value <= 0) PopulationSize.Value = 1;
if (!PlusSelection.Value && Children.Value < PopulationSize.Value)
Children.Value = PopulationSize.Value;
if (PopulationSize.Value < ParentsPerChild.Value)
ParentsPerChild.Value = PopulationSize.Value;
}
private void ParentsPerChildParameter_ValueChanged(object sender, EventArgs e) {
ParentsPerChild.ValueChanged += new EventHandler(ParentsPerChild_ValueChanged);
ParentsPerChild_ValueChanged(null, EventArgs.Empty);
}
private void ParentsPerChild_ValueChanged(object sender, EventArgs e) {
if (ParentsPerChild.Value < 1 || ParentsPerChild.Value > 1 && RecombinatorParameter.ValidValues.Count == 0)
ParentsPerChild.Value = 1;
if (ParentsPerChild.Value > 1 && Recombinator == null) Recombinator = RecombinatorParameter.ValidValues.First();
if (ParentsPerChild.Value > 1 && ParentsPerChild.Value > PopulationSize.Value)
PopulationSize.Value = ParentsPerChild.Value;
}
private void ChildrenParameter_ValueChanged(object sender, EventArgs e) {
Children.ValueChanged += new EventHandler(Children_ValueChanged);
Children_ValueChanged(null, EventArgs.Empty);
}
private void Children_ValueChanged(object sender, EventArgs e) {
if (Children.Value <= 0) Children.Value = 1;
if (!PlusSelection.Value && Children.Value < PopulationSize.Value)
PopulationSize.Value = Children.Value;
}
private void PlusSelectionParameter_ValueChanged(object sender, EventArgs e) {
PlusSelection.ValueChanged += new EventHandler(PlusSelection_ValueChanged);
PlusSelection_ValueChanged(null, EventArgs.Empty);
}
private void PlusSelection_ValueChanged(object sender, EventArgs e) {
if (!PlusSelection.Value && Children.Value < PopulationSize.Value)
Children.Value = PopulationSize.Value;
}
private void RecombinatorParameter_ValueChanged(object sender, EventArgs e) {
if (Recombinator == null && ParentsPerChild.Value > 1) ParentsPerChild.Value = 1;
else if (Recombinator != null && ParentsPerChild.Value == 1) ParentsPerChild.Value = 2;
if (Recombinator != null && Mutator is ISelfAdaptiveManipulator && StrategyParameterCrossover == null) {
if (StrategyParameterCrossoverParameter.ValidValues.Count > 0)
StrategyParameterCrossover = StrategyParameterCrossoverParameter.ValidValues.First();
}
}
private void MutatorParameter_ValueChanged(object sender, EventArgs e) {
if (Mutator is ISelfAdaptiveManipulator) {
UpdateStrategyParameterOperators();
if (StrategyParameterCreatorParameter.ValidValues.Count == 0) throw new InvalidOperationException("ERROR: There is no strategy parameter creator for this manipulation operator.");
} else {
StrategyParameterCreatorParameter.ValidValues.Clear();
StrategyParameterCrossoverParameter.ValidValues.Clear();
StrategyParameterManipulatorParameter.ValidValues.Clear();
UpdateRecombinators();
}
}
private void StrategyParameterCreatorParameter_ValueChanged(object sender, EventArgs e) {
if (Mutator is ISelfAdaptiveManipulator && StrategyParameterCreator == null && StrategyParameterCreatorParameter.ValidValues.Count > 0)
StrategyParameterCreator = StrategyParameterCreatorParameter.ValidValues.First();
}
private void StrategyParameterCrossoverParameter_ValueChanged(object sender, EventArgs e) {
if (Mutator is ISelfAdaptiveManipulator && Recombinator != null && StrategyParameterCrossover == null && StrategyParameterCrossoverParameter.ValidValues.Count > 0)
StrategyParameterCrossover = StrategyParameterCrossoverParameter.ValidValues.First();
}
#endregion
#region Helpers
[StorableHook(HookType.AfterDeserialization)]
private void Initialize() {
PopulationSizeParameter.ValueChanged += new EventHandler(PopulationSizeParameter_ValueChanged);
PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
ParentsPerChildParameter.ValueChanged += new EventHandler(ParentsPerChildParameter_ValueChanged);
ParentsPerChild.ValueChanged += new EventHandler(ParentsPerChild_ValueChanged);
ChildrenParameter.ValueChanged += new EventHandler(ChildrenParameter_ValueChanged);
Children.ValueChanged += new EventHandler(Children_ValueChanged);
PlusSelectionParameter.ValueChanged += new EventHandler(PlusSelectionParameter_ValueChanged);
PlusSelection.ValueChanged += new EventHandler(PlusSelection_ValueChanged);
RecombinatorParameter.ValueChanged += new EventHandler(RecombinatorParameter_ValueChanged);
MutatorParameter.ValueChanged += new EventHandler(MutatorParameter_ValueChanged);
StrategyParameterCrossoverParameter.ValueChanged += new EventHandler(StrategyParameterCrossoverParameter_ValueChanged);
StrategyParameterCreatorParameter.ValueChanged += new EventHandler(StrategyParameterCreatorParameter_ValueChanged);
if (Problem != null)
Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
}
private void ParameterizeSolutionsCreator() {
SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
}
private void ParameterizeMainLoop() {
MainLoop.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
}
private void ParameterizeStochasticOperator(IOperator op) {
if (op is IStochasticOperator)
((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
}
private void ParameterizeAnalyzers() {
qualityAnalyzer.ResultsParameter.ActualName = "Results";
if (Problem != null) {
qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
}
}
private void ParameterizeIterationBasedOperators() {
if (Problem != null) {
foreach (IIterationBasedOperator op in Problem.Operators.OfType()) {
op.IterationsParameter.ActualName = "Generations";
op.MaximumIterationsParameter.ActualName = "MaximumGenerations";
}
}
}
private void UpdateStrategyParameterOperators() {
IStrategyParameterCreator oldStrategyCreator = StrategyParameterCreator;
IStrategyParameterCrossover oldStrategyCrossover = StrategyParameterCrossover;
IStrategyParameterManipulator oldStrategyManipulator = StrategyParameterManipulator;
ClearStrategyParameterOperators();
ISelfAdaptiveManipulator manipulator = (Mutator as ISelfAdaptiveManipulator);
if (manipulator != null) {
var operators = Problem.Operators.Where(x => manipulator.StrategyParameterType.IsAssignableFrom(x.GetType())).OrderBy(x => x.Name);
foreach (IStrategyParameterCreator strategyCreator in operators.OfType())
StrategyParameterCreatorParameter.ValidValues.Add(strategyCreator);
foreach (IStrategyParameterCrossover strategyRecombinator in operators.OfType())
StrategyParameterCrossoverParameter.ValidValues.Add(strategyRecombinator);
foreach (IStrategyParameterManipulator strategyManipulator in operators.OfType())
StrategyParameterManipulatorParameter.ValidValues.Add(strategyManipulator);
if (StrategyParameterCrossoverParameter.ValidValues.Count == 0)
RecombinatorParameter.ValidValues.Clear(); // if there is no strategy parameter crossover, there can be no crossover when the mutation operator needs strategy parameters
if (oldStrategyCreator != null) {
IStrategyParameterCreator tmp1 = StrategyParameterCreatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldStrategyCreator.GetType());
if (tmp1 != null) StrategyParameterCreator = tmp1;
} else if (StrategyParameterCreatorParameter.ValidValues.Count > 0) StrategyParameterCreator = StrategyParameterCreatorParameter.ValidValues.First();
if (oldStrategyCrossover != null) {
IStrategyParameterCrossover tmp2 = StrategyParameterCrossoverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldStrategyCrossover.GetType());
if (tmp2 != null) StrategyParameterCrossover = tmp2;
} else if (StrategyParameterCrossoverParameter.ValidValues.Count > 0) StrategyParameterCrossover = StrategyParameterCrossoverParameter.ValidValues.First();
if (oldStrategyManipulator != null) {
IStrategyParameterManipulator tmp3 = StrategyParameterManipulatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldStrategyManipulator.GetType());
if (tmp3 != null) StrategyParameterManipulator = tmp3;
} else if (StrategyParameterManipulatorParameter.ValidValues.Count > 0) StrategyParameterManipulator = StrategyParameterManipulatorParameter.ValidValues.First();
}
}
private void ClearStrategyParameterOperators() {
StrategyParameterCreatorParameter.ValidValues.Clear();
StrategyParameterCrossoverParameter.ValidValues.Clear();
StrategyParameterManipulatorParameter.ValidValues.Clear();
}
private void UpdateRecombinators() {
ICrossover oldRecombinator = Recombinator;
RecombinatorParameter.ValidValues.Clear();
foreach (ICrossover recombinator in Problem.Operators.OfType().OrderBy(x => x.Name)) {
RecombinatorParameter.ValidValues.Add(recombinator);
}
if (oldRecombinator != null) {
ICrossover recombinator = RecombinatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldRecombinator.GetType());
if (recombinator != null) RecombinatorParameter.Value = recombinator;
}
}
private void UpdateMutators() {
IManipulator oldMutator = MutatorParameter.Value;
MutatorParameter.ValidValues.Clear();
foreach (IManipulator mutator in Problem.Operators.OfType().OrderBy(x => x.Name))
MutatorParameter.ValidValues.Add(mutator);
if (oldMutator != null) {
IManipulator mutator = MutatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMutator.GetType());
if (mutator != null) MutatorParameter.Value = mutator;
}
}
private void UpdateAnalyzers() {
Analyzer.Operators.Clear();
Analyzer.Operators.Add(qualityAnalyzer);
if (Problem != null) {
foreach (IAnalyzer analyzer in Problem.Operators.OfType().OrderBy(x => x.Name))
Analyzer.Operators.Add(analyzer);
}
}
#endregion
}
}