#region License Information /* HeuristicLab * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using HeuristicLab.Core; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Data; using HeuristicLab.Common; using HeuristicLab.Encodings.PackingEncoding; namespace HeuristicLab.Problems.BinPacking { [StorableClass] public abstract class PackingRatioEvaluator : EvaluatorBase where D : class, IPackingPosition where B : PackingShape where I : PackingShape, IPackingItem { [StorableConstructor] protected PackingRatioEvaluator(bool deserializing) : base(deserializing) { } protected PackingRatioEvaluator(PackingRatioEvaluator original, Cloner cloner) : base(original, cloner) { } public PackingRatioEvaluator() : base() { } protected override DoubleValue Evaluate() { DoubleValue quality = new DoubleValue(0); IPackingPlan plan = PackingPlanParameter.ActualValue; B binMeasure = PackingBinMeasuresParameter.ActualValue; ItemList itemMeasures = PackingItemMeasuresParameter.ActualValue; //Check if data is valid //if (plan.PackingItemPositions.Count != itemMeasures.Count) // throw new Exception("ERROR: ItemMeasures.count does not match packingPosition.count"); ////Check if any items are overlapping or not contained in their bins //bool itemPositionsAreValid = !HasOverlappingOrNotContainedItems(plan.PackingItemPositions, binMeasure, itemMeasures, nrOfBins); //if (itemPositionsAreValid) return CalculatePackingRatio(plan as PackingPlan); //return quality; } /* Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing fBPP = (SUM[i=1..N](Fi / C)^k)/N N.......the number of bins used in the solution, Fi......the sum of sizes of the items in the bin i (the fill of the bin), C.......the bin capacity and k.......a constant, k>1. */ public static DoubleValue CalculatePackingRatio(PackingPlan plan) { int nrOfBins = plan.NrOfBins; double result = 0; //C //double usableSpace = binMeasure.MultipliedMeasures; //nrOfBins = N for (int i = 0; i < nrOfBins; i++) { //C //double usableSpace = plan.GetPackingBinMeasuresForBinNr(0).MultipliedMeasures;//plan.GetPackingBinMeasuresForBinNr(i).MultipliedMeasures; //var indexes = plan.PackingItemPositions.Select((Value, Index) => new { Value, Index }).Where(s => s.Value.Value.AssignedBin == i).Select(s => s.Index); //var packedItemsInThisBin = plan.PackingItemMeasures.Select((Value, Index) => new { Value, Index }).Where(s => indexes.Contains(s.Index)); //Fi //double usedSpaceInThisBin = packedItemsInThisBin.Select(s => s.Value.MultipliedMeasures).Sum(); //k = 2 --> (Fi/C)*(Fi/C) //result += (((usedSpaceInThisBin) / (usableSpace)) * ((usedSpaceInThisBin) / (usableSpace))) / (i*i + 1); var PD = plan.BinPackings[i].PackingDensity; result += (PD * PD) / (i + 1); } result = result / nrOfBins; return new DoubleValue(result); } } }