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)

Bases: object

Class managing the selection and performance analysis of the operators

__init__(operators)

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()

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()

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)

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)

Bases: Pareto

Class managing the solutions

__init__(max_neighborhood, pareto_file=None)

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)

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)

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)

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.

select()

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(operators)

Bases: object

Abstract class defining a problem

__init__(operators)

generate_neighbor(element, neighborhood_size, attempts=5)

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)

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()

Notify that a neighbor has been accepted by the algorithm. Used to update the statistics on the operators.

Parameters:

• solution (biogeme.pareto.SetElement) – solution modified

• a_neighbor (biogeme.pareto.SetElement) – neighbor

last_neighbor_rejected()

Notify that a neighbor has been rejected by the algorithm. Used to update the statistics on the operators.

Parameters:

• solution (biogeme.pareto.SetElement) – solution modified

• a_neighbor (biogeme.pareto.SetElement) – neighbor

biogeme.vns.vns(problem, first_solutions, pareto, number_of_neighbors=10, maximum_attempts=100)

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.