Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15562


Ignore:
Timestamp:
12/29/17 23:56:43 (7 years ago)
Author:
abeham
Message:

#1614: added additional algorithms

Location:
branches/GeneralizedQAP
Files:
19 added
5 edited
4 copied
4 moved

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/ESContext.cs

    r15558 r15562  
    2020#endregion
    2121
    22 using System;
    2322using System.Collections.Generic;
    24 using System.Linq;
    25 using System.Runtime.CompilerServices;
    26 using System.Threading;
    2723using HeuristicLab.Common;
    2824using HeuristicLab.Core;
    29 using HeuristicLab.Data;
    30 using HeuristicLab.Optimization;
    3125using HeuristicLab.Parameters;
    3226using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    33 using HeuristicLab.Random;
    3427
    35 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {
    36   [Item("GRASP+PR (GQAP) Context", "Context for GRASP+PR (GQAP).")]
     28namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary {
     29  [Item("Evolution Strategy (GQAP) Context", "Context for Evolution Strategies (GQAP).")]
    3730  [StorableClass]
    38   public sealed class GRASPContext : ParameterizedNamedItem, IExecutionContext {
     31  public sealed class ESContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<ESGQAPSolution>> {
    3932   
    40     private IExecutionContext parent;
    41     public IExecutionContext Parent {
    42       get { return parent; }
    43       set { parent = value; }
    44     }
    45 
    46     [Storable]
    47     private IScope scope;
    48     public IScope Scope {
    49       get { return scope; }
    50       private set { scope = value; }
    51     }
    52 
    53     IKeyedItemCollection<string, IParameter> IExecutionContext.Parameters {
    54       get { return Parameters; }
    55     }
    56 
    5733    [Storable]
    5834    private IValueParameter<GQAP> problem;
    … …  
    6137      set { problem.Value = value; }
    6238    }
    63     public bool Maximization {
    64       get { return Problem.Maximization; }
    65     }
    6639
    6740    [Storable]
    68     private IValueParameter<BoolValue> initialized;
    69     public bool Initialized {
    70       get { return initialized.Value.Value; }
    71       set { initialized.Value.Value = value; }
    72     }
    73 
    74     [Storable]
    75     private IValueParameter<IntValue> iterations;
    76     public int Iterations {
    77       get { return iterations.Value.Value; }
    78       set { iterations.Value.Value = value; }
    79     }
    80 
    81     [Storable]
    82     private IValueParameter<IntValue> evaluatedSolutions;
    83     public int EvaluatedSolutions {
    84       get { return evaluatedSolutions.Value.Value; }
    85       set { evaluatedSolutions.Value.Value = value; }
    86     }
    87 
    88     [Storable]
    89     private IValueParameter<DoubleValue> bestQuality;
    90     public double BestQuality {
    91       get { return bestQuality.Value.Value; }
    92       set { bestQuality.Value.Value = value; }
    93     }
    94 
    95     [Storable]
    96     private IValueParameter<GQAPSolution> bestSolution;
    97     public GQAPSolution BestSolution {
     41    private IValueParameter<ESGQAPSolution> bestSolution;
     42    public ESGQAPSolution BestSolution {
    9843      get { return bestSolution.Value; }
    9944      set { bestSolution.Value = value; }
    10045    }
    10146
    102     [Storable]
    103     private IValueParameter<IntValue> localSearchEvaluations;
    104     public int LocalSearchEvaluations {
    105       get { return localSearchEvaluations.Value.Value; }
    106       set { localSearchEvaluations.Value.Value = value; }
    107     }
    108    
    109     [Storable]
    110     private IValueParameter<IRandom> random;
    111     public IRandom Random {
    112       get { return random.Value; }
    113       set { random.Value = value; }
    114     }
    115 
    116     public IEnumerable<ISingleObjectiveSolutionScope<GQAPSolution>> Population {
    117       get { return scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>(); }
    118     }
    119     public void AddToPopulation(ISingleObjectiveSolutionScope<GQAPSolution> solScope) {
    120       scope.SubScopes.Add(solScope);
    121     }
    122     public void ReplaceAtPopulation(int index, ISingleObjectiveSolutionScope<GQAPSolution> solScope) {
    123       scope.SubScopes[index] = solScope;
    124     }
    125     public ISingleObjectiveSolutionScope<GQAPSolution> AtPopulation(int index) {
    126       return scope.SubScopes[index] as ISingleObjectiveSolutionScope<GQAPSolution>;
    127     }
    128     public void SortPopulation() {
    129       scope.SubScopes.Replace(scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>().OrderBy(x => Maximization ? -x.Fitness : x.Fitness).ToList());
    130     }
    131     public int PopulationCount {
    132       get { return scope.SubScopes.Count; }
     47    public void ReplacePopulation(IEnumerable<ISingleObjectiveSolutionScope<ESGQAPSolution>> replacement) {
     48      Scope.SubScopes.Replace(replacement);
    13349    }
    13450   
    13551    [StorableConstructor]
    136     private GRASPContext(bool deserializing) : base(deserializing) { }
    137     private GRASPContext(GRASPContext original, Cloner cloner)
     52    private ESContext(bool deserializing) : base(deserializing) { }
     53    private ESContext(ESContext original, Cloner cloner)
    13854      : base(original, cloner) {
    139       scope = cloner.Clone(original.scope);
    14055      problem = cloner.Clone(original.problem);
    141       initialized = cloner.Clone(original.initialized);
    142       iterations = cloner.Clone(original.iterations);
    143       evaluatedSolutions = cloner.Clone(original.evaluatedSolutions);
    144       bestQuality = cloner.Clone(original.bestQuality);
    14556      bestSolution = cloner.Clone(original.bestSolution);
    146       localSearchEvaluations = cloner.Clone(original.localSearchEvaluations);
    147       random = cloner.Clone(original.random);
    14857    }
    149     public GRASPContext() : this("GRASP+PR (GQAP) Context") { }
    150     public GRASPContext(string name) : base(name) {
    151       scope = new Scope("Global");
    152 
     58    public ESContext() : this("Evolution Strategy (GQAP) Context") { }
     59    public ESContext(string name) : base(name) {
    15360      Parameters.Add(problem = new ValueParameter<GQAP>("Problem"));
    154       Parameters.Add(initialized = new ValueParameter<BoolValue>("Initialized", new BoolValue(false)));
    155       Parameters.Add(iterations = new ValueParameter<IntValue>("Iterations", new IntValue(0)));
    156       Parameters.Add(evaluatedSolutions = new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
    157       Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN)));
    158       Parameters.Add(bestSolution = new ValueParameter<GQAPSolution>("BestFoundSolution"));
    159       Parameters.Add(localSearchEvaluations = new ValueParameter<IntValue>("LocalSearchEvaluations", new IntValue(0)));
    160       Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
     61      Parameters.Add(bestSolution = new ValueParameter<ESGQAPSolution>("BestFoundSolution"));
    16162    }
    16263
    16364    public override IDeepCloneable Clone(Cloner cloner) {
    164       return new GRASPContext(this, cloner);
     65      return new ESContext(this, cloner);
    16566    }
    16667
    167     public ISingleObjectiveSolutionScope<GQAPSolution> ToScope(GQAPSolution code, double fitness = double.NaN) {
     68    public ISingleObjectiveSolutionScope<ESGQAPSolution> ToScope(ESGQAPSolution code, double fitness = double.NaN) {
    16869      var name = Problem.Encoding.Name;
    169       var scope = new SingleObjectiveSolutionScope<GQAPSolution>(code,
     70      var scope = new SingleObjectiveSolutionScope<ESGQAPSolution>(code,
    17071        name + "Solution", fitness, Problem.Evaluator.QualityParameter.ActualName) {
    17172        Parent = Scope
    … …  
    17576      return scope;
    17677    }
    177 
    178     public void IncrementEvaluatedSolutions(int byEvaluations) {
    179       if (byEvaluations < 0) throw new ArgumentException("Can only increment and not decrement evaluated solutions.");
    180       EvaluatedSolutions += byEvaluations;
    181     }
    182    
    183     private static void ExecuteAlgorithm(IAlgorithm algorithm) {
    184       using (var evt = new AutoResetEvent(false)) {
    185         EventHandler exeStateChanged = (o, args) => {
    186           if (algorithm.ExecutionState != ExecutionState.Started)
    187             evt.Set();
    188         };
    189         algorithm.ExecutionStateChanged += exeStateChanged;
    190         if (algorithm.ExecutionState != ExecutionState.Prepared) {
    191           algorithm.Prepare(true);
    192           evt.WaitOne();
    193         }
    194         algorithm.Start();
    195         evt.WaitOne();
    196         algorithm.ExecutionStateChanged -= exeStateChanged;
    197       }
    198     }
    199     [MethodImpl(MethodImplOptions.AggressiveInlining)]
    200     public bool IsBetter(ISingleObjectiveSolutionScope<GQAPSolution> a, ISingleObjectiveSolutionScope<GQAPSolution> b) {
    201       return IsBetter(a.Fitness, b.Fitness);
    202     }
    203     [MethodImpl(MethodImplOptions.AggressiveInlining)]
    204     public bool IsBetter(double a, double b) {
    205       return double.IsNaN(b) && !double.IsNaN(a)
    206         || Maximization && a > b
    207         || !Maximization && a < b;
    208     }
    209 
    210     #region IExecutionContext members
    211     public IAtomicOperation CreateOperation(IOperator op) {
    212       return new Core.ExecutionContext(this, op, Scope);
    213     }
    214 
    215     public IAtomicOperation CreateOperation(IOperator op, IScope s) {
    216       return new Core.ExecutionContext(this, op, s);
    217     }
    218 
    219     public IAtomicOperation CreateChildOperation(IOperator op) {
    220       return new Core.ExecutionContext(this, op, Scope);
    221     }
    222 
    223     public IAtomicOperation CreateChildOperation(IOperator op, IScope s) {
    224       return new Core.ExecutionContext(this, op, s);
    225     }
    226     #endregion
    227 
    228     #region Engine Helper
    229     public void RunOperator(IOperator op, IScope scope, CancellationToken cancellationToken) {
    230       var stack = new Stack<IOperation>();
    231       stack.Push(CreateChildOperation(op, scope));
    232 
    233       while (stack.Count > 0) {
    234         cancellationToken.ThrowIfCancellationRequested();
    235 
    236         var next = stack.Pop();
    237         if (next is OperationCollection) {
    238           var coll = (OperationCollection)next;
    239           for (int i = coll.Count - 1; i >= 0; i--)
    240             if (coll[i] != null) stack.Push(coll[i]);
    241         } else if (next is IAtomicOperation) {
    242           var operation = (IAtomicOperation)next;
    243           try {
    244             next = operation.Operator.Execute((IExecutionContext)operation, cancellationToken);
    245           } catch (Exception ex) {
    246             stack.Push(operation);
    247             if (ex is OperationCanceledException) throw ex;
    248             else throw new OperatorExecutionException(operation.Operator, ex);
    249           }
    250           if (next != null) stack.Push(next);
    251         }
    252       }
    253     }
    254     #endregion
    25578  }
    25679}

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/EvolutionStrategy.cs

    r15558 r15562  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Linq;
    2425using System.Threading;
    25 using HeuristicLab.Analysis;
    2626using HeuristicLab.Common;
    2727using HeuristicLab.Core;
    … …  
    3333using HeuristicLab.Random;
    3434
    35 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {
    36 
    37   /// <summary>
    38   /// This is an implementation of the algorithm described in Mateus, G.R., Resende, M.G.C. & Silva, R.M.A. J Heuristics (2011) 17: 527. https://doi.org/10.1007/s10732-010-9144-0
    39   /// </summary>
    40   [Item("GRASP+PR (GQAP)", "The algorithm implements the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking as described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
     35namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary {
     36  public enum ESSelection { Plus = 0, Comma = 1 }
     37
     38  [Item("Evolution Strategy (GQAP)", "The algorithm implements a simple evolution strategy (ES).")]
    4139  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
    4240  [StorableClass]
    43   public class GRASP : BasicAlgorithm {
     41  public sealed class EvolutionStrategy : StochasticAlgorithm<ESContext> {
    4442
    4543    public override bool SupportsPause {
    … …  
    5755
    5856    [Storable]
    59     private ValueParameter<IAnalyzer> analyzerParameter;
    60     public IValueParameter<IAnalyzer> AnalyzerParameter {
    61       get { return analyzerParameter; }
    62     }
    63 
     57    private FixedValueParameter<IntValue> lambdaParameter;
     58    private IFixedValueParameter<IntValue> LambdaParameter {
     59      get { return lambdaParameter; }
     60    }
    6461    [Storable]
    65     private FixedValueParameter<BoolValue> setSeedRandomlyParameter;
    66     private IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
    67       get { return setSeedRandomlyParameter; }
     62    private FixedValueParameter<IntValue> muParameter;
     63    public IFixedValueParameter<IntValue> MuParameter {
     64      get { return muParameter; }
    6865    }
    6966    [Storable]
    70     private FixedValueParameter<IntValue> seedParameter;
    71     private IFixedValueParameter<IntValue> SeedParameter {
    72       get { return seedParameter; }
    73     }
    74     [Storable]
    75     private FixedValueParameter<IntValue> eliteSetSizeParameter;
    76     private IFixedValueParameter<IntValue> EliteSetSizeParameter {
    77       get { return eliteSetSizeParameter; }
    78     }
    79     [Storable]
    80     private FixedValueParameter<IntValue> minimiumEliteSetSizeParameter;
    81     public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
    82       get { return minimiumEliteSetSizeParameter; }
    83     }
    84     [Storable]
    85     private FixedValueParameter<IntValue> maximumIterationsParameter;
    86     public IFixedValueParameter<IntValue> MaximumIterationsParameter {
    87       get { return maximumIterationsParameter; }
    88     }
    89     [Storable]
    90     private FixedValueParameter<IntValue> maximumLocalSearchIterationsParameter;
    91     public IFixedValueParameter<IntValue> MaximumLocalSearchIterationsParameter {
    92       get { return maximumIterationsParameter; }
    93     }
    94     [Storable]
    95     private FixedValueParameter<PercentValue> candidateSizeFactorParameter;
    96     public IFixedValueParameter<PercentValue> CandidateSizeFactorParameter {
    97       get { return candidateSizeFactorParameter; }
    98     }
    99     [Storable]
    100     private FixedValueParameter<IntValue> maximumCandidateListSizeParameter;
    101     public IFixedValueParameter<IntValue> MaximumCandidateListSizeParameter {
    102       get { return maximumCandidateListSizeParameter; }
    103     }
    104     [Storable]
    105     private FixedValueParameter<PercentValue> oneMoveProbabilityParameter;
    106     public IFixedValueParameter<PercentValue> OneMoveProbabilityParameter {
    107       get { return oneMoveProbabilityParameter; }
    108     }
    109     [Storable]
    110     private FixedValueParameter<IntValue> minimumDifferenceParameter;
    111     public IFixedValueParameter<IntValue> MinimumDifferenceParameter {
    112       get { return minimumDifferenceParameter; }
    113     }
    114    
    115     public bool SetSeedRandomly {
    116       get { return setSeedRandomlyParameter.Value.Value; }
    117       set { setSeedRandomlyParameter.Value.Value = value; }
    118     }
    119     public int Seed {
    120       get { return seedParameter.Value.Value; }
    121       set { seedParameter.Value.Value = value; }
    122     }
    123     public int EliteSetSize {
    124       get { return eliteSetSizeParameter.Value.Value; }
    125       set { eliteSetSizeParameter.Value.Value = value; }
    126     }
    127     public int MinimumEliteSetSize {
    128       get { return minimiumEliteSetSizeParameter.Value.Value; }
    129       set { minimiumEliteSetSizeParameter.Value.Value = value; }
    130     }
    131     public int MaximumIterations {
    132       get { return maximumIterationsParameter.Value.Value; }
    133       set { maximumIterationsParameter.Value.Value = value; }
    134     }
    135     public int MaximumLocalSearchIterations {
    136       get { return maximumLocalSearchIterationsParameter.Value.Value; }
    137       set { maximumLocalSearchIterationsParameter.Value.Value = value; }
    138     }
    139     public double CandidateSizeFactor {
    140       get { return candidateSizeFactorParameter.Value.Value; }
    141       set { candidateSizeFactorParameter.Value.Value = value; }
    142     }
    143     public int MaximumCandidateListSize {
    144       get { return maximumCandidateListSizeParameter.Value.Value; }
    145       set { maximumCandidateListSizeParameter.Value.Value = value; }
    146     }
    147     public double OneMoveProbability {
    148       get { return oneMoveProbabilityParameter.Value.Value; }
    149       set { oneMoveProbabilityParameter.Value.Value = value; }
    150     }
    151     public int MinimumDifference {
    152       get { return minimumDifferenceParameter.Value.Value; }
    153       set { minimumDifferenceParameter.Value.Value = value; }
     67    private FixedValueParameter<EnumValue<ESSelection>> selectionParameter;
     68    public IFixedValueParameter<EnumValue<ESSelection>> SelectionParameter {
     69      get { return selectionParameter; }
     70    }
     71
     72    public int Lambda {
     73      get { return lambdaParameter.Value.Value; }
     74      set { lambdaParameter.Value.Value = value; }
     75    }
     76    public int Mu {
     77      get { return muParameter.Value.Value; }
     78      set { muParameter.Value.Value = value; }
     79    }
     80    public ESSelection Selection {
     81      get { return selectionParameter.Value.Value; }
     82      set { selectionParameter.Value.Value = value; }
    15483    }
    15584
    15685    [StorableConstructor]
    157     protected GRASP(bool deserializing) : base(deserializing) { }
    158     protected GRASP(GRASP original, Cloner cloner)
     86    private EvolutionStrategy(bool deserializing) : base(deserializing) { }
     87    private EvolutionStrategy(EvolutionStrategy original, Cloner cloner)
    15988      : base(original, cloner) {
    160       setSeedRandomlyParameter = cloner.Clone(original.setSeedRandomlyParameter);
    161       seedParameter = cloner.Clone(original.seedParameter);
    162       analyzerParameter = cloner.Clone(original.analyzerParameter);
    163       eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter);
    164       minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter);
    165       maximumIterationsParameter = cloner.Clone(original.maximumIterationsParameter);
    166       maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter);
    167       candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter);
    168       maximumCandidateListSizeParameter = cloner.Clone(original.maximumCandidateListSizeParameter);
    169       oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter);
    170       minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter);
    171       context = cloner.Clone(original.context);
    172     }
    173     public GRASP() {
    174       Parameters.Add(setSeedRandomlyParameter = new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether to overwrite the seed with a random value each time the algorithm is run.", new BoolValue(true)));
    175       Parameters.Add(seedParameter = new FixedValueParameter<IntValue>("Seed", "The random seed that is used in the stochastic algorithm", new IntValue(0)));
    176       Parameters.Add(analyzerParameter = new ValueParameter<IAnalyzer>("Analyzer", "The analyzers that are used to perform an analysis of the solutions.", new MultiAnalyzer()));
    177       Parameters.Add(eliteSetSizeParameter = new FixedValueParameter<IntValue>("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10)));
    178       Parameters.Add(minimiumEliteSetSizeParameter = new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimal size of the elite set, before local search and path relinking are applied.", new IntValue(2)));
    179       Parameters.Add(maximumIterationsParameter = new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(1000)));
    180       Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter<IntValue>("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100)));
    181       Parameters.Add(candidateSizeFactorParameter = new FixedValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path - relinking step relative to the maximum size.A value of 50 % means that only half of all possible moves are considered each step.", new PercentValue(0.5)));
    182       Parameters.Add(maximumCandidateListSizeParameter = new FixedValueParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
    183       Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
    184       Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<IntValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new IntValue(4)));
     89      lambdaParameter = cloner.Clone(original.lambdaParameter);
     90      muParameter = cloner.Clone(original.muParameter);
     91      selectionParameter = cloner.Clone(original.selectionParameter);
     92    }
     93    public EvolutionStrategy() {
     94      Parameters.Add(lambdaParameter = new FixedValueParameter<IntValue>("Lambda", "(λ) The amount of offspring that are created each generation.", new IntValue(10)));
     95      Parameters.Add(muParameter = new FixedValueParameter<IntValue>("Mu", "(μ) The population size.", new IntValue(1)));
     96      Parameters.Add(selectionParameter= new FixedValueParameter<EnumValue<ESSelection>>("Selection", "The selection strategy: elitist (plus) or generational (comma).", new EnumValue<ESSelection>(ESSelection.Plus)));
     97     
    18598      Problem = new GQAP();
    18699    }
    187100
    188101    public override IDeepCloneable Clone(Cloner cloner) {
    189       return new GRASP(this, cloner);
    190     }
    191 
    192     public override void Prepare() {
    193       base.Prepare();
    194       Results.Clear();
    195       context = null;
    196     }
    197 
    198     [Storable]
    199     private GRASPContext context;
     102      return new EvolutionStrategy(this, cloner);
     103    }
    200104
    201105    protected override void Initialize(CancellationToken cancellationToken) {
    202106      base.Initialize(cancellationToken);
    203       context = new GRASPContext();
    204       context.Problem = Problem;
    205       context.Scope.Variables.Add(new Variable("Results", Results));
    206 
    207       IExecutionContext ctxt = null;
    208       foreach (var item in Problem.ExecutionContextItems)
    209         ctxt = new Core.ExecutionContext(ctxt, item, context.Scope);
    210       ctxt = new Core.ExecutionContext(ctxt, this, context.Scope);
    211       context.Parent = ctxt;
    212 
    213       if (SetSeedRandomly) {
    214         var rnd = new System.Random();
    215         Seed = rnd.Next();
     107
     108      Context.Problem = Problem;     
     109      Context.BestQuality = double.NaN;
     110      Context.BestSolution = null;
     111
     112      for (var m = 0; m < Mu; m++) {
     113        var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
     114        var eval = Problem.ProblemInstance.Evaluate(assign);
     115        Context.EvaluatedSolutions++;
     116
     117        var ind = new ESGQAPSolution(assign, eval, 1.0 / assign.Length);
     118        var fit = Problem.ProblemInstance.ToSingleObjective(eval);
     119        Context.AddToPopulation(Context.ToScope(ind, fit));
     120        if (double.IsNaN(Context.BestQuality) || fit < Context.BestQuality) {
     121          Context.BestQuality = fit;
     122          Context.BestSolution = (ESGQAPSolution)ind.Clone();
     123        }
    216124      }
    217       context.Random = new MersenneTwister((uint)Seed);
    218       context.Iterations = 0;
    219       context.EvaluatedSolutions = 0;
    220       context.BestQuality = double.NaN;
    221       context.BestSolution = null;
    222 
    223       context.Initialized = true;
    224 
    225       Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
    226       Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
    227       Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
    228       Results.Add(new Result("BestSolution", typeof(GQAPSolution)));
    229 
    230       context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
     125
     126      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     127      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     128      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
     129      Results.Add(new Result("BestSolution", Context.BestSolution));
     130
     131      Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
    231132    }
    232133
    233134    protected override void Run(CancellationToken cancellationToken) {
    234       var eq = new IntegerVectorEqualityComparer();
    235       while (!StoppingCriterion()) { // line 2 in Algorithm 1
    236         // next: line 3 in Algorithm 1
    237         var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
    238         if (context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
    239           GQAPSolution pi_prime;
    240           if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
    241             pi_prime = context.AtPopulation(context.Random.Next(context.PopulationCount)).Solution; // line 6 in Algorithm 1
    242           else {
    243             // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
    244             pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
    245             context.EvaluatedSolutions++;
    246           }
    247 
    248           ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
    249           var pi_plus = context.AtPopulation(context.Random.Next(context.PopulationCount)); // line 9 in Algorithm 1
    250           pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
    251           ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
    252           var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
    253           // Book-keeping
    254           if (context.BestQuality > fitness) {
    255             context.BestQuality = fitness;
    256             context.BestSolution = (GQAPSolution)pi_prime.Clone();
    257           }
    258 
    259           if (context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
    260             var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
    261             double[] similarities = context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
    262             if (similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
    263               var replacement = context.Population.Select((v, i) => new { V = v, Index = i })
    264                                           .Where(x => x.V.Fitness >= fit).ToArray();
    265               if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1
    266                 // next two lines: line 14 in Algorithm 1
    267                 replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray();
    268                 context.ReplaceAtPopulation(replacement.Last().Index, context.ToScope(pi_prime, fit));
    269               }
    270             }
    271           } else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
    272             context.AddToPopulation(context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
    273           }
    274         } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
    275           && IsSufficientlyDifferent(pi_prime_vec))  /* cond. 2 of line 21 in Algorithm 1 */ {
    276           var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
    277           context.EvaluatedSolutions++;
    278           var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
    279           context.AddToPopulation(context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
    280           // Book-keeping
    281           if (context.PopulationCount == 1 || context.BestQuality > fitness) {
    282             context.BestQuality = fitness;
    283             context.BestSolution = (GQAPSolution)pi_prime.Clone();
     135      while (!StoppingCriterion()) {
     136        var nextGen = new List<ISingleObjectiveSolutionScope<ESGQAPSolution>>(Lambda);
     137
     138        for (var l = 0; l < Lambda; l++) {
     139          var m = Context.AtRandomPopulation();
     140
     141          var offspring = (ESGQAPSolution)m.Solution.Clone();
     142          var count = Mutate(m, offspring);
     143          offspring.SParam += ((1.0 / count) - offspring.SParam) / 10.0;
     144
     145          offspring.Evaluation = Problem.ProblemInstance.Evaluate(offspring.Assignment);
     146          Context.EvaluatedSolutions++;
     147          var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation);
     148          nextGen.Add(Context.ToScope(offspring, fit));
     149
     150          if (fit < Context.BestQuality) {
     151            Context.BestQuality = fit;
     152            Context.BestSolution = (ESGQAPSolution)offspring.Clone();
    284153          }
    285154        }
    286155
     156        if (Selection == ESSelection.Comma) {
     157          Context.ReplacePopulation(nextGen.OrderBy(x => x.Fitness).Take(Mu));
     158        } else if (Selection == ESSelection.Plus) {
     159          var best = nextGen.Concat(Context.Population).OrderBy(x => x.Fitness).Take(Mu).ToList();
     160          Context.ReplacePopulation(best);
     161        } else throw new InvalidOperationException("Unknown Selection strategy: " + Selection);
     162
    287163        IResult result;
    288164        if (Results.TryGetValue("Iterations", out result))
    289           ((IntValue)result.Value).Value = context.Iterations;
    290         else Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
     165          ((IntValue)result.Value).Value = Context.Iterations;
     166        else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    291167        if (Results.TryGetValue("EvaluatedSolutions", out result))
    292           ((IntValue)result.Value).Value = context.EvaluatedSolutions;
    293         else Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
     168          ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
     169        else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    294170        if (Results.TryGetValue("BestQuality", out result))
    295           ((DoubleValue)result.Value).Value = context.BestQuality;
    296         else Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
     171          ((DoubleValue)result.Value).Value = Context.BestQuality;
     172        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
    297173        if (Results.TryGetValue("BestSolution", out result))
    298           result.Value = context.BestSolution;
    299         else Results.Add(new Result("BestSolution", context.BestSolution));
    300 
    301         context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
    302 
    303         context.Iterations++;
     174          result.Value = Context.BestSolution;
     175        else Results.Add(new Result("BestSolution", Context.BestSolution));
     176
     177        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     178
     179        Context.Iterations++;
     180        if (cancellationToken.IsCancellationRequested) break;
    304181      }
    305182    }
    306183
    307     private bool IsSufficientlyDifferent(IntegerVector vec) {
    308       return context.Population.All(x =>
    309         HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
    310       );
    311     }
    312 
    313     private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) {
    314       // Following code represents line 1 of Algorithm 4
    315       IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment;
    316       Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation;
    317       var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval);
    318       var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval);
    319       if (targetFit < sourceFit) {
    320         var h = source;
    321         source = target;
    322         target = h;
    323         var hh = sourceEval;
    324         sourceEval = targetEval;
    325         targetEval = hh;
     184    private int Mutate(ISingleObjectiveSolutionScope<ESGQAPSolution> m, ESGQAPSolution offspring) {
     185      var offspringFeasible = offspring.Evaluation.IsFeasible;
     186      double[] slack = null;
     187      if (offspringFeasible) slack = offspring.Evaluation.Slack.ToArray();
     188      var count = 1;
     189      foreach (var equip in Enumerable.Range(0, Problem.ProblemInstance.Demands.Length).Shuffle(Context.Random)) {
     190        var currentLoc = offspring.Assignment[equip];
     191        if (offspringFeasible) {
     192          var demand = Problem.ProblemInstance.Demands[equip];
     193          var feasibleLoc = slack.Select((v, i) => new { Index = i, Value = v })
     194            .Where(x => x.Index != currentLoc
     195            && x.Value >= demand).ToList();
     196          int newLoc = -1;
     197          if (feasibleLoc.Count == 0) {
     198            newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
     199            if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
     200            offspringFeasible = false;
     201          } else {
     202            newLoc = feasibleLoc.SampleRandom(Context.Random).Index;
     203          }
     204          offspring.Assignment[equip] = newLoc;
     205          slack[currentLoc] += demand;
     206          slack[newLoc] -= demand;
     207        } else {
     208          var newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
     209          if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
     210          offspring.Assignment[equip] = newLoc;
     211        }
     212        if (Context.Random.NextDouble() < m.Solution.SParam) break;
     213        count++;
    326214      }
    327       int evaluatedSolutions;
    328       // lines 2-36 of Algorithm 4 are implemented in the following call
    329       var pi_star = GQAPPathRelinking.Apply(context.Random, source, sourceEval,
    330         target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
    331         out evaluatedSolutions);
    332       context.EvaluatedSolutions += evaluatedSolutions;
    333       return pi_star;
    334     }
    335 
    336     private void ApproxLocalSearch(GQAPSolution pi_prime) {
    337       var localSearchEvaluations = 0;
    338       ApproximateLocalSearch.Apply(context.Random, pi_prime, MaximumCandidateListSize,
    339         OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
    340       context.EvaluatedSolutions += localSearchEvaluations;
    341     }
    342 
    343     private bool StoppingCriterion() {
    344       return context.Iterations > MaximumIterations;
     215
     216      return count;
    345217    }
    346218  }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs

    r15561 r15562  
    2323using System.Linq;
    2424using System.Threading;
    25 using HeuristicLab.Analysis;
    2625using HeuristicLab.Common;
    2726using HeuristicLab.Core;
    … …  
    3130using HeuristicLab.Parameters;
    3231using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    33 using HeuristicLab.Random;
    3432
    3533namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {
    … …  
    4139  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
    4240  [StorableClass]
    43   public class GRASP : BasicAlgorithm {
     41  public sealed class GRASP : StochasticAlgorithm<GRASPContext> {
    4442
    4543    public override bool SupportsPause {
    … …  
    5755
    5856    [Storable]
    59     private ValueParameter<IAnalyzer> analyzerParameter;
    60     public IValueParameter<IAnalyzer> AnalyzerParameter {
    61       get { return analyzerParameter; }
    62     }
    63 
    64     [Storable]
    65     private FixedValueParameter<BoolValue> setSeedRandomlyParameter;
    66     private IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
    67       get { return setSeedRandomlyParameter; }
    68     }
    69     [Storable]
    70     private FixedValueParameter<IntValue> seedParameter;
    71     private IFixedValueParameter<IntValue> SeedParameter {
    72       get { return seedParameter; }
    73     }
    74     [Storable]
    7557    private FixedValueParameter<IntValue> eliteSetSizeParameter;
    7658    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
    … …  
    8365    }
    8466    [Storable]
    85     private FixedValueParameter<IntValue> maximumIterationsParameter;
    86     public IFixedValueParameter<IntValue> MaximumIterationsParameter {
    87       get { return maximumIterationsParameter; }
    88     }
    89     [Storable]
    9067    private FixedValueParameter<IntValue> maximumLocalSearchIterationsParameter;
    9168    public IFixedValueParameter<IntValue> MaximumLocalSearchIterationsParameter {
    92       get { return maximumIterationsParameter; }
     69      get { return maximumLocalSearchIterationsParameter; }
    9370    }
    9471    [Storable]
    … …  
    11390    }
    11491   
    115     public bool SetSeedRandomly {
    116       get { return setSeedRandomlyParameter.Value.Value; }
    117       set { setSeedRandomlyParameter.Value.Value = value; }
    118     }
    119     public int Seed {
    120       get { return seedParameter.Value.Value; }
    121       set { seedParameter.Value.Value = value; }
    122     }
    12392    public int EliteSetSize {
    12493      get { return eliteSetSizeParameter.Value.Value; }
    … …  
    12998      set { minimiumEliteSetSizeParameter.Value.Value = value; }
    13099    }
    131     public int MaximumIterations {
    132       get { return maximumIterationsParameter.Value.Value; }
    133       set { maximumIterationsParameter.Value.Value = value; }
    134     }
    135100    public int MaximumLocalSearchIterations {
    136101      get { return maximumLocalSearchIterationsParameter.Value.Value; }
    … …  
    155120
    156121    [StorableConstructor]
    157     protected GRASP(bool deserializing) : base(deserializing) { }
    158     protected GRASP(GRASP original, Cloner cloner)
     122    private GRASP(bool deserializing) : base(deserializing) { }
     123    private GRASP(GRASP original, Cloner cloner)
    159124      : base(original, cloner) {
    160       setSeedRandomlyParameter = cloner.Clone(original.setSeedRandomlyParameter);
    161       seedParameter = cloner.Clone(original.seedParameter);
    162       analyzerParameter = cloner.Clone(original.analyzerParameter);
    163125      eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter);
    164126      minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter);
    165       maximumIterationsParameter = cloner.Clone(original.maximumIterationsParameter);
    166127      maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter);
    167128      candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter);
    … …  
    169130      oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter);
    170131      minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter);
    171       context = cloner.Clone(original.context);
    172132    }
    173133    public GRASP() {
    174       Parameters.Add(setSeedRandomlyParameter = new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether to overwrite the seed with a random value each time the algorithm is run.", new BoolValue(true)));
    175       Parameters.Add(seedParameter = new FixedValueParameter<IntValue>("Seed", "The random seed that is used in the stochastic algorithm", new IntValue(0)));
    176       Parameters.Add(analyzerParameter = new ValueParameter<IAnalyzer>("Analyzer", "The analyzers that are used to perform an analysis of the solutions.", new MultiAnalyzer()));
    177134      Parameters.Add(eliteSetSizeParameter = new FixedValueParameter<IntValue>("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10)));
    178135      Parameters.Add(minimiumEliteSetSizeParameter = new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimal size of the elite set, before local search and path relinking are applied.", new IntValue(2)));
    179       Parameters.Add(maximumIterationsParameter = new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(1000)));
    180136      Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter<IntValue>("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100)));
    181137      Parameters.Add(candidateSizeFactorParameter = new FixedValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path - relinking step relative to the maximum size.A value of 50 % means that only half of all possible moves are considered each step.", new PercentValue(0.5)));
    … …  
    183139      Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
    184140      Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<IntValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new IntValue(4)));
     141
    185142      Problem = new GQAP();
    186143    }
    … …  
    190147    }
    191148
    192     public override void Prepare() {
    193       base.Prepare();
    194       Results.Clear();
    195       context = null;
    196     }
    197 
    198     [Storable]
    199     private GRASPContext context;
    200 
    201149    protected override void Initialize(CancellationToken cancellationToken) {
    202150      base.Initialize(cancellationToken);
    203       context = new GRASPContext();
    204       context.Problem = Problem;
    205       context.Scope.Variables.Add(new Variable("Results", Results));
    206 
    207       IExecutionContext ctxt = null;
    208       foreach (var item in Problem.ExecutionContextItems)
    209         ctxt = new Core.ExecutionContext(ctxt, item, context.Scope);
    210       ctxt = new Core.ExecutionContext(ctxt, this, context.Scope);
    211       context.Parent = ctxt;
    212 
    213       if (SetSeedRandomly) {
    214         var rnd = new System.Random();
    215         Seed = rnd.Next();
    216       }
    217       context.Random = new MersenneTwister((uint)Seed);
    218       context.Iterations = 0;
    219       context.EvaluatedSolutions = 0;
    220       context.BestQuality = double.NaN;
    221       context.BestSolution = null;
    222 
    223       context.Initialized = true;
    224 
    225       Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
    226       Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
    227       Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
     151
     152      Context.Problem = Problem;     
     153      Context.BestQuality = double.NaN;
     154      Context.BestSolution = null;
     155
     156      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     157      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     158      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
    228159      Results.Add(new Result("BestSolution", typeof(GQAPSolution)));
    229160
    230       context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
     161      Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
    231162    }
    232163
    … …  
    235166      while (!StoppingCriterion()) { // line 2 in Algorithm 1
    236167        // next: line 3 in Algorithm 1
    237         var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
    238         if (context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
     168        var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
     169        if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
    239170          GQAPSolution pi_prime;
    240171          if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
    241             pi_prime = context.AtPopulation(context.Random.Next(context.PopulationCount)).Solution; // line 6 in Algorithm 1
     172            pi_prime = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution; // line 6 in Algorithm 1
    242173          else {
    243174            // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
    244175            pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
    245             context.EvaluatedSolutions++;
     176            Context.EvaluatedSolutions++;
    246177          }
    247178
    248179          ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
    249           var pi_plus = context.AtPopulation(context.Random.Next(context.PopulationCount)); // line 9 in Algorithm 1
     180          var pi_plus = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)); // line 9 in Algorithm 1
    250181          pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
    251182          ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
    252183          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
    253184          // Book-keeping
    254           if (context.BestQuality > fitness) {
    255             context.BestQuality = fitness;
    256             context.BestSolution = (GQAPSolution)pi_prime.Clone();
    257           }
    258 
    259           if (context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
     185          if (Context.BestQuality > fitness) {
     186            Context.BestQuality = fitness;
     187            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
     188          }
     189
     190          if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
    260191            var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
    261             double[] similarities = context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
     192            double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
    262193            if (similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
    263               var replacement = context.Population.Select((v, i) => new { V = v, Index = i })
     194              var replacement = Context.Population.Select((v, i) => new { V = v, Index = i })
    264195                                          .Where(x => x.V.Fitness >= fit).ToArray();
    265196              if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1
    266197                // next two lines: line 14 in Algorithm 1
    267198                replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray();
    268                 context.ReplaceAtPopulation(replacement.Last().Index, context.ToScope(pi_prime, fit));
     199                Context.ReplaceAtPopulation(replacement.Last().Index, Context.ToScope(pi_prime, fit));
    269200              }
    270201            }
    271202          } else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
    272             context.AddToPopulation(context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
     203            Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
    273204          }
    274205        } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
    275206          && IsSufficientlyDifferent(pi_prime_vec))  /* cond. 2 of line 21 in Algorithm 1 */ {
    276207          var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
    277           context.EvaluatedSolutions++;
     208          Context.EvaluatedSolutions++;
    278209          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
    279           context.AddToPopulation(context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
     210          Context.AddToPopulation(Context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
    280211          // Book-keeping
    281           if (context.PopulationCount == 1 || context.BestQuality > fitness) {
    282             context.BestQuality = fitness;
    283             context.BestSolution = (GQAPSolution)pi_prime.Clone();
     212          if (Context.PopulationCount == 1 || Context.BestQuality > fitness) {
     213            Context.BestQuality = fitness;
     214            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
    284215          }
    285216        }
    … …  
    287218        IResult result;
    288219        if (Results.TryGetValue("Iterations", out result))
    289           ((IntValue)result.Value).Value = context.Iterations;
    290         else Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
     220          ((IntValue)result.Value).Value = Context.Iterations;
     221        else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    291222        if (Results.TryGetValue("EvaluatedSolutions", out result))
    292           ((IntValue)result.Value).Value = context.EvaluatedSolutions;
    293         else Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
     223          ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
     224        else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    294225        if (Results.TryGetValue("BestQuality", out result))
    295           ((DoubleValue)result.Value).Value = context.BestQuality;
    296         else Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
     226          ((DoubleValue)result.Value).Value = Context.BestQuality;
     227        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
    297228        if (Results.TryGetValue("BestSolution", out result))
    298           result.Value = context.BestSolution;
    299         else Results.Add(new Result("BestSolution", context.BestSolution));
    300 
    301         context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
    302 
    303         context.Iterations++;
     229          result.Value = Context.BestSolution;
     230        else Results.Add(new Result("BestSolution", Context.BestSolution));
     231
     232        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     233
     234        Context.Iterations++;
     235        if (cancellationToken.IsCancellationRequested) break;
    304236      }
    305237    }
    306238
    307239    private bool IsSufficientlyDifferent(IntegerVector vec) {
    308       return context.Population.All(x =>
     240      return Context.Population.All(x =>
    309241        HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
    310242      );
    … …  
    327259      int evaluatedSolutions;
    328260      // lines 2-36 of Algorithm 4 are implemented in the following call
    329       var pi_star = GQAPPathRelinking.Apply(context.Random, source, sourceEval,
     261      var pi_star = GQAPPathRelinking.Apply(Context.Random, source, sourceEval,
    330262        target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
    331263        out evaluatedSolutions);
    332       context.EvaluatedSolutions += evaluatedSolutions;
     264      Context.EvaluatedSolutions += evaluatedSolutions;
    333265      return pi_star;
    334266    }
    … …  
    336268    private void ApproxLocalSearch(GQAPSolution pi_prime) {
    337269      var localSearchEvaluations = 0;
    338       ApproximateLocalSearch.Apply(context.Random, pi_prime, MaximumCandidateListSize,
     270      ApproximateLocalSearch.Apply(Context.Random, pi_prime, MaximumCandidateListSize,
    339271        OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
    340       context.EvaluatedSolutions += localSearchEvaluations;
    341     }
    342 
    343     private bool StoppingCriterion() {
    344       return context.Iterations > MaximumIterations;
     272      Context.EvaluatedSolutions += localSearchEvaluations;
    345273    }
    346274  }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASPContext.cs

    r15561 r15562  
    2020#endregion
    2121
    22 using System;
    23 using System.Collections.Generic;
    2422using System.Linq;
    25 using System.Runtime.CompilerServices;
    26 using System.Threading;
    2723using HeuristicLab.Common;
    2824using HeuristicLab.Core;
    29 using HeuristicLab.Data;
    30 using HeuristicLab.Optimization;
    3125using HeuristicLab.Parameters;
    3226using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    33 using HeuristicLab.Random;
    3427
    3528namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {
    3629  [Item("GRASP+PR (GQAP) Context", "Context for GRASP+PR (GQAP).")]
    3730  [StorableClass]
    38   public sealed class GRASPContext : ParameterizedNamedItem, IExecutionContext {
     31  public sealed class GRASPContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
    3932   
    40     private IExecutionContext parent;
    41     public IExecutionContext Parent {
    42       get { return parent; }
    43       set { parent = value; }
    44     }
    45 
    46     [Storable]
    47     private IScope scope;
    48     public IScope Scope {
    49       get { return scope; }
    50       private set { scope = value; }
    51     }
    52 
    53     IKeyedItemCollection<string, IParameter> IExecutionContext.Parameters {
    54       get { return Parameters; }
    55     }
    56 
    5733    [Storable]
    5834    private IValueParameter<GQAP> problem;
    … …  
    6036      get { return problem.Value; }
    6137      set { problem.Value = value; }
    62     }
    63     public bool Maximization {
    64       get { return Problem.Maximization; }
    65     }
    66 
    67     [Storable]
    68     private IValueParameter<BoolValue> initialized;
    69     public bool Initialized {
    70       get { return initialized.Value.Value; }
    71       set { initialized.Value.Value = value; }
    72     }
    73 
    74     [Storable]
    75     private IValueParameter<IntValue> iterations;
    76     public int Iterations {
    77       get { return iterations.Value.Value; }
    78       set { iterations.Value.Value = value; }
    79     }
    80 
    81     [Storable]
    82     private IValueParameter<IntValue> evaluatedSolutions;
    83     public int EvaluatedSolutions {
    84       get { return evaluatedSolutions.Value.Value; }
    85       set { evaluatedSolutions.Value.Value = value; }
    86     }
    87 
    88     [Storable]
    89     private IValueParameter<DoubleValue> bestQuality;
    90     public double BestQuality {
    91       get { return bestQuality.Value.Value; }
    92       set { bestQuality.Value.Value = value; }
    9338    }
    9439
    … …  
    9944      set { bestSolution.Value = value; }
    10045    }
    101 
    102     [Storable]
    103     private IValueParameter<IntValue> localSearchEvaluations;
    104     public int LocalSearchEvaluations {
    105       get { return localSearchEvaluations.Value.Value; }
    106       set { localSearchEvaluations.Value.Value = value; }
    107     }
    10846   
    109     [Storable]
    110     private IValueParameter<IRandom> random;
    111     public IRandom Random {
    112       get { return random.Value; }
    113       set { random.Value = value; }
    114     }
    115 
    116     public IEnumerable<ISingleObjectiveSolutionScope<GQAPSolution>> Population {
    117       get { return scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>(); }
    118     }
    119     public void AddToPopulation(ISingleObjectiveSolutionScope<GQAPSolution> solScope) {
    120       scope.SubScopes.Add(solScope);
    121     }
    122     public void ReplaceAtPopulation(int index, ISingleObjectiveSolutionScope<GQAPSolution> solScope) {
    123       scope.SubScopes[index] = solScope;
    124     }
    125     public ISingleObjectiveSolutionScope<GQAPSolution> AtPopulation(int index) {
    126       return scope.SubScopes[index] as ISingleObjectiveSolutionScope<GQAPSolution>;
    127     }
    12847    public void SortPopulation() {
    129       scope.SubScopes.Replace(scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>().OrderBy(x => Maximization ? -x.Fitness : x.Fitness).ToList());
    130     }
    131     public int PopulationCount {
    132       get { return scope.SubScopes.Count; }
     48      Scope.SubScopes.Replace(Scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>().OrderBy(x => Problem.Maximization ? -x.Fitness : x.Fitness).ToList());
    13349    }
    13450   
    … …  
    13753    private GRASPContext(GRASPContext original, Cloner cloner)
    13854      : base(original, cloner) {
    139       scope = cloner.Clone(original.scope);
    14055      problem = cloner.Clone(original.problem);
    141       initialized = cloner.Clone(original.initialized);
    142       iterations = cloner.Clone(original.iterations);
    143       evaluatedSolutions = cloner.Clone(original.evaluatedSolutions);
    144       bestQuality = cloner.Clone(original.bestQuality);
    14556      bestSolution = cloner.Clone(original.bestSolution);
    146       localSearchEvaluations = cloner.Clone(original.localSearchEvaluations);
    147       random = cloner.Clone(original.random);
    14857    }
    14958    public GRASPContext() : this("GRASP+PR (GQAP) Context") { }
    15059    public GRASPContext(string name) : base(name) {
    151       scope = new Scope("Global");
    152 
    15360      Parameters.Add(problem = new ValueParameter<GQAP>("Problem"));
    154       Parameters.Add(initialized = new ValueParameter<BoolValue>("Initialized", new BoolValue(false)));
    155       Parameters.Add(iterations = new ValueParameter<IntValue>("Iterations", new IntValue(0)));
    156       Parameters.Add(evaluatedSolutions = new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
    157       Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN)));
    15861      Parameters.Add(bestSolution = new ValueParameter<GQAPSolution>("BestFoundSolution"));
    159       Parameters.Add(localSearchEvaluations = new ValueParameter<IntValue>("LocalSearchEvaluations", new IntValue(0)));
    160       Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
    16162    }
    16263
    … …  
    17576      return scope;
    17677    }
    177 
    178     public void IncrementEvaluatedSolutions(int byEvaluations) {
    179       if (byEvaluations < 0) throw new ArgumentException("Can only increment and not decrement evaluated solutions.");
    180       EvaluatedSolutions += byEvaluations;
    181     }
    182    
    183     private static void ExecuteAlgorithm(IAlgorithm algorithm) {
    184       using (var evt = new AutoResetEvent(false)) {
    185         EventHandler exeStateChanged = (o, args) => {
    186           if (algorithm.ExecutionState != ExecutionState.Started)
    187             evt.Set();
    188         };
    189         algorithm.ExecutionStateChanged += exeStateChanged;
    190         if (algorithm.ExecutionState != ExecutionState.Prepared) {
    191           algorithm.Prepare(true);
    192           evt.WaitOne();
    193         }
    194         algorithm.Start();
    195         evt.WaitOne();
    196         algorithm.ExecutionStateChanged -= exeStateChanged;
    197       }
    198     }
    199     [MethodImpl(MethodImplOptions.AggressiveInlining)]
    200     public bool IsBetter(ISingleObjectiveSolutionScope<GQAPSolution> a, ISingleObjectiveSolutionScope<GQAPSolution> b) {
    201       return IsBetter(a.Fitness, b.Fitness);
    202     }
    203     [MethodImpl(MethodImplOptions.AggressiveInlining)]
    204     public bool IsBetter(double a, double b) {
    205       return double.IsNaN(b) && !double.IsNaN(a)
    206         || Maximization && a > b
    207         || !Maximization && a < b;
    208     }
    209 
    210     #region IExecutionContext members
    211     public IAtomicOperation CreateOperation(IOperator op) {
    212       return new Core.ExecutionContext(this, op, Scope);
    213     }
    214 
    215     public IAtomicOperation CreateOperation(IOperator op, IScope s) {
    216       return new Core.ExecutionContext(this, op, s);
    217     }
    218 
    219     public IAtomicOperation CreateChildOperation(IOperator op) {
    220       return new Core.ExecutionContext(this, op, Scope);
    221     }
    222 
    223     public IAtomicOperation CreateChildOperation(IOperator op, IScope s) {
    224       return new Core.ExecutionContext(this, op, s);
    225     }
    226     #endregion
    227 
    228     #region Engine Helper
    229     public void RunOperator(IOperator op, IScope scope, CancellationToken cancellationToken) {
    230       var stack = new Stack<IOperation>();
    231       stack.Push(CreateChildOperation(op, scope));
    232 
    233       while (stack.Count > 0) {
    234         cancellationToken.ThrowIfCancellationRequested();
    235 
    236         var next = stack.Pop();
    237         if (next is OperationCollection) {
    238           var coll = (OperationCollection)next;
    239           for (int i = coll.Count - 1; i >= 0; i--)
    240             if (coll[i] != null) stack.Push(coll[i]);
    241         } else if (next is IAtomicOperation) {
    242           var operation = (IAtomicOperation)next;
    243           try {
    244             next = operation.Operator.Execute((IExecutionContext)operation, cancellationToken);
    245           } catch (Exception ex) {
    246             stack.Push(operation);
    247             if (ex is OperationCanceledException) throw ex;
    248             else throw new OperatorExecutionException(operation.Operator, ex);
    249           }
    250           if (next != null) stack.Push(next);
    251         }
    252       }
    253     }
    254     #endregion
    25578  }
    25679}

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj

    r15553 r15562  
    9999  </ItemGroup>
    100100  <ItemGroup>
    101     <Compile Include="GRASPContext.cs" />
    102     <Compile Include="GRASP.cs" />
    103     <Compile Include="Interfaces.cs" />
     101    <Compile Include="Evolutionary\ESContext.cs" />
     102    <Compile Include="Evolutionary\ESGQAPSolution.cs" />
     103    <Compile Include="Evolutionary\EvolutionStrategy.cs" />
     104    <Compile Include="Infrastructure\Algorithms\StochasticAlgorithm.cs" />
     105    <Compile Include="Infrastructure\Contexts\SingleObjectiveSingleSolutionContext.cs" />
     106    <Compile Include="Infrastructure\Contexts\SingleObjectivePopulationContext.cs" />
     107    <Compile Include="Infrastructure\Contexts\StochasticContext.cs" />
     108    <Compile Include="Infrastructure\Contexts\BasicContext.cs" />
     109    <Compile Include="Infrastructure\Algorithms\ContextAlgorithm.cs" />
     110    <Compile Include="GRASP\GRASPContext.cs" />
     111    <Compile Include="GRASP\GRASP.cs" />
     112    <Compile Include="LocalSearch\LocalSearchContext.cs" />
     113    <Compile Include="Infrastructure\Interfaces.cs" />
     114    <Compile Include="LocalSearch\IteratedLS.cs" />
     115    <Compile Include="LocalSearch\MultistartLS.cs" />
    104116    <Compile Include="Plugin.cs" />
     117    <Compile Include="Infrastructure\Contexts\SingleSolutionContext.cs" />
     118    <Compile Include="Infrastructure\Contexts\PopulationContext.cs" />
    105119    <Compile Include="Properties\AssemblyInfo.cs" />
    106     <Compile Include="SingleObjectiveSolutionScope.cs" />
     120    <Compile Include="Infrastructure\SingleObjectiveSolutionScope.cs" />
    107121  </ItemGroup>
    108122  <ItemGroup>

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Interfaces.cs

    r15561 r15562  
    2929    void Adopt(ISingleObjectiveSolutionScope<TSolution> orphan);
    3030  }
     31
     32  public interface IContext : IExecutionContext {
     33    new IExecutionContext Parent { get; set; }
     34    int Iterations { get; set; }
     35    int EvaluatedSolutions { get; set; }
     36  }
     37
     38  public interface IStochasticContext : IContext {
     39    IRandom Random { get; set; }
     40  }
    3141}

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj

    r15553 r15562  
    104104    <Compile Include="GQAPInstance.cs" />
    105105    <Compile Include="Interfaces\Parameter\IAssignmentAwareGQAPOperator.cs" />
     106    <Compile Include="Moves\ExhaustiveOneMoveGenerator.cs" />
    106107    <Compile Include="Operators\Crossovers\CordeauCrossover.cs" />
     108    <Compile Include="Operators\LocalImprovers\OneOptLocalSearch.cs" />
    107109    <Compile Include="SolutionCreators\SlackMinimizationSolutionCreator.cs" />
    108110    <Compile Include="SolutionCreators\RandomButFeasibleSolutionCreator.cs" />

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Interfaces/Operator/IGQAPLocalImprovementOperator.cs

    r15504 r15562  
    2121
    2222using HeuristicLab.Core;
    23 using HeuristicLab.Data;
    2423using HeuristicLab.Encodings.IntegerVectorEncoding;
    2524using HeuristicLab.Optimization;
    … …  
    2726namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
    2827  public interface IGQAPLocalImprovementOperator : ILocalImprovementAlgorithmOperator {
    29     IValueLookupParameter<IntValue> MaximumCandidateListSizeParameter { get; }
    3028    ILookupParameter<IntegerVector> AssignmentParameter { get; }
    3129  }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/ExhaustiveOneMoveGenerator.cs

    r15519 r15562  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using HeuristicLab.Common;
    2425using HeuristicLab.Core;
    25 using HeuristicLab.Data;
    2626using HeuristicLab.Encodings.IntegerVectorEncoding;
    2727using HeuristicLab.Optimization;
    2828using HeuristicLab.Parameters;
    2929using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     30using HeuristicLab.Random;
    3031
    3132namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
    32   [Item("Stochastic N-Move MultiMoveGenerator", "Randomly samples a number of N-Moves.")]
     33  [Item("Exhaustive 1-Move MoveGenerator", "Exhaustively generates all possible 1-moves.")]
    3334  [StorableClass]
    34   public class StochasticNMoveMultiMoveGenerator : GQAPNMoveGenerator, IStochasticOperator, IMultiMoveGenerator {
     35  public class ExhaustiveOneMoveGenerator : GQAPNMoveGenerator, IStochasticOperator, IExhaustiveMoveGenerator {
    3536   
    3637    public ILookupParameter<IRandom> RandomParameter {
    3738      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    3839    }
    39     public IValueLookupParameter<IntValue> SampleSizeParameter {
    40       get { return (IValueLookupParameter<IntValue>)Parameters["SampleSize"]; }
    41     }
    4240
    4341    [StorableConstructor]
    44     protected StochasticNMoveMultiMoveGenerator(bool deserializing) : base(deserializing) { }
    45     protected StochasticNMoveMultiMoveGenerator(StochasticNMoveMultiMoveGenerator original, Cloner cloner) : base(original, cloner) { }
    46     public StochasticNMoveMultiMoveGenerator()
     42    protected ExhaustiveOneMoveGenerator(bool deserializing) : base(deserializing) { }
     43    protected ExhaustiveOneMoveGenerator(ExhaustiveOneMoveGenerator original, Cloner cloner) : base(original, cloner) { }
     44    public ExhaustiveOneMoveGenerator()
    4745      : base() {
    4846      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that should be used."));
    49       Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "The number of moves to generate."));
     47      NParameter.Value.Value = 1;
     48      NParameter.Hidden = true;
    5049    }
    5150
    5251    public override IDeepCloneable Clone(Cloner cloner) {
    53       return new StochasticNMoveMultiMoveGenerator(this, cloner);
     52      return new ExhaustiveOneMoveGenerator(this, cloner);
    5453    }
    5554
    56     public static IEnumerable<NMove> Generate(IRandom random, IntegerVector assignment, int n, GQAPInstance problemInstance, int sampleSize) {
    57       for (int i = 0; i < sampleSize; i++)
    58         yield return StochasticNMoveSingleMoveGenerator.GenerateUpToN(random, assignment, n, problemInstance.Capacities);
     55    public static IEnumerable<NMove> Generate(IntegerVector assignment, GQAPInstance problemInstance) {
     56      var equipments = problemInstance.Demands.Length;
     57      var locations = problemInstance.Capacities.Length;
     58      var tmp = new int[equipments];
     59      for (var e = 0; e < equipments; e++) {
     60        var indices = new List<int> { e };
     61        for (var l = 0; l < locations; l++) {
     62          if (assignment[e] == l) continue;
     63          var reassign = (int[])tmp.Clone();
     64          reassign[e] = l + 1;
     65          yield return new NMove(reassign, indices);
     66        }
     67      }
     68    }
     69
     70    public static IEnumerable<NMove> GenerateAllNxM(GQAPInstance problemInstance) {
     71      var equipments = problemInstance.Demands.Length;
     72      var locations = problemInstance.Capacities.Length;
     73      var tmp = new int[equipments];
     74      for (var e = 0; e < equipments; e++) {
     75        var indices = new List<int> { e };
     76        for (var l = 0; l < locations; l++) {
     77          var reassign = (int[])tmp.Clone();
     78          reassign[e] = l + 1;
     79          yield return new NMove(reassign, indices);
     80        }
     81      }
    5982    }
    6083
    6184    public override IEnumerable<NMove> GenerateMoves(IntegerVector assignment, int n, GQAPInstance problemInstance) {
    62       return Generate(RandomParameter.ActualValue, assignment, n, problemInstance, SampleSizeParameter.ActualValue.Value);
     85      if (n != 1) throw new ArgumentException("N must be equal to 1 for the exhaustive 1-move generator.");
     86      var random = RandomParameter.ActualValue;
     87      return Generate(assignment, problemInstance).Shuffle(random);
    6388    }
    6489  }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/OneOptLocalSearch.cs

    r15558 r15562  
    1 #region License Information
     1
     2#region License Information
    23/* HeuristicLab
    34 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    … …  
    2122
    2223using System;
    23 using System.Collections.Generic;
    2424using System.Linq;
    2525using HeuristicLab.Common;
    … …  
    3434
    3535namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
    36   /// <summary>
    37   /// This is an implementation of the algorithm described in Mateus, G.R., Resende, M.G.C. & Silva, R.M.A. J Heuristics (2011) 17: 527. https://doi.org/10.1007/s10732-010-9144-0
    38   /// </summary>
    39   [Item("ApproximateLocalSearch", "The approximate local search is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
     36  [Item("1-opt LocalSearch", "A simple exhaustive 1-change local search.")]
    4037  [StorableClass]
    41   public class ApproximateLocalSearch : SingleSuccessorOperator, IProblemInstanceAwareGQAPOperator,
     38  public class OneOptLocalSearch : SingleSuccessorOperator, IProblemInstanceAwareGQAPOperator,
    4239    IQualityAwareGQAPOperator, IGQAPLocalImprovementOperator, IAssignmentAwareGQAPOperator, IStochasticOperator {
    4340    public IProblem Problem { get; set; }
    … …  
    6764      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    6865    }
    69     public IValueLookupParameter<IntValue> MaximumCandidateListSizeParameter {
    70       get { return (IValueLookupParameter<IntValue>)Parameters["MaximumCandidateListSize"]; }
    71     }
    72     public IValueLookupParameter<PercentValue> OneMoveProbabilityParameter {
    73       get { return (IValueLookupParameter<PercentValue>)Parameters["OneMoveProbability"]; }
    74     }
    7566    public ILookupParameter<ResultCollection> ResultsParameter {
    7667      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
    7768    }
    78     public IValueLookupParameter<BoolValue> GreedyParameter {
    79       get { return (IValueLookupParameter<BoolValue>)Parameters["Greedy"]; }
    80     }
    8169
    8270    [StorableConstructor]
    83     protected ApproximateLocalSearch(bool deserializing) : base(deserializing) { }
    84     protected ApproximateLocalSearch(ApproximateLocalSearch original, Cloner cloner) : base(original, cloner) { }
    85     public ApproximateLocalSearch()
     71    protected OneOptLocalSearch(bool deserializing) : base(deserializing) { }
     72    protected OneOptLocalSearch(OneOptLocalSearch original, Cloner cloner) : base(original, cloner) { }
     73    public OneOptLocalSearch()
    8674      : base() {
    8775      Parameters.Add(new LookupParameter<GQAPInstance>("ProblemInstance", GQAP.ProblemInstanceDescription));
    … …  
    8977      Parameters.Add(new LookupParameter<DoubleValue>("Quality", ""));
    9078      Parameters.Add(new LookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));
    91       Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of iterations that should be performed."));
     79      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "This parameter is ignored by the operator.") { Hidden = true });
    9280      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solution equivalents."));
    9381      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
    94       Parameters.Add(new ValueLookupParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
    95       Parameters.Add(new ValueLookupParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
    9682      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The result collection that stores the results."));
    97       Parameters.Add(new ValueLookupParameter<BoolValue>("Greedy", "Whether to use a greedy selection strategy or a probabilistic one.", new BoolValue(true)));
    9883    }
    9984
    10085    public override IDeepCloneable Clone(Cloner cloner) {
    101       return new ApproximateLocalSearch(this, cloner);
     86      return new OneOptLocalSearch(this, cloner);
    10287    }
    10388
    104     public static void Apply(IRandom random, GQAPSolution sol, int maxCLS,
    105       double oneMoveProbability, int maximumIterations,
    106       GQAPInstance problemInstance, out int evaluatedSolutions, bool greedy = true) {
     89    public static void Apply(IRandom random, GQAPSolution sol,
     90      GQAPInstance problemInstance, out int evaluatedSolutions) {
    10791      var fit = problemInstance.ToSingleObjective(sol.Evaluation);
    10892      var eval = sol.Evaluation;
    109       Apply(random, sol.Assignment, ref fit, ref eval, maxCLS, oneMoveProbability, maximumIterations, problemInstance,
    110         out evaluatedSolutions, greedy);
     93      Apply(random, sol.Assignment, ref fit, ref eval, problemInstance, out evaluatedSolutions);
    11194      sol.Evaluation = eval;
    11295    }
    … …  
    125108    /// <param name="greedy">Greedy selection performed better in 5 of 8 instances according to the paper</param>
    126109    public static void Apply(IRandom random, IntegerVector assignment,
    127       ref double quality, ref Evaluation evaluation, int maxCLS,
    128       double oneMoveProbability, int maximumIterations,
    129       GQAPInstance problemInstance, out int evaluatedSolutions, bool greedy = true) {
     110      ref double quality, ref Evaluation evaluation,
     111      GQAPInstance problemInstance, out int evaluatedSolutions) {
    130112      evaluatedSolutions = 0;
    131113      var capacities = problemInstance.Capacities;
    … …  
    133115      var evaluations = 0.0;
    134116      var deltaEvaluationFactor = 1.0 / assignment.Length;
    135       while (true) { // line 1 of Algorithm 3
    136         var count = 0; // line 2 of Algorithm 3
    137         var CLS = new List<Tuple<NMove, double, Evaluation>>(); // line 3 of Algorithm 3
    138         do {
    139           var move = Move(random, assignment, oneMoveProbability, capacities); // line 4 of Algorithm 3
    140 
     117      var change = true;
     118      var moves = ExhaustiveOneMoveGenerator.GenerateAllNxM(problemInstance).ToList();
     119      var slack = evaluation.Slack.ToList();
     120      while (change) {
     121        change = false;
     122        var feasible = evaluation.IsFeasible;
     123        foreach (var move in moves
     124            .Where(x => {
     125              var equip = x.Indices[0];
     126              var assignTo = x.Reassignments[equip] - 1;
     127              if (assignTo == assignment[equip]) return false;
     128              var dem = problemInstance.Demands[equip];
     129              if (feasible) return slack[assignTo] >= dem;
     130              return slack[assignTo] - dem > slack[assignment[equip]];
     131            })
     132            .Shuffle(random)) {
    141133          var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
    142           evaluations += move.Indices.Count * deltaEvaluationFactor;
    143           double moveQuality = problemInstance.ToSingleObjective(moveEval);
    144 
    145           if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality) { // line 5 of Algorithm 3
    146             CLS.Add(Tuple.Create(move, moveQuality, moveEval)); // line 6 of Algorithm 3
     134          evaluations += deltaEvaluationFactor;
     135          var moveQuality = problemInstance.ToSingleObjective(moveEval);
     136          if (moveQuality < quality) {
     137            NMoveMaker.Apply(assignment, move);
     138            quality = moveQuality;
     139            evaluation = moveEval;
     140            change = true;
     141            break;
    147142          }
    148           count++; // line 8 of Algorithm 3
    149         } while (CLS.Count < maxCLS && count < maximumIterations); // line 9 of Algorithm 3
    150 
    151         if (CLS.Count == 0) { // line 10 of Algorithm 3
    152           evaluatedSolutions += (int)Math.Ceiling(evaluations);
    153           return; // END
    154         } else {
    155           // line 11 of Algorithm 3
    156           Tuple<NMove, double, Evaluation> selected;
    157           if (greedy) {
    158             selected = CLS.MinItems(x => x.Item2).Shuffle(random).First();
    159           } else {
    160             selected = CLS.SampleProportional(random, 1, CLS.Select(x => 1.0 / x.Item2), false, false).Single();
    161           }
    162           NMoveMaker.Apply(assignment, selected.Item1);
    163           quality = selected.Item2;
    164           evaluation = selected.Item3;
    165143        }
    166144      }
     145      evaluatedSolutions += (int)Math.Ceiling(evaluations);
    167146    }
    168147
    … …  
    183162        ref fit,
    184163        ref evaluation,
    185         MaximumCandidateListSizeParameter.ActualValue.Value,
    186         OneMoveProbabilityParameter.ActualValue.Value,
    187         MaximumIterationsParameter.ActualValue.Value,
    188164        ProblemInstanceParameter.ActualValue,
    189         out evaluatedSolutions,
    190         GreedyParameter.ActualValue.Value);
     165        out evaluatedSolutions);
    191166
    192167      EvaluationParameter.ActualValue = evaluation;

  • branches/GeneralizedQAP/UnitTests/ApproximateLocalSearchTest.cs

    r15558 r15562  
    1313    [TestMethod]
    1414    public void ApproximateLocalSearchApplyTest() {
    15       CollectionAssert.AreEqual(new [] { 3, 2, 1, 1, 3, 0, 1, 0, 3, 0 }, assignment.ToArray());
     15      CollectionAssert.AreEqual(new [] { 2, 0, 1, 1, 2, 3, 0, 3, 0, 0 }, assignment.ToArray());
    1616
    1717      var evaluation = instance.Evaluate(assignment);
    18       Assert.AreEqual(4091776, evaluation.FlowCosts);
    19       Assert.AreEqual(42, evaluation.InstallationCosts);
     18      Assert.AreEqual(3985258, evaluation.FlowCosts);
     19      Assert.AreEqual(30, evaluation.InstallationCosts);
    2020      Assert.AreEqual(0, evaluation.ExcessDemand);
    2121
    2222      var quality = instance.ToSingleObjective(evaluation);
    23       Assert.AreEqual(15903846.056964701, quality, 1e-9);
     23      Assert.AreEqual(15489822.781533258, quality, 1e-9);
    2424
    2525      var evaluatedSolutions = 0;
    2626      ApproximateLocalSearch.Apply(random, assignment, ref quality,
    27         ref evaluation, 10, 0.5, 1000, instance,
     27        ref evaluation, 10, 0.5, 100, instance,
    2828        out evaluatedSolutions);
    29       Assert.AreEqual(680, evaluatedSolutions);
    30       CollectionAssert.AreEqual(new[] { 3, 1, 0, 3, 0, 0, 1, 2, 3, 0 }, assignment.ToArray());
    31       Assert.AreEqual(12440163.936988469, quality, 1e-9);
     29      Assert.AreEqual(61, evaluatedSolutions);
     30      CollectionAssert.AreEqual(new[] { 2, 0, 0, 0, 2, 1, 0, 3, 0, 0 }, assignment.ToArray());
     31      Assert.AreEqual(10167912.633734789, quality, 1e-9);
    3232    }
    3333

  • branches/GeneralizedQAP/UnitTests/UnitTests.csproj

    r15512 r15562  
    110110    <Compile Include="Properties\AssemblyInfo.cs" />
    111111    <Compile Include="ApproximateLocalSearchTest.cs" />
     112    <Compile Include="GRASPTest.cs" />
    112113  </ItemGroup>
    113114  <ItemGroup>
    … …  
    115116      <Project>{14ab8d24-25bc-400c-a846-4627aa945192}</Project>
    116117      <Name>HeuristicLab.Optimization-3.3</Name>
     118    </ProjectReference>
     119    <ProjectReference Include="..\HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms\3.3\HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj">
     120      <Project>{577239EC-7D7F-4505-A0A4-572E34010DBA}</Project>
     121      <Name>HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3</Name>
    117122    </ProjectReference>
    118123    <ProjectReference Include="..\HeuristicLab.Problems.GeneralizedQuadraticAssignment\3.3\HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj">
Note: See TracChangeset for help on using the changeset viewer.