- Timestamp:
- 01/09/18 15:46:53 (7 years ago)
- Location:
- branches/2817-BinPackingSpeedup
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs
r15488 r15585 205 205 SortingMethod[] sortings, 206 206 FittingMethod[] fittings, 207 ExtremePointCreationMethod[] e PGeneration,207 ExtremePointCreationMethod[] epCreationMethods, 208 208 CancellationToken token) { 209 209 SortingMethod? bestSorting = null; … … 214 214 foreach (var fit in fittings) { 215 215 foreach (var sort in sortings) { 216 foreach (var epCreation in e PGeneration) {216 foreach (var epCreation in epCreationMethods) { 217 217 IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder() { 218 218 FittingMethod = fit, -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/ExtremePointCreator.cs
r15554 r15585 20 20 21 21 /// <summary> 22 /// Updates the residual space for a given bin packing 22 /// Updates the residual space for a given bin packing. 23 23 /// </summary> 24 24 /// <param name="binPacking"></param> … … 26 26 /// <param name="position"></param> 27 27 protected abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position); 28 29 /// <summary> 30 /// Adds an extreme point to the bin packing. 31 /// </summary> 32 /// <param name="binPacking"></param> 33 /// <param name="position"></param> 34 /// <returns></returns> 28 35 protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position); 29 36 … … 214 221 215 222 /// <summary> 216 /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point217 /// </summary> 218 /// <param name="pos"> </param>223 /// Returns true, if the given poisition (pos) and the related residual space is within any residual space of the given extreme point (ep). 224 /// </summary> 225 /// <param name="pos">Given poisition</param> 219 226 /// <param name="rsPos"></param> 220 /// <param name="ep"> </param>227 /// <param name="ep">Given extreme point</param> 221 228 /// <param name="rsEp"></param> 222 229 /// <returns></returns> … … 226 233 227 234 /// <summary> 228 /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point229 /// </summary> 230 /// <param name="pos"> </param>235 /// Returns true, if the given poisition (pos) and the related residual space is within the residual space of the given extreme point (ep). 236 /// </summary> 237 /// <param name="pos">Given poisition</param> 231 238 /// <param name="rsPos"></param> 232 /// <param name="ep"> </param>239 /// <param name="ep">Given extreme point</param> 233 240 /// <param name="rsEp"></param> 234 241 /// <returns></returns> 235 242 protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) { 243 /*old implementation 236 244 return rsEp.Width >= pos.X - ep.X + rsPos.Width 237 245 && rsEp.Height >= pos.Y - ep.Y + rsPos.Height 238 && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth; 246 && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;*/ 247 248 var x = pos.X >= ep.X && pos.X + rsPos.Width <= ep.X + rsEp.Width; 249 var y = pos.Y >= ep.Y && pos.Y + rsPos.Height <= ep.Y + rsEp.Height; 250 var z = pos.Z >= ep.Z && pos.Z + rsPos.Depth <= ep.Z + rsEp.Depth; 251 252 return x && y && z; 239 253 } 240 254 -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/LineProjectionBasedEPCreator.cs
r15554 r15585 23 23 GenerateNewExtremePointsForItem(binPacking, it, p); 24 24 } 25 } 26 27 /// <summary> 28 /// Adds a new extreme point an the related residual spaces to a given bin packing. 29 /// - The given position has to be valid. 30 /// - The extreme point does not exist in the bin packing. 31 /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero. 32 /// </summary> 33 /// <param name="binPacking"></param> 34 /// <param name="position"></param> 35 /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns> 36 protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) { 37 if (position == null) { 38 return false; 39 } 40 41 if (PointIsInAnyItem(binPacking, new Vector3D(position))) { 42 return false; 43 } 44 45 if (binPacking.ExtremePoints.ContainsKey(position)) { 46 return false; 47 } 48 49 var rs = CalculateResidualSpace(binPacking, new Vector3D(position)); 50 51 if (rs.Count() <= 0) { 52 return false; 53 } 54 55 // todo 56 /* 57 ist der extrempunkt im residual space eines anderen muss ueberprueft werden: 58 - ist der andere ep in der luft, kann auch dieser hinzugefuegt werden. 59 - hat der andere ep ein item unterhalb, darf dieser nicht hinzugefuegt werden. 60 -> neu methode basierend auf IsWithinResidualSpaceOfAnotherExtremePoint, die den ep oder rs zurueck gibt, der einen anderen rs einschließt. 61 eventuell gehoert diese logik in den ResidualSpaceCreator. 62 if (LiesOnAnyItem(binPacking, position)) { 63 return false; 64 }*/ 65 66 binPacking.ExtremePoints.Add(position, rs); 67 return true; 68 } 69 25 26 // remove not needed extreme points. 27 foreach (var extremePoint in binPacking.ExtremePoints.ToList()) { 28 // check if a residual space can be removed 29 foreach (var rs in extremePoint.Value.ToList()) { 30 if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) { 31 ((IList<ResidualSpace>)extremePoint.Value).Remove(rs); 32 } 33 } 34 // if the current extreme point has no more residual spaces, it can be removed. 35 if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) { 36 binPacking.ExtremePoints.Remove(extremePoint); 37 } 38 } 39 } 40 41 /// <summary> 42 /// Returns true if a given residual space can be removed. 43 /// The given residual space can be removed if it is within another residual space and 44 /// - neither the position of the other residual space and the current extreme point have an item below or 45 /// - the current extreme point has an item below. 46 /// </summary> 47 /// <param name="binPacking"></param> 48 /// <param name="position"></param> 49 /// <param name="rs"></param> 50 /// <returns></returns> 51 private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) { 52 foreach (var extremePoint in binPacking.ExtremePoints) { 53 if (position.Equals(extremePoint.Key)) { 54 continue; 55 } 56 if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) { 57 var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key); 58 var itemBelowPos = LiesOnAnyItem(binPacking, position); 59 60 if (itemBelowEp || !itemBelowEp && !itemBelowPos) { 61 return true; 62 } 63 } 64 } 65 return false; 66 } 67 68 /// <summary> 69 /// Returns true if the given position lies on an item or an the ground. 70 /// </summary> 71 /// <param name="binPacking"></param> 72 /// <param name="position"></param> 73 /// <returns></returns> 70 74 private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) { 71 75 if (position.Y == 0) { … … 85 89 86 90 return items.Count() > 0; 91 } 92 93 94 /// <summary> 95 /// Adds a new extreme point an the related residual spaces to a given bin packing. 96 /// - The given position has to be valid. 97 /// - The extreme point does not exist in the bin packing. 98 /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero. 99 /// </summary> 100 /// <param name="binPacking"></param> 101 /// <param name="position"></param> 102 /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns> 103 protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) { 104 if (position == null) { 105 return false; 106 } 107 108 if (PointIsInAnyItem(binPacking, new Vector3D(position))) { 109 return false; 110 } 111 112 if (binPacking.ExtremePoints.ContainsKey(position)) { 113 return false; 114 } 115 116 var rs = CalculateResidualSpace(binPacking, new Vector3D(position)); 117 118 if (rs.Count() <= 0) { 119 return false; 120 } 121 122 binPacking.ExtremePoints.Add(position, rs); 123 return true; 87 124 } 88 125 -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculator.cs
r15554 r15585 19 19 if (!rs1.IsZero()) { 20 20 residualSpaces.Add(rs1); 21 } 22 21 } 23 22 24 23 if (!rs2.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs2))) { … … 31 30 } 32 31 32 /// <summary> 33 /// Calculates a resiual space by expanding to the limits of the axis in the following order: 34 /// 1. x 35 /// 2. z 36 /// 3. y 37 /// </summary> 38 /// <param name="binPacking"></param> 39 /// <param name="point"></param> 40 /// <returns></returns> 33 41 private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) { 34 42 ResidualSpace rs = new ResidualSpace(binPacking, point); … … 40 48 } 41 49 50 /// <summary> 51 /// Calculates a resiual space by expanding to the limits of the axis in the following order: 52 /// 1. z 53 /// 2. y 54 /// 3. x 55 /// </summary> 56 /// <param name="binPacking"></param> 57 /// <param name="point"></param> 58 /// <returns></returns> 42 59 private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) { 43 60 ResidualSpace rs = new ResidualSpace(binPacking, point); … … 49 66 } 50 67 68 /// <summary> 69 /// Calculates a resiual space by expanding to the limits of the axis in the following order: 70 /// 1. y 71 /// 2. x 72 /// 3. z 73 /// </summary> 74 /// <param name="binPacking"></param> 75 /// <param name="point"></param> 76 /// <returns></returns> 51 77 private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) { 52 78 ResidualSpace rs = new ResidualSpace(binPacking, point); … … 114 140 115 141 private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) { 116 // if point.x >= position.x , the residual space would belocated on the left side!142 // if point.x >= position.x => the residual space is being located on the left side! 117 143 if (point.X >= position.X) { 118 144 return false; … … 133 159 } 134 160 161 135 162 private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) { 136 163 if (point.Y >= position.Y) { … … 142 169 return x && z; 143 170 } 144 171 172 /// <summary> 173 /// Recalculates the width of a given residual space. 174 /// The new width is being limited by any item right of the residual space or the dimension of the bin shape. 175 /// If the new width is zero, the whole residual space is being set to zero. 176 /// </summary> 177 /// <param name="binPacking"></param> 178 /// <param name="point"></param> 179 /// <param name="residualSpace"></param> 145 180 private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) { 146 181 if (residualSpace.IsZero()) { … … 163 198 } 164 199 200 /// <summary> 201 /// Recalculates the depth of a given residual space. 202 /// The new depth is being limited by any item in front of the residual space or the dimension of the bin shape. 203 /// If the new depth is zero, the whole residual space is being set to zero. 204 /// </summary> 205 /// <param name="binPacking"></param> 206 /// <param name="point"></param> 207 /// <param name="residualSpace"></param> 165 208 private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) { 166 209 if (residualSpace.IsZero()) { … … 183 226 } 184 227 228 /// <summary> 229 /// Recalculates the height of a given residual space. 230 /// The new height is being limited by any item above the residual space or the dimension of the bin shape. 231 /// If the new height is zero, the whole residual space is being set to zero. 232 /// </summary> 233 /// <param name="binPacking"></param> 234 /// <param name="point"></param> 235 /// <param name="residualSpace"></param> 185 236 private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) { 186 237 if (residualSpace.IsZero()) { -
branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Algorithms/ExtremePointAlgorithmTest.cs
r15554 r15585 74 74 }; 75 75 76 object[] parameters = new object[] { _packingShape3, _items, new SortingMethod[] { SortingMethod.Given }, new FittingMethod[] { FittingMethod.FirstFit }, new CancellationToken() }; 76 object[] parameters = new object[] { _packingShape3, 77 _items, 78 new SortingMethod[] { SortingMethod.Given }, 79 new FittingMethod[] { FittingMethod.FirstFit }, 80 new ExtremePointCreationMethod[] { ExtremePointCreationMethod.PointProjection}, 81 new CancellationToken() }; 77 82 _extremPointAlgorithm.SortingMethodParameter.Value.Value = SortingMethod.Given; 78 83 _extremPointAlgorithm.FittingMethodParameter.Value.Value = FittingMethod.FirstFit; 79 84 _extremPointAlgorithm.ExtremePointCreationMethodParameter.Value.Value = ExtremePointCreationMethod.PointProjection; 80 85 _extremPointAlgorithm.SortByMaterialParameter.Value.Value = false; 81 var result = TestUtils.InvokeMethod(typeof(ExtremePointAlgorithm), _extremPointAlgorithm, "GetBest", parameters) as Tuple<Solution, double, SortingMethod?, FittingMethod? >;86 var result = TestUtils.InvokeMethod(typeof(ExtremePointAlgorithm), _extremPointAlgorithm, "GetBest", parameters) as Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?>; 82 87 83 88 int i = 0; -
branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Instances/RandomInstanceProviderTest.cs
r15554 r15585 170 170 //foreach (FittingMethod fittingMethod in Enum.GetValues(typeof(FittingMethod))) { 171 171 FittingMethod fittingMethod = FittingMethod.FirstFit; 172 TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod); 172 foreach (ExtremePointCreationMethod epCreationMethod in Enum.GetValues(typeof(ExtremePointCreationMethod))) { 173 TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod, epCreationMethod); 174 } 175 173 176 //} 174 177 } 175 178 } 176 179 177 private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod ) {180 private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod, ExtremePointCreationMethod epCreationMethod) { 178 181 var dataDescriptors = randomInstanceProvider.GetDataDescriptors(); 179 182 var referenceValues = GetReferenceAlgorithmValues(); … … 189 192 algorithm.SortingMethodParameter.Value.Value = sortingMethod; 190 193 algorithm.FittingMethodParameter.Value.Value = fittingMethod; 194 algorithm.ExtremePointCreationMethodParameter.Value.Value = epCreationMethod; 191 195 algorithm.Problem.Load(packingData); 192 196 … … 207 211 208 212 if (referenceValues.TryGetValue(new Tuple<int, int, SortingMethod>(@class, numItems, sortingMethod), out referenceValue)) { 209 Console.WriteLine($"{numItems}-{@class}-{sortingMethod} : \tReference: {referenceValue} \tImplementation: {(double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES} \t{(referenceValue - ((double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES)):F2}");213 Console.WriteLine($"{numItems}-{@class}-{sortingMethod}-{epCreationMethod}: \tReference: {referenceValue} \tImplementation: {(double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES} \t{(referenceValue - ((double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES)):F2}"); 210 214 Assert.AreEqual(referenceValue, (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES, 20.0); 211 215 }
Note: See TracChangeset
for help on using the changeset viewer.