#region License Information
/* HeuristicLab
* Copyright (C) 2002-2014 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;
namespace HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm {
[Item("PopDivOffspringSelector", "")]
[StorableClass]
public class PopDivOffspringSelector : InstrumentedOperator, IOffspringSelector {
private const string SuccessRatioChart = "SuccessRatioChart";
private const string SuccessRatioDataRow = "SuccessRatio";
public ValueLookupParameter MaximumSelectionPressureParameter {
get { return (ValueLookupParameter)Parameters["MaximumSelectionPressure"]; }
}
public ValueLookupParameter SuccessRatioParameter {
get { return (ValueLookupParameter)Parameters["SuccessRatio"]; }
}
public LookupParameter SelectionPressureParameter {
get { return (ValueLookupParameter)Parameters["SelectionPressure"]; }
}
public LookupParameter CurrentSuccessRatioParameter {
get { return (LookupParameter)Parameters["CurrentSuccessRatio"]; }
}
public LookupParameter> OffspringPopulationParameter {
get { return (LookupParameter>)Parameters["OffspringPopulation"]; }
}
public LookupParameter OffspringPopulationWinnersParameter {
get { return (LookupParameter)Parameters["OffspringPopulationWinners"]; }
}
public ScopeTreeLookupParameter SuccessfulOffspringParameter {
get { return (ScopeTreeLookupParameter)Parameters["SuccessfulOffspring"]; }
}
public IValueLookupParameter FillPopulationWithParentsParameter {
get { return (IValueLookupParameter)Parameters["FillPopulationWithParents"]; }
}
public ILookupParameter EnoughChildrenGeneratedParameter {
get { return (ILookupParameter)Parameters["EnoughChildrenGenerated"]; }
}
public IValueLookupParameter SimilarityCalculatorParameter {
get { return (IValueLookupParameter)Parameters["SimilarityCalculator"]; }
}
public ValueLookupParameter ResultsParameter {
get { return (ValueLookupParameter)Parameters["Results"]; }
}
public ValueLookupParameter DiversityComparisonFactorParameter {
get { return (ValueLookupParameter)Parameters["DiversityComparisonFactor"]; }
}
private ValueLookupParameter ComparisonFactorLowerBoundParameter {
get { return (ValueLookupParameter)Parameters["DiversityComparisonFactorLowerBound"]; }
}
private ValueLookupParameter ComparisonFactorUpperBoundParameter {
get { return (ValueLookupParameter)Parameters["DiversityComparisonFactorUpperBound"]; }
}
public IConstrainedValueParameter ComparisonFactorModifierParameter {
get { return (IConstrainedValueParameter)Parameters["ComparisonFactorModifier"]; }
}
[StorableConstructor]
protected PopDivOffspringSelector(bool deserializing) : base(deserializing) { }
protected PopDivOffspringSelector(PopDivOffspringSelector original, Cloner cloner)
: base(original, cloner) {
}
public override IDeepCloneable Clone(Cloner cloner) {
return new PopDivOffspringSelector(this, cloner);
}
public PopDivOffspringSelector()
: base() {
Parameters.Add(new ValueLookupParameter("MaximumSelectionPressure", "The maximum selection pressure which prematurely terminates the offspring selection step."));
Parameters.Add(new ValueLookupParameter("SuccessRatio", "The ratio of successful offspring that has to be produced."));
Parameters.Add(new ValueLookupParameter("SelectionPressure", "The amount of selection pressure currently necessary to fulfill the success ratio."));
Parameters.Add(new ValueLookupParameter("CurrentSuccessRatio", "The current success ratio indicates how much of the successful offspring have already been generated."));
Parameters.Add(new LookupParameter>("OffspringPopulation", "Temporary store of the offspring population."));
Parameters.Add(new LookupParameter("OffspringPopulationWinners", "Temporary store the number of successful offspring in the offspring population."));
Parameters.Add(new ScopeTreeLookupParameter("SuccessfulOffspring", "True if the offspring was more successful than its parents.", 2));
Parameters.Add(new ValueLookupParameter("FillPopulationWithParents", "True if the population should be filled with parent individual or false if worse children should be used when the maximum selection pressure is exceeded."));
Parameters.Add(new LookupParameter("EnoughChildrenGenerated", "True if enough children have been generated, otherwise false."));
Parameters.Add(new ValueLookupParameter("SimilarityCalculator", "The similarity calculator that should be used to calculate solution similarity."));
Parameters.Add(new ValueLookupParameter("Results", "The result collection where the population diversity analysis results should be stored."));
Parameters.Add(new ValueLookupParameter("DiversityComparisonFactor", "Determines if the quality should be compared to the better parent (1.0), to the worse (0.0) or to any linearly interpolated value between them.", new DoubleValue(0.0)));
Parameters.Add(new ValueLookupParameter("DiversityComparisonFactorLowerBound", "The lower bound of the comparison factor (start).", new DoubleValue(0.5)));
Parameters.Add(new ValueLookupParameter("DiversityComparisonFactorUpperBound", "The upper bound of the comparison factor (end).", new DoubleValue(1.0)));
Parameters.Add(new OptionalConstrainedValueParameter("ComparisonFactorModifier", "The operator used to modify the comparison factor.", new ItemSet(new IDiscreteDoubleValueModifier[] { new LinearDiscreteDoubleValueModifier() }), new LinearDiscreteDoubleValueModifier()));
foreach (IDiscreteDoubleValueModifier modifier in ApplicationManager.Manager.GetInstances().OrderBy(x => x.Name))
ComparisonFactorModifierParameter.ValidValues.Add(modifier);
IDiscreteDoubleValueModifier linearModifier = ComparisonFactorModifierParameter.ValidValues.FirstOrDefault(x => x.GetType().Name.Equals("LinearDiscreteDoubleValueModifier"));
if (linearModifier != null) ComparisonFactorModifierParameter.Value = linearModifier;
ParameterizeComparisonFactorModifiers();
this.AfterExecutionOperators.Clear();
this.AfterExecutionOperators.Add(ComparisonFactorModifierParameter.Value);
ComparisonFactorModifierParameter.ValueChanged += ComparisonFactorModifierParameter_ValueChanged;
}
void ComparisonFactorModifierParameter_ValueChanged(object sender, EventArgs e) {
this.AfterExecutionOperators.Clear();
this.AfterExecutionOperators.Add(ComparisonFactorModifierParameter.Value);
}
private void ParameterizeComparisonFactorModifiers() {
//TODO: does not work if Generations parameter names are changed
foreach (IDiscreteDoubleValueModifier modifier in ComparisonFactorModifierParameter.ValidValues) {
modifier.IndexParameter.ActualName = "Generations";
modifier.EndIndexParameter.ActualName = "MaximumGenerations";
modifier.EndValueParameter.ActualName = ComparisonFactorUpperBoundParameter.Name;
modifier.StartIndexParameter.Value = new IntValue(0);
modifier.StartValueParameter.ActualName = ComparisonFactorLowerBoundParameter.Name;
modifier.ValueParameter.ActualName = "DiversityComparisonFactor";
}
}
public override IOperation InstrumentedApply() {
double maxSelPress = MaximumSelectionPressureParameter.ActualValue.Value;
double successRatio = SuccessRatioParameter.ActualValue.Value;
bool fillPopulationWithParents = false;
if (FillPopulationWithParentsParameter.ActualValue != null)
fillPopulationWithParents = FillPopulationWithParentsParameter.ActualValue.Value;
IScope scope = ExecutionContext.Scope;
IScope parents = scope.SubScopes[0];
IScope offspring = scope.SubScopes[1];
int populationSize = parents.SubScopes.Count;
// retrieve actual selection pressure and success ratio
DoubleValue selectionPressure = SelectionPressureParameter.ActualValue;
if (selectionPressure == null) {
selectionPressure = new DoubleValue(0);
SelectionPressureParameter.ActualValue = selectionPressure;
}
DoubleValue currentSuccessRatio = CurrentSuccessRatioParameter.ActualValue;
if (currentSuccessRatio == null) {
currentSuccessRatio = new DoubleValue(0);
CurrentSuccessRatioParameter.ActualValue = currentSuccessRatio;
}
DataTable successRatioDataTable;
if (ResultsParameter.ActualValue.ContainsKey(SuccessRatioChart)) {
successRatioDataTable = (DataTable)ResultsParameter.ActualValue[SuccessRatioChart].Value;
} else {
successRatioDataTable = new DataTable(SuccessRatioChart);
successRatioDataTable.Rows.Add(new DataRow(SuccessRatioDataRow));
ResultsParameter.ActualValue.Add(new Result(SuccessRatioChart, successRatioDataTable));
}
// retrieve next population
ItemList population = OffspringPopulationParameter.ActualValue;
IntValue successfulOffspring;
if (population == null) {
population = new ItemList();
OffspringPopulationParameter.ActualValue = population;
selectionPressure.Value = 0; // initialize selection pressure for this round
currentSuccessRatio.Value = 0; // initialize current success ratio for this round
successfulOffspring = new IntValue(0);
OffspringPopulationWinnersParameter.ActualValue = successfulOffspring;
} else successfulOffspring = OffspringPopulationWinnersParameter.ActualValue;
int worseOffspringNeeded = (int)((1 - successRatio) * populationSize) - (population.Count - successfulOffspring.Value);
int successfulOffspringAdded = 0;
double avgPopDiv = DiversityComparisonFactorParameter.Value.Value;
bool takeWorseOffspring = false;
// implement the ActualValue fetch here - otherwise the parent scope would also be included, given that there may be 1000 or more parents, this is quite unnecessary
string tname = SuccessfulOffspringParameter.TranslatedName;
double tmpSelPress = selectionPressure.Value, tmpSelPressInc = 1.0 / populationSize;
int cnt = 0;
int stepWidth = offspring.SubScopes.Count / 5;
for (int i = 0; i < offspring.SubScopes.Count; i++) {
//calculate population diversity so far
if (cnt != 0 && cnt % stepWidth == 0) {
Scope tmpScope = new Scope();
tmpScope.SubScopes.AddRange(population);
double popDiversity = SimilarityCalculatorParameter.ActualValue.CalculateSolutionCrowdSimilarity(tmpScope).Average(x => x.Average());
//this assumes that low-quality solutions are of high diversity
if (popDiversity > avgPopDiv) {
takeWorseOffspring = true;
} else {
takeWorseOffspring = false;
}
}
cnt++;
// fetch value
IVariable tmpVar;
if (!offspring.SubScopes[i].Variables.TryGetValue(tname, out tmpVar)) throw new InvalidOperationException(Name + ": Could not determine if an offspring was successful or not.");
BoolValue tmp = (tmpVar.Value as BoolValue);
if (tmp == null) throw new InvalidOperationException(Name + ": The variable that indicates whether an offspring is successful or not must contain a BoolValue.");
if (takeWorseOffspring) {
IScope currentOffspring = offspring.SubScopes[i];
offspring.SubScopes.Remove(currentOffspring);
i--;
population.Add(currentOffspring);
worseOffspringNeeded--;
} else if (tmp.Value) {
IScope currentOffspring = offspring.SubScopes[i];
offspring.SubScopes.Remove(currentOffspring);
i--;
population.Add(currentOffspring);
successfulOffspringAdded++;
} else if (worseOffspringNeeded > 0 || tmpSelPress >= maxSelPress) {
IScope currentOffspring;
if (!fillPopulationWithParents || worseOffspringNeeded > 0) {
currentOffspring = offspring.SubScopes[i];
offspring.SubScopes.Remove(currentOffspring);
i--;
worseOffspringNeeded--;
} else {
currentOffspring = parents.SubScopes[i];
}
population.Add(currentOffspring);
}
tmpSelPress += tmpSelPressInc;
if (population.Count >= populationSize) break;
}
successfulOffspring.Value += successfulOffspringAdded;
// calculate actual selection pressure and success ratio
selectionPressure.Value = tmpSelPress;
currentSuccessRatio.Value = successfulOffspring.Value / ((double)populationSize);
successRatioDataTable.Rows[SuccessRatioDataRow].Values.Add(currentSuccessRatio.Value);
if (EnoughChildrenGeneratedParameter.ActualValue == null) {
EnoughChildrenGeneratedParameter.ActualValue = new BoolValue();
}
// check if enough children have been generated
if (((selectionPressure.Value < maxSelPress) &&
(currentSuccessRatio.Value < successRatio) &&
(population.Count < populationSize)) ||
(population.Count < populationSize)) {
// more children required -> reduce left and start children generation again
scope.SubScopes.Remove(parents);
scope.SubScopes.Remove(offspring);
while (parents.SubScopes.Count > 0) {
IScope parent = parents.SubScopes[0];
parents.SubScopes.RemoveAt(0);
scope.SubScopes.Add(parent);
}
EnoughChildrenGeneratedParameter.ActualValue.Value = false;
} else {
// enough children generated
offspring.SubScopes.Clear();
offspring.SubScopes.AddRange(population);
scope.Variables.Remove(OffspringPopulationParameter.TranslatedName);
scope.Variables.Remove(OffspringPopulationWinnersParameter.TranslatedName);
EnoughChildrenGeneratedParameter.ActualValue.Value = true;
}
return base.InstrumentedApply();
}
}
}