Package org.tweetyproject.math.examples

Class TravelingSalesman

java.lang.Object

java.util.AbstractCollection<OptProbElement>

java.util.AbstractSet<OptProbElement>

java.util.HashSet<OptProbElement>

org.tweetyproject.math.opt.problem.GeneralConstraintSatisfactionProblem

org.tweetyproject.math.opt.problem.CombinatoricsProblem

org.tweetyproject.math.examples.TravelingSalesman

All Implemented Interfaces:

Serializable, Cloneable, Iterable<OptProbElement>, Collection<OptProbElement>, Set<OptProbElement>

public class TravelingSalesman
extends CombinatoricsProblem

implements the traveling salesman problem. Every element has an x- coordinate and a y- coordinate. Every city can be connected to each other and the distance is the cartesian distance bewteen them. Therefore the graph is fully connected.

Author:

Sebastian Franke

See Also:

• Serialized Form

Field Summary

Fields inherited from class org.tweetyproject.math.opt.problem.CombinatoricsProblem

elements, MAXIMIZE, MINIMIZE

Constructor Summary

Constructors

Constructor	Description
TravelingSalesman(ArrayList<ElementOfCombinatoricsProb> elements)	constructor

Method Summary

Modifier and Type	Method	Description
ArrayList<ElementOfCombinatoricsProb>	createRandomNewSolution(ArrayList<ElementOfCombinatoricsProb> currSol)	create a solution that changes the solution currSol a little bit (i.e.: for TSP: swap 2 cities; for KnapSack: add a random element) for currSol == null: create a random solution
double	evaluate(ArrayList<ElementOfCombinatoricsProb> sol)	evaluates the solution
Double	getHeuristicValue(ElementOfCombinatoricsProb solutionComponent, Integer getCurrentIndex, ElementOfCombinatoricsProb initialReference, ElementOfCombinatoricsProb[] sol)	for Ant optimization: give a chance between 0 and 1 for accepting solutionComponent to the solution sol
double[][]	getRepresentation()	for Ant optimization: represent the problem as an adjacence matrix
boolean	isValid(ArrayList<ElementOfCombinatoricsProb> solution)	checks if a given solution is valid under all constraints
double	sumOfWeights(ArrayList<ElementOfCombinatoricsProb> sol)	Return if the solution sol is valid under the constraints of the problem

Methods inherited from class org.tweetyproject.math.opt.problem.CombinatoricsProblem

createDifference, formNeighborhood, getGraphrepresentation

Methods inherited from class java.util.HashSet

add, clear, clone, contains, isEmpty, iterator, newHashSet, remove, size, spliterator, toArray, toArray

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, retainAll, toString

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.Set

addAll, containsAll, equals, hashCode, removeAll, retainAll

Constructor Details

TravelingSalesman

public TravelingSalesman(ArrayList<ElementOfCombinatoricsProb> elements)

constructor

Parameters:

elements - elements in TSP

Method Details

createRandomNewSolution

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

Description copied from class: CombinatoricsProblem

create a solution that changes the solution currSol a little bit (i.e.: for TSP: swap 2 cities; for KnapSack: add a random element) for currSol == null: create a random solution

Specified by:

createRandomNewSolution in class CombinatoricsProblem

Parameters:

currSol - the current solution

Returns:

the solution

isValid

public boolean isValid(ArrayList<ElementOfCombinatoricsProb> solution)

Description copied from class: CombinatoricsProblem

checks if a given solution is valid under all constraints

Specified by:

isValid in class CombinatoricsProblem

Parameters:

solution - some solution

Returns:

true iff the solution is valid

evaluate

public double evaluate(ArrayList<ElementOfCombinatoricsProb> sol)

Description copied from class: CombinatoricsProblem

evaluates the solution

Specified by:

evaluate in class CombinatoricsProblem

Parameters:

sol - some solution

Returns:

the target function for sol

sumOfWeights

public double sumOfWeights(ArrayList<ElementOfCombinatoricsProb> sol)

Description copied from class: CombinatoricsProblem

Return if the solution sol is valid under the constraints of the problem

Specified by:

sumOfWeights in class CombinatoricsProblem

Parameters:

sol - is the solution to be viewd

Returns:

if the solution sol is valid under the constraints of the problem

getHeuristicValue

public Double getHeuristicValue(ElementOfCombinatoricsProb solutionComponent,
 Integer getCurrentIndex,
 ElementOfCombinatoricsProb initialReference,
 ElementOfCombinatoricsProb[] sol)

Description copied from class: CombinatoricsProblem

for Ant optimization: give a chance between 0 and 1 for accepting solutionComponent to the solution sol

Specified by:

getHeuristicValue in class CombinatoricsProblem

Parameters:

solutionComponent - : Element to be checked *

getCurrentIndex - : the length of the solution

initialReference - : default starting point for the solution (the first Element in the solution)

sol - : array representation of a solution (needed for Ant optimization)

Returns:

the heuristic value

getRepresentation

public double[][] getRepresentation()

Description copied from class: CombinatoricsProblem

for Ant optimization: represent the problem as an adjacence matrix

Specified by:

getRepresentation in class CombinatoricsProblem

Returns:

representation