Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/CordeauCrossover.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: 11.6 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 HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.IntegerVectorEncoding;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
31  [Item("CordeauCrossover", "The merge procedure that is described in Cordeau, J.-F., Gaudioso, M., Laporte, G., Moccia, L. 2006. A memetic heuristic for the generalized quadratic assignment problem. INFORMS Journal on Computing, 18, pp. 433–443.")]
32  [StorableClass]
33  public class CordeauCrossover : GQAPCrossover,
34    IQualitiesAwareGQAPOperator, IWeightsAwareGQAPOperator, IDistancesAwareGQAPOperator, IInstallationCostsAwareGQAPOperator,
35    IDemandsAwareGQAPOperator, ICapacitiesAwareGQAPOperator, ITransportationCostsAwareGQAPOperator,
36    IOverbookedCapacityPenaltyAwareGQAPOperator {
37
38    public ILookupParameter<BoolValue> MaximizationParameter {
39      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
40    }
41    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
42      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
43    }
44    public IScopeTreeLookupParameter<DoubleValue> FlowDistanceQualityParameter {
45      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
46    }
47    public IScopeTreeLookupParameter<DoubleValue> InstallationQualityParameter {
48      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
49    }
50    public IScopeTreeLookupParameter<DoubleValue> OverbookedCapacityParameter {
51      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
52    }
53    public ILookupParameter<DoubleMatrix> WeightsParameter {
54      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
55    }
56    public ILookupParameter<DoubleMatrix> DistancesParameter {
57      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
58    }
59    public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
60      get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
61    }
62    public ILookupParameter<DoubleArray> DemandsParameter {
63      get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
64    }
65    public ILookupParameter<DoubleArray> CapacitiesParameter {
66      get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
67    }
68    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
69      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
70    }
71    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
72      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
73    }
74
75    [StorableConstructor]
76    protected CordeauCrossover(bool deserializing) : base(deserializing) { }
77    protected CordeauCrossover(CordeauCrossover original, Cloner cloner)
78      : base(original, cloner) {
79    }
80    public CordeauCrossover()
81      : base() {
82      Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
83      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", GQAPEvaluator.QualityDescription, 1));
84      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("FlowDistanceQuality", GQAPEvaluator.FlowDistanceQualityDescription, 1));
85      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("InstallationQuality", GQAPEvaluator.InstallationQualityDescription, 1));
86      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("OverbookedCapacity", GQAPEvaluator.OverbookedCapacityDescription, 1));
87      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", GeneralizedQuadraticAssignmentProblem.WeightsDescription));
88      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", GeneralizedQuadraticAssignmentProblem.DistancesDescription));
89      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", GeneralizedQuadraticAssignmentProblem.InstallationCostsDescription));
90      Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));
91      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));
92      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
93      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
94    }
95
96    public override IDeepCloneable Clone(Cloner cloner) {
97      return new CordeauCrossover(this, cloner);
98    }
99
100    public static IntegerVector Apply(IRandom random, BoolValue maximization,
101      IntegerVector parent1, DoubleValue quality1,
102      IntegerVector parent2, DoubleValue quality2,
103      DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
104      DoubleArray demands, DoubleArray capacities,
105      DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty) {
106      var mediana = Inizialize(distances);
107      int m = capacities.Length;
108      int n = demands.Length;
109      int i, j, k, ik1, ik2;
110      int control;
111      bool nofound = false, onefound = false;
112      double fbest;
113      IntegerVector son = new IntegerVector(parent1.Length), result = null;
114
115      fbest = quality1.Value;
116      if (maximization.Value && quality1.Value < quality2.Value
117        || !maximization.Value && quality1.Value > quality2.Value) {
118        var temp = parent1;
119        parent1 = parent2;
120        parent2 = temp;
121        fbest = quality2.Value;
122      }
123      var cap = new double[m];
124      for (i = 0; i < m; i++) {
125
126        for (j = 0; j < m; j++) cap[j] = 0;
127
128        for (k = 0; k < n; k++) {
129          son[k] = -1;
130          ik1 = parent1[k];
131          ik2 = parent2[k];
132          if (distances[i, ik1] < mediana[i]) {
133            son[k] = ik1;
134            cap[ik1] += demands[k];
135          } else if (distances[i, ik2] > mediana[i]) {
136            son[k] = ik2;
137            cap[ik2] += demands[k];
138          }
139        }
140        k = 0;
141        nofound = false;
142        while (k < n && !nofound) {
143          if (son[k] < 0) {
144            control = 0;
145            do {
146              j = random.Next(m);
147              control++;
148            }
149            while (cap[j] + demands[k] > capacities[j] && control < 3 * m);
150            if (cap[j] + demands[k] <= capacities[j]) {
151              son[k] = j;
152              cap[j] += demands[k];
153            } else {
154              nofound = true;
155            }
156          }
157          k++;
158        }
159        if (!nofound) {
160          double sonQual = GQAPEvaluator.Evaluate(son, weights, distances, installationCosts, demands, capacities, transportationCosts, overbookedCapacityPenalty);
161          if (sonQual < fbest) {
162            fbest = sonQual;
163            result = (IntegerVector)son.Clone();
164            onefound = true;
165          }
166        }/* else {
167          abortedmerge++;
168          printf("aborted merge %8d\n", abortedmerge);
169        } */
170      }
171      if (!onefound && !nofound) {
172        i = random.Next(m);
173        for (j = 0; j < m; j++) {
174          cap[j] = 0.0;
175        }
176        for (k = 0; k < n; k++) {
177          son[k] = -1;
178          ik1 = parent1[k];
179          ik2 = parent2[k];
180          if (distances[i, ik1] < mediana[i]) {
181            son[k] = ik1;
182            cap[ik1] += demands[k];
183          } else if (distances[i, ik2] > mediana[i]) {
184            son[k] = ik2;
185            cap[ik2] += demands[k];
186          }
187        }
188        for (k = 0; k < n; k++) {
189          if (son[k] < 0) {
190            j = random.Next(m);
191            son[k] = j;
192            cap[j] += demands[k];
193          }
194        }
195        if (result == null) {
196          result = (IntegerVector)son.Clone();
197          onefound = true;
198        } else {
199          double sonQual = GQAPEvaluator.Evaluate(son, weights, distances, installationCosts, demands, capacities, transportationCosts, overbookedCapacityPenalty);
200          if (sonQual < fbest) {
201            fbest = sonQual;
202            result = (IntegerVector)son.Clone();
203            onefound = true;
204          }
205        }
206        /*if (tabufix(&son, 0.5 * sqrt(n * m), round(n * m * log10(n)), &tabufix_it)) {
207          solution_cost(&son);
208          if (son.cost < fbest) {
209            fbest = son.cost;
210            *sptr = son;
211            onefound = TRUE;
212            merge_fixed++;
213          }*/
214      }
215      if (result == null) throw new InvalidOperationException("Child could not be created.");
216      return result;
217    }
218
219    protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents) {
220      if (parents == null) throw new ArgumentNullException("parents");
221      if (parents.Length != 2) throw new ArgumentException(Name + " works only with exactly two parents.");
222
223      var qualities = QualityParameter.ActualValue;
224      return Apply(random, MaximizationParameter.ActualValue,
225        parents[0], qualities[0],
226        parents[1], qualities[1],
227        WeightsParameter.ActualValue, DistancesParameter.ActualValue, InstallationCostsParameter.ActualValue,
228        DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
229        TransportationCostsParameter.ActualValue, OverbookedCapacityPenaltyParameter.ActualValue);
230    }
231
232    private static double[] Inizialize(DoubleMatrix distances) {
233      int i, j;
234      double mdi;
235      double delta;
236      int ilow, ihigh;
237      bool balance;
238      int operation;
239      int count;
240      int m = distances.Rows;
241
242      double[] mediana = new double[distances.Rows];
243
244      for (i = 0; i < m; i++) {
245        mdi = 0;
246        for (j = 0; j < m; j++) {
247          mdi += distances[i, j];
248        }
249        mediana[i] = mdi / m;
250        balance = false;
251        delta = 1;
252        operation = 0;
253        count = 0;
254        while (!balance && count < 200) {
255          ilow = 0;
256          ihigh = 0;
257          count++;
258          for (j = 0; j < m; j++) {
259            if (distances[i, j] < mediana[i]) ilow++;
260            else if (distances[i, j] > mediana[i]) ihigh++;
261          }
262          if (ilow > ((m + 1) / 2)) {
263            mediana[i] = mediana[i] - delta;
264            if (operation == 1) delta = delta / 2;
265            operation = -1;
266          } else if (ihigh > ((m + 1) / 2)) {
267            mediana[i] = mediana[i] + delta;
268            if (operation == -1) delta = delta / 2;
269            operation = 1;
270          } else balance = true;
271        }
272      }
273      return mediana;
274    }
275  }
276}
Note: See TracBrowser for help on using the repository browser.