Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs @ 7523

Last change on this file since 7523 was 7523, checked in by abeham, 12 years ago

#1614

  • sorted operators
  • added crossover defined by Cordeau et al.
  • fixed a few bugs
File size: 13.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.IntegerVectorEncoding;
29using HeuristicLab.Operators;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33
34namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Operators {
35  [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  [StorableClass]
37  public class ApproximateLocalSearch : SingleSuccessorOperator, IDemandsAwareGQAPOperator, ICapacitiesAwareGQAPOperator,
38    IWeightsAwareGQAPOperator, IDistancesAwareGQAPOperator, IInstallationCostsAwareGQAPOperator,
39    ITransportationCostsAwareGQAPOperator, IOverbookedCapacityPenaltyAwareGQAPOperator,
40    IAssignmentAwareGQAPOperator, IQualityAwareGQAPOperator, IGQAPLocalImprovementOperator, IStochasticOperator {
41    public IProblem Problem { get; set; }
42    public Type ProblemType {
43      get { return typeof(GeneralizedQuadraticAssignmentProblem); }
44    }
45
46    public ILookupParameter<DoubleArray> DemandsParameter {
47      get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
48    }
49    public ILookupParameter<DoubleArray> CapacitiesParameter {
50      get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
51    }
52    public ILookupParameter<DoubleMatrix> WeightsParameter {
53      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
54    }
55    public ILookupParameter<DoubleMatrix> DistancesParameter {
56      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
57    }
58    public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
59      get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
60    }
61    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
62      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
63    }
64    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
65      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
66    }
67    public ILookupParameter<IntegerVector> AssignmentParameter {
68      get { return (ILookupParameter<IntegerVector>)Parameters["Assignment"]; }
69    }
70    public ILookupParameter<BoolValue> MaximizationParameter {
71      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
72    }
73    public ILookupParameter<DoubleValue> QualityParameter {
74      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
75    }
76    public ILookupParameter<DoubleValue> FlowDistanceQualityParameter {
77      get { return (ILookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
78    }
79    public ILookupParameter<DoubleValue> InstallationQualityParameter {
80      get { return (ILookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
81    }
82    public ILookupParameter<DoubleValue> OverbookedCapacityParameter {
83      get { return (ILookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
84    }
85    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
86      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
87    }
88    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
89      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
90    }
91    public ILookupParameter<IRandom> RandomParameter {
92      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
93    }
94    public IValueLookupParameter<IntValue> MaximumCandidateListSizeParameter {
95      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumCandidateListSize"]; }
96    }
97    public IValueLookupParameter<PercentValue> OneMoveProbabilityParameter {
98      get { return (IValueLookupParameter<PercentValue>)Parameters["OneMoveProbability"]; }
99    }
100    public ILookupParameter<ResultCollection> ResultsParameter {
101      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
102    }
103
104    [StorableConstructor]
105    protected ApproximateLocalSearch(bool deserializing) : base(deserializing) { }
106    protected ApproximateLocalSearch(ApproximateLocalSearch original, Cloner cloner) : base(original, cloner) { }
107    public ApproximateLocalSearch()
108      : base() {
109      Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));
110      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));
111      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", GeneralizedQuadraticAssignmentProblem.WeightsDescription));
112      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", GeneralizedQuadraticAssignmentProblem.DistancesDescription));
113      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", GeneralizedQuadraticAssignmentProblem.InstallationCostsDescription));
114      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
115      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
116      Parameters.Add(new LookupParameter<IntegerVector>("Assignment", GQAPSolutionCreator.AssignmentDescription));
117      Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
118      Parameters.Add(new LookupParameter<DoubleValue>("Quality", GQAPEvaluator.QualityDescription));
119      Parameters.Add(new LookupParameter<DoubleValue>("FlowDistanceQuality", GQAPEvaluator.FlowDistanceQualityDescription));
120      Parameters.Add(new LookupParameter<DoubleValue>("InstallationQuality", GQAPEvaluator.InstallationQualityDescription));
121      Parameters.Add(new LookupParameter<DoubleValue>("OverbookedCapacity", GQAPEvaluator.OverbookedCapacityDescription));
122      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of iterations that should be performed."));
123      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solution equivalents."));
124      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
125      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
126      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)));
127      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The result collection that stores the results."));
128    }
129
130    public override IDeepCloneable Clone(Cloner cloner) {
131      return new ApproximateLocalSearch(this, cloner);
132    }
133
134    /// <summary>
135    /// The implementation differs slightly from Mateus et al. in that the maximumIterations parameter defines a cap
136    /// on the number of steps that the local search can perform. While the maxSampleSize parameter corresponds to
137    /// the maxItr parameter defined by Mateus et al.
138    /// </summary>
139    /// <param name="random">The random number generator to use.</param>
140    /// <param name="assignment">The equipment-location assignment vector.</param>
141    /// <param name="quality">The solution quality.</param>
142    /// <param name="flowDistanceQuality">The quality regarding the flow-distance criteria.</param>
143    /// <param name="installationQuality">The quality regarding the installation costs.</param>
144    /// <param name="overbookedCapacity">The sum of the overbooked capacities relative to the capacity of each location.</param>
145    /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
146    /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
147    /// <param name="weights">The weights matrix describes the flows between the equipments.</param>
148    /// <param name="distances">The distances matrix describes the distances between the locations at which the equipment can be installed.</param>
149    /// <param name="installationCosts">The installation costs matrix describes the installation costs of installing equipment i at location j</param>
150    /// <param name="demands">The demands vector describes the space requirements of the equipments.</param>
151    /// <param name="capacities">The capacities vector describes the available space at the locations.</param>
152    /// <param name="transportationCosts">The transportation cost represents the flow-unit per distance-unit cost factor. This value can also be set to 1 if these costs are factored into the weights matrix already.</param>
153    /// <param name="overbookedCapacityPenalty"></param>
154    /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
155    public static void Apply(IRandom random, IntegerVector assignment,
156      DoubleValue quality, DoubleValue flowDistanceQuality, DoubleValue installationQuality, DoubleValue overbookedCapacity,
157      IntValue maxCLS, IntValue maximumIterations,
158      DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts, DoubleArray demands, DoubleArray capacities,
159      DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty, PercentValue oneMoveProbability) {
160
161      while (true) {
162        int count = 0;
163        var CLS = new List<Tuple<NMove, double, double, double, double>>();
164        double sum = 0.0;
165        do {
166          NMove move;
167          if (random.NextDouble() < oneMoveProbability.Value)
168            move = StochasticNMoveSingleMoveGenerator.GenerateExactlyN(random, assignment, 1, capacities);
169          else move = StochasticNMoveSingleMoveGenerator.GenerateExactlyN(random, assignment, 2, capacities);
170
171          double moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity;
172          GQAPNMoveEvaluator.Evaluate(move, assignment, weights, distances, installationCosts,
173            demands, capacities, out moveFlowDistanceQuality, out moveInstallationQuality, out moveOverbookedCapacity);
174          double moveQuality = GQAPEvaluator.GetCombinedQuality(moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity,
175            transportationCosts.Value, overbookedCapacityPenalty.Value);
176
177          if (moveOverbookedCapacity <= 0.0 && moveQuality < 0.0) {
178            CLS.Add(Tuple.Create(move, moveQuality, moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity));
179            sum += 1.0 / moveQuality;
180          }
181          count++;
182        } while (CLS.Count < maxCLS.Value && count < maximumIterations.Value);
183
184        if (CLS.Count == 0)
185          return; // END
186        else {
187          var ball = random.NextDouble() * sum;
188          var selected = CLS.Last();
189          foreach (var candidate in CLS) {
190            ball -= 1.0 / candidate.Item2;
191            if (ball <= 0.0) {
192              selected = candidate;
193              break;
194            }
195          }
196          NMoveMaker.Apply(assignment, selected.Item1);
197          quality.Value += selected.Item2;
198          flowDistanceQuality.Value += selected.Item3;
199          installationQuality.Value += selected.Item4;
200          overbookedCapacity.Value += selected.Item5;
201        }
202      }
203    }
204
205    public override IOperation Apply() {
206      Apply(RandomParameter.ActualValue,
207        AssignmentParameter.ActualValue,
208        QualityParameter.ActualValue,
209        FlowDistanceQualityParameter.ActualValue,
210        InstallationQualityParameter.ActualValue,
211        OverbookedCapacityParameter.ActualValue,
212        MaximumCandidateListSizeParameter.ActualValue,
213        MaximumIterationsParameter.ActualValue,
214        WeightsParameter.ActualValue, DistancesParameter.ActualValue,
215        InstallationCostsParameter.ActualValue,
216        DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
217        TransportationCostsParameter.ActualValue,
218        OverbookedCapacityPenaltyParameter.ActualValue,
219        OneMoveProbabilityParameter.ActualValue);
220      return base.Apply();
221    }
222  }
223}
Note: See TracBrowser for help on using the repository browser.