Changeset 15564 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/DiscreteLocationCrossover.cs

Timestamp:

01/01/18 23:52:39 (6 years ago)

Author:

abeham

Message:

#1614:

• Fixed some bugs
• Added OSGA
• Updated ES (added recombination)
• Reusing operators among algorihtms (RelocateEquipmentManipluator)
• Rewrote DiscreteLocationCrossover

File:

• branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/DiscreteLocationCrossover.cs (modified) (3 diffs)

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/DiscreteLocationCrossover.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -46 +47 @@
     }
 
-    public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, DoubleArray capacities) {
+    public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, DoubleArray demands, DoubleArray capacities) {
+      var locations = capacities.Length;
+      var cap = Math.Max(parents[0].Length / locations, 1);
+      var lookup = new List<int>[parents.Length][];
+      for (var p = 0; p < parents.Length; p++) {
+        lookup[p] = new List<int>[locations];
+        var assign = parents[p];
+        for (var e = 0; e < parents[p].Length; e++) {
+          var loc = assign[e];
+          if (lookup[p][loc] == null) lookup[p][loc] = new List<int>(cap);
+          lookup[p][loc].Add(e);
+        }
+      }
 
-      var groupedLocations = parents
-              .Select(p => p.Select((value, index) => new { Equipment = index, Location = value })
-              .GroupBy(x => x.Location)
-              .ToDictionary(x => x.Key, y => y.AsEnumerable())).ToArray();
-
+      var slack = capacities.ToArray();
       IntegerVector child = new IntegerVector(parents[0].Length);
-      HashSet<int> remainingEquipment = new HashSet<int>(Enumerable.Range(0, child.Length));
-      int locations = capacities.Length;
-      foreach (var i in Enumerable.Range(0, locations).Shuffle(random)) {
+      var takenEquip = new bool[child.Length];
+      foreach (var loc in Enumerable.Range(0, locations).Shuffle(random)) {
         int parent = random.Next(parents.Length);
-        if (!groupedLocations[parent].ContainsKey(i)) {
+        if (lookup[parent][loc] == null) {
           int tmp = parent;
           do {
             tmp = (tmp + 1) % parents.Length;
-          } while (tmp != parent && !groupedLocations[tmp].ContainsKey(i));
+          } while (tmp != parent && lookup[tmp][loc] == null);
           if (parent == tmp) continue;
           else parent = tmp;
         }
-        foreach (var item in groupedLocations[parent][i]) {
-          if (remainingEquipment.Contains(item.Equipment)) {
-            child[item.Equipment] = i;
-            remainingEquipment.Remove(item.Equipment);
+        foreach (var equip in lookup[parent][loc]) {
+          if (!takenEquip[equip]) {
+            child[equip] = loc;
+            takenEquip[equip] = true;
+            slack[loc] -= demands[equip];
           }
         }
       }
 
-      foreach (var equipment in remainingEquipment) {
-        int parent = random.Next(parents.Length);
-        child[equipment] = parents[parent][equipment];
+      var order = Enumerable.Range(0, takenEquip.Length).Shuffle(random); // avoid bias
+      foreach (var e in order) {
+        if (takenEquip[e]) continue;
+        var assigned = false;
+        // try 1: find a parent where equipment can be assigned feasibly
+        foreach (var p in Enumerable.Range(0, parents.Length).Shuffle(random)) {
+          if (slack[parents[p][e]] >= demands[e]) {
+            child[e] = parents[p][e];
+            slack[child[e]] -= demands[e];
+            assigned = true;
+            break;
+          }
+        }
+        // try 2: find a random feasible location
+        if (!assigned) {
+          var possible = Enumerable.Range(0, locations).Where(x => slack[x] >= demands[e]).ToList();
+          if (possible.Count > 0) {
+            var loc = possible.SampleRandom(random);
+            child[e] = loc;
+            slack[loc] -= demands[e];
+            assigned = true;
+          }
+        }
+        // try 3: insert in a random location (no feasible insert found)
+        if (!assigned) {
+          child[e] = random.Next(locations);
+          slack[child[e]] -= demands[e];
+        }
       }
 
@@ -84 +118 @@
     protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents,
       GQAPInstance problemInstance) {
-      return Apply(random, parents, problemInstance.Capacities);
+      return Apply(random, parents, problemInstance.Demands, problemInstance.Capacities);
     }
   }