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
Multiobjective 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.