Changeset 13404 for branches/ProblemRefactoring/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs

Timestamp:

11/26/15 09:30:43 (9 years ago)

Author:

abeham

Message:

#2521:

• Adapted Knapsack problem to new problem infrastructure
• Introduced additional interfaces in binary vector encoding
• Improved KnapsackImprovementOperator which requires less evaluated solutions in case of an infeasible start solution

Loosely related change:

• All LookupParameters are now shown by default
• Wiring code should make sure that wired parameters are hidden

File:

• branches/ProblemRefactoring/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs (modified) (10 diffs)

branches/ProblemRefactoring/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs

@@ -32 +32 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.PluginInfrastructure;
 
 namespace HeuristicLab.Problems.Knapsack {
@@ -38 +37 @@
   [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 200)]
   [StorableClass]
-  public sealed class KnapsackProblem : SingleObjectiveHeuristicOptimizationProblem<IKnapsackEvaluator, IBinaryVectorCreator>,
-    ISingleObjectiveProblem<BinaryVectorEncoding, BinaryVector>, IStorableContent {
-    public string Filename { get; set; }
+  public sealed class KnapsackProblem : SingleObjectiveProblem<BinaryVectorEncoding, BinaryVector> {
+    public override bool Maximization { get { return true; } }
 
     #region Parameter Properties
@@ -52 +50 @@
       get { return (ValueParameter<IntArray>)Parameters["Values"]; }
     }
-    public ValueParameter<DoubleValue> PenaltyParameter {
-      get { return (ValueParameter<DoubleValue>)Parameters["Penalty"]; }
-    }
     public OptionalValueParameter<BinaryVector> BestKnownSolutionParameter {
       get { return (OptionalValueParameter<BinaryVector>)Parameters["BestKnownSolution"]; }
@@ -61 +56 @@
 
     #region Properties
-    public IntValue KnapsackCapacity {
-      get { return KnapsackCapacityParameter.Value; }
-      set { KnapsackCapacityParameter.Value = value; }
+    public int KnapsackCapacity {
+      get { return KnapsackCapacityParameter.Value.Value; }
+      set { KnapsackCapacityParameter.Value.Value = value; }
     }
     public IntArray Weights {
@@ -73 +68 @@
       set { ValuesParameter.Value = value; }
     }
-    public DoubleValue Penalty {
-      get { return PenaltyParameter.Value; }
-      set { PenaltyParameter.Value = value; }
-    }
     public BinaryVector BestKnownSolution {
       get { return BestKnownSolutionParameter.Value; }
@@ -83 +74 @@
     private BestKnapsackSolutionAnalyzer BestKnapsackSolutionAnalyzer {
       get { return Operators.OfType<BestKnapsackSolutionAnalyzer>().FirstOrDefault(); }
-    }
-    #endregion
-
-    // BackwardsCompatibility3.3
-    #region Backwards compatible code, remove with 3.4
-    [Obsolete]
-    [Storable(Name = "operators")]
-    private IEnumerable<IOperator> oldOperators {
-      get { return null; }
-      set {
-        if (value != null && value.Any())
-          Operators.AddRange(value);
-      }
     }
     #endregion
@@ -105 +83 @@
       RegisterEventHandlers();
     }
+    public KnapsackProblem()
+      : base(new BinaryVectorEncoding("Selection")) {
+      Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(1)));
+      Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
+      Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
+      Parameters.Add(new OptionalValueParameter<BinaryVector>("BestKnownSolution", "The best known solution of this Knapsack instance."));
+
+      InitializeRandomKnapsackInstance();
+
+      InitializeOperators();
+      RegisterEventHandlers();
+    }
+
+    public override double Evaluate(BinaryVector solution, IRandom random) {
+      var totalWeight = 0.0;
+      var totalValue = 0.0;
+      for (var i = 0; i < solution.Length; i++) {
+        if (!solution[i]) continue;
+        totalWeight += Weights[i];
+        totalValue += Values[i];
+      }
+      return totalWeight > KnapsackCapacity ? KnapsackCapacity - totalWeight : totalValue;
+    }
+
     public override IDeepCloneable Clone(Cloner cloner) {
       return new KnapsackProblem(this, cloner);
     }
-    public KnapsackProblem()
-      : base(new KnapsackEvaluator(), new RandomBinaryVectorCreator()) {
-      Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(0)));
-      Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
-      Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
-      Parameters.Add(new ValueParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight.", new DoubleValue(1)));
-      Parameters.Add(new OptionalValueParameter<BinaryVector>("BestKnownSolution", "The best known solution of this Knapsack instance."));
-
-      Maximization.Value = true;
-      MaximizationParameter.Hidden = true;
-
-      SolutionCreator.BinaryVectorParameter.ActualName = "KnapsackSolution";
-
-      InitializeRandomKnapsackInstance();
-
-      ParameterizeSolutionCreator();
-      ParameterizeEvaluator();
-
-      InitializeOperators();
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
       RegisterEventHandlers();
     }
 
