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
-
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.
-
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.
-
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.
-
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 (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 (solutionClass) – solution to be evaluated
-
abstract
generateNeighbor
(aSolution, neighborhoodSize)[source]¶ Generates a neighbor of the solution.
- Parameters
aSolution (solutionClass) – solution to be modified
neighborhoodSize (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(solutionClass, int)
-
abstract
isValid
(aSolution)[source]¶ Evaluate the validity of the solution.
- Parameters
aSolution (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 (solutionClass) – solution modified
aNeighbor (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 (solutionClass) – solution modified
aNeighbor (solutionClass) – neighbor
-
abstract
-
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 pareto
- Raises
biogemeError – if the first Pareto set is empty.