org.cpsolver.ifs.algorithms

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

java.lang.Object

org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext<V,T,MetaHeuristicSearch.MetaHeuristicSearchContext>

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

Type Parameters:

V - Variable

T - Value

All Implemented Interfaces:

CanHoldContext, HasAssignmentContext<V,T,MetaHeuristicSearch.MetaHeuristicSearchContext>, NeighbourSelection<V,T>

public class MetaHeuristicSearch<V extends Variable<V,T>,T extends Value<V,T>>
extends NeighbourSelectionWithContext<V,T,MetaHeuristicSearch.MetaHeuristicSearchContext>

Meta-heuristic search neighbor selection.

It consists of the following (up to four) phases:

• Construction phase until the construction neighbor selection is not exhausted (i.e., null is returned as the next neighbor),
• Incomplete phase (e.g., StandardNeighbourSelection) until all variables are assigned (this heuristics is also used whenever the solution becomes incomplete, until it is complete again),
• Hill-climbing phase (e.g., HillClimber) until the given number if idle iterations (this phase is optional)
• Improvement phase (e.g., GreatDeluge or SimulatedAnnealing) until timeout is reached

The search is based on the SimpleSearch, however each phase can be customized by providing the appropriate neighbor selection. Also, a different selection can be used in each thread.

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	MetaHeuristicSearch.MetaHeuristicSearchContext

Field Summary

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

MetaHeuristicSearch(DataProperties properties) Constructor MetaHeuristic.ConstructionClass ... construction heuristics (if needed) MetaHeuristic.IncompleteClass ... incomplete heuristics (e.g., StandardNeighbourSelection) MetaHeuristic.HillClimberClass ... hill-climber heuristics (e.g., HillClimber or StepCountingHillClimber) MetaHeuristic.ImprovementClass ... improvement heuristics (e.g., SimulatedAnnealing or GreatDeluge)

Method Summary

Modifier and Type	Method and Description
MetaHeuristicSearch.MetaHeuristicSearchContext	createAssignmentContext(Assignment<V,T> assignment) Create a new assignment context for the given assignment.
void	init(Solver<V,T> solver) Initialization
Neighbour<V,T>	selectNeighbour(Solution<V,T> solution) Neighbour selection.

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

Constructor Detail

MetaHeuristicSearch

public MetaHeuristicSearch(DataProperties properties)

Constructor

• MetaHeuristic.ConstructionClass ... construction heuristics (if needed)
• MetaHeuristic.IncompleteClass ... incomplete heuristics (e.g., StandardNeighbourSelection)
• MetaHeuristic.HillClimberClass ... hill-climber heuristics (e.g., HillClimber or StepCountingHillClimber)
• MetaHeuristic.ImprovementClass ... improvement heuristics (e.g., SimulatedAnnealing or GreatDeluge)

Parameters:

properties - problem configuration

Method Detail

init

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

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>,MetaHeuristicSearch.MetaHeuristicSearchContext>

Parameters:

solver - current solver

selectNeighbour

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

Neighbour selection. It consists of the following phases:

• Construction phase until the construction neighbor selection is not exhausted (i.e., null is returned as the next neighbor),
• Incomplete phase (e.g., StandardNeighbourSelection) until all variables are assigned (this heuristics is also used whenever the solution becomes incomplete, until it is complete again),
• Hill-climbing phase (e.g., HillClimber) until the given number if idle iterations (this phase is optional)
• Improvement phase (e.g., GreatDeluge or SimulatedAnnealing) until timeout is reached

Parameters:

solution - given solution

Returns:

a neighbour assignment

createAssignmentContext

public MetaHeuristicSearch.MetaHeuristicSearchContext createAssignmentContext(Assignment<V,T> assignment)

Description copied from interface: HasAssignmentContext

Create a new assignment context for the given assignment. If there are already some variables assigned in the value, the method should make sure that the context is appropriately initialized.

Parameters:

assignment - an assignment for which there needs to be an assignment context

Returns:

a new instance of the assignment context, filled according to the given assignment