+    private void RegisterEventHandlers() {
+      Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged;
+      KnapsackCapacityParameter.ValueChanged += KnapsackCapacityParameter_ValueChanged;
+      WeightsParameter.ValueChanged += WeightsParameter_ValueChanged;
+      WeightsParameter.Value.Reset += WeightsValue_Reset;
+      ValuesParameter.ValueChanged += ValuesParameter_ValueChanged;
+      ValuesParameter.Value.Reset += ValuesValue_Reset;
+      // TODO: There is no even to detect if the parameter itself was changed
+      Encoding.LengthParameter.ValueChanged += Encoding_LengthParameter_ValueChanged;
+    }
+
     #region Events
+    protected override void OnEncodingChanged() {
+      base.OnEncodingChanged();
+      Parameterize();
+    }
     protected override void OnSolutionCreatorChanged() {
       base.OnSolutionCreatorChanged();
-      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
-      ParameterizeSolutionCreator();
-      ParameterizeEvaluator();
-      ParameterizeAnalyzer();
-      ParameterizeOperators();
+      Parameterize();
     }
     protected override void OnEvaluatorChanged() {
       base.OnEvaluatorChanged();
-      ParameterizeEvaluator();
-      ParameterizeAnalyzer();
-    }
-    private void SolutionCreator_BinaryVectorParameter_ActualNameChanged(object sender, EventArgs e) {
-      ParameterizeEvaluator();
-      ParameterizeAnalyzer();
-      ParameterizeOperators();
+      Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged;
+      Parameterize();
+    }
+    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
+      Parameterize();
     }
     private void KnapsackCapacityParameter_ValueChanged(object sender, EventArgs e) {
-      ParameterizeEvaluator();
-      ParameterizeAnalyzer();
+      Parameterize();
     }
     private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
