|
The applet can change its way of working, according to some parameters. This page
contains information about those parameters, and the way it influences the running of the
algorithm.
There are some parameters that can't be changed after the applet made its first
step (by pressing 'Step', 'Go', or 'Step Cycle').
In order to change those parameters, press 'Reset':
 | Graph's File URL - This is the file that
contains the graph information. It can be only relative URL. Since this is an
applet, and applets have several limitations, you can't specify a file on your
hard-disk.
We supplied several sample graphs - just select one from the combo box. Some of these
sample are taken from the TSPLIB. Click
HERE to see the supplied graphed and its solutions.
The format of this file should be:
<number of cities>
<name-1>,<x-1>,<y-1>
<name-2>,<x-2>,<y-2>
...
<name-n>,<x-n>,<y-n> |
| Number Of Ants - The ants are randomly
spread in the cities at initialization. |
| Number Of Loops - In each loop, all ants
complete a tour in all cities. Generally, the more loops you go through, the better result
you'll get. However, since this is a probabilistic algorithm, of course it won't always
work, and won't always give the best result which could be found. When there's no more
convergence in the solutions graph, one of the 2 possibilities happened: either the
(almost) best solution of this graph was found, or other parameters are not set the best
way, so best solution is almost impossible to find. An example of this is our test of graph364.tsp running. Beside that point, assuming all
parameters are optimally set, the number of needed loops depends on the graph's size and
the number of ants used to solve this graph. |
The next parameters can be changed during the running of the algorithm, affecting all
steps to come after the change:
| Pheromone/Distance (Beta) -
This parameter sets the relative importance of pheromone vs. distance. Bigger numbers give
bigger priority to distance over pheromone (i.e. make the ants more greedy and less
cooperative).
Our experiments showed that setting Beta=0, gives very bad performance, since the ants
become non-cooperative. This means that the algorithm is simply a greedy algorithm (greed
short edges), with a small probability of finding other solutions. However, once a shorter
tour was found, no convergence toward this solution will occur. On the other hand, setting
a very big beta, would make the algorithm almost ignore the length of the edges, and look
only for edges with high pheromone. This is also not the best solution, but it's
performing better then beta=0. The reason that the performance is better in the second
case, is that in the first case, there's no way of using the previous knowledge about
better solutions that were already found. In the second case, although there's no
information about edges' length, there's a "memory" (in the form of pheromone)
of previous good solutions, so convergence in solutions could be achieved. This leads us
to the conclusion that beta has to be somewhere in between. We saw the best performance
with beta=2 - beta=4, depends on the graph. We assume that bigger beta is better when
there're many cities with similar distances between them, so the distance information
can't be very useful. |
| Global Decay (Alpha) - After each
loop, the Global Updating Rule is applied. This
parameter sets how much of the pheromone on the edges would evaporate after each loop.
This parameter actually set how much "memory" of previous solutions we want.
Setting alpha=1 causes all pheromone on the edges to evaporate after each cycle, and only
the best ant of this cycle gets to leave pheromone on its tour (with the exception of 'Let
All Ants Deposit Global Pheromone' set - see below). Setting alpha=1 directs the
convergence into the first best solution that was found, instead of leaving an option of
touring other good solutions. However, setting alpha=0 let the search keep undirected, so
convergence is hard to achieve. We saw best performance with alpha=0.5, or setting high
alpha, together with the option 'Let All Ants Deposit Global Pheromone' set (see below). |
| Local Decay (P) - After each step, the Local Updating Rule is applied. This parameter sets
how much of the pheromone on the edges would evaporate after each step. This parameter
sets of how much one ant influenced by other ants. Bigger p leaves less pheromone after
each step, so one ant have no sense where did the other ants go in the previous steps, and
the search is less focused. Since the pheromone is the way of cooperation which this
algorithm is using, low p gives better performance. We saw good performance with p=0.2 for
most graphs. |
| Exploration vs. Exploitation (q0)
- Each step, all ants decide which way to go, according to Transition Rule. This rule is selecting either the
best path, which is the shortest path with the most pheromone (exploitation), or setting a
probability to each possible path, and selects the path according to a random number
(exploration). Bigger q0, yields more exploitation. We couldn't get a specific good q0.
Good values ranged from 0.4 to 0.9. |
| Let All Ants Deposit Global Pheromone
- At the end of each loop, the ant which found the shortest tour in this loop, gets to
deposit pheromone on the edges of its last tour. Each edge gets 1/(length of this tour)
more pheromone. If this parameter is set, all ants would deposit pheromone - each one
would deposit 1/(length of its last tour) on the edges of its tour. This helps making the
search for the best solution not getting into local minimum. If the global decay has a
high value, setting this parameter would help building more solutions, and not focusing on
a specific solution. |
| Show Number Of Ants In City -
Shows a label with the current number of ants in this city. |
| Show City Label - Shows a label with the
name of this city. |
| Show City Icon - Shows an icon for each
city in the graph. |
| Show Pheromone / Show Length
/ Show None - This sets a label for each edge, with the current pheromone /
length. Not recommended in case of big graphs. |
|
