#region License Information
/* HeuristicLab
* Copyright (C) 2002-2009 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.Xml;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Operators;
using HeuristicLab.Random;
using HeuristicLab.Logging;
using HeuristicLab.Selection;
using HeuristicLab.RealVector;
namespace HeuristicLab.ES {
///
/// Class for the heuristic optimization technique "evolution strategy".
///
public class ES : ItemBase, IEditable {
#region Create Operators
///
/// Creates a new evolution strategy.
///
/// The engine of the ES to create.
public static void Create(IEngine engine) {
engine.OperatorGraph.Clear();
CombinedOperator co = CreateES();
co.Name = "σSA-ES";
engine.OperatorGraph.AddOperator(co);
engine.OperatorGraph.InitialOperator = co;
engine.Reset();
}
private static CombinedOperator CreateES() {
CombinedOperator op = new CombinedOperator();
SequentialProcessor sp = new SequentialProcessor();
op.OperatorGraph.AddOperator(sp);
op.OperatorGraph.InitialOperator = sp;
CombinedOperator co1 = CreateVariableInjection();
co1.Name = "Variable Injection";
op.OperatorGraph.AddOperator(co1);
sp.AddSubOperator(co1);
// place holder for ProblemInjector
EmptyOperator eo1 = new EmptyOperator();
eo1.Name = "ProblemInjector";
op.OperatorGraph.AddOperator(eo1);
co1.AddSubOperator(eo1);
CombinedOperator co2 = CreatePopulationInitialization();
co2.Name = "Population Initialization";
op.OperatorGraph.AddOperator(co2);
sp.AddSubOperator(co2);
// place holder for SolutionGenerator
EmptyOperator eo2 = new EmptyOperator();
eo2.Name = "SolutionGenerator";
op.OperatorGraph.AddOperator(eo2);
co2.AddSubOperator(eo2);
// place holder for Evaluator
EmptyOperator eo3 = new EmptyOperator();
eo3.Name = "Evaluator";
op.OperatorGraph.AddOperator(eo3);
co2.AddSubOperator(eo3);
CombinedOperator co3 = CreateESMain();
co3.Name = "ES Main";
op.OperatorGraph.AddOperator(co3);
sp.AddSubOperator(co3);
// place holder for Mutator
EmptyOperator eo4 = new EmptyOperator();
eo4.Name = "Mutator";
op.OperatorGraph.AddOperator(eo4);
co3.AddSubOperator(eo4);
// place holder for Evaluator
co3.AddSubOperator(eo3);
// place holder for Recombinator
EmptyOperator eo5 = new EmptyOperator();
eo5.Name = "Recombinator";
op.OperatorGraph.AddOperator(eo5);
co3.AddSubOperator(eo5);
return op;
}
private static CombinedOperator CreateVariableInjection() {
CombinedOperator op = new CombinedOperator();
SequentialProcessor sp = new SequentialProcessor();
op.OperatorGraph.AddOperator(sp);
op.OperatorGraph.InitialOperator = sp;
RandomInjector ri = new RandomInjector();
op.OperatorGraph.AddOperator(ri);
sp.AddSubOperator(ri);
OperatorExtractor oe = new OperatorExtractor();
oe.Name = "ProblemInjector";
oe.GetVariableInfo("Operator").ActualName = "ProblemInjector";
op.OperatorGraph.AddOperator(oe);
sp.AddSubOperator(oe);
VariableInjector vi = new VariableInjector();
vi.AddVariable(new Variable("ESmu", new IntData(1)));
vi.AddVariable(new Variable("ESrho", new IntData(1)));
vi.AddVariable(new Variable("ESlambda", new IntData(1)));
vi.AddVariable(new Variable("EvaluatedSolutions", new IntData()));
vi.AddVariable(new Variable("PlusNotation", new BoolData(true)));
vi.AddVariable(new Variable("ProblemDimension", new IntData(1)));
vi.AddVariable(new Variable("ShakingFactorsMin", new DoubleData(0.1)));
vi.AddVariable(new Variable("ShakingFactorsMax", new DoubleData(5.0)));
vi.AddVariable(new Variable("Generations", new IntData()));
vi.AddVariable(new Variable("MaximumGenerations", new IntData(1000)));
vi.AddVariable(new Variable("GeneralLearningRate", new DoubleData(1.0 / Math.Sqrt(2))));
vi.AddVariable(new Variable("LearningRate", new DoubleData(1.0 / Math.Sqrt(2))));
op.OperatorGraph.AddOperator(vi);
sp.AddSubOperator(vi);
return op;
}
private static CombinedOperator CreatePopulationInitialization() {
CombinedOperator op = new CombinedOperator();
SequentialProcessor sp1 = new SequentialProcessor();
op.OperatorGraph.AddOperator(sp1);
op.OperatorGraph.InitialOperator = sp1;
SubScopesCreater ssc = new SubScopesCreater();
ssc.GetVariableInfo("SubScopes").ActualName = "ESmu";
op.OperatorGraph.AddOperator(ssc);
sp1.AddSubOperator(ssc);
UniformSequentialSubScopesProcessor ussp = new UniformSequentialSubScopesProcessor();
op.OperatorGraph.AddOperator(ussp);
sp1.AddSubOperator(ussp);
SequentialProcessor sp2 = new SequentialProcessor();
op.OperatorGraph.AddOperator(sp2);
ussp.AddSubOperator(sp2);
OperatorExtractor oe1 = new OperatorExtractor();
oe1.Name = "SolutionGenerator";
oe1.GetVariableInfo("Operator").ActualName = "SolutionGenerator";
op.OperatorGraph.AddOperator(oe1);
sp2.AddSubOperator(oe1);
OperatorExtractor oe2 = new OperatorExtractor();
oe2.Name = "Evaluator";
oe2.GetVariableInfo("Operator").ActualName = "Evaluator";
op.OperatorGraph.AddOperator(oe2);
sp2.AddSubOperator(oe2);
Counter c = new Counter();
c.GetVariableInfo("Value").ActualName = "EvaluatedSolutions";
op.OperatorGraph.AddOperator(c);
sp2.AddSubOperator(c);
UniformRandomRealVectorGenerator urrvg = new UniformRandomRealVectorGenerator();
urrvg.GetVariableInfo("Length").ActualName = "ProblemDimension";
urrvg.GetVariableInfo("Minimum").ActualName = "ShakingFactorsMin";
urrvg.GetVariableInfo("Maximum").ActualName = "ShakingFactorsMax";
urrvg.GetVariableInfo("RealVector").ActualName = "ShakingFactors";
op.OperatorGraph.AddOperator(urrvg);
sp2.AddSubOperator(urrvg);
Sorter s = new Sorter();
s.GetVariableInfo("Descending").ActualName = "Maximization";
s.GetVariableInfo("Value").ActualName = "Quality";
op.OperatorGraph.AddOperator(s);
sp1.AddSubOperator(s);
return op;
}
private static CombinedOperator CreateESMain() {
CombinedOperator op = new CombinedOperator();
SequentialProcessor sp = new SequentialProcessor();
op.OperatorGraph.AddOperator(sp);
op.OperatorGraph.InitialOperator = sp;
ESRandomSelector rs = new ESRandomSelector();
rs.Name = "Child Selector";
rs.GetVariableInfo("Lambda").ActualName = "ESlambda";
rs.GetVariableInfo("Rho").ActualName = "ESrho";
op.OperatorGraph.AddOperator(rs);
sp.AddSubOperator(rs);
SequentialSubScopesProcessor ssp = new SequentialSubScopesProcessor();
op.OperatorGraph.AddOperator(ssp);
sp.AddSubOperator(ssp);
EmptyOperator eo = new EmptyOperator();
op.OperatorGraph.AddOperator(eo);
ssp.AddSubOperator(eo);
CombinedOperator co1 = CreateCreateChildren();
co1.Name = "Create Children";
op.OperatorGraph.AddOperator(co1);
ssp.AddSubOperator(co1);
ConditionalBranch cb1 = new ConditionalBranch();
cb1.Name = "Plus or Comma Replacement";
cb1.GetVariableInfo("Condition").ActualName = "PlusNotation";
op.OperatorGraph.AddOperator(cb1);
sp.AddSubOperator(cb1);
MergingReducer mr = new MergingReducer();
mr.Name = "Plus Replacement";
op.OperatorGraph.AddOperator(mr);
cb1.AddSubOperator(mr);
RightReducer rr = new RightReducer();
rr.Name = "Comma Replacement";
op.OperatorGraph.AddOperator(rr);
cb1.AddSubOperator(rr);
CombinedOperator co2 = CreateReplacement();
co2.Name = "Parents Selection";
op.OperatorGraph.AddOperator(co2);
sp.AddSubOperator(co2);
QualityLogger ql = new QualityLogger();
op.OperatorGraph.AddOperator(ql);
sp.AddSubOperator(ql);
BestAverageWorstQualityCalculator bawqc = new BestAverageWorstQualityCalculator();
op.OperatorGraph.AddOperator(bawqc);
sp.AddSubOperator(bawqc);
DataCollector dc = new DataCollector();
ItemList names = dc.GetVariable("VariableNames").GetValue>();
names.Add(new StringData("BestQuality"));
names.Add(new StringData("AverageQuality"));
names.Add(new StringData("WorstQuality"));
op.OperatorGraph.AddOperator(dc);
sp.AddSubOperator(dc);
LinechartInjector lci = new LinechartInjector();
lci.GetVariableInfo("Linechart").ActualName = "Quality Linechart";
lci.GetVariable("NumberOfLines").GetValue().Data = 3;
op.OperatorGraph.AddOperator(lci);
sp.AddSubOperator(lci);
Counter c = new Counter();
c.GetVariableInfo("Value").ActualName = "Generations";
op.OperatorGraph.AddOperator(c);
sp.AddSubOperator(c);
LessThanComparator ltc = new LessThanComparator();
ltc.GetVariableInfo("LeftSide").ActualName = "Generations";
ltc.GetVariableInfo("RightSide").ActualName = "MaximumGenerations";
ltc.GetVariableInfo("Result").ActualName = "GenerationsCondition";
op.OperatorGraph.AddOperator(ltc);
sp.AddSubOperator(ltc);
ConditionalBranch cb2 = new ConditionalBranch();
cb2.GetVariableInfo("Condition").ActualName = "GenerationsCondition";
op.OperatorGraph.AddOperator(cb2);
sp.AddSubOperator(cb2);
cb2.AddSubOperator(sp);
return op;
}
private static CombinedOperator CreateCreateChildren() {
CombinedOperator op = new CombinedOperator();
SequentialProcessor sp1 = new SequentialProcessor();
op.OperatorGraph.AddOperator(sp1);
op.OperatorGraph.InitialOperator = sp1;
OperatorExtractor oe1 = new OperatorExtractor();
oe1.Name = "Recombinator";
oe1.GetVariableInfo("Operator").ActualName = "Recombinator";
op.OperatorGraph.AddOperator(oe1);
sp1.AddSubOperator(oe1);
UniformSequentialSubScopesProcessor ussp = new UniformSequentialSubScopesProcessor();
op.OperatorGraph.AddOperator(ussp);
sp1.AddSubOperator(ussp);
SequentialProcessor sp2 = new SequentialProcessor();
op.OperatorGraph.AddOperator(sp2);
ussp.AddSubOperator(sp2);
OperatorExtractor oe2 = new OperatorExtractor();
oe2.Name = "Mutator";
oe2.GetVariableInfo("Operator").ActualName = "Mutator";
op.OperatorGraph.AddOperator(oe2);
sp2.AddSubOperator(oe2);
OperatorExtractor oe3 = new OperatorExtractor();
oe3.Name = "Evaluator";
oe3.GetVariableInfo("Operator").ActualName = "Evaluator";
op.OperatorGraph.AddOperator(oe3);
sp2.AddSubOperator(oe3);
Counter c = new Counter();
c.GetVariableInfo("Value").ActualName = "EvaluatedSolutions";
op.OperatorGraph.AddOperator(c);
sp2.AddSubOperator(c);
Sorter s = new Sorter();
s.GetVariableInfo("Value").ActualName = "Quality";
s.GetVariableInfo("Descending").ActualName = "Maximization";
op.OperatorGraph.AddOperator(s);
sp1.AddSubOperator(s);
return op;
}
private static CombinedOperator CreateReplacement() {
CombinedOperator op = new CombinedOperator();
SequentialProcessor sp1 = new SequentialProcessor();
op.OperatorGraph.AddOperator(sp1);
op.OperatorGraph.InitialOperator = sp1;
Sorter s = new Sorter();
s.GetVariableInfo("Descending").ActualName = "Maximization";
s.GetVariableInfo("Value").ActualName = "Quality";
op.OperatorGraph.AddOperator(s);
sp1.AddSubOperator(s);
LeftSelector ls = new LeftSelector();
ls.Name = "Parents Selector";
ls.GetVariableInfo("Selected").ActualName = "ESmu";
ls.GetVariable("CopySelected").Value = new BoolData(false);
op.OperatorGraph.AddOperator(ls);
sp1.AddSubOperator(ls);
RightReducer rr = new RightReducer();
rr.Name = "RightReducer";
op.OperatorGraph.AddOperator(rr);
sp1.AddSubOperator(rr);
return op;
}
#endregion
#region Properties
private IEngine myEngine;
///
/// Gets the engine of the current instance.
///
public IEngine Engine {
get { return myEngine; }
}
private BoolData mySetSeedRandomly;
///
/// Gets or sets the boolean flag whether to set the seed randomly or not.
///
public bool SetSeedRandomly {
get { return mySetSeedRandomly.Data; }
set { mySetSeedRandomly.Data = value; }
}
private IntData mySeed;
///
/// Gets or sets the seed of the current instance.
///
/// Calls of base class
/// in the setter.
public int Seed {
get { return mySeed.Data; }
set {
mySeed.Data = value;
OnChanged();
}
}
private IntData myMu;
///
/// Gets or sets the µ value of the current instance.
///
/// Sets also the λ and the ρ value if necessary. Using the comma notation it must hold that λ >= µ and generally µ >= ρ must hold as well. Calls of
/// base class .
public int Mu {
get { return myMu.Data; }
set {
if (value > 0) {
myMu.Data = value;
if (!PlusNotation && value >= Lambda) myLambda.Data = value + 1;
if (value < Rho) myRho.Data = value;
OnChanged();
}
}
}
private IntData myRho;
///
/// Gets or sets the ρ value of the current instance.
///
/// Sets also the µ value to be as large as the new ρ value if it was smaller before. Calls of
/// base class .
public int Rho {
get { return myRho.Data; }
set {
if (value > 0) {
myRho.Data = value;
if (value > Mu) Mu = value;
OnChanged();
}
}
}
private IntData myLambda;
///
/// Gets or sets the λ value of the current instance.
///
/// If the comma notation is used, it also changes the µ value to be as large as the new λ value if it was larger before. Note that in general for good optimization results it needs to be fairly larger than mu.
/// Calls of base class .
public int Lambda {
get { return myLambda.Data; }
set {
if (value > 0) {
if (PlusNotation) myLambda.Data = value;
else {
if (value >= 1 && value < Mu) {
myLambda.Data = value;
myMu.Data = value;
} else if (value > Mu) {
myLambda.Data = value;
}
}
OnChanged();
}
}
}
private BoolData myPlusNotation;
///
/// Gets or sets the boolean flag whether the plus notation is used (true) or the comma notation (false).
///
/// If set to false (comma notation) it sets λ to be as large as µ if is lower. Note that in general for good optimization results it needs to be fairly larger than µ.
/// Calls of base class .
public bool PlusNotation {
get { return myPlusNotation.Data; }
set {
if (!value && myPlusNotation.Data) { // from plus to point
if (Lambda < Mu) {
myLambda.Data = Mu;
}
}
myPlusNotation.Data = value;
OnChanged();
}
}
private IntData myProblemDimension;
///
/// Gets or sets the problem dimension which determines the length of the strategy vector.
///
/// Calls of base class
/// in the setter.
public int ProblemDimension {
get { return myProblemDimension.Data; }
set { myProblemDimension.Data = value; }
}
private DoubleData myShakingFactorsMin;
///
/// Gets or sets the minimal value for each dimension of the strategy vector.
///
/// Calls of base class
/// in the setter.
public double ShakingFactorsMin {
get { return myShakingFactorsMin.Data; }
set {
myShakingFactorsMin.Data = value;
OnChanged();
}
}
private DoubleData myShakingFactorsMax;
///
/// Gets or sets the maximal value for each dimension of the strategy vector.
///
/// Calls of base class
/// in the setter.
public double ShakingFactorsMax {
get { return myShakingFactorsMax.Data; }
set {
myShakingFactorsMax.Data = value;
OnChanged();
}
}
private DoubleData myGeneralLearningRate;
///
/// Gets or sets the general learning rate (tau0).
///
/// Calls of base class
/// in the setter.
public double GeneralLearningRate {
get { return myGeneralLearningRate.Data; }
set {
if (value > 0.0 && value <= 1.0) {
myGeneralLearningRate.Data = value;
OnChanged();
}
}
}
private DoubleData myLearningRate;
///
/// Gets or sets the learning rate (tau).
///
/// Calls of base class
/// in the setter.
public double LearningRate {
get { return myLearningRate.Data; }
set {
if (value > 0.0 && value <= 1.0) {
myLearningRate.Data = value;
OnChanged();
}
}
}
private IntData myMaximumGenerations;
///
/// Gets or sets the maximum number of generations.
///
public int MaximumGenerations {
get { return myMaximumGenerations.Data; }
set { myMaximumGenerations.Data = value; }
}
private CombinedOperator myES;
private IOperator myESMain;
private IOperator myVariableInjection;
///
/// Gets or sets the problem injection operator.
///
public IOperator ProblemInjector {
get { return myVariableInjection.SubOperators[0]; }
set {
value.Name = "ProblemInjector";
myES.OperatorGraph.RemoveOperator(ProblemInjector.Guid);
myES.OperatorGraph.AddOperator(value);
myVariableInjection.AddSubOperator(value, 0);
}
}
private IOperator myPopulationInitialization;
///
/// Gets or sets the solution generation operator.
///
public IOperator SolutionGenerator {
get { return myPopulationInitialization.SubOperators[0]; }
set {
value.Name = "SolutionGenerator";
myES.OperatorGraph.RemoveOperator(SolutionGenerator.Guid);
myES.OperatorGraph.AddOperator(value);
myPopulationInitialization.AddSubOperator(value, 0);
}
}
///
/// Gets or sets the evaluation operator.
///
public IOperator Evaluator {
get { return myPopulationInitialization.SubOperators[1]; }
set {
value.Name = "Evaluator";
myES.OperatorGraph.RemoveOperator(Evaluator.Guid);
myES.OperatorGraph.AddOperator(value);
myPopulationInitialization.AddSubOperator(value, 1);
myESMain.AddSubOperator(value, 1);
}
}
///
/// Gets or sets the mutation operator.
///
public IOperator Mutator {
get { return myESMain.SubOperators[0]; }
set {
value.Name = "Mutator";
myES.OperatorGraph.RemoveOperator(Mutator.Guid);
myES.OperatorGraph.AddOperator(value);
myESMain.AddSubOperator(value, 0);
}
}
///
/// Gets or sets the recombination operator.
///
public IOperator Recombinator {
get { return myESMain.SubOperators[2]; }
set {
value.Name = "Recombinator";
myES.OperatorGraph.RemoveOperator(Recombinator.Guid);
myES.OperatorGraph.AddOperator(value);
myESMain.AddSubOperator(value, 2);
}
}
#endregion
///
/// Initializes a new instance of having a as engine.
///
public ES() {
myEngine = new SequentialEngine.SequentialEngine();
Create(myEngine);
SetReferences();
}
///
/// Creates a new instance of to display the current instance.
///
/// The created view as .
public override IView CreateView() {
return new ESEditor(this);
}
///
/// Creates a new instance of to display the current instance.
///
/// The created editor as .
public virtual IEditor CreateEditor() {
return new ESEditor(this);
}
///
/// Clones the current instance (deep clone).
///
/// Uses method of the class to
/// clone the engine.
/// A dictionary of all already cloned objects.
/// (Needed to avoid cycles.)
/// The cloned object as .
public override object Clone(IDictionary clonedObjects) {
ES clone = new ES();
clonedObjects.Add(Guid, clone);
clone.myEngine = (IEngine)Auxiliary.Clone(Engine, clonedObjects);
return clone;
}
#region SetReferences Method
private void SetReferences() {
// ES
CombinedOperator co1 = (CombinedOperator)Engine.OperatorGraph.InitialOperator;
myES = co1;
// SequentialProcessor in ES
SequentialProcessor sp1 = (SequentialProcessor)co1.OperatorGraph.InitialOperator;
// Variable Injection
CombinedOperator co2 = (CombinedOperator)sp1.SubOperators[0];
myVariableInjection = co2;
// SequentialProcessor in Variable Injection
SequentialProcessor sp2 = (SequentialProcessor)co2.OperatorGraph.InitialOperator;
// RandomInjector
RandomInjector ri = (RandomInjector)sp2.SubOperators[0];
mySetSeedRandomly = ri.GetVariable("SetSeedRandomly").GetValue();
mySeed = ri.GetVariable("Seed").GetValue();
// VariableInjector
VariableInjector vi = (VariableInjector)sp2.SubOperators[2];
myMu = vi.GetVariable("ESmu").GetValue();
myRho = vi.GetVariable("ESrho").GetValue();
myLambda = vi.GetVariable("ESlambda").GetValue();
myMaximumGenerations = vi.GetVariable("MaximumGenerations").GetValue();
myPlusNotation = vi.GetVariable("PlusNotation").GetValue();
myProblemDimension = vi.GetVariable("ProblemDimension").GetValue();
myShakingFactorsMin = vi.GetVariable("ShakingFactorsMin").GetValue();
myShakingFactorsMax = vi.GetVariable("ShakingFactorsMax").GetValue();
myGeneralLearningRate = vi.GetVariable("GeneralLearningRate").GetValue();
myLearningRate = vi.GetVariable("LearningRate").GetValue();
// Population Initialization
CombinedOperator co3 = (CombinedOperator)sp1.SubOperators[1];
myPopulationInitialization = co3;
// ES Main
CombinedOperator co4 = (CombinedOperator)sp1.SubOperators[2];
myESMain = co4;
}
#endregion
#region Persistence Methods
///
/// Saves the current instance as in the specified .
///
/// Calls of base class .
///
The engine of the current instance is saved as child node with tag name Engine.
/// The (tag)name of the .
/// The where to save the data.
/// The dictionary of all already persisted objects.
/// (Needed to avoid cycles.)
/// The saved .
public override XmlNode GetXmlNode(string name, XmlDocument document, IDictionary persistedObjects) {
XmlNode node = base.GetXmlNode(name, document, persistedObjects);
node.AppendChild(PersistenceManager.Persist("Engine", Engine, document, persistedObjects));
return node;
}
///
/// Loads the persisted ES from the specified .
///
/// Calls of base class .
/// The engine must be saved as child node with tag name Engine (see
/// ).
/// The where the value is saved.
/// The dictionary of all already restored objects.
/// (Needed to avoid cycles.)
public override void Populate(XmlNode node, IDictionary restoredObjects) {
base.Populate(node, restoredObjects);
myEngine = (IEngine)PersistenceManager.Restore(node.SelectSingleNode("Engine"), restoredObjects);
SetReferences();
}
#endregion
}
}