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

__init__(operatorNames)[source]

Parameters: operatorNames – names of 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.

length()[source]: Obtain the length of the parato set.

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.

restore(fileName)[source]: Restore the Pareto from a file

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 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(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 modified
aNeighbor (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 modified
aNeighbor (biogeme.vns.solutionClass) – neighbor

class biogeme.vns.solutionClass[source]

Bases: object

This is an abstract class defining a solution.

__eq__(other)[source]: Return self==value.

__init__()[source]

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.