Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/21/16 12:06:43 (8 years ago)
Author:
gkronber
Message:

#1966: refactoring 2d problem

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/PermutationEncoding/PermutationProblem.cs

    r14148 r14149  
    2222#endregion
    2323
    24 using System;
    25 using System.Collections.Generic;
    2624using System.Linq;
    2725using HeuristicLab.Common;
    … …  
    3230using HeuristicLab.Parameters;
    3331using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    34 using HeuristicLab.Problems.BinPacking;
    35 using HeuristicLab.Problems.BinPacking2D;
    3632using HeuristicLab.Problems.Instances;
    37 using HeuristicLab.Random;
    3833
    39 namespace HeuristicLab.Problems.BinPacking2d {
     34namespace HeuristicLab.Problems.BinPacking2D {
    4035  [Item("Bin Packing Problem (2D, permutation encoding) (BPP)", "Represents a two-dimensional bin-packing problem using only bins with identical measures and bins/items with rectangular shapes.")]
    4136  [StorableClass]
    4237  [Creatable(Category = CreatableAttribute.Categories.CombinatorialProblems, Priority = 300)]
    43   public sealed class PackingSequenceProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<BPPData>, IProblemInstanceExporter<BPPData> {
    44     private readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
    45     #region Default Instance
    46     private static readonly BPPData DefaultInstance = new BPPData() {
    47       Name = "2D BPP Default Instance",
    48       Description = "The default instance for 2D Bin Packing.",
    49       BinShape = new PackingShape(20, 16),
    50       Items = new PackingItem[] {
    51         new PackingItem(3,  8, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    52         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    53         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    54         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    55         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    56         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    57         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    58         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    59         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    60         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    61         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    62         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    63         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    64         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    65         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    66         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    67         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    68         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    69         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    70         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    71         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    72         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    73         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    74         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    75         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    76         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    77         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    78         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    79         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    80         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    81         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    82         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    83         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    84         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    85         new PackingItem(5,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    86         new PackingItem(9,  3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
    87         new PackingItem(2,  7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0}
    88       },
    89     };
    90     #endregion
    91 
    92     #region parameter properties
    93     public IValueParameter<IPermutationDecoder> DecoderParameter {
    94       get { return (IValueParameter<IPermutationDecoder>)Parameters["Decoder"]; }
    95     }
    96     public IValueParameter<BinPacking2D.IEvaluator> SolutionEvaluatorParameter {
    97       get { return (IValueParameter<BinPacking2D.IEvaluator>)Parameters[SolutionEvaluatorParameterName]; }
    98     }
    99     public IValueParameter<ReadOnlyItemList<PackingItem>> ItemsParameter {
    100       get { return (IValueParameter<ReadOnlyItemList<PackingItem>>)Parameters["Items"]; }
    101     }
    102     public IValueParameter<PackingShape> BinShapeParameter {
    103       get { return (IValueParameter<PackingShape>)Parameters["BinShape"]; }
    104     }
    105     public IValueParameter<Solution> BestKnownSolutionParameter {
    106       get { return (IValueParameter<Solution>)Parameters["BestKnownSolution"]; }
    107     }
    108     public IFixedValueParameter<IntValue> LowerBoundParameter {
    109       get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
    110     }
    111     #endregion
    112 
    113     #region properties
    114     public IPermutationDecoder Decoder {
    115       get { return DecoderParameter.Value; }
    116       set { DecoderParameter.Value = value; }
    117     }
    118     public new BinPacking2D.IEvaluator SolutionEvaluator {
    119       get { return SolutionEvaluatorParameter.Value; }
    120       set { SolutionEvaluatorParameter.Value = value; }
    121     }
    122     public ReadOnlyItemList<PackingItem> Items {
    123       get { return ItemsParameter.Value; }
    124       set { ItemsParameter.Value = value; }
    125     }
    126     public PackingShape BinShape {
    127       get { return BinShapeParameter.Value; }
    128       set { BinShapeParameter.Value = value; }
    129     }
    130     public Solution BestKnownSolution {
    131       get { return BestKnownSolutionParameter.Value; }
    132       set { BestKnownSolutionParameter.Value = value; }
    133     }
    134     public int LowerBound {
    135       get { return LowerBoundParameter.Value.Value; }
    136     }
    137     public int NumberOfItems {
    138       get { return Items == null ? 0 : Items.Count; }
    139     }
    140     #endregion
    141 
     38  public sealed class PermutationProblem : ProblemBase<PermutationEncoding, Permutation> {
    14239    // persistence
    14340    [StorableConstructor]
    144     private PackingSequenceProblem(bool deserializing) : base(deserializing) { }
     41    private PermutationProblem(bool deserializing) : base(deserializing) { }
    14542
    14643    // cloning
    147     private PackingSequenceProblem(PackingSequenceProblem original, Cloner cloner)
     44    private PermutationProblem(PermutationProblem original, Cloner cloner)
    14845      : base(original, cloner) {
    14946      RegisterEventHandlers();
    15047    }
    15148
    152     public PackingSequenceProblem()
     49    public PermutationProblem()
    15350      : base() {
    154       var defaultEvaluator = new PackingRatioEvaluator();
    155       var defaultDecoder = new ExtremePointPermutationDecoder();
    156       Parameters.Add(new ValueParameter<IPermutationDecoder>("Decoder", "The decoder translates a permutation to a packing solution candidiates", defaultDecoder));
    157       Parameters.Add(new ValueParameter<BinPacking2D.IEvaluator>(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator));
    158       Parameters.Add(new ValueParameter<ReadOnlyItemList<PackingItem>>("Items", "The items which must be packed into bins"));
    159       Parameters.Add(new ValueParameter<PackingShape>("BinShape", "The size of bins into which items must be packed"));
    160       Parameters.Add(new OptionalValueParameter<Solution>("BestKnownSolution", "The best solution found so far"));
    161       Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));
     51      Decoder = new ExtremePointPermutationDecoder(); // default decoder
    16252
    163       Load(DefaultInstance);
    164 
    165       Encoding = new PermutationEncoding("PackingSequence", Items.Count, PermutationTypes.Absolute);
     53      Encoding = new PermutationEncoding(EncodedSolutionName, Items.Count, PermutationTypes.Absolute);
    16654      AddOperators();
    16755      RegisterEventHandlers();
    16856    }
    16957    public override IDeepCloneable Clone(Cloner cloner) {
    170       return new PackingSequenceProblem(this, cloner);
     58      return new PermutationProblem(this, cloner);
    17159    }
    17260
    … …  
    19280      ItemsParameter.ValueChanged += (sender, args) => Encoding.Length = Items.Count;
    19381    }
    194 
    195     public override bool Maximization { get { return true; } }
    196 
    197 
    198     public override double Evaluate(Individual individual, IRandom random) {
    199       var permutation = individual.Permutation("PackingSequence");
    200       var decoder = Decoder;
    201       var solution = decoder.Decode(permutation, BinShape, Items);
    202       return SolutionEvaluator.Evaluate(solution);
    203     }
    204 
    205     public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
    206       base.Analyze(individuals, qualities, results, random);
    207       Analyze(individuals.Select(i => i.Permutation("PackingSequence")).ToArray(), qualities, results, random);
    208     }
    209 
    210     public void Analyze(Permutation[] individuals, double[] qualities, ResultCollection results, IRandom random) {
    211       var bestSolutionResultName = "Best Packing Solution";
    212       var numContainersResultName = "Nr of Containers";
    213       var binUtilResultName = "Overall Bin Utilization";
    214 
    215       if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution)));
    216       if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue)));
    217       if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue)));
    218 
    219 
    220       // find index of item with max quality
    221       int bestIdx = 0;
    222       for (int j = 1; j < qualities.Length; j++)
    223         if (qualities[j] > qualities[bestIdx]) bestIdx = j;
    224 
    225 
    226       // update best solution so far
    227       var bestSolution = results[bestSolutionResultName].Value as Solution;
    228       if (bestSolution == null ||
    229         bestSolution.Quality.Value < qualities[bestIdx]) {
    230 
    231         var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items);
    232         newBestSolution.Quality = new DoubleValue(qualities[bestIdx]);
    233         results[bestSolutionResultName].Value = newBestSolution;
    234         results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins);
    235         results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution));
    236 
    237         // update best known solution
    238         var bestKnownQuality = BestKnownQualityParameter.Value;
    239         if (bestKnownQuality == null ||
    240             bestKnownQuality.Value < qualities[bestIdx]) {
    241           BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]);
    242           BestKnownSolutionParameter.ActualValue = newBestSolution;
    243         }
    244       }
    245     }
    246 
    247 
    248     #region Problem instance handling
    249     public void Load(BPPData data) {
    250       BestKnownSolutionParameter.Value = null;
    251       BestKnownQualityParameter.Value = null;
    252 
    253       if (data.BestKnownQuality.HasValue)
    254         BestKnownQuality = data.BestKnownQuality.Value;
    255 
    256       BinShape = data.BinShape;
    257       var items = new ItemList<PackingItem>(data.Items);
    258       items.Sort((x, y) => y.CompareTo(x));
    259       Items = items.AsReadOnly();
    260 
    261       ApplyHorizontalOrientation();
    262       LowerBoundParameter.Value.Value = CalculateLowerBound();
    263     }
    264 
    265 
    266     public BPPData Export() {
    267       return new BPPData {
    268         Name = Name,
    269         Description = Description,
    270         BinShape = BinShape,
    271         Items = Items.ToArray()
    272       };
    273     }
    274     #endregion
    275 
    276 
    277     #region helpers
    278     private void ApplyHorizontalOrientation() {
    279       BinShape.ApplyHorizontalOrientation();
    280       foreach (var shape in Items) {
    281         shape.ApplyHorizontalOrientation();
    282       }
    283     }
    284 
    285     private int CalculateLowerBound() {
    286       //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
    287       int itemsVol = Items.Select(x => x.Volume).Sum();
    288       int binVol = BinShape.Volume;
    289       return (itemsVol + binVol - 1) / (binVol);
    290     }
    291 
    292     #endregion
    29382  }
    29483}
Note: See TracChangeset for help on using the changeset viewer.