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

Timestamp:

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

Author:

abeham

Message:

#1614:

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

Location:

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators

Files:

• Crossovers/DiscreteLocationCrossover.cs (modified) (3 diffs)
• Manipulators/RelocateEquipmentManipluator.cs (modified) (2 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);
     }
   }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Manipulators/RelocateEquipmentManipluator.cs

@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.Data;
 using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -47 +45 @@
     }
 
-    public static void Apply(IRandom random, IntegerVector assignment, DoubleArray capacities, DoubleArray demands) {
-      int locations = capacities.Length;
+    public static void Apply(IRandom random, IntegerVector assignment, int locations, double stopProb) {
       if (locations < 2) throw new InvalidOperationException("There are not enough locations for relocation operations.");
 
-      Dictionary<int, double> usedCapacities = new Dictionary<int, double>();
-      Dictionary<int, List<int>> groupedLocations = new Dictionary<int, List<int>>();
-      for (int i = 0; i < locations; i++) {
-        usedCapacities[i] = 0.0;
-        groupedLocations.Add(i, new List<int>());
-      }
-      for (int i = 0; i < assignment.Length; i++) {
-        usedCapacities[assignment[i]] += demands[i];
-        groupedLocations[assignment[i]].Add(i);
-      }
-
-      var overbookedLocations = usedCapacities.Where(x => capacities[x.Key] < x.Value);
-      var freeLocations = usedCapacities.Where(x => capacities[x.Key] > x.Value);
-      if (!overbookedLocations.Any() || !freeLocations.Any()) { // perform a random relocation
-        assignment[random.Next(assignment.Length)] = random.Next(locations);
-        return;
-      }
-
-      var sourceLocation = overbookedLocations.SampleRandom(random);
-      int equipmentToRelocate = groupedLocations[sourceLocation.Key].SampleRandom(random);
-      var bestFreeLocations = freeLocations.Where(x => capacities[x.Key] > x.Value + demands[equipmentToRelocate]);
-
-      if (bestFreeLocations.Any()) { // a feasible solution will still be feasible, an infeasible solution might become feasible
-        var selected = bestFreeLocations.SampleRandom(random);
-        assignment[equipmentToRelocate] = sourceLocation.Key;
-      } else { // the solution will become infeasible
-        sourceLocation = freeLocations.SampleRandom(random);
-        assignment[equipmentToRelocate] = sourceLocation.Key;
+      var equipments = Enumerable.Range(0, assignment.Length).Shuffle(random);
+      foreach (var equipment in equipments) {
+        var oldLoc = assignment[equipment];
+        var newLoc =random.Next(locations - 1);
+        if (newLoc >= oldLoc) newLoc++; // don't reassign to current loc
+        assignment[equipment] = newLoc;
+        if (random.NextDouble() < stopProb) break;
       }
     }
 
     protected override void Manipulate(IRandom random, IntegerVector vector, GQAPInstance problemInstance) {
-      Apply(random, vector, problemInstance.Capacities, problemInstance.Demands);
+      Apply(random, vector, problemInstance.Capacities.Length, 4.0 / problemInstance.Demands.Length);
     }
   }