source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/CordeauCrossover.cs @ 15504

Last change on this file since 15504 was 15504, checked in by abeham, 2 years ago

#1614: refactored code

  • change problem to derive from basic problem
  • using a combined instance class instead of individual parameters
File size: 8.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 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.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.IntegerVectorEncoding;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Random;
31
32namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
33  [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.")]
34  [StorableClass]
35  public class CordeauCrossover : GQAPCrossover,
36    IQualitiesAwareGQAPOperator, IProblemInstanceAwareGQAPOperator {
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<Evaluation> EvaluationParameter {
45      get { return (IScopeTreeLookupParameter<Evaluation>)Parameters["Evaluation"]; }
46    }
47    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
48      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
49    }
50
51    [StorableConstructor]
52    protected CordeauCrossover(bool deserializing) : base(deserializing) { }
53    protected CordeauCrossover(CordeauCrossover original, Cloner cloner)
54      : base(original, cloner) {
55    }
56    public CordeauCrossover()
57      : base() {
58      Parameters.Add(new LookupParameter<BoolValue>("Maximization", ""));
59      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The quality of the parents", 1));
60      Parameters.Add(new ScopeTreeLookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription, 1));
61      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solutions."));
62    }
63
64    public override IDeepCloneable Clone(Cloner cloner) {
65      return new CordeauCrossover(this, cloner);
66    }
67
68    public static IntegerVector Apply(IRandom random, bool maximization,
69      IntegerVector parent1, DoubleValue quality1,
70      IntegerVector parent2, DoubleValue quality2,
71      GQAPInstance problemInstance, IntValue evaluatedSolutions) {
72      var distances = problemInstance.Distances;
73      var capacities = problemInstance.Capacities;
74      var demands = problemInstance.Demands;
75
76      var medianDistances = Enumerable.Range(0, distances.Rows).Select(x => distances.GetRow(x).Median()).ToArray();
77
78      int m = capacities.Length;
79      int n = demands.Length;
80     
81      bool onefound = false;
82      double fbest, fbestAttempt = maximization ? double.MinValue : double.MaxValue;
83      IntegerVector bestAttempt = null;
84      IntegerVector result = null;
85
86      fbest = quality1.Value;
87      if (maximization && quality1.Value < quality2.Value
88        || !maximization && quality1.Value > quality2.Value) {
89        var temp = parent1;
90        parent1 = parent2;
91        parent2 = temp;
92        fbest = quality2.Value;
93      }
94      var cap = new double[m];
95      for (var i = 0; i < m; i++) {
96        int unassigned;
97        Array.Clear(cap, 0, m);
98        var child = Merge(parent1, parent2, distances, demands, medianDistances, m, n, i, cap, out unassigned);
99        if (unassigned > 0)
100          TryRandomAssignment(random, demands, capacities, m, n, cap, child, ref unassigned);
101        if (unassigned == 0) {
102          var childFit = problemInstance.ToSingleObjective(problemInstance.Evaluate(child));
103          evaluatedSolutions.Value++;
104          if (maximization && childFit >= fbest
105            || !maximization && childFit <= fbest) {
106            fbest = childFit;
107            result = child;
108            onefound = true;
109          }
110          if (!onefound && (maximization && fbestAttempt < childFit || !maximization && fbestAttempt > childFit)) {
111            bestAttempt = child;
112            fbestAttempt = childFit;
113          }
114        }
115      }
116
117      if (!onefound) {
118        var i = random.Next(m);
119        int unassigned;
120        Array.Clear(cap, 0, m);
121        var child = Merge(parent1, parent2, distances, demands, medianDistances, m, n, i, cap, out unassigned);
122        RandomAssignment(random, demands, capacities, m, n, cap, child, ref unassigned);
123
124        var childFit = problemInstance.ToSingleObjective(problemInstance.Evaluate(child));
125        evaluatedSolutions.Value++;
126        if (childFit < fbest) {
127          fbest = childFit;
128          result = child;
129          onefound = true;
130        }
131
132        if (!onefound && (maximization && fbestAttempt < childFit || !maximization && fbestAttempt > childFit)) {
133          bestAttempt = child;
134          fbestAttempt = childFit;
135        }
136      }
137        /*if (tabufix(&son, 0.5 * sqrt(n * m), round(n * m * log10(n)), &tabufix_it)) {
138          solution_cost(&son);
139          if (son.cost < fbest) {
140            fbest = son.cost;
141            *sptr = son;
142            onefound = TRUE;
143            merge_fixed++;
144          }*/
145      return result ?? bestAttempt;
146    }
147
148    private static IntegerVector Merge(IntegerVector p1, IntegerVector p2,
149      DoubleMatrix distances, DoubleArray demands, double[] mediana,
150      int m, int n, int i, double[] cap, out int unassigned) {
151      unassigned = n;
152      var child = new IntegerVector(n);
153      for (var k = 0; k < n; k++) {
154        child[k] = -1;
155        var ik1 = p1[k];
156        var ik2 = p2[k];
157        if (distances[i, ik1] < mediana[i]) {
158          child[k] = ik1;
159          cap[ik1] += demands[k];
160          unassigned--;
161        } else if (distances[i, ik2] > mediana[i]) {
162          child[k] = ik2;
163          cap[ik2] += demands[k];
164          unassigned--;
165        };
166      }
167      return child;
168    }
169
170    private static bool TryRandomAssignment(IRandom random, DoubleArray demands, DoubleArray capacities, int m, int n, double[] cap, IntegerVector child, ref int unassigned) {
171      var unbiasedOrder = Enumerable.Range(0, n).Shuffle(random).ToList();
172      for (var idx = 0; idx < n; idx++) {
173        var k = unbiasedOrder[idx];
174        if (child[k] < 0) {
175          var feasibleInserts = Enumerable.Range(0, m)
176            .Select((v, i) => new { Pos = i, Slack = capacities[i] - cap[i] })
177            .Where(x => x.Slack >= demands[k]).ToList();
178          if (feasibleInserts.Count == 0) return false;
179          var j = feasibleInserts.SampleRandom(random).Pos;
180          child[k] = j;
181          cap[j] += demands[k];
182          unassigned--;
183        }
184      }
185      return true;
186    }
187
188    private static void RandomAssignment(IRandom random, DoubleArray demands, DoubleArray capacities, int m, int n, double[] cap, IntegerVector child, ref int unassigned) {
189      for (var k = 0; k < n; k++) {
190        if (child[k] < 0) {
191          var j = random.Next(m);
192          child[k] = j;
193          cap[j] += demands[k];
194          unassigned--;
195        }
196      }
197    }
198
199    protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents,
200      GQAPInstance problemInstance) {
201      if (parents == null) throw new ArgumentNullException("parents");
202      if (parents.Length != 2) throw new ArgumentException(Name + " works only with exactly two parents.");
203
204      var qualities = QualityParameter.ActualValue;
205      return Apply(random, MaximizationParameter.ActualValue.Value,
206        parents[0], qualities[0],
207        parents[1], qualities[1],
208        problemInstance,
209        EvaluatedSolutionsParameter.ActualValue);
210    }
211  }
212}
Note: See TracBrowser for help on using the repository browser.