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(operatorNames)[source]
Bases:
object
Class managing the selection and performance analysis of the operators
- available
dict of availability of the operators
- decreaseScore(operator)[source]
Decrease the score of an operator. If it has already the minimum score, it increases the others.
- Parameters
operator (str) – name of the operator
- Raises
biogemeError – if the operator is not known.
- increaseScore(operator)[source]
Increase the score of an operator.
- Parameters
operator (str) – name of the operator
- Raises
biogemeError – if the operator is not known.
- names
Names of the operators
- scores
dict of scores obtained by the operators
- selectOperator(minProbability=0.01, scale=0.1)[source]
Select an operator based on the scores
- Parameters
minProbability (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(maxNeighborhood, archiveInputFile=None)[source]
Bases:
object
Class managing the solutions
- __init__(maxNeighborhood, archiveInputFile=None)[source]
- Parameters
maxNeighborhood (int) – the maximum size of the neighborhood that must be considered
archiveInputFile (str) – name of a pickle file contaning sets from previous runs
- add(elem)[source]
We define the set D as the set of members of the current Pareto set that are dominated by the element elem.
We define the set S as the set of members of the current Pareto set that dominate the element elem.
If S is empty, we add elem to the Pareto set, and remove all elements in D.
- Parameters
elem (solutionClass) – elem to be considered for inclusion in the Pareto set.
- Returns
True is elem has been included. False otherwise.
- Return type
bool
- changeNeighborhood(sol)[source]
Change the size of the neighborhood for a solution in the Pareto set.
- Parameters
sol (solutionClass) – solution for which the neighborhood size must be increased.
- considered
set of solutions that have been considered at some point by the algorithm
- dump(fileName)[source]
Dump the three sets on a file using pickle
- Parameters
fileName (str) – name of the file where the sets must be saved.
- Raises
biogemeError – if a problem has occured during dumping.
- maxNeighborhood
the maximum size of the neighborhood that must be considered
- pareto
dict containing the pareto set. The keys are the solutions (class
biogeme.vns.solutionClass
), and the values are the size of the neighborhood that must be applied the next time tat the solution is selected by the algorithm.
- removed
set of solutions that have been in the Pareto set ar some point, but have been removed because dominated by another solution.
- resetNeighborhood(sol)[source]
Reset the size of the neighborhood to 1 for a solution.
- Parameters
sol (solutionClass) – solution for which the neighborhood size must be reset.
- select()[source]
Select a candidate to be modified during the next iteration.
- Returns
a candidate and the neghborhoodsize
- Return type
tuple(solutionClass, int)
- class biogeme.vns.problemClass[source]
Bases:
object
Abstract class defining a problem
- abstract describe(aSolution)[source]
Short description of the solution. Used for reporting.
- Parameters
aSolution (
biogeme.vns.solutionClass
) – solution to be described- Returns
short description of the solution.
- Return type
str
- abstract evaluate(aSolution)[source]
Evaluate the objectives functions of the solution and store them in the solution object.
- Parameters
aSolution (
biogeme.vns.solutionClass
) – solution to be evaluated
- abstract generateNeighbor(aSolution, neighborhoodSize)[source]
Generates a neighbor of the solution.
- Parameters
aSolution (
biogeme.vns.solutionClass
) – solution to be modifiedneighborhoodSize (int) – size of the neighborhood to be applied
- Returns
a neighbor solution, and the number of changes that have been actually applied.
- Return type
tuple(
biogeme.vns.solutionClass
, int)
- abstract isValid(aSolution)[source]
Evaluate the validity of the solution.
- Parameters
aSolution (
biogeme.vns.solutionClass
) – 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)
- abstract neighborAccepted(aSolution, aNeighbor)[source]
Notify that a neighbor has been accepted by the algorithm. Used to update the statistics on the operators.
- Parameters
aSolution (
biogeme.vns.solutionClass
) – solution modifiedaNeighbor (
biogeme.vns.solutionClass
) – neighbor
- abstract neighborRejected(aSolution, aNeighbor)[source]
Notify that a neighbor has been rejected by the algorithm. Used to update the statistics on the operators.
- Parameters
aSolution (
biogeme.vns.solutionClass
) – solution modifiedaNeighbor (
biogeme.vns.solutionClass
) – neighbor
- class biogeme.vns.solutionClass[source]
Bases:
object
This is an abstract class defining a solution.
- dominates(anotherSolution)[source]
Checks if the current solution dominates another one. It is assumed that all objectives are minimized.
- Parameters
anotherSolution (solutionClass) – the other solution to be compared with.
- Returns
True is self dominates anotherSolution, False otherwise.
- Return type
bool
- Raises
biogemeError – if the value of no value is availaboe for the objective functions of ego.
biogemeError – if the value of no value is availaboe for the objective functions of alter.
biogemeError – if the number of objective functions are incompatible.
- biogeme.vns.vns(problem, firstSolutions, maxNeighborhood=20, numberOfNeighbors=10, archiveInputFile=None, pickleOutputFile=None)[source]
Multi objective Variable Neighborhood Search
- Parameters
problem (problemClass) – problem description
firstSolutions (list(solutionClass)) – several models to initialize the algorithm
maxNeighborhood (int) – the maximum size of the neighborhood that must be considered. Default: 20
numberOfNeighbors (int) – if none of this neighbors improves the solution, it is considered that a local optimum has been reached.
archiveInputFile (str) – name of pickle file containing specifications from a previous run of the algorithm. Default: None
pickleOutputFile (str) – name of file where the set of models are stored:
- 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.