#region License Information /* HeuristicLab * Copyright (C) 2002-2017 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 System.Threading; using HEAL.Attic; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.IntegerVectorEncoding; using HeuristicLab.Optimization; using HeuristicLab.Parameters; using HeuristicLab.Random; namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary { [StorableType("d568d524-1f84-461c-adf5-573d8e472063")] public enum ESSelection { Plus = 0, Comma = 1 } [Item("Evolution Strategy (GQAP)", "The algorithm implements a simple evolution strategy (ES).")] [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)] [StorableType("A1590185-F2E3-4163-896E-28EEC93A5CDF")] public sealed class EvolutionStrategy : StochasticAlgorithm { public override bool SupportsPause { get { return true; } } public override Type ProblemType { get { return typeof(GQAP); } } public new GQAP Problem { get { return (GQAP)base.Problem; } set { base.Problem = value; } } [Storable] private FixedValueParameter lambdaParameter; private IFixedValueParameter LambdaParameter { get { return lambdaParameter; } } [Storable] private FixedValueParameter muParameter; public IFixedValueParameter MuParameter { get { return muParameter; } } [Storable] private FixedValueParameter> selectionParameter; public IFixedValueParameter> SelectionParameter { get { return selectionParameter; } } [Storable] private FixedValueParameter useRecombinationParameter; public IFixedValueParameter UseRecombinationParameter { get { return useRecombinationParameter; } } public int Lambda { get { return lambdaParameter.Value.Value; } set { lambdaParameter.Value.Value = value; } } public int Mu { get { return muParameter.Value.Value; } set { muParameter.Value.Value = value; } } public ESSelection Selection { get { return selectionParameter.Value.Value; } set { selectionParameter.Value.Value = value; } } public bool UseRecombination { get { return useRecombinationParameter.Value.Value; } set { useRecombinationParameter.Value.Value = value; } } [StorableConstructor] private EvolutionStrategy(StorableConstructorFlag _) : base(_) { } private EvolutionStrategy(EvolutionStrategy original, Cloner cloner) : base(original, cloner) { lambdaParameter = cloner.Clone(original.lambdaParameter); muParameter = cloner.Clone(original.muParameter); selectionParameter = cloner.Clone(original.selectionParameter); useRecombinationParameter = cloner.Clone(original.useRecombinationParameter); } public EvolutionStrategy() { Parameters.Add(lambdaParameter = new FixedValueParameter("Lambda", "(λ) The amount of offspring that are created each generation.", new IntValue(10))); Parameters.Add(muParameter = new FixedValueParameter("Mu", "(μ) The population size.", new IntValue(1))); Parameters.Add(selectionParameter= new FixedValueParameter>("Selection", "The selection strategy: elitist (plus) or generational (comma).", new EnumValue(ESSelection.Plus))); Parameters.Add(useRecombinationParameter = new FixedValueParameter("Use Recombination", "Whether to create an \"intermediate\" solution to perform the mutation from.", new BoolValue(false))); Problem = new GQAP(); } public override IDeepCloneable Clone(Cloner cloner) { return new EvolutionStrategy(this, cloner); } protected override void Initialize(CancellationToken cancellationToken) { base.Initialize(cancellationToken); Context.NormalRand = new NormalDistributedRandom(Context.Random, 0, 1); Context.Problem = Problem; Context.BestSolution = null; for (var m = 0; m < Mu; m++) { var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length); var eval = Problem.ProblemInstance.Evaluate(assign); Context.EvaluatedSolutions++; var min = (1.0 / assign.Length) * 2 - 1; // desired min prob var max = (4.0 / assign.Length) * 2 - 1; // desired max prob min = 0.5 * (Math.Log(1 + min) - Math.Log(1 - min)); // arctanh max = 0.5 * (Math.Log(1 + max) - Math.Log(1 - max)); var ind = new ESGQAPSolution(assign, eval, min + Context.Random.NextDouble() * (max - min)); var fit = Problem.ProblemInstance.ToSingleObjective(eval); Context.AddToPopulation(Context.ToScope(ind, fit)); if (double.IsNaN(Context.BestQuality) || fit < Context.BestQuality) { Context.BestQuality = fit; Context.BestSolution = (ESGQAPSolution)ind.Clone(); } } Results.Add(new Result("Iterations", new IntValue(Context.Iterations))); Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions))); Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality))); Results.Add(new Result("BestSolution", Context.BestSolution)); Context.RunOperator(Analyzer, cancellationToken); } protected override void Run(CancellationToken cancellationToken) { base.Run(cancellationToken); var lastUpdate = ExecutionTime; var eq = new IntegerVectorEqualityComparer(); while (!StoppingCriterion()) { var nextGen = new List>(Lambda); for (var l = 0; l < Lambda; l++) { IntegerVector child = null; var sParam = 0.0; if (UseRecombination) { child = DiscreteLocationCrossover.Apply(Context.Random, new ItemArray(Context.Population.Select(x => x.Solution.Assignment)), Problem.ProblemInstance.Demands, Problem.ProblemInstance.Capacities); sParam = Context.Population.Select(x => x.Solution.SParam).Average(); } else { var m = Context.AtRandomPopulation(); child = (IntegerVector)m.Solution.Assignment.Clone(); sParam = m.Solution.SParam; } sParam += 0.7071 * Context.NormalRand.NextDouble(); RelocateEquipmentManipluator.Apply(Context.Random, child, Problem.ProblemInstance.Capacities.Length, (Math.Tanh(sParam) + 1) / 2.0); var eval = Problem.ProblemInstance.Evaluate(child); Context.EvaluatedSolutions++; var offspring = new ESGQAPSolution(child, eval, sParam); var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation); if (Selection == ESSelection.Comma || Context.Population.Select(x => x.Solution.Assignment).All(x => !eq.Equals(child, x))) nextGen.Add(Context.ToScope(offspring, fit)); if (fit < Context.BestQuality) { Context.BestQuality = fit; Context.BestSolution = (ESGQAPSolution)offspring.Clone(); } } if (Selection == ESSelection.Comma) { Context.ReplacePopulation(nextGen.OrderBy(x => x.Fitness).Take(Mu)); } else if (Selection == ESSelection.Plus) { var best = Context.Population.Concat(nextGen).OrderBy(x => x.Fitness).Take(Mu).ToList(); Context.ReplacePopulation(best); } else throw new InvalidOperationException("Unknown Selection strategy: " + Selection); IResult result; if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) { if (Results.TryGetValue("Iterations", out result)) ((IntValue)result.Value).Value = Context.Iterations; else Results.Add(new Result("Iterations", new IntValue(Context.Iterations))); if (Results.TryGetValue("EvaluatedSolutions", out result)) ((IntValue)result.Value).Value = Context.EvaluatedSolutions; else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions))); lastUpdate = ExecutionTime; } if (Results.TryGetValue("BestQuality", out result)) ((DoubleValue)result.Value).Value = Context.BestQuality; else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality))); if (Results.TryGetValue("BestSolution", out result)) result.Value = Context.BestSolution; else Results.Add(new Result("BestSolution", Context.BestSolution)); try { Context.RunOperator(Analyzer, cancellationToken); } catch (OperationCanceledException) { } Context.Iterations++; if (cancellationToken.IsCancellationRequested) break; } IResult result2; if (Results.TryGetValue("Iterations", out result2)) ((IntValue)result2.Value).Value = Context.Iterations; else Results.Add(new Result("Iterations", new IntValue(Context.Iterations))); if (Results.TryGetValue("EvaluatedSolutions", out result2)) ((IntValue)result2.Value).Value = Context.EvaluatedSolutions; else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions))); } } }