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
23namespace 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...