Ignore:
Timestamp:
07/21/16 10:19:55 (5 years ago)
Author:
gkronber
Message:

#1966: new implementation for 2d bin packing problem with permutation encoding

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingRatioEvaluator.cs

    r14050 r14146  
    2020#endregion
    2121
    22 
     22using System;
     23using System.Linq;
    2324using HeuristicLab.Core;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2526using HeuristicLab.Common;
     27using HeuristicLab.Data;
     28using HeuristicLab.Encodings.PackingEncoding;
    2629using HeuristicLab.Problems.BinPacking;
     30using System.Collections.Generic;
    2731
    2832namespace HeuristicLab.Problems.BinPacking2D {
    29   [Item("Packing-Ratio Evaluator (2d)", "Calculates the ratio between packed and unpacked space. Found in Falkenauer:1996")]
     33  [Item("Packing-Ratio Evaluator (2d)", "Calculates the ratio between packed and unpacked space.")]
    3034  [StorableClass]
    31   public class PackingRatioEvaluator : PackingRatioEvaluator<PackingPosition, PackingShape, PackingItem> {
     35  public class PackingRatioEvaluator : Item, IEvaluator {
    3236
    3337    [StorableConstructor]
    34     protected PackingRatioEvaluator (bool deserializing) : base(deserializing) { }
    35     protected PackingRatioEvaluator (PackingRatioEvaluator original, Cloner cloner)
     38    protected PackingRatioEvaluator(bool deserializing) : base(deserializing) { }
     39    protected PackingRatioEvaluator(PackingRatioEvaluator original, Cloner cloner)
    3640      : base(original, cloner) {
    3741    }
     
    4044      return new PackingRatioEvaluator(this, cloner);
    4145    }
     46
     47    #region IEvaluator Members
     48    public double Evaluate(Solution solution) {
     49      return CalculatePackingRatio(solution);
     50    }
     51
     52    /*
     53        Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
     54       
     55        fBPP = (SUM[i=1..N](Fi / C)^k)/N
     56        N.......the number of bins used in the solution,
     57        Fi......the sum of sizes of the items in the bin i (the fill of the bin),
     58        C.......the bin capacity and
     59        k.......a constant, k>1.
     60     */
     61    public static double CalculatePackingRatio(Solution solution) {
     62      int nrOfBins = solution.NrOfBins;
     63      double result = 0;
     64      const double k = 2;
     65      for (int i = 0; i < nrOfBins; i++) {
     66        var f = solution.BinPackings[i].ItemMeasures.Sum(kvp => kvp.Value.Volume);
     67        var c = solution.BinPackings[i].BinMeasures.Volume;
     68        result += Math.Pow(f / c, k);
     69      }
     70
     71      result = result / nrOfBins;
     72      return result;
     73    }
     74
     75    #endregion
    4276  }
    4377}
Note: See TracChangeset for help on using the changeset viewer.