-      ParameterizeEvaluator();
-      ParameterizeAnalyzer();
-      ParameterizeSolutionCreator();
-
-      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
+      Parameterize();
+      WeightsParameter.Value.Reset += WeightsValue_Reset;
     }
     private void WeightsValue_Reset(object sender, EventArgs e) {
-      ParameterizeSolutionCreator();
-
-      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
-        ((IStringConvertibleArray)ValuesParameter.Value).Length = WeightsParameter.Value.Length;
+      if (WeightsParameter.Value != null && ValuesParameter.Value != null) {
+        ((IStringConvertibleArray)ValuesParameter.Value).Length = Weights.Length;
+        Encoding.Length = Weights.Length;
+      }
+      Parameterize();
     }
     private void ValuesParameter_ValueChanged(object sender, EventArgs e) {
-      ParameterizeEvaluator();
-      ParameterizeAnalyzer();
-      ParameterizeSolutionCreator();
-
-      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
+      Parameterize();
+      ValuesParameter.Value.Reset += ValuesValue_Reset;
     }
     private void ValuesValue_Reset(object sender, EventArgs e) {
-      ParameterizeSolutionCreator();
-
-      if (WeightsParameter.Value != null && ValuesParameter.Value != null)
-        ((IStringConvertibleArray)WeightsParameter.Value).Length = ValuesParameter.Value.Length;
-    }
-    private void PenaltyParameter_ValueChanged(object sender, EventArgs e) {
-      ParameterizeEvaluator();
-    }
-    private void OneBitflipMoveParameter_ActualNameChanged(object sender, EventArgs e) {
-      string name = ((ILookupParameter<OneBitflipMove>)sender).ActualName;
-      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
-        op.OneBitflipMoveParameter.ActualName = name;
-      }
+      if (WeightsParameter.Value != null && ValuesParameter.Value != null) {
+        ((IStringConvertibleArray)WeightsParameter.Value).Length = Values.Length;
+        Encoding.Length = Values.Length;
+      }
+      Parameterize();
+    }
+    private void Encoding_LengthParameter_ValueChanged(object sender, EventArgs e) {
+      if (Weights.Length != Encoding.Length) {
+        ((IStringConvertibleArray)WeightsParameter.Value).Length = Encoding.Length;
+      }
+      if (Values.Length != Encoding.Length) {
+        ((IStringConvertibleArray)ValuesParameter.Value).Length = Encoding.Length;
+      }
+      Parameterize();
     }
     #endregion
 
     #region Helpers
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      // BackwardsCompatibility3.3
-      #region Backwards compatible code (remove with 3.4)
-      if (Operators.Count == 0) InitializeOperators();
-      #endregion
-      RegisterEventHandlers();
-    }
-
-    private void RegisterEventHandlers() {
-      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
-      KnapsackCapacityParameter.ValueChanged += new EventHandler(KnapsackCapacityParameter_ValueChanged);
-      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
-      WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
-      ValuesParameter.ValueChanged += new EventHandler(ValuesParameter_ValueChanged);
-      ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
-      PenaltyParameter.ValueChanged += new EventHandler(PenaltyParameter_ValueChanged);
-    }
-    private void ParameterizeSolutionCreator() {
-      if (SolutionCreator.LengthParameter.Value == null ||
-        SolutionCreator.LengthParameter.Value.Value != WeightsParameter.Value.Length)
-        SolutionCreator.LengthParameter.Value = new IntValue(WeightsParameter.Value.Length);
-    }
-    private void ParameterizeEvaluator() {
-      if (Evaluator is KnapsackEvaluator) {
-        KnapsackEvaluator knapsackEvaluator =
-          (KnapsackEvaluator)Evaluator;
-        knapsackEvaluator.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
-        knapsackEvaluator.BinaryVectorParameter.Hidden = true;
-        knapsackEvaluator.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
-        knapsackEvaluator.KnapsackCapacityParameter.Hidden = true;
-        knapsackEvaluator.WeightsParameter.ActualName = WeightsParameter.Name;
-        knapsackEvaluator.WeightsParameter.Hidden = true;
-        knapsackEvaluator.ValuesParameter.ActualName = ValuesParameter.Name;
-        knapsackEvaluator.ValuesParameter.Hidden = true;
-        knapsackEvaluator.PenaltyParameter.ActualName = PenaltyParameter.Name;
-        knapsackEvaluator.PenaltyParameter.Hidden = true;
-      }
-    }
-    private void ParameterizeAnalyzer() {
-      if (BestKnapsackSolutionAnalyzer != null) {
-        BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
-        BestKnapsackSolutionAnalyzer.MaximizationParameter.Hidden = true;
-        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
-        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.Hidden = true;
-        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
-        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.Hidden = true;
-        BestKnapsackSolutionAnalyzer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
-        BestKnapsackSolutionAnalyzer.BinaryVectorParameter.Hidden = true;
-        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
-        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.Hidden = true;
-        BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
-        BestKnapsackSolutionAnalyzer.WeightsParameter.Hidden = true;
-        BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
-        BestKnapsackSolutionAnalyzer.ValuesParameter.Hidden = true;
-      }
-    }
     private void InitializeOperators() {
       Operators.Add(new KnapsackImprovementOperator());
@@ -258 +191 @@
       Operators.Add(new BestKnapsackSolutionAnalyzer());
       Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
-      ParameterizeAnalyzer();
-      foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
-        if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
-          Operators.Add(op);
-        }
-      }
-      ParameterizeOperators();
-      InitializeMoveGenerators();
-    }
-    private void InitializeMoveGenerators() {
-      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
-        if (op is IMoveGenerator) {
-          op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
-        }
-      }
-    }
-    private void ParameterizeOperators() {
-      foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
-        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
-        op.ParentsParameter.Hidden = true;
-        op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
-        op.ChildParameter.Hidden = true;
-      }
-      foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
-        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
-        op.BinaryVectorParameter.Hidden = true;
-      }
-      foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
-        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
-        op.BinaryVectorParameter.Hidden = true;
-      }
-      foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
+
+      Parameterize();
+    }
+    private void Parameterize() {
+      var operators = new List<IItem>();
+
+      if (BestKnapsackSolutionAnalyzer != null) {
+        operators.Add(BestKnapsackSolutionAnalyzer);
+        BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
+        BestKnapsackSolutionAnalyzer.MaximizationParameter.Hidden = true;
+        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
+        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.Hidden = true;
+        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
+        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.Hidden = true;
+        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
+        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.Hidden = true;
+        BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
+        BestKnapsackSolutionAnalyzer.WeightsParameter.Hidden = true;
+        BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
+        BestKnapsackSolutionAnalyzer.ValuesParameter.Hidden = true;
+      }
+      foreach (var op in Operators.OfType<IKnapsackMoveEvaluator>()) {
+        operators.Add(op);
         op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
         op.KnapsackCapacityParameter.Hidden = true;
-        op.PenaltyParameter.ActualName = PenaltyParameter.Name;
-        op.PenaltyParameter.Hidden = true;
         op.WeightsParameter.ActualName = WeightsParameter.Name;
         op.WeightsParameter.Hidden = true;
         op.ValuesParameter.ActualName = ValuesParameter.Name;
         op.ValuesParameter.Hidden = true;
-      }
-      foreach (IBinaryVectorMultiNeighborhoodShakingOperator op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
-        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
-        op.BinaryVectorParameter.Hidden = true;
-      }
-      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
-        op.SolutionParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
+
+        var bitflipMoveEval = op as IKnapsackOneBitflipMoveEvaluator;
+        if (bitflipMoveEval != null) {
+          foreach (var moveOp in Encoding.Operators.OfType<IOneBitflipMoveQualityOperator>()) {
+            moveOp.MoveQualityParameter.ActualName = bitflipMoveEval.MoveQualityParameter.ActualName;
+            moveOp.MoveQualityParameter.Hidden = true;
+          }
+        }
+      }
+      foreach (var op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
+        operators.Add(op);
+        op.SolutionParameter.ActualName = Encoding.Name;
         op.SolutionParameter.Hidden = true;
       }
