#region License Information
/* HeuristicLab
* Copyright (C) 2002-2018 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.GeneticAlgorithm {
///
/// A genetic algorithm.
///
[Item("Genetic Algorithm (GA)", "A genetic algorithm.")]
[Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 100)]
[StorableClass]
public sealed class GeneticAlgorithm : 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
private ValueParameter SeedParameter {
get { return (ValueParameter)Parameters["Seed"]; }
}
private ValueParameter SetSeedRandomlyParameter {
get { return (ValueParameter)Parameters["SetSeedRandomly"]; }
}
private ValueParameter PopulationSizeParameter {
get { return (ValueParameter)Parameters["PopulationSize"]; }
}
public IConstrainedValueParameter SelectorParameter {
get { return (IConstrainedValueParameter)Parameters["Selector"]; }
}
public IConstrainedValueParameter CrossoverParameter {
get { return (IConstrainedValueParameter)Parameters["Crossover"]; }
}
private ValueParameter MutationProbabilityParameter {
get { return (ValueParameter)Parameters["MutationProbability"]; }
}
public IConstrainedValueParameter MutatorParameter {
get { return (IConstrainedValueParameter)Parameters["Mutator"]; }
}
private ValueParameter ElitesParameter {
get { return (ValueParameter)Parameters["Elites"]; }
}
private IFixedValueParameter ReevaluateElitesParameter {
get { return (IFixedValueParameter)Parameters["ReevaluateElites"]; }
}
private ValueParameter AnalyzerParameter {
get { return (ValueParameter)Parameters["Analyzer"]; }
}
private ValueParameter MaximumGenerationsParameter {
get { return (ValueParameter)Parameters["MaximumGenerations"]; }
}
#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 ISelector Selector {
get { return SelectorParameter.Value; }
set { SelectorParameter.Value = value; }
}
public ICrossover Crossover {
get { return CrossoverParameter.Value; }
set { CrossoverParameter.Value = value; }
}
public PercentValue MutationProbability {
get { return MutationProbabilityParameter.Value; }
set { MutationProbabilityParameter.Value = value; }
}
public IManipulator Mutator {
get { return MutatorParameter.Value; }
set { MutatorParameter.Value = value; }
}
public IntValue Elites {
get { return ElitesParameter.Value; }
set { ElitesParameter.Value = value; }
}
public bool ReevaluteElites {
get { return ReevaluateElitesParameter.Value.Value; }
set { ReevaluateElitesParameter.Value.Value = value; }
}
public MultiAnalyzer Analyzer {
get { return AnalyzerParameter.Value; }
set { AnalyzerParameter.Value = value; }
}
public IntValue MaximumGenerations {
get { return MaximumGenerationsParameter.Value; }
set { MaximumGenerationsParameter.Value = value; }
}
private RandomCreator RandomCreator {
get { return (RandomCreator)OperatorGraph.InitialOperator; }
}
private SolutionsCreator SolutionsCreator {
get { return (SolutionsCreator)RandomCreator.Successor; }
}
private GeneticAlgorithmMainLoop GeneticAlgorithmMainLoop {
get { return FindMainLoop(SolutionsCreator.Successor); }
}
[Storable]
private BestAverageWorstQualityAnalyzer qualityAnalyzer;
#endregion
public GeneticAlgorithm()
: 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", "The size of the population of solutions.", new IntValue(100)));
Parameters.Add(new ConstrainedValueParameter("Selector", "The operator used to select solutions for reproduction."));
Parameters.Add(new ConstrainedValueParameter("Crossover", "The operator used to cross solutions."));
Parameters.Add(new ValueParameter("MutationProbability", "The probability that the mutation operator is applied on a solution.", new PercentValue(0.05)));
Parameters.Add(new ConstrainedValueParameter("Mutator", "The operator used to mutate solutions."));
Parameters.Add(new ValueParameter("Elites", "The numer of elite solutions which are kept in each generation.", new IntValue(1)));
Parameters.Add(new FixedValueParameter("ReevaluateElites", "Flag to determine if elite individuals should be reevaluated (i.e., if stochastic fitness functions are used.)", new BoolValue(false)) { Hidden = true });
Parameters.Add(new ValueParameter("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
Parameters.Add(new ValueParameter("MaximumGenerations", "The maximum number of generations which should be processed.", new IntValue(1000)));
RandomCreator randomCreator = new RandomCreator();
SolutionsCreator solutionsCreator = new SolutionsCreator();
SubScopesCounter subScopesCounter = new SubScopesCounter();
ResultsCollector resultsCollector = new ResultsCollector();
GeneticAlgorithmMainLoop mainLoop = new GeneticAlgorithmMainLoop();
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 = subScopesCounter;
subScopesCounter.Name = "Initialize EvaluatedSolutions";
subScopesCounter.ValueParameter.ActualName = "EvaluatedSolutions";
subScopesCounter.Successor = resultsCollector;
resultsCollector.CollectedValues.Add(new LookupParameter("Evaluated Solutions", null, "EvaluatedSolutions"));
resultsCollector.ResultsParameter.ActualName = "Results";
resultsCollector.Successor = mainLoop;
mainLoop.SelectorParameter.ActualName = SelectorParameter.Name;
mainLoop.CrossoverParameter.ActualName = CrossoverParameter.Name;
mainLoop.ElitesParameter.ActualName = ElitesParameter.Name;
mainLoop.ReevaluateElitesParameter.ActualName = ReevaluateElitesParameter.Name;
mainLoop.MaximumGenerationsParameter.ActualName = MaximumGenerationsParameter.Name;
mainLoop.MutatorParameter.ActualName = MutatorParameter.Name;
mainLoop.MutationProbabilityParameter.ActualName = MutationProbabilityParameter.Name;
mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
mainLoop.PopulationSizeParameter.ActualName = PopulationSizeParameter.Name;
mainLoop.ResultsParameter.ActualName = "Results";
foreach (ISelector selector in ApplicationManager.Manager.GetInstances().Where(x => !(x is IMultiObjectiveSelector)).OrderBy(x => x.Name))
SelectorParameter.ValidValues.Add(selector);
ISelector proportionalSelector = SelectorParameter.ValidValues.FirstOrDefault(x => x.GetType().Name.Equals("ProportionalSelector"));
if (proportionalSelector != null) SelectorParameter.Value = proportionalSelector;
ParameterizeSelectors();
qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
ParameterizeAnalyzers();
UpdateAnalyzers();
Initialize();
}
[StorableConstructor]
private GeneticAlgorithm(bool deserializing) : base(deserializing) { }
[StorableHook(HookType.AfterDeserialization)]
private void AfterDeserialization() {
// BackwardsCompatibility3.3
#region Backwards compatible code, remove with 3.4
if (!Parameters.ContainsKey("ReevaluateElites")) {
Parameters.Add(new FixedValueParameter("ReevaluateElites", "Flag to determine if elite individuals should be reevaluated (i.e., if stochastic fitness functions are used.)", (BoolValue)new BoolValue(false).AsReadOnly()) { Hidden = true });
}
var optionalMutatorParameter = MutatorParameter as OptionalConstrainedValueParameter;
if (optionalMutatorParameter != null) {
Parameters.Remove(optionalMutatorParameter);
Parameters.Add(new ConstrainedValueParameter("Mutator", "The operator used to mutate solutions."));
foreach (var m in optionalMutatorParameter.ValidValues)
MutatorParameter.ValidValues.Add(m);
if (optionalMutatorParameter.Value == null) MutationProbability.Value = 0; // to guarantee that the old configuration results in the same behavior
else Mutator = optionalMutatorParameter.Value;
optionalMutatorParameter.ValidValues.Clear(); // to avoid dangling references to the old parameter its valid values are cleared
}
#endregion
Initialize();
}
private GeneticAlgorithm(GeneticAlgorithm original, Cloner cloner)
: base(original, cloner) {
qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
Initialize();
}
public override IDeepCloneable Clone(Cloner cloner) {
return new GeneticAlgorithm(this, cloner);
}
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.OfType()) ParameterizeStochasticOperator(op);
ParameterizeSolutionsCreator();
ParameterizeGeneticAlgorithmMainLoop();
ParameterizeSelectors();
ParameterizeAnalyzers();
ParameterizeIterationBasedOperators();
UpdateCrossovers();
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();
ParameterizeGeneticAlgorithmMainLoop();
ParameterizeSelectors();
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.OfType()) ParameterizeStochasticOperator(op);
ParameterizeIterationBasedOperators();
UpdateCrossovers();
UpdateMutators();
UpdateAnalyzers();
base.Problem_OperatorsChanged(sender, e);
}
private void ElitesParameter_ValueChanged(object sender, EventArgs e) {
Elites.ValueChanged += new EventHandler(Elites_ValueChanged);
ParameterizeSelectors();
}
private void Elites_ValueChanged(object sender, EventArgs e) {
ParameterizeSelectors();
}
private void PopulationSizeParameter_ValueChanged(object sender, EventArgs e) {
PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
ParameterizeSelectors();
}
private void PopulationSize_ValueChanged(object sender, EventArgs e) {
ParameterizeSelectors();
}
private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
ParameterizeGeneticAlgorithmMainLoop();
ParameterizeSelectors();
ParameterizeAnalyzers();
}
#endregion
#region Helpers
private void Initialize() {
PopulationSizeParameter.ValueChanged += new EventHandler(PopulationSizeParameter_ValueChanged);
PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
ElitesParameter.ValueChanged += new EventHandler(ElitesParameter_ValueChanged);
Elites.ValueChanged += new EventHandler(Elites_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 ParameterizeGeneticAlgorithmMainLoop() {
GeneticAlgorithmMainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
GeneticAlgorithmMainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
GeneticAlgorithmMainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
}
private void ParameterizeStochasticOperator(IOperator op) {
IStochasticOperator stochasticOp = op as IStochasticOperator;
if (stochasticOp != null) {
stochasticOp.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
stochasticOp.RandomParameter.Hidden = true;
}
}
private void ParameterizeSelectors() {
foreach (ISelector selector in SelectorParameter.ValidValues) {
selector.CopySelected = new BoolValue(true);
selector.NumberOfSelectedSubScopesParameter.Value = new IntValue(2 * (PopulationSizeParameter.Value.Value - ElitesParameter.Value.Value));
selector.NumberOfSelectedSubScopesParameter.Hidden = true;
ParameterizeStochasticOperator(selector);
}
if (Problem != null) {
foreach (ISingleObjectiveSelector selector in SelectorParameter.ValidValues.OfType()) {
selector.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
selector.MaximizationParameter.Hidden = true;
selector.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
selector.QualityParameter.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.ActualName = Problem.Evaluator.QualityParameter.ActualName;
qualityAnalyzer.QualityParameter.Depth = 1;
qualityAnalyzer.QualityParameter.Hidden = true;
qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
qualityAnalyzer.BestKnownQualityParameter.Hidden = true;
}
}
private void ParameterizeIterationBasedOperators() {
if (Problem != null) {
foreach (IIterationBasedOperator op in Problem.Operators.OfType()) {
op.IterationsParameter.ActualName = "Generations";
op.IterationsParameter.Hidden = true;
op.MaximumIterationsParameter.ActualName = "MaximumGenerations";
op.MaximumIterationsParameter.Hidden = true;
}
}
}
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);
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 UpdateMutators() {
IManipulator oldMutator = MutatorParameter.Value;
MutatorParameter.ValidValues.Clear();
IManipulator defaultMutator = Problem.Operators.OfType().FirstOrDefault();
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;
else oldMutator = null;
}
if (oldMutator == null && defaultMutator != null)
MutatorParameter.Value = defaultMutator;
}
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 GeneticAlgorithmMainLoop FindMainLoop(IOperator start) {
IOperator mainLoop = start;
while (mainLoop != null && !(mainLoop is GeneticAlgorithmMainLoop))
mainLoop = ((SingleSuccessorOperator)mainLoop).Successor;
if (mainLoop == null) return null;
else return (GeneticAlgorithmMainLoop)mainLoop;
}
#endregion
}
}