#region License Information
/* HeuristicLab
* Copyright (C) 2002-2016 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 System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.BinPacking;
using HeuristicLab.Problems.BinPacking2D;
using HeuristicLab.Problems.Instances;
using HeuristicLab.Random;
namespace HeuristicLab.Problems.BinPacking2d {
[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.")]
[StorableClass]
[Creatable(Category = CreatableAttribute.Categories.CombinatorialProblems, Priority = 300)]
public sealed class PackingSequenceProblem : SingleObjectiveBasicProblem, IProblemInstanceConsumer, IProblemInstanceExporter {
private readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
#region Default Instance
private static readonly BPPData DefaultInstance = new BPPData() {
Name = "2D BPP Default Instance",
Description = "The default instance for 2D Bin Packing.",
BinShape = new PackingShape(20, 16),
Items = new PackingItem[] {
new PackingItem(3, 8, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(5, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(9, 3, new PackingShape(20, 16)) { Material = 1, Weight = 1.0},
new PackingItem(2, 7, new PackingShape(20, 16)) { Material = 1, Weight = 1.0}
},
};
#endregion
#region parameter properties
public IValueParameter DecoderParameter {
get { return (IValueParameter)Parameters["Decoder"]; }
}
public IValueParameter SolutionEvaluatorParameter {
get { return (IValueParameter)Parameters[SolutionEvaluatorParameterName]; }
}
public IValueParameter> ItemsParameter {
get { return (IValueParameter>)Parameters["Items"]; }
}
public IValueParameter BinShapeParameter {
get { return (IValueParameter)Parameters["BinShape"]; }
}
public IValueParameter BestKnownSolutionParameter {
get { return (IValueParameter)Parameters["BestKnownSolution"]; }
}
public IFixedValueParameter LowerBoundParameter {
get { return (IFixedValueParameter)Parameters["LowerBound"]; }
}
#endregion
#region properties
public IPermutationDecoder Decoder {
get { return DecoderParameter.Value; }
set { DecoderParameter.Value = value; }
}
public new BinPacking2D.IEvaluator SolutionEvaluator {
get { return SolutionEvaluatorParameter.Value; }
set { SolutionEvaluatorParameter.Value = value; }
}
public ReadOnlyItemList Items {
get { return ItemsParameter.Value; }
set { ItemsParameter.Value = value; }
}
public PackingShape BinShape {
get { return BinShapeParameter.Value; }
set { BinShapeParameter.Value = value; }
}
public Solution BestKnownSolution {
get { return BestKnownSolutionParameter.Value; }
set { BestKnownSolutionParameter.Value = value; }
}
public int LowerBound {
get { return LowerBoundParameter.Value.Value; }
}
public int NumberOfItems {
get { return Items == null ? 0 : Items.Count; }
}
#endregion
// persistence
[StorableConstructor]
private PackingSequenceProblem(bool deserializing) : base(deserializing) { }
// cloning
private PackingSequenceProblem(PackingSequenceProblem original, Cloner cloner)
: base(original, cloner) {
RegisterEventHandlers();
}
public PackingSequenceProblem()
: base() {
var defaultEvaluator = new PackingRatioEvaluator();
var defaultDecoder = new ExtremePointPermutationDecoder();
Parameters.Add(new ValueParameter("Decoder", "The decoder translates a permutation to a packing solution candidiates", defaultDecoder));
Parameters.Add(new ValueParameter(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator));
Parameters.Add(new ValueParameter>("Items", "The items which must be packed into bins"));
Parameters.Add(new ValueParameter("BinShape", "The size of bins into which items must be packed"));
Parameters.Add(new OptionalValueParameter("BestKnownSolution", "The best solution found so far"));
Parameters.Add(new FixedValueParameter("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));
Load(DefaultInstance);
Encoding = new PermutationEncoding("PackingSequence", Items.Count, PermutationTypes.Absolute);
AddOperators();
RegisterEventHandlers();
}
public override IDeepCloneable Clone(Cloner cloner) {
return new PackingSequenceProblem(this, cloner);
}
[StorableHook(HookType.AfterDeserialization)]
private void AfterDeserialization() {
RegisterEventHandlers();
}
private void AddOperators() {
Operators.Add(new StochasticInsertionMultiMoveGenerator());
Operators.Add(new ExhaustiveInsertionMoveGenerator());
Operators.Add(new TranslocationMoveMaker());
Operators.Add(new TranslocationMoveEvaluator());
Operators.Add(new TranslocationMoveTabuMaker());
Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);
Encoding.ConfigureOperators(Operators.OfType());
}
private void RegisterEventHandlers() {
// update encoding length when number of items is changed
ItemsParameter.ValueChanged += (sender, args) => Encoding.Length = Items.Count;
}
public override bool Maximization { get { return true; } }
public override double Evaluate(Individual individual, IRandom random) {
var permutation = individual.Permutation("PackingSequence");
var decoder = Decoder;
var solution = decoder.Decode(permutation, BinShape, Items);
return SolutionEvaluator.Evaluate(solution);
}
public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
base.Analyze(individuals, qualities, results, random);
Analyze(individuals.Select(i => i.Permutation("PackingSequence")).ToArray(), qualities, results, random);
}
public void Analyze(Permutation[] individuals, double[] qualities, ResultCollection results, IRandom random) {
var bestSolutionResultName = "Best Packing Solution";
var numContainersResultName = "Nr of Containers";
var binUtilResultName = "Overall Bin Utilization";
if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution)));
if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue)));
if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue)));
// find index of item with max quality
int bestIdx = 0;
for (int j = 1; j < qualities.Length; j++)
if (qualities[j] > qualities[bestIdx]) bestIdx = j;
// update best solution so far
var bestSolution = results[bestSolutionResultName].Value as Solution;
if (bestSolution == null ||
bestSolution.Quality.Value < qualities[bestIdx]) {
var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items);
newBestSolution.Quality = new DoubleValue(qualities[bestIdx]);
results[bestSolutionResultName].Value = newBestSolution;
results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins);
results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution));
// update best known solution
var bestKnownQuality = BestKnownQualityParameter.Value;
if (bestKnownQuality == null ||
bestKnownQuality.Value < qualities[bestIdx]) {
BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]);
BestKnownSolutionParameter.ActualValue = newBestSolution;
}
}
}
#region Problem instance handling
public void Load(BPPData data) {
BestKnownSolutionParameter.Value = null;
BestKnownQualityParameter.Value = null;
if (data.BestKnownQuality.HasValue)
BestKnownQuality = data.BestKnownQuality.Value;
BinShape = data.BinShape;
var items = new ItemList(data.Items);
items.Sort((x, y) => y.CompareTo(x));
Items = items.AsReadOnly();
ApplyHorizontalOrientation();
LowerBoundParameter.Value.Value = CalculateLowerBound();
}
public BPPData Export() {
return new BPPData {
Name = Name,
Description = Description,
BinShape = BinShape,
Items = Items.ToArray()
};
}
#endregion
#region helpers
private void ApplyHorizontalOrientation() {
BinShape.ApplyHorizontalOrientation();
foreach (var shape in Items) {
shape.ApplyHorizontalOrientation();
}
}
private int CalculateLowerBound() {
//This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
int itemsVol = Items.Select(x => x.Volume).Sum();
int binVol = BinShape.Volume;
return (itemsVol + binVol - 1) / (binVol);
}
#endregion
}
}