sources/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs

   1 #region License Information
   2 /* HeuristicLab
   3  * Copyright (C) 2002-2011 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
  22 using System;
  23 using System.Collections.Generic;
  24 using System.Drawing;
  25 using System.Linq;
  26 using HeuristicLab.Common;
  27 using HeuristicLab.Core;
  28 using HeuristicLab.Data;
  29 using HeuristicLab.Encodings.BinaryVectorEncoding;
  30 using HeuristicLab.Optimization;
  31 using HeuristicLab.Parameters;
  32 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
  33 using HeuristicLab.PluginInfrastructure;
  34
  35 namespace HeuristicLab.Problems.Knapsack {
  36   [Item("Knapsack Problem", "Represents a Knapsack problem.")]
  37   [Creatable("Problems")]
  38   [StorableClass]
  39   public sealed class KnapsackProblem : ParameterizedNamedItem, ISingleObjectiveHeuristicOptimizationProblem, IStorableContent {
  40     public string Filename { get; set; }
  41
  42     public override Image ItemImage {
  43       get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
  44     }
  45
  46     #region Parameter Properties
  47     public ValueParameter<BoolValue> MaximizationParameter {
  48       get { return (ValueParameter<BoolValue>)Parameters["Maximization"]; }
  49     }
  50     IParameter ISingleObjectiveHeuristicOptimizationProblem.MaximizationParameter {
  51       get { return MaximizationParameter; }
  52     }
  53     public ValueParameter<IntValue> KnapsackCapacityParameter {
  54       get { return (ValueParameter<IntValue>)Parameters["KnapsackCapacity"]; }
  55     }
  56     public ValueParameter<IntArray> WeightsParameter {
  57       get { return (ValueParameter<IntArray>)Parameters["Weights"]; }
  58     }
  59     public ValueParameter<IntArray> ValuesParameter {
  60       get { return (ValueParameter<IntArray>)Parameters["Values"]; }
  61     }
  62     public ValueParameter<DoubleValue> PenaltyParameter {
  63       get { return (ValueParameter<DoubleValue>)Parameters["Penalty"]; }
  64     }
  65     public ValueParameter<IBinaryVectorCreator> SolutionCreatorParameter {
  66       get { return (ValueParameter<IBinaryVectorCreator>)Parameters["SolutionCreator"]; }
  67     }
  68     IParameter IHeuristicOptimizationProblem.SolutionCreatorParameter {
  69       get { return SolutionCreatorParameter; }
  70     }
  71     public ValueParameter<IKnapsackEvaluator> EvaluatorParameter {
  72       get { return (ValueParameter<IKnapsackEvaluator>)Parameters["Evaluator"]; }
  73     }
  74     IParameter IHeuristicOptimizationProblem.EvaluatorParameter {
  75       get { return EvaluatorParameter; }
  76     }
  77     public OptionalValueParameter<DoubleValue> BestKnownQualityParameter {
  78       get { return (OptionalValueParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
  79     }
  80     IParameter ISingleObjectiveHeuristicOptimizationProblem.BestKnownQualityParameter {
  81       get { return BestKnownQualityParameter; }
  82     }
  83     public OptionalValueParameter<BinaryVector> BestKnownSolutionParameter {
  84       get { return (OptionalValueParameter<BinaryVector>)Parameters["BestKnownSolution"]; }
  85     }
  86     #endregion
  87
  88     #region Properties
  89     public BoolValue Maximization {
  90       get { return MaximizationParameter.Value; }
  91       set { MaximizationParameter.Value = value; }
  92     }
  93     public IntValue KnapsackCapacity {
  94       get { return KnapsackCapacityParameter.Value; }
  95       set { KnapsackCapacityParameter.Value = value; }
  96     }
  97     public IntArray Weights {
  98       get { return WeightsParameter.Value; }
  99       set { WeightsParameter.Value = value; }
 100     }
 101     public IntArray Values {
 102       get { return ValuesParameter.Value; }
 103       set { ValuesParameter.Value = value; }
 104     }
 105     public DoubleValue Penalty {
 106       get { return PenaltyParameter.Value; }
 107       set { PenaltyParameter.Value = value; }
 108     }
 109     public IBinaryVectorCreator SolutionCreator {
 110       get { return SolutionCreatorParameter.Value; }
 111       set { SolutionCreatorParameter.Value = value; }
 112     }
 113     ISolutionCreator IHeuristicOptimizationProblem.SolutionCreator {
 114       get { return SolutionCreatorParameter.Value; }
 115     }
 116     public IKnapsackEvaluator Evaluator {
 117       get { return EvaluatorParameter.Value; }
 118       set { EvaluatorParameter.Value = value; }
 119     }
 120     ISingleObjectiveEvaluator ISingleObjectiveHeuristicOptimizationProblem.Evaluator {
 121       get { return EvaluatorParameter.Value; }
 122     }
 123     IEvaluator IHeuristicOptimizationProblem.Evaluator {
 124       get { return EvaluatorParameter.Value; }
 125     }
 126     public DoubleValue BestKnownQuality {
 127       get { return BestKnownQualityParameter.Value; }
 128       set { BestKnownQualityParameter.Value = value; }
 129     }
 130     public BinaryVector BestKnownSolution {
 131       get { return BestKnownSolutionParameter.Value; }
 132       set { BestKnownSolutionParameter.Value = value; }
 133     }
 134     public IEnumerable<IOperator> Operators {
 135       get { return operators.Cast<IOperator>(); }
 136     }
 137     private BestKnapsackSolutionAnalyzer BestKnapsackSolutionAnalyzer {
 138       get { return operators.OfType<BestKnapsackSolutionAnalyzer>().FirstOrDefault(); }
 139     }
 140     #endregion
 141
 142     [Storable]
 143     private List<IOperator> operators;
 144
 145     [StorableConstructor]
 146     private KnapsackProblem(bool deserializing) : base(deserializing) { }
 147     private KnapsackProblem(KnapsackProblem original, Cloner cloner)
 148       : base(original, cloner) {
 149       this.operators = original.operators.Select(x => (IOperator)cloner.Clone(x)).ToList();
 150       AttachEventHandlers();
 151     }
 152     public override IDeepCloneable Clone(Cloner cloner) {
 153       return new KnapsackProblem(this, cloner);
 154     }
 155     public KnapsackProblem()
 156       : base() {
 157       RandomBinaryVectorCreator creator = new RandomBinaryVectorCreator();
 158       KnapsackEvaluator evaluator = new KnapsackEvaluator();
 159
 160       Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to true as the Knapsack Problem is a maximization problem.", new BoolValue(true)));
 161       Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(0)));
 162       Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
 163       Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
 164       Parameters.Add(new ValueParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight.", new DoubleValue(1)));
 165       Parameters.Add(new ValueParameter<IBinaryVectorCreator>("SolutionCreator", "The operator which should be used to create new Knapsack solutions.", creator));
 166       Parameters.Add(new ValueParameter<IKnapsackEvaluator>("Evaluator", "The operator which should be used to evaluate Knapsack solutions.", evaluator));
 167       Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this Knapsack instance."));
 168       Parameters.Add(new OptionalValueParameter<BinaryVector>("BestKnownSolution", "The best known solution of this Knapsack instance."));
 169
 170       creator.BinaryVectorParameter.ActualName = "KnapsackSolution";
 171
 172       InitializeRandomKnapsackInstance();
 173
 174       ParameterizeSolutionCreator();
 175       ParameterizeEvaluator();
 176
 177       InitializeOperators();
 178       AttachEventHandlers();
 179     }
 180
 181     #region Events
 182     public event EventHandler SolutionCreatorChanged;
 183     private void OnSolutionCreatorChanged() {
 184       EventHandler handler = SolutionCreatorChanged;
 185       if (handler != null) handler(this, EventArgs.Empty);
 186     }
 187     public event EventHandler EvaluatorChanged;
 188     private void OnEvaluatorChanged() {
 189       EventHandler handler = EvaluatorChanged;
 190       if (handler != null) handler(this, EventArgs.Empty);
 191     }
 192     public event EventHandler OperatorsChanged;
 193     private void OnOperatorsChanged() {
 194       EventHandler handler = OperatorsChanged;
 195       if (handler != null) handler(this, EventArgs.Empty);
 196     }
 197     public event EventHandler Reset;
 198     private void OnReset() {
 199       EventHandler handler = Reset;
 200       if (handler != null) handler(this, EventArgs.Empty);
 201     }
 202
 203     private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
 204       SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
 205       ParameterizeSolutionCreator();
 206       ParameterizeEvaluator();
 207       ParameterizeAnalyzer();
 208       ParameterizeOperators();
 209       OnSolutionCreatorChanged();
 210     }
 211     private void SolutionCreator_BinaryVectorParameter_ActualNameChanged(object sender, EventArgs e) {
 212       ParameterizeEvaluator();
 213       ParameterizeAnalyzer();
 214       ParameterizeOperators();
 215     }
 216     private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
 217       ParameterizeEvaluator();
 218       ParameterizeAnalyzer();
 219       OnEvaluatorChanged();
 220     }
 221     void KnapsackCapacityParameter_ValueChanged(object sender, EventArgs e) {
 222       ParameterizeEvaluator();
 223       ParameterizeAnalyzer();
 224     }
 225     void WeightsParameter_ValueChanged(object sender, EventArgs e) {
 226       ParameterizeEvaluator();
 227       ParameterizeAnalyzer();
 228       ParameterizeSolutionCreator();
 229
 230       WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
 231     }
 232     void WeightsValue_Reset(object sender, EventArgs e) {
 233       ParameterizeSolutionCreator();
 234
 235       if (WeightsParameter.Value != null && ValuesParameter.Value != null)
 236         ((IStringConvertibleArray)ValuesParameter.Value).Length = WeightsParameter.Value.Length;
 237     }
 238     void ValuesParameter_ValueChanged(object sender, EventArgs e) {
 239       ParameterizeEvaluator();
 240       ParameterizeAnalyzer();
 241       ParameterizeSolutionCreator();
 242
 243       ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
 244     }
 245     void ValuesValue_Reset(object sender, EventArgs e) {
 246       ParameterizeSolutionCreator();
 247
 248       if (WeightsParameter.Value != null && ValuesParameter.Value != null)
 249         ((IStringConvertibleArray)WeightsParameter.Value).Length = ValuesParameter.Value.Length;
 250     }
 251     void PenaltyParameter_ValueChanged(object sender, EventArgs e) {
 252       ParameterizeEvaluator();
 253     }
 254     void OneBitflipMoveParameter_ActualNameChanged(object sender, EventArgs e) {
 255       string name = ((ILookupParameter<OneBitflipMove>)sender).ActualName;
 256       foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
 257         op.OneBitflipMoveParameter.ActualName = name;
 258       }
 259     }
 260     #endregion
 261
 262     #region Helpers
 263     [StorableHook(HookType.AfterDeserialization)]
 264     private void AfterDeserialization() {
 265       // BackwardsCompatibility3.3
 266       #region Backwards compatible code (remove with 3.4)
 267       if (operators == null) InitializeOperators();
 268       #endregion
 269       AttachEventHandlers();
 270     }
 271
 272     private void AttachEventHandlers() {
 273       SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
 274       SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
 275       EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
 276       KnapsackCapacityParameter.ValueChanged += new EventHandler(KnapsackCapacityParameter_ValueChanged);
 277       WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
 278       WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
 279       ValuesParameter.ValueChanged += new EventHandler(ValuesParameter_ValueChanged);
 280       ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
 281       PenaltyParameter.ValueChanged += new EventHandler(PenaltyParameter_ValueChanged);
 282     }
 283     private void ParameterizeSolutionCreator() {
 284       if (SolutionCreator.LengthParameter.Value == null ||
 285         SolutionCreator.LengthParameter.Value.Value != WeightsParameter.Value.Length)
 286         SolutionCreator.LengthParameter.Value = new IntValue(WeightsParameter.Value.Length);
 287     }
 288     private void ParameterizeEvaluator() {
 289       if (Evaluator is KnapsackEvaluator) {
 290         KnapsackEvaluator knapsackEvaluator =
 291           (KnapsackEvaluator)Evaluator;
 292         knapsackEvaluator.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
 293         knapsackEvaluator.BinaryVectorParameter.Hidden = true;
 294         knapsackEvaluator.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
 295         knapsackEvaluator.KnapsackCapacityParameter.Hidden = true;
 296         knapsackEvaluator.WeightsParameter.ActualName = WeightsParameter.Name;
 297         knapsackEvaluator.WeightsParameter.Hidden = true;
 298         knapsackEvaluator.ValuesParameter.ActualName = ValuesParameter.Name;
 299         knapsackEvaluator.ValuesParameter.Hidden = true;
 300         knapsackEvaluator.PenaltyParameter.ActualName = PenaltyParameter.Name;
 301         knapsackEvaluator.PenaltyParameter.Hidden = true;
 302       }
 303     }
 304     private void ParameterizeAnalyzer() {
 305       BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
 306       BestKnapsackSolutionAnalyzer.MaximizationParameter.Hidden = true;
 307       BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
 308       BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.Hidden = true;
 309       BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
 310       BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.Hidden = true;
 311       BestKnapsackSolutionAnalyzer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
 312       BestKnapsackSolutionAnalyzer.BinaryVectorParameter.Hidden = true;
 313       BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
 314       BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.Hidden = true;
 315       BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
 316       BestKnapsackSolutionAnalyzer.WeightsParameter.Hidden = true;
 317       BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
 318       BestKnapsackSolutionAnalyzer.ValuesParameter.Hidden = true;
 319     }
 320     private void InitializeOperators() {
 321       operators = new List<IOperator>();
 322       operators.Add(new BestKnapsackSolutionAnalyzer());
 323       ParameterizeAnalyzer();
 324       foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
 325         if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
 326           operators.Add(op);
 327         }
 328       }
 329       ParameterizeOperators();
 330       InitializeMoveGenerators();
 331     }
 332     private void InitializeMoveGenerators() {
 333       foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
 334         if (op is IMoveGenerator) {
 335           op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
 336         }
 337       }
 338     }
 339     private void ParameterizeOperators() {
 340       foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
 341         op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
 342         op.ParentsParameter.Hidden = true;
 343         op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
 344         op.ChildParameter.Hidden = true;
 345       }
 346       foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
 347         op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
 348         op.BinaryVectorParameter.Hidden = true;
 349       }
 350       foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
 351         op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
 352         op.BinaryVectorParameter.Hidden = true;
 353       }
 354       foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
 355         op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
 356         op.KnapsackCapacityParameter.Hidden = true;
 357         op.PenaltyParameter.ActualName = PenaltyParameter.Name;
 358         op.PenaltyParameter.Hidden = true;
 359         op.WeightsParameter.ActualName = WeightsParameter.Name;
 360         op.WeightsParameter.Hidden = true;
 361         op.ValuesParameter.ActualName = ValuesParameter.Name;
 362         op.ValuesParameter.Hidden = true;
 363       }
 364       foreach (var op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
 365         op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
 366         op.BinaryVectorParameter.Hidden = true;
 367       }
 368     }
 369     #endregion
 370
 371     private void InitializeRandomKnapsackInstance() {
 372       System.Random rand = new System.Random();
 373
 374       int itemCount = rand.Next(10, 100);
 375       Weights = new IntArray(itemCount);
 376       Values = new IntArray(itemCount);
 377
 378       double totalWeight = 0;
 379
 380       for (int i = 0; i < itemCount; i++) {
 381         int value = rand.Next(1, 10);
 382         int weight = rand.Next(1, 10);
 383
 384         Values[i] = value;
 385         Weights[i] = weight;
 386         totalWeight += weight;
 387       }
 388
 389       int capacity = (int)Math.Round(0.7 * totalWeight);
 390       KnapsackCapacity = new IntValue(capacity);
 391     }
 392   }
 393 }