Free cookie consent management tool by TermsFeed Policy Generator

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

#1614: added additional algorithms

File:
1 copied

Legend:

Unmodified
Added
Removed

  • 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;
Note: See TracChangeset for help on using the changeset viewer.