#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 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 {
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; }
}
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("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)));
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>(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 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;
}
}
}