Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Criteria autofit? #35

Closed
N-Wouda opened this issue May 12, 2020 · 1 comment · Fixed by #41
Closed

Criteria autofit? #35

N-Wouda opened this issue May 12, 2020 · 1 comment · Fixed by #41
Labels
enhancement New feature or request good first issue Good for newcomers

Comments

@N-Wouda
Copy link
Owner

N-Wouda commented May 12, 2020

Fairly often I see things like

The starting temperature of the simulated annealing procedure is set such that, in the first iteration, a solution with an objective up to 5% worse than the current solution is accepted with probability 0.5, and the cooling rate is set such that the temperature in the last iteration is 0.2 percent of the start temperature. - Hornstra et al, 2020, in a paper on the VRPSPD-H.

This sort of 'autofit' is interesting to add, and not too hard to do either.
@N-Wouda N-Wouda added enhancement New feature or request good first issue Good for newcomers labels May 12, 2020
@N-Wouda
Copy link
Owner Author

N-Wouda commented May 17, 2020 •
edited
Loading

Roozbeh et al. (2018) show how to do this for the starting temperature, but it's easy to derive for yourself as well. Once you know the starting and end temperatures, the cooling rate r can be computed from the following equivalence: T_end = r ** n * T_start, with n the number of iterations.

Roozbeh et al. (2018). An Adaptive Large Neighbourhood Search for asset protection during escaped wildfires. Computers & Operations Research 97: 125 - 134.

@N-Wouda N-Wouda mentioned this issue Mar 8, 2021
Merged
4 tasks
N-Wouda added a commit that referenced this issue Mar 1, 2022
@N-Wouda
Merge pull request #41 from N-Wouda/adaptive-weighting-schemes
8a83423 
Features
--------

- Weight schemes, which control how `alns.ALNS` selects operators. Two schemes commonly used in the literature (convex updating and segmented weights) have been implemented, as `alns.weight_schemes.SimpleWeights` and `alns.weight_schemes.SegmentedWeights`, respectively (issue #29).
- An `autofit()` function for `alns.criteria.SimulatedAnnealing` (issue #35).
- The `alns` package is considerably better typed now, and passes `mypy` static analysis.

API changes
-----------

The following list details all breaking API changes. The example notebooks have been updated to the new behaviour, and can be used as a reference for how to adapt your own algorithm.

- `alns.ALNS.iterate()` now takes a `weight_scheme` argument, rather than various weight-related parameters it previously accepted.
- `alns.ALNS.iterate()` no longer provides the option not to collect statistics. Statistics are now always collected.
- Any criterion implementing `alns.criteria.AcceptanceCriterion` should now implement `__call__`, not `accept()`. The function signature is unchanged.
- `alns.Result.plot_operator_counts()` now takes a `fig` argument, rather than `figure`.
- Removed `alns.tools.exceptions.NotCollectedError`, since statistics are now always collected.
- Removed `alns.tools.warnings.OverwriteWarning`. Operators are now silently overwritten when a new operator with the same name as an existing one is passed into the ALNS instance.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement New feature or request good first issue Good for newcomers
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Adaptive weighting schemes N-Wouda/ALNS
1 participant
@N-Wouda