source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/OSGA.cs @ 15572

#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.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;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary {
  [Item("OSGA (GQAP)", "The algorithm implements a strict offspring selection genetic algorithm (OSGA).")]
  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
  [StorableClass]
  public sealed class OSGA : StochasticAlgorithm<OSGAContext, IntegerVectorEncoding> {

    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> populationSizeParameter;
    public IFixedValueParameter<IntValue> PopulationSizeParameter {
      get { return populationSizeParameter; }
    }
    [Storable]
    private FixedValueParameter<PercentValue> mutationProbabilityParameter;
    public IFixedValueParameter<PercentValue> MutationProbabilityParameter {
      get { return mutationProbabilityParameter; }
    }

    public int PopulationSize {
      get { return populationSizeParameter.Value.Value; }
      set { populationSizeParameter.Value.Value = value; }
    }
    public double MutationProbability {
      get { return mutationProbabilityParameter.Value.Value; }
      set { mutationProbabilityParameter.Value.Value = value; }
    }

    [StorableConstructor]
    private OSGA(bool deserializing) : base(deserializing) { }
    private OSGA(OSGA original, Cloner cloner)
      : base(original, cloner) {
      populationSizeParameter = cloner.Clone(original.populationSizeParameter);
      mutationProbabilityParameter = cloner.Clone(original.mutationProbabilityParameter);
    }
    public OSGA() {
      Parameters.Add(populationSizeParameter = new FixedValueParameter<IntValue>("Population Size", "(μ) The population size.", new IntValue(500)));
      Parameters.Add(mutationProbabilityParameter = new FixedValueParameter<PercentValue>("Mutation Probability", "The chance for an offspring to get mutated.", new PercentValue(0.05)));

      Problem = new GQAP();
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new OSGA(this, cloner);
    }

    protected override void Initialize(CancellationToken cancellationToken) {
      base.Initialize(cancellationToken);
      
      Context.Problem = Problem;
      Context.BestQuality = double.NaN;
      Context.BestSolution = null;

      for (var m = 0; m < PopulationSize; 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 GQAPSolution(assign, eval);
        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 = (GQAPSolution)ind.Clone();
        }
      }

      Context.SelectionPressure = 0;
      Context.Attempts = 0;
      Context.NextGeneration = new ItemList<ISingleObjectiveSolutionScope<GQAPSolution>>();

      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()) {
        
        while (!StoppingCriterion() && Context.NextGeneration.Count < PopulationSize
          && Context.SelectionPressure < 500) {

          var idx1 = Context.Random.Next(PopulationSize);
          var idx2 = (idx1 + Context.Random.Next(1, PopulationSize)) % PopulationSize;

          var p1 = Context.AtPopulation(idx1);
          var p2 = Context.AtPopulation(idx2);

          var assign = DiscreteLocationCrossover.Apply(Context.Random,
            new ItemArray<IntegerVector>(new[] { p1.Solution.Assignment, p2.Solution.Assignment }),
            Problem.ProblemInstance.Demands, Problem.ProblemInstance.Capacities);

          if (Context.Random.NextDouble() < MutationProbability) {
            RelocateEquipmentManipluator.Apply(Context.Random, assign, Problem.ProblemInstance.Capacities.Length, 4.0 / assign.Length);
          }

          var eval = Problem.ProblemInstance.Evaluate(assign);
          Context.EvaluatedSolutions++;

          var offspring = new GQAPSolution(assign, eval);

          var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation);
          if (fit < p1.Fitness && fit < p2.Fitness) { // strict OS
            Context.NextGeneration.Add(Context.ToScope(offspring, fit));

            if (fit < Context.BestQuality) {
              Context.BestQuality = fit;
              Context.BestSolution = (GQAPSolution)offspring.Clone();
            }
          }

          Context.SelectionPressure += 1.0 / PopulationSize;
          Context.Attempts++;
          if (Context.SelectionPressure > 1
            && Context.NextGeneration.Count / (double)PopulationSize < Context.SelectionPressure / 500)
            break;
          if (cancellationToken.IsCancellationRequested) return;
        }
        
        var restart = Context.NextGeneration.Count < PopulationSize;

        if (restart) {
          var best = Context.Population.Concat(Context.NextGeneration)
            .OrderBy(x => x.Fitness).Take(PopulationSize).ToList();
          Context.ReplacePopulation(best);
        } else {
          Context.ReplacePopulation(Context.NextGeneration);
        }
        Context.NextGeneration.Clear();

        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, Context.Scope, cancellationToken);
        } catch (OperationCanceledException) { }

        Context.Iterations++;

        if (restart) {
          var seed = Context.Population.Select(x => (IntegerVector)x.Solution.Assignment.Clone()).ToList();
          for (var s = 0; s < seed.Count; s++) {
            RelocateEquipmentManipluator.Apply(Context.Random, seed[s], Problem.ProblemInstance.Capacities.Length, 0.0);
            var eval = Problem.ProblemInstance.Evaluate(seed[s]);
            Context.EvaluatedSolutions++;
            var fit = Problem.ProblemInstance.ToSingleObjective(eval);
            Context.NextGeneration.Add(Context.ToScope(new GQAPSolution(seed[s], eval), fit));
          }
          Context.ReplacePopulation(Context.NextGeneration);
          Context.NextGeneration.Clear();
        }
        Context.SelectionPressure = 0;

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