Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/ProblemRefactoring/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs

    r13364 r13404  
    3232using HeuristicLab.Parameters;
    3333using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    34 using HeuristicLab.PluginInfrastructure;
    3534
    3635namespace HeuristicLab.Problems.Knapsack {
     
    3837  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 200)]
    3938  [StorableClass]
    40   public sealed class KnapsackProblem : SingleObjectiveHeuristicOptimizationProblem<IKnapsackEvaluator, IBinaryVectorCreator>,
    41     ISingleObjectiveProblem<BinaryVectorEncoding, BinaryVector>, IStorableContent {
    42     public string Filename { get; set; }
     39  public sealed class KnapsackProblem : SingleObjectiveProblem<BinaryVectorEncoding, BinaryVector> {
     40    public override bool Maximization { get { return true; } }
    4341
    4442    #region Parameter Properties
     
    5250      get { return (ValueParameter<IntArray>)Parameters["Values"]; }
    5351    }
    54     public ValueParameter<DoubleValue> PenaltyParameter {
    55       get { return (ValueParameter<DoubleValue>)Parameters["Penalty"]; }
    56     }
    5752    public OptionalValueParameter<BinaryVector> BestKnownSolutionParameter {
    5853      get { return (OptionalValueParameter<BinaryVector>)Parameters["BestKnownSolution"]; }
     
    6156
    6257    #region Properties
    63     public IntValue KnapsackCapacity {
    64       get { return KnapsackCapacityParameter.Value; }
    65       set { KnapsackCapacityParameter.Value = value; }
     58    public int KnapsackCapacity {
     59      get { return KnapsackCapacityParameter.Value.Value; }
     60      set { KnapsackCapacityParameter.Value.Value = value; }
    6661    }
    6762    public IntArray Weights {
     
    7368      set { ValuesParameter.Value = value; }
    7469    }
    75     public DoubleValue Penalty {
    76       get { return PenaltyParameter.Value; }
    77       set { PenaltyParameter.Value = value; }
    78     }
    7970    public BinaryVector BestKnownSolution {
    8071      get { return BestKnownSolutionParameter.Value; }
     
    8374    private BestKnapsackSolutionAnalyzer BestKnapsackSolutionAnalyzer {
    8475      get { return Operators.OfType<BestKnapsackSolutionAnalyzer>().FirstOrDefault(); }
    85     }
    86     #endregion
    87 
    88     // BackwardsCompatibility3.3
    89     #region Backwards compatible code, remove with 3.4
    90     [Obsolete]
    91     [Storable(Name = "operators")]
    92     private IEnumerable<IOperator> oldOperators {
    93       get { return null; }
    94       set {
    95         if (value != null && value.Any())
    96           Operators.AddRange(value);
    97       }
    9876    }
    9977    #endregion
     
    10583      RegisterEventHandlers();
    10684    }
     85    public KnapsackProblem()
     86      : base(new BinaryVectorEncoding("Selection")) {
     87      Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(1)));
     88      Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
     89      Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
     90      Parameters.Add(new OptionalValueParameter<BinaryVector>("BestKnownSolution", "The best known solution of this Knapsack instance."));
     91
     92      InitializeRandomKnapsackInstance();
     93
     94      InitializeOperators();
     95      RegisterEventHandlers();
     96    }
     97
     98    public override double Evaluate(BinaryVector solution, IRandom random) {
     99      var totalWeight = 0.0;
     100      var totalValue = 0.0;
     101      for (var i = 0; i < solution.Length; i++) {
     102        if (!solution[i]) continue;
     103        totalWeight += Weights[i];
     104        totalValue += Values[i];
     105      }
     106      return totalWeight > KnapsackCapacity ? KnapsackCapacity - totalWeight : totalValue;
     107    }
     108
    107109    public override IDeepCloneable Clone(Cloner cloner) {
    108110      return new KnapsackProblem(this, cloner);
    109111    }
    110     public KnapsackProblem()
    111       : base(new KnapsackEvaluator(), new RandomBinaryVectorCreator()) {
    112       Parameters.Add(new ValueParameter<IntValue>("KnapsackCapacity", "Capacity of the Knapsack.", new IntValue(0)));
    113       Parameters.Add(new ValueParameter<IntArray>("Weights", "The weights of the items.", new IntArray(5)));
    114       Parameters.Add(new ValueParameter<IntArray>("Values", "The values of the items.", new IntArray(5)));
    115       Parameters.Add(new ValueParameter<DoubleValue>("Penalty", "The penalty value for each unit of overweight.", new DoubleValue(1)));
    116       Parameters.Add(new OptionalValueParameter<BinaryVector>("BestKnownSolution", "The best known solution of this Knapsack instance."));
    117 
    118       Maximization.Value = true;
    119       MaximizationParameter.Hidden = true;
    120 
    121       SolutionCreator.BinaryVectorParameter.ActualName = "KnapsackSolution";
    122 
    123       InitializeRandomKnapsackInstance();
    124 
    125       ParameterizeSolutionCreator();
    126       ParameterizeEvaluator();
    127 
    128       InitializeOperators();
     112
     113    [StorableHook(HookType.AfterDeserialization)]
     114    private void AfterDeserialization() {
    129115      RegisterEventHandlers();
    130116    }
    131117
     118    private void RegisterEventHandlers() {
     119      Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged;
     120      KnapsackCapacityParameter.ValueChanged += KnapsackCapacityParameter_ValueChanged;
     121      WeightsParameter.ValueChanged += WeightsParameter_ValueChanged;
     122      WeightsParameter.Value.Reset += WeightsValue_Reset;
     123      ValuesParameter.ValueChanged += ValuesParameter_ValueChanged;
     124      ValuesParameter.Value.Reset += ValuesValue_Reset;
     125      // TODO: There is no even to detect if the parameter itself was changed
     126      Encoding.LengthParameter.ValueChanged += Encoding_LengthParameter_ValueChanged;
     127    }
     128
    132129    #region Events
     130    protected override void OnEncodingChanged() {
     131      base.OnEncodingChanged();
     132      Parameterize();
     133    }
    133134    protected override void OnSolutionCreatorChanged() {
    134135      base.OnSolutionCreatorChanged();
    135       SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
    136       ParameterizeSolutionCreator();
    137       ParameterizeEvaluator();
    138       ParameterizeAnalyzer();
    139       ParameterizeOperators();
     136      Parameterize();
    140137    }
    141138    protected override void OnEvaluatorChanged() {
    142139      base.OnEvaluatorChanged();
    143       ParameterizeEvaluator();
    144       ParameterizeAnalyzer();
    145     }
    146     private void SolutionCreator_BinaryVectorParameter_ActualNameChanged(object sender, EventArgs e) {
    147       ParameterizeEvaluator();
    148       ParameterizeAnalyzer();
    149       ParameterizeOperators();
     140      Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged;
     141      Parameterize();
     142    }
     143    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
     144      Parameterize();
    150145    }
    151146    private void KnapsackCapacityParameter_ValueChanged(object sender, EventArgs e) {
    152       ParameterizeEvaluator();
    153       ParameterizeAnalyzer();
     147      Parameterize();
    154148    }
    155149    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
    156       ParameterizeEvaluator();
    157       ParameterizeAnalyzer();
    158       ParameterizeSolutionCreator();
    159 
    160       WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
     150      Parameterize();
     151      WeightsParameter.Value.Reset += WeightsValue_Reset;
    161152    }
    162153    private void WeightsValue_Reset(object sender, EventArgs e) {
    163       ParameterizeSolutionCreator();
    164 
    165       if (WeightsParameter.Value != null && ValuesParameter.Value != null)
    166         ((IStringConvertibleArray)ValuesParameter.Value).Length = WeightsParameter.Value.Length;
     154      if (WeightsParameter.Value != null && ValuesParameter.Value != null) {
     155        ((IStringConvertibleArray)ValuesParameter.Value).Length = Weights.Length;
     156        Encoding.Length = Weights.Length;
     157      }
     158      Parameterize();
    167159    }
    168160    private void ValuesParameter_ValueChanged(object sender, EventArgs e) {
    169       ParameterizeEvaluator();
    170       ParameterizeAnalyzer();
    171       ParameterizeSolutionCreator();
    172 
    173       ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
     161      Parameterize();
     162      ValuesParameter.Value.Reset += ValuesValue_Reset;
    174163    }
    175164    private void ValuesValue_Reset(object sender, EventArgs e) {
    176       ParameterizeSolutionCreator();
    177 
    178       if (WeightsParameter.Value != null && ValuesParameter.Value != null)
    179         ((IStringConvertibleArray)WeightsParameter.Value).Length = ValuesParameter.Value.Length;
    180     }
    181     private void PenaltyParameter_ValueChanged(object sender, EventArgs e) {
    182       ParameterizeEvaluator();
    183     }
    184     private void OneBitflipMoveParameter_ActualNameChanged(object sender, EventArgs e) {
    185       string name = ((ILookupParameter<OneBitflipMove>)sender).ActualName;
    186       foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
    187         op.OneBitflipMoveParameter.ActualName = name;
    188       }
     165      if (WeightsParameter.Value != null && ValuesParameter.Value != null) {
     166        ((IStringConvertibleArray)WeightsParameter.Value).Length = Values.Length;
     167        Encoding.Length = Values.Length;
     168      }
     169      Parameterize();
     170    }
     171    private void Encoding_LengthParameter_ValueChanged(object sender, EventArgs e) {
     172      if (Weights.Length != Encoding.Length) {
     173        ((IStringConvertibleArray)WeightsParameter.Value).Length = Encoding.Length;
     174      }
     175      if (Values.Length != Encoding.Length) {
     176        ((IStringConvertibleArray)ValuesParameter.Value).Length = Encoding.Length;
     177      }
     178      Parameterize();
    189179    }
    190180    #endregion
    191181
    192182    #region Helpers
    193     [StorableHook(HookType.AfterDeserialization)]
    194     private void AfterDeserialization() {
    195       // BackwardsCompatibility3.3
    196       #region Backwards compatible code (remove with 3.4)
    197       if (Operators.Count == 0) InitializeOperators();
    198       #endregion
    199       RegisterEventHandlers();
    200     }
    201 
    202     private void RegisterEventHandlers() {
    203       SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
    204       KnapsackCapacityParameter.ValueChanged += new EventHandler(KnapsackCapacityParameter_ValueChanged);
    205       WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
    206       WeightsParameter.Value.Reset += new EventHandler(WeightsValue_Reset);
    207       ValuesParameter.ValueChanged += new EventHandler(ValuesParameter_ValueChanged);
    208       ValuesParameter.Value.Reset += new EventHandler(ValuesValue_Reset);
    209       PenaltyParameter.ValueChanged += new EventHandler(PenaltyParameter_ValueChanged);
    210     }
    211     private void ParameterizeSolutionCreator() {
    212       if (SolutionCreator.LengthParameter.Value == null ||
    213         SolutionCreator.LengthParameter.Value.Value != WeightsParameter.Value.Length)
    214         SolutionCreator.LengthParameter.Value = new IntValue(WeightsParameter.Value.Length);
    215     }
    216     private void ParameterizeEvaluator() {
    217       if (Evaluator is KnapsackEvaluator) {
    218         KnapsackEvaluator knapsackEvaluator =
    219           (KnapsackEvaluator)Evaluator;
    220         knapsackEvaluator.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
    221         knapsackEvaluator.BinaryVectorParameter.Hidden = true;
    222         knapsackEvaluator.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
    223         knapsackEvaluator.KnapsackCapacityParameter.Hidden = true;
    224         knapsackEvaluator.WeightsParameter.ActualName = WeightsParameter.Name;
    225         knapsackEvaluator.WeightsParameter.Hidden = true;
    226         knapsackEvaluator.ValuesParameter.ActualName = ValuesParameter.Name;
    227         knapsackEvaluator.ValuesParameter.Hidden = true;
    228         knapsackEvaluator.PenaltyParameter.ActualName = PenaltyParameter.Name;
    229         knapsackEvaluator.PenaltyParameter.Hidden = true;
    230       }
    231     }
    232     private void ParameterizeAnalyzer() {
    233       if (BestKnapsackSolutionAnalyzer != null) {
    234         BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
    235         BestKnapsackSolutionAnalyzer.MaximizationParameter.Hidden = true;
    236         BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
    237         BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.Hidden = true;
    238         BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
    239         BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.Hidden = true;
    240         BestKnapsackSolutionAnalyzer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
    241         BestKnapsackSolutionAnalyzer.BinaryVectorParameter.Hidden = true;
    242         BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
    243         BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.Hidden = true;
    244         BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
    245         BestKnapsackSolutionAnalyzer.WeightsParameter.Hidden = true;
    246         BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
    247         BestKnapsackSolutionAnalyzer.ValuesParameter.Hidden = true;
    248       }
    249     }
    250183    private void InitializeOperators() {
    251184      Operators.Add(new KnapsackImprovementOperator());
     
    258191      Operators.Add(new BestKnapsackSolutionAnalyzer());
    259192      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
    260       ParameterizeAnalyzer();
    261       foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
    262         if (!(op is ISingleObjectiveMoveEvaluator) || (op is IKnapsackMoveEvaluator)) {
    263           Operators.Add(op);
    264         }
    265       }
    266       ParameterizeOperators();
    267       InitializeMoveGenerators();
    268     }
    269     private void InitializeMoveGenerators() {
    270       foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
    271         if (op is IMoveGenerator) {
    272           op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
    273         }
    274       }
    275     }
    276     private void ParameterizeOperators() {
    277       foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
    278         op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
    279         op.ParentsParameter.Hidden = true;
    280         op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
    281         op.ChildParameter.Hidden = true;
    282       }
    283       foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
    284         op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
    285         op.BinaryVectorParameter.Hidden = true;
    286       }
    287       foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
    288         op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
    289         op.BinaryVectorParameter.Hidden = true;
    290       }
    291       foreach (IKnapsackMoveEvaluator op in Operators.OfType<IKnapsackMoveEvaluator>()) {
     193
     194      Parameterize();
     195    }
     196    private void Parameterize() {
     197      var operators = new List<IItem>();
     198
     199      if (BestKnapsackSolutionAnalyzer != null) {
     200        operators.Add(BestKnapsackSolutionAnalyzer);
     201        BestKnapsackSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
     202        BestKnapsackSolutionAnalyzer.MaximizationParameter.Hidden = true;
     203        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
     204        BestKnapsackSolutionAnalyzer.BestKnownQualityParameter.Hidden = true;
     205        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
     206        BestKnapsackSolutionAnalyzer.BestKnownSolutionParameter.Hidden = true;
     207        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
     208        BestKnapsackSolutionAnalyzer.KnapsackCapacityParameter.Hidden = true;
     209        BestKnapsackSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
     210        BestKnapsackSolutionAnalyzer.WeightsParameter.Hidden = true;
     211        BestKnapsackSolutionAnalyzer.ValuesParameter.ActualName = ValuesParameter.Name;
     212        BestKnapsackSolutionAnalyzer.ValuesParameter.Hidden = true;
     213      }
     214      foreach (var op in Operators.OfType<IKnapsackMoveEvaluator>()) {
     215        operators.Add(op);
    292216        op.KnapsackCapacityParameter.ActualName = KnapsackCapacityParameter.Name;
    293217        op.KnapsackCapacityParameter.Hidden = true;
    294         op.PenaltyParameter.ActualName = PenaltyParameter.Name;
    295         op.PenaltyParameter.Hidden = true;
    296218        op.WeightsParameter.ActualName = WeightsParameter.Name;
    297219        op.WeightsParameter.Hidden = true;
    298220        op.ValuesParameter.ActualName = ValuesParameter.Name;
    299221        op.ValuesParameter.Hidden = true;
    300       }
    301       foreach (IBinaryVectorMultiNeighborhoodShakingOperator op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>()) {
    302         op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
    303         op.BinaryVectorParameter.Hidden = true;
    304       }
    305       foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
    306         op.SolutionParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
     222
     223        var bitflipMoveEval = op as IKnapsackOneBitflipMoveEvaluator;
     224        if (bitflipMoveEval != null) {
     225          foreach (var moveOp in Encoding.Operators.OfType<IOneBitflipMoveQualityOperator>()) {
     226            moveOp.MoveQualityParameter.ActualName = bitflipMoveEval.MoveQualityParameter.ActualName;
     227            moveOp.MoveQualityParameter.Hidden = true;
     228          }
     229        }
     230      }
     231      foreach (var op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
     232        operators.Add(op);
     233        op.SolutionParameter.ActualName = Encoding.Name;
    307234        op.SolutionParameter.Hidden = true;
    308235      }
    309       foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
    310         op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
     236      foreach (var op in Operators.OfType<ISingleObjectivePathRelinker>()) {
     237        operators.Add(op);
     238        op.ParentsParameter.ActualName = Encoding.Name;
    311239        op.ParentsParameter.Hidden = true;
    312240      }
    313       foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
    314         op.SolutionVariableName = SolutionCreator.BinaryVectorParameter.ActualName;
     241      foreach (var op in Operators.OfType<ISolutionSimilarityCalculator>()) {
     242        operators.Add(op);
     243        op.SolutionVariableName = Encoding.Name;
    315244        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
    316245      }
     246
     247      if (operators.Count > 0) Encoding.ConfigureOperators(Operators);
    317248    }
    318249    #endregion
    319250
    320251    private void InitializeRandomKnapsackInstance() {
    321       System.Random rand = new System.Random();
    322 
    323       int itemCount = rand.Next(10, 100);
     252      var sysrand = new System.Random();
     253
     254      var itemCount = sysrand.Next(10, 100);
    324255      Weights = new IntArray(itemCount);
    325256      Values = new IntArray(itemCount);
     
    328259
    329260      for (int i = 0; i < itemCount; i++) {
    330         int value = rand.Next(1, 10);
    331         int weight = rand.Next(1, 10);
     261        var value = sysrand.Next(1, 10);
     262        var weight = sysrand.Next(1, 10);
    332263
    333264        Values[i] = value;
     
    336267      }
    337268
    338       int capacity = (int)Math.Round(0.7 * totalWeight);
    339       KnapsackCapacity = new IntValue(capacity);
     269      KnapsackCapacity = (int)Math.Round(0.7 * totalWeight);
    340270    }
    341271  }
Note: See TracChangeset for help on using the changeset viewer.