org.cpsolver.ifs.algorithms

Class NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>

java.lang.Object

org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext<V,T,NeighbourSearch.NeighbourSearchContext>

org.cpsolver.ifs.algorithms.NeighbourSearch<V,T>

Type Parameters:

V - Variable

T - Value

All Implemented Interfaces:

CanHoldContext, HasAssignmentContext<V,T,NeighbourSearch.NeighbourSearchContext>, NeighbourSelection<V,T>, LazyNeighbour.LazyNeighbourAcceptanceCriterion<V,T>, SolutionListener<V,T>

Direct Known Subclasses:

GreatDeluge, HillClimber, SimulatedAnnealing

public abstract class NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>
extends NeighbourSelectionWithContext<V,T,NeighbourSearch.NeighbourSearchContext>
implements LazyNeighbour.LazyNeighbourAcceptanceCriterion<V,T>, SolutionListener<V,T>

Base class for the search techniques like hill climber, great deluge, or simulated annealing. It implements the SolutionListener and the variable neighbourhood selection.

Version:

IFS 1.3 (Iterative Forward Search)
Copyright (C) 2014 Tomáš Müller
muller@unitime.org
http://muller.unitime.org

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.

Author:

Tomáš Müller

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	NeighbourSearch.NeighbourSearchContext Search context

Field Summary

Fields

Modifier and Type	Field and Description
protected DecimalFormat	iDF2
protected String	iPhase

Fields inherited from class org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext

iContextOverride

Fields inherited from interface org.cpsolver.ifs.assignment.context.CanHoldContext

sMaxSize

Constructor Summary

Constructors

Constructor and Description
NeighbourSearch(DataProperties properties)

Method Summary

Modifier and Type	Method and Description
boolean	accept(Assignment<V,T> assignment, LazyNeighbour<V,T> neighbour, double value) Accept lazy neighbour -- calling the acceptance criterion with lazy = true.
protected boolean	accept(NeighbourSearch.NeighbourSearchContext context, Solution<V,T> solution, Neighbour<V,T> neighbour) True if the generated move is to be accepted.
protected void	addNeighbourSelection(NeighbourSelection<V,T> ns, double bonus) Add neighbour selection
void	bestCleared(Solution<V,T> solution) Called by the solution when method Solution.clearBest() is called.
void	bestRestored(Solution<V,T> solution) Called by the solution when method Solution.restoreBest() is called.
void	bestSaved(Solution<V,T> solution) Called by the solution when method Solution.saveBest() is called.
Neighbour<V,T>	generateMove(Solution<V,T> solution) Generate a random move
void	getInfo(Solution<V,T> solution, Map<String,String> info) Called by the solution when it is asked to produce info table, see Solution.getInfo().
void	getInfo(Solution<V,T> solution, Map<String,String> info, Collection<V> variables) Called by the solution when it is asked to produce info table, see Solution.getInfo().
protected List<? extends NeighbourSelection<V,T>>	getNeighbours() Return list of neighbour selections
abstract String	getParameterBaseName() Parameter base name.
protected void	info(String message) Prints a message into the log
void	init(Solver<V,T> solver) Criterion initialization
boolean	isMaster(Solution<V,T> solution) In single solution multiple threads environments return true if the given solution is of the first thread
protected void	logNeibourStatus() Log some information about neigbour selections once in a while
protected NeighbourSelection<V,T>	nextNeighbourSelection() Generate and return next neighbour selection
Neighbour<V,T>	selectNeighbour(Solution<V,T> solution) select a neighbour of a given solution
protected void	setHCMode(boolean hcMode) Set HC mode for all the neighbour selections that support the HillClimberSelection interface.
protected void	setProgress(long progress) Set search progress
protected void	setProgressPhase(String phase) Set search progress phase
void	solutionUpdated(Solution<V,T> solution) Called by the solution when it is updated, see Solution.update(double).

Methods inherited from class org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext

getAssignmentContextReference, getContext, getContext, hasContextOverride, isSingleContextSolver, setAssignmentContextReference

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.cpsolver.ifs.assignment.context.HasAssignmentContext

createAssignmentContext

Field Detail

iDF2

protected DecimalFormat iDF2

iPhase

protected String iPhase

Constructor Detail

NeighbourSearch

public NeighbourSearch(DataProperties properties)

Method Detail

info

protected void info(String message)

Prints a message into the log

Parameters:

message - a message to log

setProgress

protected void setProgress(long progress)

Set search progress

Parameters:

progress - between 0 and 100

setProgressPhase

protected void setProgressPhase(String phase)

Set search progress phase

Parameters:

