Class ACS

java.lang.Object
  ACS

public class ACS
extends java.lang.Object

ACS is the main class that keeps track of all agents and manipulates pheromone as necessary. The important functions of ACS include:

• Intialization of problem from a file or randomly
• Creation and control of Agents
• Creation and modification of PherMatrix
• Ability to run through iterations of the ACS algorithm
• Keeping track of the best route found so far

ACS variables are public such that they can be accessed and analyzed by other drivers.

Field Summary

java.util.ArrayList	ants
Route	bestSoFar
(package private) double	CONSTANTQ
ACSDisplay	display
int[][]	distances
boolean	dynamic
int	iterationChanged
int	lastRouteLength
double[]	lengthIterationStorage
Node[]	nodes
PherMatrix	phers
int	STRECH
int	totalLengths
int[]	valids
int	validsChanged

Constructor Summary

ACS(java.lang.String filename, int n, int strech, boolean changing, ACSDisplay tempDisplay)
Creates ACS.

Method Summary

void	accountPherNode(int n) Notify the PherMatrix of a node addition.
void	ACSUpdatePhers() Calls PherMatrix to update pheromone values using the Ant Colony System (ACS) implementation.
void	actIndependent() Continues a ACO algorithm automatically until an end condition.
void	changeValids() Changes the set of valid nodes in the DTSP problem and notifies PherMatrix of changes.
int	findDistance(int x, int y) Helper method for intializing the distance matrix.
void	intializeAnts(boolean changing) Intializes ants ArrayList.
void	intializeDistances() Intializes distances matrix.
void	intializeFile(java.lang.String filename, boolean changing) Intializes TSP from file.
void	intializePher() Intializes PherMatrix for the TSP.
void	intializeRandom(int num, boolean changing) Intializes TSP randomly.
void	intializeValids(boolean changing) Intializes valids array that relates to whether a node in nodes array is currently active.
void	intializeVariables(java.lang.String filename, int n, boolean changing) Decides whether or not the TSP is coming from a file or to be generated randomly.
void	iteration(boolean changing) One step of ACO algorithm.
void	MinMaxUpdatePhers() Calls multiple PherMatrix methods to effectively update pheromone values using the Min-Max implementation.
boolean	nodesContains(int x, int y, int n) Helper method for random generation to insure that two nodes do not occupy the same location.
void	removePherNode(int n) Notify the PherMatrix of a node removal.
void	updatePhers() Updates pheromone values after agents have generated their Routes.

Methods inherited from class java.lang.Object

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

Field Detail

ants

public java.util.ArrayList ants

nodes

public Node[] nodes

distances

public int[][] distances

valids

public int[] valids

lengthIterationStorage

public double[] lengthIterationStorage

phers

public PherMatrix phers

bestSoFar

public Route bestSoFar

STRECH

public int STRECH

totalLengths

public int totalLengths

lastRouteLength

public int lastRouteLength

display

public ACSDisplay display

dynamic

public boolean dynamic

validsChanged

public int validsChanged

iterationChanged

public int iterationChanged

CONSTANTQ

double CONSTANTQ

Constructor Detail

ACS

public ACS(java.lang.String filename,
           int n,
           int strech,
           boolean changing,
           ACSDisplay tempDisplay)

Creates ACS.

Parameters:

filename - The name of the file containing TSP data. If the problem is to be generated randomly, the filename "random" will be passed

n - The size of a random problem.

strech - The scale of the problem. For drawing purposes involving ACSDisplay

changing - Indicates if the problem is dynamic

tempDisplay - Pointer to an ACSDisplay if it is being used. null if not used

Method Detail

actIndependent

public void actIndependent()

Continues a ACO algorithm automatically until an end condition. End condition is currently after 5000 iterations. Automates going through iteration steps. One step is defined as having all the agents create their routes and then updating pheromone values. Changes starting node of ants if the problem is dynamic and if the ant is starting on an invalid node. Updates bestSoFar as necessary.

See Also:

iteration(boolean changing)

iteration

public void iteration(boolean changing)

One step of ACO algorithm. One step is defined as having all the agents create their routes and then updating pheromone values. Changes starting node of ants if the problem is dynamic and if the ant is starting on an invalid node. Updates bestSoFar as necessary.

