Package org.tweetyproject.math.opt.solver

Class IteratedLocalSearch

java.lang.Object

org.tweetyproject.math.opt.solver.Solver

org.tweetyproject.math.opt.solver.CombinatoricsSolver

org.tweetyproject.math.opt.solver.IteratedLocalSearch

public class IteratedLocalSearch
extends CombinatoricsSolver

implements the Iterates local search algorithm for combinatorial problems

Author:

Sebastian Franke

Constructor Summary

Constructors

Constructor	Description
IteratedLocalSearch(double perturbationStrength, int maxnumberOfRestarts, int maxIterations)	Constructs an IteratedLocalSearch instance with the specified parameters.

Method Summary

Modifier and Type	Method	Description
ArrayList<ElementOfCombinatoricsProb>	bestNeighbor(ArrayList<ElementOfCombinatoricsProb> currSol)	performs one step of a local search
ArrayList<ElementOfCombinatoricsProb>	pertubate(ArrayList<ElementOfCombinatoricsProb> currSol)	changes the solution drastically to escape a local minimum
ArrayList<ElementOfCombinatoricsProb>	solve(CombinatoricsProblem prob)	Solves the given combinatorics problem using the Iterated Local Search (ILS) 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

IteratedLocalSearch

public IteratedLocalSearch(double perturbationStrength,
 int maxnumberOfRestarts,
 int maxIterations)

Constructs an IteratedLocalSearch instance with the specified parameters.

Parameters:

perturbationStrength - The strength of the perturbation applied during the search process. This value controls the extent to which the current solution is altered to escape local optima.

maxnumberOfRestarts - The maximum number of restarts allowed during the search process. This value controls how many times the algorithm can restart from a new initial solution.

maxIterations - The maximum number of iterations allowed within the search process. This value limits the number of iterations the local search algorithm can perform in each phase.

Method Details

bestNeighbor

public ArrayList<ElementOfCombinatoricsProb> bestNeighbor(ArrayList<ElementOfCombinatoricsProb> currSol)

performs one step of a local search

Parameters:

currSol - the current state of which we check the neighborhood

Returns:

the best neighbor / the current state

pertubate

public ArrayList<ElementOfCombinatoricsProb> pertubate(ArrayList<ElementOfCombinatoricsProb> currSol)

changes the solution drastically to escape a local minimum

Parameters:

currSol - the solution to be pertubated

Returns:

the new currSol

solve

public ArrayList<ElementOfCombinatoricsProb> solve(CombinatoricsProblem prob)

Solves the given combinatorics problem using the Iterated Local Search (ILS) algorithm. The method iteratively applies local search to find the best solution, perturbs the solution to escape local optima, and restarts the search process when necessary.

Parameters:

prob - The combinatorics problem to be solved. This problem defines the search space and the evaluation function used to assess the quality of solutions.

Returns:

An ArrayList of ElementOfCombinatoricsProb representing the best solution found by the algorithm.