phase - a progress phase to set

addNeighbourSelection

protected void addNeighbourSelection(NeighbourSelection<V,T> ns,
                                     double bonus)

Add neighbour selection

Parameters:

ns - a selection

bonus - execution bonus (more bonus means more executions of this neighbour selection, see NeighbourSelector)

setHCMode

protected void setHCMode(boolean hcMode)

Set HC mode for all the neighbour selections that support the HillClimberSelection interface.

Parameters:

hcMode - true if the search is a hill climber (worsening moves are always rejected)

getNeighbours

protected List<? extends NeighbourSelection<V,T>> getNeighbours()

Return list of neighbour selections

Returns:

list of neighbour selections

init

public void init(Solver<V,T> solver)

Description copied from interface: NeighbourSelection

Criterion initialization

Specified by:

init in interface NeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>

Overrides:

init in class NeighbourSelectionWithContext<V extends Variable<V,T>,T extends Value<V,T>,NeighbourSearch.NeighbourSearchContext>

Parameters:

solver - current solver

nextNeighbourSelection

protected NeighbourSelection<V,T> nextNeighbourSelection()

Generate and return next neighbour selection

Returns:

next neighbour selection to use

logNeibourStatus

protected void logNeibourStatus()

Log some information about neigbour selections once in a while

generateMove

public Neighbour<V,T> generateMove(Solution<V,T> solution)

Generate a random move

Parameters:

solution - current solution

Returns:

generated neighbour

selectNeighbour

public Neighbour<V,T> selectNeighbour(Solution<V,T> solution)

Description copied from interface: NeighbourSelection

select a neighbour of a given solution

Specified by:

selectNeighbour in interface NeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

solution - given solution

Returns:

a neighbour assignment

accept

protected boolean accept(NeighbourSearch.NeighbourSearchContext context,
                         Solution<V,T> solution,
                         Neighbour<V,T> neighbour)

True if the generated move is to be accepted.

Parameters:

context - search context

solution - current solution

neighbour - a generated move

Returns:

true if the generated move should be assigned

accept

public boolean accept(Assignment<V,T> assignment,
                      LazyNeighbour<V,T> neighbour,
                      double value)

Accept lazy neighbour -- calling the acceptance criterion with lazy = true.

Specified by:

accept in interface LazyNeighbour.LazyNeighbourAcceptanceCriterion<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

assignment - current assignment

neighbour - neighbour that was assigned

value - change in overall solution value

Returns:

true if the neighbour can be accepted (false to undo the assignment)

getParameterBaseName

public abstract String getParameterBaseName()

Parameter base name. This can be used to distinguish between parameters of different search algorithms.

Returns:

solver parameter base name for this search technique

bestSaved

public void bestSaved(Solution<V,T> solution)

Description copied from interface: SolutionListener

Called by the solution when method Solution.saveBest() is called.

Specified by:

bestSaved in interface SolutionListener<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

solution - source solution

solutionUpdated

public void solutionUpdated(Solution<V,T> solution)

Description copied from interface: SolutionListener

Called by the solution when it is updated, see Solution.update(double).

Specified by:

solutionUpdated in interface SolutionListener<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

solution - source solution

getInfo

public void getInfo(Solution<V,T> solution,
                    Map<String,String> info)

Description copied from interface: SolutionListener

Called by the solution when it is asked to produce info table, see Solution.getInfo(). A listener can also add some its info into this table.

Specified by:

getInfo in interface SolutionListener<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

solution - source solution

info - produced info table

getInfo

public void getInfo(Solution<V,T> solution,
                    Map<String,String> info,
                    Collection<V> variables)

Description copied from interface: SolutionListener

Called by the solution when it is asked to produce info table, see Solution.getInfo(). A listener can also add some its info into this table.

Specified by:

getInfo in interface SolutionListener<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

solution - source solution

info - produced info table

variables - only variables from this set are included

bestCleared

public void bestCleared(Solution<V,T> solution)

Description copied from interface: SolutionListener

Called by the solution when method Solution.clearBest() is called.

Specified by:

bestCleared in interface SolutionListener<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

solution - source solution

bestRestored

public void bestRestored(Solution<V,T> solution)

Description copied from interface: SolutionListener

Called by the solution when method Solution.restoreBest() is called.

Specified by:

bestRestored in interface SolutionListener<V extends Variable<V,T>,T extends Value<V,T>>

Parameters:

solution - source solution

isMaster

public boolean isMaster(Solution<V,T> solution)

In single solution multiple threads environments return true if the given solution is of the first thread

Parameters:

solution - current solution

Returns:

if the current thread is master (can alter bound etc.)