Package edu.cnu.mdi.sim.simanneal.tspdemo

Class TspAnnealingProblem

java.lang.Object

edu.cnu.mdi.sim.simanneal.tspdemo.TspAnnealingProblem

All Implemented Interfaces:

AnnealingProblem<TspSolution>

public final class TspAnnealingProblem
extends Object
implements AnnealingProblem<TspSolution>

AnnealingProblem adapter that connects the TSP model to the MDI simulated annealing framework.

This class is responsible for three things the framework requires:

1. Solution generation — randomSolution(java.util.Random) produces a uniformly random permutation of all city indices using a Fisher-Yates shuffle. This is used both for the initial working solution and, during initialization, by the TemperatureHeuristic to sample the energy distribution for T₀ estimation.
2. Energy evaluation — energy(edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution) delegates to TspSolution.getTourLength(), which sums edge distances including any river penalty or bonus.
3. Move generation — randomMove(java.util.Random, edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution) returns a reusable TspMove instance. The move object is allocated once and cached; its random parameters are chosen freshly each step inside TspMove.prepare(TspSolution).

Move reuse

Rather than allocating a new TspMove on every call to randomMove(java.util.Random, edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution), this class caches a single instance in cachedMove. This is safe because the framework's inner loop always calls TspMove.prepare(edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution) before TspMove.deltaE(edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution) and TspMove.apply(edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution) or TspMove.undo(edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution), so the move is always in a freshly prepared state when used. Eliminating per-step allocation avoids generating millions of short-lived objects and the GC pressure that entails.

Thread safety

This class is not thread-safe. It is owned exclusively by the simulation thread and must not be shared across threads.

Constructor Summary

Constructors

Constructor	Description
TspAnnealingProblem(TspModel model)	Construct the problem adapter for the given TSP model.

Method Summary

Modifier and Type	Method	Description
double	energy(TspSolution sol)	Compute the energy (cost) of a solution as its total tour length.
AnnealingMove<TspSolution>	randomMove(Random rng, TspSolution current)	Return a prepared TspMove for the next annealing step.
TspSolution	randomSolution(Random rng)	Generate a uniformly random tour by shuffling all city indices.

Methods inherited from class java.lang.Object

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

Constructor Details

TspAnnealingProblem

public TspAnnealingProblem(TspModel model)

Construct the problem adapter for the given TSP model.

Parameters:

model - the TSP model containing city coordinates and the optional river (non-null)

Method Details

randomSolution

public TspSolution randomSolution(Random rng)

Generate a uniformly random tour by shuffling all city indices.

Uses a Fisher-Yates shuffle to produce an unbiased random permutation. This method is called by the framework both to create the initial working solution and (repeatedly) during T₀ estimation by the TemperatureHeuristic.

Specified by:

randomSolution in interface AnnealingProblem<TspSolution>

Parameters:

rng - source of randomness (non-null)

Returns:

a new TspSolution with a random tour visiting all cities

energy

public double energy(TspSolution sol)

Compute the energy (cost) of a solution as its total tour length.

Delegates to TspSolution.getTourLength(), which sums TspModel.getDistance(int, int) for all consecutive city pairs including the closing edge. River penalties or bonuses are incorporated by the distance function.

Specified by:

energy in interface AnnealingProblem<TspSolution>

Parameters:

sol - the solution to evaluate (non-null, tour must be initialised)

Returns:

total tour length; lower is better

randomMove

public AnnealingMove<TspSolution> randomMove(Random rng,
 TspSolution current)

Return a prepared TspMove for the next annealing step.

Returns the cached move instance, creating it on the first call. The framework calls TspMove.prepare(TspSolution) immediately after this method returns, so the move's random segment parameters are always freshly chosen before TspMove.deltaE(edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution) or TspMove.apply(edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution) is called.

Specified by:

randomMove in interface AnnealingProblem<TspSolution>

Parameters:

rng - source of randomness passed to the move (non-null)

current - the current solution (unused here; segment selection happens inside TspMove.prepare(edu.cnu.mdi.sim.simanneal.tspdemo.TspSolution))

Returns:

the reusable TspMove instance