-      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
-        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
+      foreach (var op in Operators.OfType<ISingleObjectivePathRelinker>()) {
+        operators.Add(op);
+        op.ParentsParameter.ActualName = Encoding.Name;
         op.ParentsParameter.Hidden = true;
       }
-      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
-        op.SolutionVariableName = SolutionCreator.BinaryVectorParameter.ActualName;
+      foreach (var op in Operators.OfType<ISolutionSimilarityCalculator>()) {
+        operators.Add(op);
+        op.SolutionVariableName = Encoding.Name;
         op.QualityVariableName = Evaluator.QualityParameter.ActualName;
       }
+
+      if (operators.Count > 0) Encoding.ConfigureOperators(Operators);
     }
     #endregion
 
     private void InitializeRandomKnapsackInstance() {
-      System.Random rand = new System.Random();
-
-      int itemCount = rand.Next(10, 100);
+      var sysrand = new System.Random();
+
+      var itemCount = sysrand.Next(10, 100);
       Weights = new IntArray(itemCount);
       Values = new IntArray(itemCount);
@@ -328 +259 @@
 
       for (int i = 0; i < itemCount; i++) {
-        int value = rand.Next(1, 10);
-        int weight = rand.Next(1, 10);
+        var value = sysrand.Next(1, 10);
+        var weight = sysrand.Next(1, 10);
 
         Values[i] = value;
@@ -336 +267 @@
       }
 
-      int capacity = (int)Math.Round(0.7 * totalWeight);
-      KnapsackCapacity = new IntValue(capacity);
+      KnapsackCapacity = (int)Math.Round(0.7 * totalWeight);
     }
   }