Changeset 15454 for branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances
- Timestamp:
- 11/07/17 08:24:24 (7 years ago)
- Location:
- branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances
- Files:
-
- 1 deleted
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
TabularUnified branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs ¶
r15418 r15454 26 26 using System.IO; 27 27 using System.Linq; 28 using System.Reflection; 28 29 using HeuristicLab.Common; 29 30 using HeuristicLab.Core; 30 31 using HeuristicLab.Problems.Instances; 31 32 using HeuristicLab.Random; 32 33 namespace HeuristicLab.Problems.BinPacking3D { 33 using HeuristicLab.Problems.BinPacking.Random; 34 35 namespace HeuristicLab.Problems.BinPacking3D.Instances { 34 36 // make sure that for each class we have a separate entry in the problem instance providers 37 35 38 public class RandomInstanceClass1Provider : RandomInstanceProvider { 36 public RandomInstanceClass1Provider() : base() { @class = 1; binWidth = binHeight = binDepth = 100; } 37 } 39 public RandomInstanceClass1Provider() : base(new SRand48()) { @class = 1; binWidth = binHeight = binDepth = 100; } 40 41 } 42 38 43 public class RandomInstanceClass2Provider : RandomInstanceProvider { 39 public RandomInstanceClass2Provider() : base() { @class = 2; binWidth = binHeight = binDepth = 100; } 44 public RandomInstanceClass2Provider() : base(new SRand48()) { @class = 2; binWidth = binHeight = binDepth = 100; } 45 40 46 } 41 47 public class RandomInstanceClass3Provider : RandomInstanceProvider { 42 public RandomInstanceClass3Provider() : base() { @class = 3; binWidth = binHeight = binDepth = 100; } 48 public RandomInstanceClass3Provider() : base(new SRand48()) { @class = 3; binWidth = binHeight = binDepth = 100; } 49 43 50 } 44 51 public class RandomInstanceClass4Provider : RandomInstanceProvider { 45 public RandomInstanceClass4Provider() : base() { @class = 4; binWidth = binHeight = binDepth = 100; } 52 public RandomInstanceClass4Provider() : base(new SRand48()) { @class = 4; binWidth = binHeight = binDepth = 100; } 53 46 54 } 47 55 public class RandomInstanceClass5Provider : RandomInstanceProvider { 48 public RandomInstanceClass5Provider() : base() { @class = 5; binWidth = binHeight = binDepth = 100; } 56 public RandomInstanceClass5Provider() : base(new SRand48()) { @class = 5; binWidth = binHeight = binDepth = 100; } 57 49 58 } 50 59 51 60 public class RandomInstanceClass6Provider : RandomInstanceProvider { 52 public RandomInstanceClass6Provider() : base( ) {61 public RandomInstanceClass6Provider() : base(new SRand48()) { 53 62 @class = 6; 54 63 binWidth = binHeight = binDepth = 10; 55 64 } 56 65 protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) { 57 w = rand.Next(1, 1 1);58 h = rand.Next(1, 1 1);59 d = rand.Next(1, 1 1);66 w = rand.Next(1, 10); 67 h = rand.Next(1, 10); 68 d = rand.Next(1, 10); 60 69 } 61 70 } 62 71 public class RandomInstanceClass7Provider : RandomInstanceProvider { 63 public RandomInstanceClass7Provider() : base( ) {72 public RandomInstanceClass7Provider() : base(new SRand48()) { 64 73 @class = 7; 65 74 binWidth = binHeight = binDepth = 40; 66 75 } 67 76 protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) { 68 w = rand.Next(1, 3 6);69 h = rand.Next(1, 3 6);70 d = rand.Next(1, 3 6);77 w = rand.Next(1, 35); 78 h = rand.Next(1, 35); 79 d = rand.Next(1, 35); 71 80 } 72 81 } 73 82 public class RandomInstanceClass8Provider : RandomInstanceProvider { 74 public RandomInstanceClass8Provider() : base( ) {83 public RandomInstanceClass8Provider() : base(new SRand48()) { 75 84 @class = 8; 76 85 binWidth = binHeight = binDepth = 100; 77 86 } 78 87 protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) { 79 w = rand.Next(1, 10 1);80 h = rand.Next(1, 10 1);81 d = rand.Next(1, 10 1);88 w = rand.Next(1, 100); 89 h = rand.Next(1, 100); 90 d = rand.Next(1, 100); 82 91 } 83 92 } … … 88 97 public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> { 89 98 99 /// <summary> 100 /// Number of created test items. This items are used for packing them into the bin 101 /// </summary> 102 private readonly int[] _numberOfGeneratedTestItems = new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 }; 103 104 /// <summary> 105 /// Number of instance for which should be created for each instance 106 /// </summary> 107 private readonly int _numberOfGeneratedInstances; 108 109 /// <summary> 110 /// Random generator for creating random packing items. 111 /// </summary> 112 private readonly IRandom _randomGenerator; 90 113 91 114 … … 93 116 protected int binWidth, binHeight, binDepth; 94 117 118 #region Common information for displaying on the ui 119 95 120 public override string Name { 96 121 get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); } … … 109 134 } 110 135 111 public RandomInstanceProvider() : base() { } 112 136 #endregion 137 138 139 public RandomInstanceProvider(IRandom randomGenerator, int numberOfGeneratedInstances = 10, int[] numberOfGeneratedTestItems = null) : base() { 140 _numberOfGeneratedInstances = numberOfGeneratedInstances; 141 if (numberOfGeneratedTestItems != null) { 142 _numberOfGeneratedTestItems = numberOfGeneratedTestItems; 143 } 144 _randomGenerator = randomGenerator; 145 } 146 147 148 /// <summary> 149 /// Returns a collection of data descriptors. Each descriptor contains the seed for the random generator. 150 /// </summary> 151 /// <returns></returns> 113 152 public override IEnumerable<IDataDescriptor> GetDataDescriptors() { 114 153 // 10 classes 115 var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same 116 foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90 }) { 117 // get class parameters 118 // generate 30 different instances for each class 119 foreach (int instance in Enumerable.Range(1, 30)) { 154 foreach (int numItems in _numberOfGeneratedTestItems) { 155 for (int instance = 1; instance <= _numberOfGeneratedInstances; instance++) { 120 156 string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class); 121 var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next()); 122 yield return dd; 157 /* As in the test programm of Silvano Martello, David Pisinger, Daniele Vigo given, 158 * the seed of the instance provider will be calculated by adding the number of generated items and teh instance number. 159 * This guarantees that the instances will always be the same 160 */ 161 yield return new RandomDataDescriptor(name, name, numItems, @class, seed: numItems + instance); 123 162 } 124 163 } 125 164 } 165 126 166 127 167 public override BPPData LoadData(IDataDescriptor dd) { 128 168 var randDd = dd as RandomDataDescriptor; 129 if (randDd == null) 169 if (randDd == null) { 130 170 throw new NotSupportedException("Cannot load data descriptor " + dd); 171 } 131 172 132 173 var data = new BPPData() { … … 134 175 Items = new PackingItem[randDd.NumItems] 135 176 }; 136 var instanceRand = new MersenneTwister((uint)randDd.Seed);177 _randomGenerator.Reset(randDd.Seed); 137 178 for (int i = 0; i < randDd.NumItems; i++) { 138 179 int w, h, d; 139 SampleItemParameters( instanceRand, out w, out h, out d);180 SampleItemParameters(_randomGenerator, out w, out h, out d); 140 181 data.Items[i] = new PackingItem(w, h, d, data.BinShape); 141 182 } … … 143 184 } 144 185 145 // default implementation for class 1 .. 5 186 187 /// <summary> 188 /// Generates the dimensions for a item by using the given random generator 189 /// </summary> 190 /// <param name="rand">Given random generator</param> 191 /// <param name="w">Calculated width of the item</param> 192 /// <param name="h">Calculated height of the item</param> 193 /// <param name="d">Calculated depth of the item</param> 146 194 protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) { 147 // for classes 1 - 5148 195 Contract.Assert(@class >= 1 && @class <= 5); 149 var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };196 /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 }; 150 197 weights[@class - 1] = 0.6; 151 198 var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First(); 152 153 int minW, maxW; 154 int minH, maxH; 155 int minD, maxD; 156 GetItemParameters(type, rand, binWidth, binHeight, binDepth, 157 out minW, out maxW, out minH, out maxH, out minD, out maxD); 158 159 w = rand.Next(minW, maxW + 1); 160 h = rand.Next(minH, maxH + 1); 161 d = rand.Next(minD, maxD + 1); 162 } 163 164 private void GetItemParameters(int type, IRandom rand, 165 int w, int h, int d, 166 out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) { 199 */ 200 201 // as by Martello and Vigo 202 int type = @class; 203 if (type <= 5) { 204 var t = rand.Next(1, 10); 205 if (t <= 5) { 206 type = t; 207 } 208 } 209 167 210 switch (type) { 168 case 1: { 169 minW = 1; 170 maxW = w / 2; // integer division on purpose (see paper) 171 minH = h * 2 / 3; 172 maxH = h; 173 minD = d * 2 / 3; 174 maxD = d; 175 break; 176 } 177 case 2: { 178 minW = w * 2 / 3; 179 maxW = w; 180 minH = 1; 181 maxH = h / 2; 182 minD = d * 2 / 3; 183 maxD = d; 184 break; 185 } 186 case 3: { 187 minW = w * 2 / 3; 188 maxW = w; 189 minH = h * 2 / 3; 190 maxH = h; 191 minD = 1; 192 maxD = d / 2; 193 break; 194 } 195 case 4: { 196 minW = w / 2; 197 maxW = w; 198 minH = h / 2; 199 maxH = h; 200 minD = d / 2; 201 maxD = d; 202 break; 203 } 204 case 5: { 205 minW = 1; 206 maxW = w / 2; 207 minH = 1; 208 maxH = h / 2; 209 minD = 1; 210 maxD = d / 2; 211 break; 212 } 213 default: { 214 throw new InvalidProgramException(); 215 } 216 } 217 } 211 case 1: 212 CreateInstanceDimensionsType1(rand, out w, out h, out d); 213 break; 214 case 2: 215 CreateInstanceDimensionsType2(rand, out w, out h, out d); 216 break; 217 case 3: 218 CreateInstanceDimensionsType3(rand, out w, out h, out d); 219 break; 220 case 4: 221 CreateInstanceDimensionsType4(rand, out w, out h, out d); 222 break; 223 case 5: 224 CreateInstanceDimensionsType5(rand, out w, out h, out d); 225 break; 226 default: 227 throw new InvalidProgramException(); 228 } 229 } 230 231 232 #region Instance dimensions generators for type 1 - 5 233 private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) { 234 w = rand.Next(1, binWidth / 2); 235 h = rand.Next((binHeight * 2) / 3, binHeight); 236 d = rand.Next((binDepth * 2) / 3, binDepth); 237 } 238 239 private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) { 240 w = rand.Next(((binWidth * 2) / 3), binWidth); 241 h = rand.Next(1, binHeight / 2); 242 d = rand.Next(((binDepth * 2) / 3), binDepth); 243 } 244 245 private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) { 246 w = rand.Next(((binWidth * 2) / 3), binWidth); 247 h = rand.Next(((binHeight * 2) / 3), binHeight); 248 d = rand.Next(1, binDepth / 2); 249 } 250 private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) { 251 w = rand.Next(binWidth / 2, binWidth); 252 h = rand.Next(binHeight / 2, binHeight); 253 d = rand.Next(binDepth / 2, binDepth); 254 } 255 private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) { 256 w = rand.Next(1, binWidth / 2); 257 h = rand.Next(1, binHeight / 2); 258 d = rand.Next(1, binDepth / 2); 259 } 260 261 #endregion 262 263 218 264 219 265 public override bool CanImportData { … … 242 288 else 243 289 writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth); 244 245 290 } 246 291 writer.Flush(); 247 292 } 248 293 } 249 250 294 } 251 295 }
Note: See TracChangeset
for help on using the changeset viewer.