#region License Information /* HeuristicLab * Copyright (C) 2002-2015 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.Algorithms.OffspringSelectionGeneticAlgorithm; 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; using HeuristicLab.Selection; namespace HeuristicLab.Algorithms.ALPS.OffspringSelection { [Item("ALPS Offspring Selection Genetic Algorithm", "A genetic algorithm with an age-layered population structure and Offspring Selection.")] [Creatable("Algorithms")] [StorableClass] public sealed class AlpsOffspringSelectionGeneticAlgorithm : Alps { #region Parameter Properties private IValueParameter PopulationSizeParameter { get { return (IValueParameter)Parameters["PopulationSize"]; } } public IConstrainedValueParameter SelectorParameter { get { return (IConstrainedValueParameter)Parameters["Selector"]; } } public IConstrainedValueParameter CrossoverParameter { get { return (IConstrainedValueParameter)Parameters["Crossover"]; } } private IValueParameter MutationProbabilityParameter { get { return (IValueParameter)Parameters["MutationProbability"]; } } public IConstrainedValueParameter MutatorParameter { get { return (IConstrainedValueParameter)Parameters["Mutator"]; } } private IValueParameter ElitesParameter { get { return (IValueParameter)Parameters["Elites"]; } } private IFixedValueParameter ReevaluateElitesParameter { get { return (IFixedValueParameter)Parameters["ReevaluateElites"]; } } private IFixedValueParameter MaximumGenerationsParameter { get { return (IFixedValueParameter)Parameters["MaximumGenerations"]; } } private ValueLookupParameter SuccessRatioParameter { get { return (ValueLookupParameter)Parameters["SuccessRatio"]; } } private ValueLookupParameter ComparisonFactorLowerBoundParameter { get { return (ValueLookupParameter)Parameters["ComparisonFactorLowerBound"]; } } private ValueLookupParameter ComparisonFactorUpperBoundParameter { get { return (ValueLookupParameter)Parameters["ComparisonFactorUpperBound"]; } } public IConstrainedValueParameter ComparisonFactorModifierParameter { get { return (IConstrainedValueParameter)Parameters["ComparisonFactorModifier"]; } } private IFixedValueParameter MaximumSelectionPressureParameter { get { return (IFixedValueParameter)Parameters["MaximumSelectionPressure"]; } } private ValueLookupParameter OffspringSelectionBeforeMutationParameter { get { return (ValueLookupParameter)Parameters["OffspringSelectionBeforeMutation"]; } } private ValueLookupParameter SelectedParentsParameter { get { return (ValueLookupParameter)Parameters["SelectedParents"]; } } private IValueParameter MaximumEvaluatedSolutionsParameter { get { return (IValueParameter)Parameters["MaximumEvaluatedSolutions"]; } } private IFixedValueParameter FillPopulationWithParentsParameter { get { return (IFixedValueParameter)Parameters["FillPopulationWithParents"]; } } #endregion #region Properties public IntArray 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 int MaximumGenerations { get { return MaximumGenerationsParameter.Value.Value; } set { MaximumGenerationsParameter.Value.Value = value; } } public DoubleValue SuccessRatio { get { return SuccessRatioParameter.Value; } set { SuccessRatioParameter.Value = value; } } public DoubleValue ComparisonFactorLowerBound { get { return ComparisonFactorLowerBoundParameter.Value; } set { ComparisonFactorLowerBoundParameter.Value = value; } } public DoubleValue ComparisonFactorUpperBound { get { return ComparisonFactorUpperBoundParameter.Value; } set { ComparisonFactorUpperBoundParameter.Value = value; } } public IDiscreteDoubleValueModifier ComparisonFactorModifier { get { return ComparisonFactorModifierParameter.Value; } set { ComparisonFactorModifierParameter.Value = value; } } public double MaximumSelectionPressure { get { return MaximumSelectionPressureParameter.Value.Value; } set { MaximumSelectionPressureParameter.Value.Value = value; } } public BoolValue OffspringSelectionBeforeMutation { get { return OffspringSelectionBeforeMutationParameter.Value; } set { OffspringSelectionBeforeMutationParameter.Value = value; } } public IntValue SelectedParents { get { return SelectedParentsParameter.Value; } set { SelectedParentsParameter.Value = value; } } public bool FillPopulationWithParents { get { return FillPopulationWithParentsParameter.Value.Value; } set { FillPopulationWithParentsParameter.Value.Value = value; } } private AlpsOffspringSelectionGeneticAlgorithmMainLoop MainLoop { get { return OperatorGraph.Iterate().OfType().First(); } } #endregion [Storable] private ValueAnalyzer layerSelectionPressureAnalyzer; [Storable] private SuccessfulOffspringAnalyzer successfulOffspringAnalyzer; [Storable] private ComparisonTerminator generationsTerminator; //[Storable]private ComparisonTerminator selectionPressureTerminator; [StorableConstructor] private AlpsOffspringSelectionGeneticAlgorithm(bool deserializing) : base(deserializing) { } private AlpsOffspringSelectionGeneticAlgorithm(AlpsOffspringSelectionGeneticAlgorithm original, Cloner cloner) : base(original, cloner) { layerSelectionPressureAnalyzer = cloner.Clone(original.layerSelectionPressureAnalyzer); successfulOffspringAnalyzer = cloner.Clone(original.successfulOffspringAnalyzer); generationsTerminator = cloner.Clone(original.generationsTerminator); //selectionPressureTerminator = cloner.Clone(original.selectionPressureTerminator); Initialize(); } public override IDeepCloneable Clone(Cloner cloner) { return new AlpsOffspringSelectionGeneticAlgorithm(this, cloner); } public AlpsOffspringSelectionGeneticAlgorithm() : base() { Parameters.Add(new ValueParameter("PopulationSize", "The size of the population of solutions each layer.", new IntArray(new[] { 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 OptionalConstrainedValueParameter("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 FixedValueParameter("MaximumGenerations", "The maximum number of generations which should be processed.", new IntValue(1000))); Parameters.Add(new ValueLookupParameter("SuccessRatio", "The ratio of successful to total children that should be achieved.", new DoubleValue(1))); Parameters.Add(new ValueLookupParameter("ComparisonFactorLowerBound", "The lower bound of the comparison factor (start).", new DoubleValue(0))); Parameters.Add(new ValueLookupParameter("ComparisonFactorUpperBound", "The upper bound of the comparison factor (end).", new DoubleValue(1))); Parameters.Add(new OptionalConstrainedValueParameter("ComparisonFactorModifier", "The operator used to modify the comparison factor.", new ItemSet(new IDiscreteDoubleValueModifier[] { new LinearDiscreteDoubleValueModifier() }), new LinearDiscreteDoubleValueModifier())); Parameters.Add(new FixedValueParameter("MaximumSelectionPressure", "The maximum selection pressure that terminates the algorithm.", new DoubleValue(100))); Parameters.Add(new ValueLookupParameter("OffspringSelectionBeforeMutation", "True if the offspring selection step should be applied before mutation, false if it should be applied after mutation.", new BoolValue(false))); Parameters.Add(new ValueLookupParameter("SelectedParents", "How much parents should be selected each time the offspring selection step is performed until the population is filled. This parameter should be about the same or twice the size of PopulationSize for smaller problems, and less for large problems.", new IntValue(200))); Parameters.Add(new FixedValueParameter("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.", new BoolValue(false)) { Hidden = true }); var globalRandomCreator = new RandomCreator(); var layer0Creator = new SubScopesCreator() { Name = "Create Layer Zero" }; var layer0Processor = new LayerUniformSubScopesProcessor(); var localRandomCreator = new LocalRandomCreator(); var layerVariableCreator = new VariableCreator(); var layerSolutionsCreator = new SolutionsCreator(); var initializeAgeProcessor = new UniformSubScopesProcessor(); var initializeAge = new VariableCreator() { Name = "Initialize Age" }; var initializeLayerPopulationSize = new SubScopesCounter() { Name = "Init LayerPopulationCounter" }; var initializeLocalEvaluatedSolutions = new Assigner() { Name = "Initialize LayerEvaluatedSolutions" }; var initializeGlobalEvaluatedSolutions = new DataReducer() { Name = "Initialize EvaluatedSolutions" }; var resultsCollector = new ResultsCollector(); var mainLoop = new AlpsOffspringSelectionGeneticAlgorithmMainLoop(); OperatorGraph.InitialOperator = globalRandomCreator; globalRandomCreator.RandomParameter.ActualName = "GlobalRandom"; globalRandomCreator.SeedParameter.Value = null; globalRandomCreator.SetSeedRandomlyParameter.Value = null; globalRandomCreator.Successor = layer0Creator; layer0Creator.NumberOfSubScopesParameter.Value = new IntValue(1); layer0Creator.Successor = layer0Processor; layer0Processor.Operator = localRandomCreator; layer0Processor.Successor = initializeGlobalEvaluatedSolutions; localRandomCreator.Successor = layerVariableCreator; layerVariableCreator.CollectedValues.Add(new ValueParameter("Layer", new IntValue(0))); layerVariableCreator.Successor = layerSolutionsCreator; layerSolutionsCreator.NumberOfSolutionsParameter.ActualName = PopulationSizeParameter.Name; layerSolutionsCreator.Successor = initializeAgeProcessor; initializeAgeProcessor.Operator = initializeAge; initializeAgeProcessor.Successor = initializeLayerPopulationSize; initializeLayerPopulationSize.ValueParameter.ActualName = "LayerPopulationSize"; initializeLayerPopulationSize.Successor = initializeLocalEvaluatedSolutions; initializeAge.CollectedValues.Add(new ValueParameter("Age", new IntValue(0))); initializeAge.Successor = null; initializeLocalEvaluatedSolutions.LeftSideParameter.ActualName = "LayerEvaluatedSolutions"; initializeLocalEvaluatedSolutions.RightSideParameter.ActualName = "LayerPopulationSize"; initializeLocalEvaluatedSolutions.Successor = null; initializeGlobalEvaluatedSolutions.ReductionOperation.Value.Value = ReductionOperations.Sum; initializeGlobalEvaluatedSolutions.TargetOperation.Value.Value = ReductionOperations.Assign; initializeGlobalEvaluatedSolutions.ParameterToReduce.ActualName = "LayerEvaluatedSolutions"; initializeGlobalEvaluatedSolutions.TargetParameter.ActualName = "EvaluatedSolutions"; initializeGlobalEvaluatedSolutions.Successor = resultsCollector; resultsCollector.CollectedValues.Add(new LookupParameter("Evaluated Solutions", null, "EvaluatedSolutions")); resultsCollector.Successor = mainLoop; mainLoop.ComparisonFactorModifierParameter.ActualName = ComparisonFactorModifierParameter.Name; mainLoop.ComparisonFactorParameter.ActualName = "ComparisonFactor"; mainLoop.ComparisonFactorStartParameter.ActualName = ComparisonFactorLowerBoundParameter.Name; foreach (var selector in ApplicationManager.Manager.GetInstances().Where(s => !(s is IMultiObjectiveSelector)).OrderBy(s => Name)) SelectorParameter.ValidValues.Add(selector); var tournamentSelector = SelectorParameter.ValidValues.OfType().FirstOrDefault(); if (tournamentSelector != null) { tournamentSelector.GroupSizeParameter.Value = new IntValue(4); SelectorParameter.Value = tournamentSelector; } ParameterizeSelectors(); 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(); layerSelectionPressureAnalyzer = new ValueAnalyzer(); successfulOffspringAnalyzer = new SuccessfulOffspringAnalyzer(); layerSelectionPressureAnalyzer.Name = "SelectionPressure Analyzer"; //layerSelectionPressureAnalyzer.ResultsParameter.ActualName = "Results"; layerSelectionPressureAnalyzer.ValueParameter.ActualName = "SelectionPressure"; layerSelectionPressureAnalyzer.ValueParameter.Depth = 0; layerSelectionPressureAnalyzer.ValuesParameter.ActualName = "Selection Pressure History"; //successfulOffspringAnalyzer.ResultsParameter.ActualName = "Results"; successfulOffspringAnalyzer.GenerationsParameter.ActualName = "Generations"; successfulOffspringAnalyzer.SuccessfulOffspringFlagParameter.Value.Value = "SuccessfulOffspring"; successfulOffspringAnalyzer.DepthParameter.Value = new IntValue(1); generationsTerminator = new ComparisonTerminator("Generations", ComparisonType.Less, MaximumGenerationsParameter) { Name = "Generations" }; //selectionPressureTerminator = new ComparisonTerminator("SelectionPressure", ComparisonType.Less, MaximumSelectionPressureParameter) { Name = "Selection Pressure" }; UpdateAnalyzers(); UpdateTerminators(); Initialize(); } #region Events protected override void OnProblemChanged() { base.OnProblemChanged(); ParameterizeSolutionsCreator(); ParameterizeMainLoop(); ParameterizeSelectors(); ParameterizeIterationBasedOperators(); UpdateCrossovers(); UpdateMutators(); UpdateAnalyzers(); UpdateTerminators(); } protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) { base.Problem_SolutionCreatorChanged(sender, e); ParameterizeSolutionsCreator(); } protected override void Problem_EvaluatorChanged(object sender, EventArgs e) { base.Problem_EvaluatorChanged(sender, e); ParameterizeSolutionsCreator(); ParameterizeMainLoop(); ParameterizeSelectors(); } protected override void Problem_OperatorsChanged(object sender, EventArgs e) { base.Problem_OperatorsChanged(sender, e); ParameterizeIterationBasedOperators(); UpdateCrossovers(); UpdateMutators(); UpdateAnalyzers(); UpdateTerminators(); } protected override void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) { base.Evaluator_QualityParameter_ActualNameChanged(sender, e); ParameterizeMainLoop(); ParameterizeSelectors(); } #endregion #region Parameterization private void Initialize() { } private void ParameterizeSolutionsCreator() { MainLoop.LayerUpdator.SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name; MainLoop.LayerUpdator.SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name; } private void ParameterizeMainLoop() { MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name; MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName; MainLoop.MainOperator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name; MainLoop.MainOperator.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name; MainLoop.MainOperator.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName; MainLoop.LayerUpdator.SolutionsCreator.NumberOfSolutionsParameter.ActualName = PopulationSizeParameter.Name; } private void ParameterizeSelectors() { foreach (var selector in SelectorParameter.ValidValues) { selector.CopySelected = new BoolValue(true); selector.NumberOfSelectedSubScopesParameter.Value = null; selector.NumberOfSelectedSubScopesParameter.ActualName = SelectedParentsParameter.Name; selector.NumberOfSelectedSubScopesParameter.Hidden = true; ParameterizeStochasticOperatorForLayer(selector); } if (Problem != null) { foreach (var 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 ParameterizeComparisonFactorModifiers() { foreach (IDiscreteDoubleValueModifier modifier in ComparisonFactorModifierParameter.ValidValues) { modifier.IndexParameter.ActualName = "Generations"; modifier.EndIndexParameter.ActualName = MaximumGenerationsParameter.Name; modifier.EndValueParameter.ActualName = ComparisonFactorUpperBoundParameter.Name; modifier.StartIndexParameter.Value = new IntValue(0); modifier.StartValueParameter.ActualName = ComparisonFactorLowerBoundParameter.Name; modifier.ValueParameter.ActualName = "ComparisonFactor"; } } private void ParameterizeIterationBasedOperators() { if (Problem != null) { foreach (var @operator in Problem.Operators.OfType()) { @operator.IterationsParameter.ActualName = "Generations"; @operator.IterationsParameter.Hidden = true; @operator.MaximumIterationsParameter.ActualName = MaximumGenerationsParameter.Name; @operator.MaximumIterationsParameter.Hidden = true; } } } protected override ReductionOperations GetAgeInheritanceReduction(AgeInheritance ageInheritance) { switch (ageInheritance) { case ALPS.AgeInheritance.Older: return ReductionOperations.Max; case ALPS.AgeInheritance.Agerage: return ReductionOperations.Avg; case ALPS.AgeInheritance.Younger: return ReductionOperations.Min; default: throw new NotSupportedException("AgeInheritance " + ageInheritance + " is not supported."); } } #endregion #region Updates private void UpdateTerminators() { var newTerminators = new Dictionary { {generationsTerminator, !Terminators.Operators.Contains(generationsTerminator) || Terminators.Operators.ItemChecked(generationsTerminator)}, //{selectionPressureTerminator, !Terminators.Operators.Contains(generationsTerminator) || Terminators.Operators.ItemChecked(selectionPressureTerminator)}, {evaluationsTerminator, Terminators.Operators.Contains(evaluationsTerminator) && Terminators.Operators.ItemChecked(evaluationsTerminator)}, {qualityTerminator, Terminators.Operators.Contains(qualityTerminator) && Terminators.Operators.ItemChecked(qualityTerminator) }, {executionTimeTerminator, Terminators.Operators.Contains(executionTimeTerminator) && Terminators.Operators.ItemChecked(executionTimeTerminator)} }; if (Problem != null) { foreach (var terminator in Problem.Operators.OfType()) newTerminators.Add(terminator, !Terminators.Operators.Contains(terminator) || Terminators.Operators.ItemChecked(terminator)); } Terminators.Operators.Clear(); foreach (var newTerminator in newTerminators) Terminators.Operators.Add(newTerminator.Key, newTerminator.Value); } private void UpdateCrossovers() { var oldCrossover = CrossoverParameter.Value; var defaultCrossover = Problem.Operators.OfType().FirstOrDefault(); CrossoverParameter.ValidValues.Clear(); foreach (var crossover in Problem.Operators.OfType().OrderBy(c => c.Name)) { ParameterizeStochasticOperatorForLayer(crossover); CrossoverParameter.ValidValues.Add(crossover); } if (oldCrossover != null) { var crossover = CrossoverParameter.ValidValues.FirstOrDefault(c => c.GetType() == oldCrossover.GetType()); if (crossover != null) CrossoverParameter.Value = crossover; else oldCrossover = null; } if (oldCrossover == null && defaultCrossover != null) CrossoverParameter.Value = defaultCrossover; } private void UpdateMutators() { var oldMutator = MutatorParameter.Value; MutatorParameter.ValidValues.Clear(); foreach (var mutator in Problem.Operators.OfType().OrderBy(m => m.Name)) { ParameterizeStochasticOperatorForLayer(mutator); MutatorParameter.ValidValues.Add(mutator); } if (oldMutator != null) { var mutator = MutatorParameter.ValidValues.FirstOrDefault(m => m.GetType() == oldMutator.GetType()); if (mutator != null) MutatorParameter.Value = mutator; } } private void UpdateAnalyzers() { LayerAnalyzer.Operators.Add(layerSelectionPressureAnalyzer, layerSelectionPressureAnalyzer.EnabledByDefault); layerSelectionPressureAnalyzer.ValueParameter.Depth = 0; // Correct Depth because the depth of layer-analyzers is automatically set to 1 LayerAnalyzer.Operators.Add(successfulOffspringAnalyzer, successfulOffspringAnalyzer.EnabledByDefault); } #endregion } }