TSP Applet using ACO algorithms, Ryan Ward (Java 1.4)

Press Start to begin and Stop to end. This applet shows the dynamic Traveling Salesman Problem. The objective is to find the shortest tour visiting all the nodes. Since the set of nodes is changing over time, it is necessary to reset pheromone information after a change such that good information is kept while harmful information is reset. The Distance-Based Method performs well when changes to the problem are small and frequent, while the Reset Method performs well when the changes are large and infrequent. For dynamic problems, a color of blue indicates the node(s) is being added, and a color of red means the node(s) is being removed. Initially 50 nodes are randomly distributed.

INSTRUCTIONS:

• Create New Nodes: Creates a new problem with the given parameters and set number of nodes (number of nodes is to the left of this button). For dynamic problems, the number of nodes is cut in half to create a pool of valid and invalid nodes. To change the problem type, number of nodes, severity, and frequency, it is necessary to create a new problem, as changing these fields does not directly effect the current problems.

• Start: Start iterations of the algorithm.

• Stop: Stop iterations of the algorithm.

• Step: Perform one iteration of the algorithm.

• Change Method Type: Changes the pheromone modification during a change between the Reset Method or Distance-Based Method. The Reset Method resets all pheromone information after a change in the problem, while the Distance-Based method resets pheromone based on a node's proximity to a change. It is possible to change between these two methods during a problem.

• Change Problem Type: Changes between static and dynamic problems.

• Severity: The number of nodes added and removed at a change.

• Frequency: The number of iterations between changes.

  Note that you need to press "Create New Nodes" when you've changed any of the above parameters in order for the changes to take effect.

SAMPLE PROBLEMS:

75 nodes
Static

100 nodes
Dynamic
Severity 3
Frequency 10

100 nodes
Dynamic
Severity 10
Frequency 25

Ryan Ward