Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PackingRatioEvaluator.cs @ 14146

Last change on this file since 14146 was 14146, checked in by gkronber, 8 years ago

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

File size: 2.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using HeuristicLab.Core;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Common;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.PackingEncoding;
29using HeuristicLab.Problems.BinPacking;
30using System.Collections.Generic;
31
32namespace HeuristicLab.Problems.BinPacking2D {
33  [Item("Packing-Ratio Evaluator (2d)", "Calculates the ratio between packed and unpacked space.")]
34  [StorableClass]
35  public class PackingRatioEvaluator : Item, IEvaluator {
36
37    [StorableConstructor]
38    protected PackingRatioEvaluator(bool deserializing) : base(deserializing) { }
39    protected PackingRatioEvaluator(PackingRatioEvaluator original, Cloner cloner)
40      : base(original, cloner) {
41    }
42    public PackingRatioEvaluator() : base() { }
43    public override IDeepCloneable Clone(Cloner cloner) {
44      return new PackingRatioEvaluator(this, cloner);
45    }
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
76  }
77}
Note: See TracBrowser for help on using the repository browser.