OR-Tools  8.2
adaptative_parameter_value.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_UTIL_ADAPTATIVE_PARAMETER_VALUE_H_
15 #define OR_TOOLS_UTIL_ADAPTATIVE_PARAMETER_VALUE_H_
16 
17 #include <algorithm>
18 #include <cmath>
19 #include <cstdint>
20 
22 
23 namespace operations_research {
24 
25 // Basic adaptive [0.0, 1.0] parameter that can be increased or decreased with a
26 // step that get smaller and smaller with the number of updates.
27 //
28 // After a while, if the probability of getting a Decrease() vs Increase() when
29 // running at a given value is f(value), then this should converge towards a
30 // value such that f(value) = 0.5 provided f is a non-decreasing function over
31 // [0.0, 1.0].
32 //
33 // TODO(user): The current logic work well in practice, but has no strong
34 // theoretical foundation. We should be able to come up with a better understood
35 // formula that converge way faster. It will also be nice to generalize the 0.5
36 // above to a target probability p.
38  public:
39  // Initial value is in [0.0, 1.0], both 0.0 and 1.0 are valid.
40  explicit AdaptiveParameterValue(double initial_value)
41  : value_(initial_value) {}
42 
43  void Reset() { num_changes_ = 0; }
44 
45  void Increase() {
46  const double factor = IncreaseNumChangesAndGetFactor();
47  value_ = std::min(1.0 - (1.0 - value_) / factor, value_ * factor);
48  }
49 
50  void Decrease() {
51  const double factor = IncreaseNumChangesAndGetFactor();
52  value_ = std::max(value_ / factor, 1.0 - (1.0 - value_) * factor);
53  }
54 
55  // If we get more than 1 datapoints from the same value(), we use a formula
56  // that is more sound than calling n times Increase()/Decrease() which depends
57  // on the order of calls.
58  void Update(int num_decreases, int num_increases) {
59  if (num_decreases == num_increases) {
60  num_changes_ += num_decreases + num_increases;
61  } else if (num_decreases < num_increases) {
62  for (int i = num_decreases; i < num_increases; ++i) Increase();
63  num_changes_ += 2 * num_decreases;
64  } else {
65  for (int i = num_increases; i < num_decreases; ++i) Decrease();
66  num_changes_ += 2 * num_increases;
67  }
68  }
69 
70  double value() const { return value_; }
71 
72  private:
73  // We want to change the parameters more and more slowly.
74  double IncreaseNumChangesAndGetFactor() {
75  ++num_changes_;
76  return 1.0 + 1.0 / std::sqrt(num_changes_ + 1);
77  }
78 
79  double value_;
80  int64_t num_changes_ = 0;
81 };
82 
83 } // namespace operations_research
84 
85 #endif // OR_TOOLS_UTIL_ADAPTATIVE_PARAMETER_VALUE_H_
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
void Update(int num_decreases, int num_increases)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...