Package org.tweetyproject.math.opt.solver

Class StochasticLocalSearch

java.lang.Object

org.tweetyproject.math.opt.solver.Solver

org.tweetyproject.math.opt.solver.CombinatoricsSolver

org.tweetyproject.math.opt.solver.StochasticLocalSearch

public class StochasticLocalSearch
extends CombinatoricsSolver

local search

Author:

Sebastian Franke

Constructor Summary

Constructors

Constructor	Description
StochasticLocalSearch(int maxIteration, int maxStepsWithNoImprove, double chanceForRandomStep)	Constructor

Method Summary

Modifier and Type	Method	Description
ArrayList<ElementOfCombinatoricsProb>	findbestNeighbor(ArrayList<ArrayList<ElementOfCombinatoricsProb>> neighbors)	Finds and returns the best neighbor solution from a given list of neighbors.
ArrayList<ElementOfCombinatoricsProb>	findrandomNeighbor(ArrayList<ArrayList<ElementOfCombinatoricsProb>> neighbors)	Finds and returns a random neighbor solution from a given list of neighbors.
ArrayList<ElementOfCombinatoricsProb>	solve(CombinatoricsProblem prob)	Solves the given combinatorics problem using an iterative neighborhood search algorithm.

Methods inherited from class org.tweetyproject.math.opt.solver.CombinatoricsSolver

solve

Methods inherited from class org.tweetyproject.math.opt.solver.Solver

getDefaultGeneralSolver, getDefaultIntegerLinearSolver, getDefaultLinearSolver, hasDefaultGeneralSolver, hasDefaultIntegerLinearSolver, hasDefaultLinearSolver, isInstalled, setDefaultGeneralSolver, setDefaultIntegerLinearSolver, setDefaultLinearSolver

Methods inherited from class java.lang.Object

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

Constructor Details

StochasticLocalSearch

public StochasticLocalSearch(int maxIteration,
 int maxStepsWithNoImprove,
 double chanceForRandomStep)

Constructor

Parameters:

maxIteration - maxIteration

maxStepsWithNoImprove - maxStepsWithNoImprove

chanceForRandomStep - chanceForRandomStep

Method Details

findbestNeighbor

public ArrayList<ElementOfCombinatoricsProb> findbestNeighbor(ArrayList<ArrayList<ElementOfCombinatoricsProb>> neighbors)

Finds and returns the best neighbor solution from a given list of neighbors.

This method iterates through the provided list of neighbor solutions and evaluates each one using the associated combinatorics problem's evaluation function. The neighbor with the highest evaluation score is considered the best and is returned as the result.

Parameters:

neighbors - A list of neighbor solutions, where each neighbor is represented as an ArrayList<ElementOfCombinatoricsProb>.

Returns:

The neighbor solution with the highest evaluation score.

findrandomNeighbor

public ArrayList<ElementOfCombinatoricsProb> findrandomNeighbor(ArrayList<ArrayList<ElementOfCombinatoricsProb>> neighbors)

Finds and returns a random neighbor solution from a given list of neighbors.

This method selects a neighbor solution at random from the provided list of neighbors and returns it as the result. The random selection is done using a uniformly distributed random number generator.

Parameters:

neighbors - A list of neighbor solutions, where each neighbor is represented as an ArrayList<ElementOfCombinatoricsProb>.

Returns:

A randomly selected neighbor solution from the list.

solve

public ArrayList<ElementOfCombinatoricsProb> solve(CombinatoricsProblem prob)

Solves the given combinatorics problem using an iterative neighborhood search algorithm.

This method starts with an initial random solution and iteratively explores the neighborhood of the current solution to find better solutions. The search continues until either a maximum number of iterations is reached or no improvements are found within a specified number of steps. The search strategy includes both deterministic (best neighbor) and stochastic (random neighbor) steps, controlled by a probability parameter.

Parameters:

prob - The CombinatoricsProblem to be solved, which defines the problem space, evaluation function, and neighborhood generation.

Returns:

An ArrayList<ElementOfCombinatoricsProb> representing the best solution found during the search process.