See Also:

Agent, PherMatrix

updatePhers

public void updatePhers()

Updates pheromone values after agents have generated their Routes. Calls different update methods depending on type of ACO implementation.

See Also:

ACSUpdatePhers(), MinMaxUpdatePhers()

ACSUpdatePhers

public void ACSUpdatePhers()

Calls PherMatrix to update pheromone values using the Ant Colony System (ACS) implementation. ACS adds pheomone to the best route so far while evaporating pheromone from all nodes.

See Also:

PherMatrix

MinMaxUpdatePhers

public void MinMaxUpdatePhers()

Calls multiple PherMatrix methods to effectively update pheromone values using the Min-Max implementation. Min-Max adds pheomone to the best route so far while evaporating pheromone from all nodes. In Min-Max, there is a lower bound and upper bound limit on pheromone values.

See Also:

PherMatrix

changeValids

public void changeValids()

Changes the set of valid nodes in the DTSP problem and notifies PherMatrix of changes. Done by making changes to the problem while storing appropriate reset values for nodes in PherMatrix. After node addition/removal is done, PherMatrix is notified to reset pheromone values according to found reset values. For dynamic problems only.

See Also:

removePherNode(int n), accountPherNode(int n), PherMatrix

removePherNode

public void removePherNode(int n)

Notify the PherMatrix of a node removal. For dynamic problems only.

Parameters:

n - Node number being removed

See Also:

PherMatrix

accountPherNode

public void accountPherNode(int n)

Notify the PherMatrix of a node addition. For dynamic problems only.

Parameters:

n - Node number being added

See Also:

PherMatrix

intializeVariables

public void intializeVariables(java.lang.String filename,
                               int n,
                               boolean changing)

Decides whether or not the TSP is coming from a file or to be generated randomly. Calls the apporpriate variable intialization methods.

Parameters:

filename - The name of the file containing TSP data. If the problem is to be generated randomly, the filename "random" will be passed

n - The size of a random problem.

changing - Indicates if the problem is dynamic

See Also:

intializeRandom(int num, boolean changing), intializeFile(String filename, boolean changing)

intializeFile

public void intializeFile(java.lang.String filename,
                          boolean changing)

Intializes TSP from file.

Parameters:

filename - The name of the file containing TSP data

changing - Indicates if the problem is dynamic

See Also:

intializeValids(boolean changing), intializeDistances(), intializePher(), intializeAnts(boolean changing)

intializeRandom

public void intializeRandom(int num,
                            boolean changing)

Intializes TSP randomly.

Parameters:

num - The number of nodes to be included in the TSP problem

changing - Indicates if the problem is dynamic

See Also:

nodesContains(int x, int y, int n), intializeValids(boolean changing), intializeDistances(), intializePher(), intializeAnts(boolean changing)

intializeValids

public void intializeValids(boolean changing)

Intializes valids array that relates to whether a node in nodes array is currently active. A value >0 indicates a node currently in use, <=0 is not used. valids is only created if changing is true.

Parameters:

changing - Indicates if the problem is dynamic

intializeDistances

public void intializeDistances()

Intializes distances matrix. distances[i][j] is equal to the distance between node i and node j. Since all TSP dealt with in this study are symmetric, distances[i][j] = distances[j][i]. For historical reasons, all TSP distance data is measured using rounded integers.

See Also:

findDistance(int x, int y)

intializePher

public void intializePher()

Intializes PherMatrix for the TSP.

See Also:

PherMatrix

intializeAnts

public void intializeAnts(boolean changing)

Intializes ants ArrayList. If problem is dynamic, the amound of agents is cut in half.

Parameters:

changing - Indicates if the problem is dynamic

nodesContains

public boolean nodesContains(int x,
                             int y,
                             int n)

Helper method for random generation to insure that two nodes do not occupy the same location.

Parameters:

x - X coordinate of point to be added

y - Y coordinate of point to be added

n - The number of nodes added to the problem so far

Returns:

if the current (x,y) point is already occupied

findDistance

public int findDistance(int x,
                        int y)

Helper method for intializing the distance matrix. For historical reasons, all TSP distance data is measured using rounded integers.

Parameters:

x - 1st node number

y - 2nd node number

Returns:

distance between 1st and 2nd node