source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/EvolutionStrategy.cs @ 15563

#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 <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Random;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary {
  public enum ESSelection { Plus = 0, Comma = 1 }

  [Item("Evolution Strategy (GQAP)", "The algorithm implements a simple evolution strategy (ES).")]
  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
  [StorableClass]
  public sealed class EvolutionStrategy : StochasticAlgorithm<ESContext> {

    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<IntValue> lambdaParameter;
    private IFixedValueParameter<IntValue> LambdaParameter {
      get { return lambdaParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> muParameter;
    public IFixedValueParameter<IntValue> MuParameter {
      get { return muParameter; }
    }
    [Storable]
    private FixedValueParameter<EnumValue<ESSelection>> selectionParameter;
    public IFixedValueParameter<EnumValue<ESSelection>> SelectionParameter {
      get { return selectionParameter; }
    }

    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; }
    }

    [StorableConstructor]
    private EvolutionStrategy(bool deserializing) : base(deserializing) { }
    private EvolutionStrategy(EvolutionStrategy original, Cloner cloner)
      : base(original, cloner) {
      lambdaParameter = cloner.Clone(original.lambdaParameter);
      muParameter = cloner.Clone(original.muParameter);
      selectionParameter = cloner.Clone(original.selectionParameter);
    }
    public EvolutionStrategy() {
      Parameters.Add(lambdaParameter = new FixedValueParameter<IntValue>("Lambda", "(λ) The amount of offspring that are created each generation.", new IntValue(10)));
      Parameters.Add(muParameter = new FixedValueParameter<IntValue>("Mu", "(μ) The population size.", new IntValue(1)));
      Parameters.Add(selectionParameter= new FixedValueParameter<EnumValue<ESSelection>>("Selection", "The selection strategy: elitist (plus) or generational (comma).", new EnumValue<ESSelection>(ESSelection.Plus)));
      
      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.BestQuality = double.NaN;
      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 ind = new ESGQAPSolution(assign, eval, Context.Random.NextDouble() * 2 - 1);
        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, Context.Scope, cancellationToken);
    }

    protected override void Run(CancellationToken cancellationToken) {
      var lastUpdate = ExecutionTime;

      while (!StoppingCriterion()) {
        var nextGen = new List<ISingleObjectiveSolutionScope<ESGQAPSolution>>(Lambda);

        for (var l = 0; l < Lambda; l++) {
          var m = Context.AtRandomPopulation();

          var offspring = (ESGQAPSolution)m.Solution.Clone();
          var count = Mutate(m, offspring);
          offspring.SParam += 0.7071 * Context.NormalRand.NextDouble(); //((1.0 / count) - offspring.SParam) / 10.0;

          offspring.Evaluation = Problem.ProblemInstance.Evaluate(offspring.Assignment);
          Context.EvaluatedSolutions++;
          var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation);
          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 = nextGen.Concat(Context.Population).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));

        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);

        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)));
    }

    private int Mutate(ISingleObjectiveSolutionScope<ESGQAPSolution> m, ESGQAPSolution offspring) {
      var stopProb = (Math.Tanh(m.Solution.SParam) + 1) / 2.0; // squash strategy parameter to ]0;1[
      var offspringFeasible = offspring.Evaluation.IsFeasible;
      double[] slack = null;
      if (offspringFeasible) slack = offspring.Evaluation.Slack.ToArray();
      var count = 1;
      foreach (var equip in Enumerable.Range(0, Problem.ProblemInstance.Demands.Length).Shuffle(Context.Random)) {
        var currentLoc = offspring.Assignment[equip];
        if (offspringFeasible) {
          var demand = Problem.ProblemInstance.Demands[equip];
          var feasibleLoc = slack.Select((v, i) => new { Index = i, Value = v })
            .Where(x => x.Index != currentLoc
            && x.Value >= demand).ToList();
          int newLoc = -1;
          if (feasibleLoc.Count == 0) {
            newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
            if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
            offspringFeasible = false;
          } else {
            newLoc = feasibleLoc.SampleRandom(Context.Random).Index;
          }
          offspring.Assignment[equip] = newLoc;
          slack[currentLoc] += demand;
          slack[newLoc] -= demand;
        } else {
          var newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
          if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
          offspring.Assignment[equip] = newLoc;
        }
        if (Context.Random.NextDouble() < stopProb) break;
        count++;
      }

      return count;
    }
  }
}