Variable Neighborhood Search
Implementation of the VNS algorithm
biogeme.vns module
File vns.py
- author:
Michel Bierlaire, EPFL
- date:
Wed Sep 16 16:55:30 2020
Multi-objective variable neighborhood search algorithm
- class biogeme.vns.OperatorsManagement(operators)[source]
Bases:
object
Class managing the selection and performance analysis of the operators
- __init__(operators)[source]
Ctor
- Parameters:
operators (dict(str: fct)) – dict where the keys are the names of the operators, and the values are the operators themselves. An operator is a function that takes two arguments (the current solution and the size of the neighborhood), and return a neightbor solution.
- available
dict of availability of the operators
- decrease_score_last_operator()[source]
Decrease the score of the last operator. If it has already the minimum score, it increases the others.
- Raises:
BiogemeError – if the operator is not known.
- increase_score_last_operator()[source]
Increase the score of the last operator.
- Raises:
BiogemeError – if the operator is not known.
- names
Names of the operators
- scores
dict of scores obtained by the operators
- select_operator(min_probability=0.01, scale=0.1)[source]
Select an operator based on the scores
- Parameters:
min_probability (float) – minimum probability to select any operator. This is meant to avoid degeneracy, that is to have operators that have no chance to be chosen
scale (float) – parameter for the choice probability
- Returns:
name of the selected operator
- Return type:
str
- Raises:
BiogemeError – if the minimum probability is too large for the number of operators. It must be less or equal to 1 / N, where N is the number of operators.
- class biogeme.vns.ParetoClass(max_neighborhood, pareto_file=None)[source]
Bases:
Pareto
Class managing the solutions
- __init__(max_neighborhood, pareto_file=None)[source]
- Parameters:
max_neighborhood (int) – the maximum size of the neighborhood that must be considered
pareto_file (str) – name of a file contaning sets from previous runs
- add(element)[source]
Add an element :param element: element to be considered for inclusion in the Pareto set. :type element: SetElement
- Returns:
True if solution has been included. False otherwise.
- Return type:
bool
- change_neighborhood(element)[source]
Change the size of the neighborhood for a solution in the Pareto set.
- Parameters:
element (SetElement) – ID of the solution for which the neighborhood size must be increased.
- max_neighborhood
the maximum size of the neighborhood that must be considered
- neighborhood_size
dict associating the solutions IDs with the neighborhoodsize
- reset_neighborhood(element)[source]
Reset the size of the neighborhood to 1 for a solution.
- Parameters:
element (biogeme.pareto.SetElement) – ID of the solution for which the neighborhood size must be reset.
- class biogeme.vns.ProblemClass(operators)[source]
Bases:
object
Abstract class defining a problem
- generate_neighbor(element, neighborhood_size, attempts=5)[source]
Generate a neighbor from the negihborhood of size ``neighborhood_size``using one of the operators
- Parameters:
element (SetElement) – current solution
neighborhood_size (int) – size of the neighborhood
attempts – number of attempts until we give up
- Returns:
number of modifications actually made
- Return type:
int
- abstract is_valid(element)[source]
Check the validity of the solution.
- Parameters:
element (
biogeme.pareto.SetElement
) – solution to be checked- Returns:
valid, why where valid is True if the solution is valid, and False otherwise. why contains an explanation why it is invalid.
- Return type:
tuple(bool, str)
- last_neighbor_accepted()[source]
Notify that a neighbor has been accepted by the algorithm. Used to update the statistics on the operators.
- Parameters:
solution (
biogeme.pareto.SetElement
) – solution modifieda_neighbor (
biogeme.pareto.SetElement
) – neighbor
- last_neighbor_rejected()[source]
Notify that a neighbor has been rejected by the algorithm. Used to update the statistics on the operators.
- Parameters:
solution (
biogeme.pareto.SetElement
) – solution modifieda_neighbor (
biogeme.pareto.SetElement
) – neighbor
- biogeme.vns.vns(problem, first_solutions, pareto, number_of_neighbors=10, maximum_attempts=100)[source]
Multi objective Variable Neighborhood Search
- Parameters:
problem (ProblemClass) – problem description
first_solutions (list(biogeme.pareto.SetElement)) – several models to initialize the algorithm
pareto (ParetoClass) – object managing the Pareto set
number_of_neighbors (int) – if none of this neighbors improves the solution, it is considered that a local optimum has been reached.
maximum_attempts (int) – an attempts consists in selecting a solution in the Pareto set, and trying to improve it. The parameters imposes an upper bound on the total number of attemps, irrespectively if they are successful or not.
- Returns:
the pareto set, the set of models that have been in the pareto set and then removed, and the set of all models considered by the algorithm.
- Return type:
class
biogeme.vns.ParetoClass
- Raises:
BiogemeError – if the first Pareto set is empty.