Download and Try Viz
To start using Viz for designing,
tuning, and analyzing your SLS algorithm is easy.
Please follow the steps below:
1. Pre-requisites
2. Installation Steps and Running Viz EW and Viz SIMRA for the first time
3.
Using Viz for your OWN SLS algorithm on your OWN COP
4. Release Notes
1. Pre-requisites
Your computer must run
Windows XP,
Windows Vista, or Windows 7! This is
because
Viz is developed for Windows-based PC, especially Windows XP or Vista. If you are running other operating system, please borrow/use other PC
which has Windows XP or Vista.
We use .NET Framework version 2.0 to
develop the GUI components of Viz.
Thus, you must ensure that
Microsoft .NET Framework version 2.0 or above (~22mb) is
installed.
In Windows XP:
If you update your Windows XP (Service Pack 2) frequently via
Windows Update, it is quite likely that you already have .NET Framework
2.0 installed in your PC. If not, download (click the link above) and install
the framework. You will need administrator privileges to be able to
install the framework.
In Windows Vista/7:
Windows Vista/7 have .NET Framework version 2.0
and 3.0
pre-installed by default.
Known issues with all Windows
platform:
Viz do some String processing which may be incompatible under non
English localization setting (e.g. French, German, etc). If
this happens, temporarily switch your Windows localization setting to
English when using Viz (Control Panel, Regional and Language Options, set the settings
to English language). Remember that Viz is part of a research project
and thus we do not
have time to provide support for localization as commonly done with
commercial software. We also do not have plan to develop Viz for another OS platform(s)
as it is not the focus of the main author's PhD thesis.
Known issues with Windows
Vista:
Sometimes a strange visualization error (e.g. Viz SIMRA loads
successfully but the visualization does not appear) occurs on some Vista
machines. We have not found the cure yet. Quick fix: please switch to
Windows XP machine temporarily if that happens with your machine.
2. Installation Steps and Running Viz EW and Viz SIMRA for the first time
First, download this zip file:
Viz version 3 (final one in PhD thesis) - stable
-
(v3.2008.11.13) (~8mb).
This zip file is uploaded on 30 May 2011, 1
year after Steven's PhD defense.
Notes: Viz is free
for academic or research usage.
For commercial usage, please
contact us first via stevenhalim at gmail dot com.
The only "payment" that we ask is that you
give us some feedbacks. Feel free to drop us any comments/critics/ideas/or even successful reports on the usage of Viz in analyzing your
OWN SLS behavior.
Then, extract this zip file into any folder that you like.
It contains: -. The executable VizEW.exe and VizSIMRA.exe :) -. 3rd party
open source/free programs/dlls:
csgl,
opengl/glut,
NEATO (GraphViz),
7-zip.
*.
You do not need to individually install them as we have packed all into
this zip file. -.
All the (old) documentation files and our papers (in pdf). The newest documents are
here. -. QAP_TS (Ro-TS) and TSP_ILS
executable, QAPLIB/TSPLIB instances, and some configuration files. -. Several sample demo Visual Data Files
(VDFs). The video version is
available in our result page.
Screen shot (on Viz version 2) |
What to do |
|
1). Click "Add" COP, point to the installation folder -> subfolder "COP/QAPLIB", select "tai35b.datx"
2). Click "Add" SLS, installation folder -> subfolder "SLS/QAP", select "QAP_TS.exe" and
"Ro-TS-B.fac"
Then, you will see something like
the one shown in the next screen: |
|
3). Next, click "Run & Examine"
You will see something like this: |
|
After a while (at most one minute
if you do not change anything),
you will see: |
|
4). Select one Visual Data File (VDF)
5). Click "Launch SIMRA",
then the following screen will appear: |
|
6). Click "Play" button to playback the search.
7). Click "Pause" or "Stop" to pause/stop the playback.
8). Congratulations. You have run Viz for the first time.
Please
feel free to test Viz EW and Viz SIMRA. Let the program itself guides you.
Just point your mouse cursor over a certain feature (button, checkbox,
combo box, etc), then you will see a tool tip appears.
In Viz SIMRA, you
can also look at the status bar at the top right corner of the Viz
SIMRA's window for the details of past action (locate the message "look
here after performing an action for context-sensitive explanation").
|
3.
Using Viz for your OWN SLS algorithm on your OWN COP
Using Viz EW and Viz SIMRA to analyze your OWN SLS
algorithm on your OWN COP is relatively easy.
You will need to follow our rules but our rules are not
difficult.
In summary, the rules are as follows:
1. SLS(command line
parameters) {
// format: "InstanceFileName" "ConfigurationFileName"
RunID
A .
set the SLS to read in COP instance data based on file
InstanceFileName;
B .
configure SLS based on file ConfigurationFileName;
2.
start from any solution of the COP instance;
C .
create RunLog file with name: CurrentDir\InstanceFileName_ConfigurationFileName_RunID.RunLog;
D . record header information for RunLog (Row 1-9,
see below);
3. while (not finished) {
4. locally modify (search around) the current
solution with some heuristic/stochastic rule;
5.
if (the newly found solution is better than the best solution so
far)
6.
update the best solution status;
E .
record solution and
algorithm specific information (Row 10-17, see below) into RunLog;
7.
}
F .
close the RunLog;
8. return the best found solution that it manages to find throughout
the search process;
9. } |
First, adjust your SLS algorithm to
read in three command line
parameters (line A and B). Note that we need to use
double quotes "" to group long file name with spaces into one parameter!
Otherwise your program may tokenize the parameters incorrectly.
The command line parameters format is as
follows:
1. "InstanceFileName" that specify the COP instance that your SLS
will attack.
You will just need one simple
modification here.
Please add one line of Best Known (BK) objective value of that
particular instance as the first line of the instance file.
Simply write 0 if BK is
still unknown, then Viz will use best found value instead.
However, please update the value as soon as you find better BK
objective value for more accurate analysis.
Viz EW uses this information to compute important performance
statistics... Thus more accurate BK is preferred.
Of course, your SLS program must now skip this first additional line
when you parse the modified instance file.
For example: compare the original lin105.tsp
(TSPLIB) versus lin105.tspx
(modified). Only one line of BK objective value is added!
2. "ConfigurationFileName"
that specify how to externally configure your SLS algorithm.
SLS algorithm usually have three group of
things that can be configured:
*. the parameter values
*. decision variables to switch between using certain SLS components
*. decision variables to switch between executing certain search
strategies
To allow Viz EW to execute your SLS implementation with various
configurations, you must allow it to read external configuration file
like this. This configuration file is a simple text file with 3 columns
separated by tab ('\t') character (value, field, comment).
Only your SLS algorithm understands the configuration file designed by
you. You SLS algorithm will read the configuration file one by one and
configure itself.
For example, look at this ILS-T.cfg.
There are 5 lines.
The comments on each line should clearly explain which part of the SLS
algorithm that the line is meant to configure. Your SLS algorithm will
read these 5 lines and set its behavior according to what is written in
the configuration file... That is, it will stop after 5000 iterations,
etc... (please look at ILS-T.cfg to get the context).
However, Viz EW will actually read in
ILS-T.fac file, and not
ILS-T.cfg. This
ILS-T.fac file is used to
perform full factorial design with ease. Full factorial design is an
experiment design where we try all possible combination of
configurations. ILS-T.fac file
is basically the same ILS-T.cfg
but now you can have several values for a field. In this case:
BETTER_ACCEPTANCE_CRITERIA can be either (0|1), and
NON_IMPROVING_MOVES_TOLERANCE can be either (2|200)*n. This produces
2^2=4 different configurations and each will perform differently. If you
only want one configuration, set the domain of all fields to be 1 value
only.
Btw, for quick start, you can simply create empty *.fac file (that is,
your SLS will use its default configuration). Viz EW will not complain.
Notes: All the 3 columns
must be present! Do not omit the third column (comment). Viz EW assumes
the *.fac file contains 3 columns during parsing.
3. RunID, a number which will be used to indicate replications in
Viz EW. By default, it starts with "1".
Next, modify your SLS
implementation to
log
some simple information from the SLS run into a log file called RunLog
(example
~1Mb). This RunLog is a simple log file
that records some header information
(line D
above, row 1-9 below) and important search information
(line E
above, row 10-17 below) from
start (iteration=1) to end (iteration=last). The RunLog
file must be precisely named as
"InstanceFileName_ConfigurationFileName_RunID.RunLog"
and stored in the current working directory (the same directory where
all your COP instances, SLS executables, configuration files reside)
so that Viz EW can interpret it correctly. If existing RunLog file
exists (you have run your program before), simple overwrite it with the
information from the most recent SLS run.
Notes: Please store all
your files inside the current working directory. If your SLS executable
requires external DLL files, copy those files into the working directory
too. The current version of Viz EW will only process the files inside
this working directory.
The RunLog 2006b file format is described
in the table below:
Row |
Example |
Field Name |
Type |
Remarks |
1 |
2006b |
FormatVersion |
String |
Current Viz EW will only use
this version |
2 |
TSP |
ProblemName
|
String
|
Abbreviated
version only (TSP|QAP|etc) |
3 |
1 |
IsMinimizing
|
Boolean |
0: False, 1:
True |
4 |
eil51 |
InstanceName
|
String |
Full path is
not required. |
5 |
51 |
InstanceSize |
Integer |
Usually the
size is also indicated in file name, but this one is
preferred. |
6 |
ILS |
SolverName |
String |
The
abbreviated solver name: (TS|ILS|SA).
Algorithm specific visualization is disabled if your solver
is not one of these. |
7 |
Anything |
RunDescription |
String |
You can write
one line to describe your solver... |
8 |
1000 |
NumberOfEntries |
Integer |
The row 10-17
below are repeated this many times |
9 |
|
Dummy1 |
EmptyLine |
Reserved for future version of
Viz |
10 |
0,1,2,...,50, |
Solution |
Integer List |
Comma separated, including the
last item. Note that index start from 0! |
11 |
1 |
IsFeasible |
Boolean |
0: Infeasible,
1: Feasible |
12 |
426.000000 |
ObjectiveValue |
Double |
- |
13 |
0.435000 |
TimeStamp |
Double |
Use timer
inside SLS, default: 0.0 |
14 |
''Tag'' |
Tag |
String |
Leave blank if
not needed |
15 |
4 |
AlgorithmSpecific1 |
Double |
For TS:
TabuTenure, ILS: PerturbStr, SA: Temp |
16 |
1 |
AlgorithmSpecific2 |
Double |
For TS: -, ILS:
Accept-1/Reject-0, SA: TossValue |
17 |
|
AlgorithmSpecific3 |
EmptyLine |
Reserved for future version of
Viz |
Note that when you write row 10-17
iteratively, please write in flushing mode rather than buffering mode,
so that when the program is killed by Viz EW due to time/iteration limit
exceeded, the RunLog for the past iterations before the program is
killed is already written.
Some notes on when
you should record the information (row 10-17) for various
SLS algorithm:
For Tabu Search (TS) and Simulated Annealing
(SA), record row 10-17 at the end of each iteration
so that we can see the step by step progress taken by TS/SA.
If we only record the local optima, we cannot see TS/SA
detailed trajectory.
For Iterated Local Search (ILS), record row 10-17
before and after the acceptance criteria step, so that we can see
the effect of the local search phase and whether that (new)
local optima is accepted or rejected. Otherwise you will
only see limited movement when many local optima after local
search phase are rejected (you will be returned back to the
old local optima - that is, no movement).
For population based search
(e.g. GA, ACO, PSO), you are working with population over
generations. In order to make Viz display the most
meaningful information for your population based search,
please record the RunLog using this technique:
-. write the
generation
best solution (or the best
ant within colony of ants) according to row 10-17.
-. repeat the process to the other member of the
population in the current generation.
-. example: if you have 100 generations, and each generation
has 20 members, then you will write 2.000 entries of row
10-17 into the RunLog and record the total number of entries
in RunLog (row 8) to be 100*20 = 2.000 instead of 100!
-. then, in Viz SIMRA, set the playback trail to be 20 (show
me the 20 members of the population) and then advance the
playback per 20 iterations. This will give you the
visualization of the movement of best solution from
generation to generation as well as the information of
diversity of the other 19 members...
For other SLS, try to
record row 10-17 in a place within your SLS.exe code so that
the amount of information that you record is maximized. |
Viz EW uses the information from these RunLog
files
(of the same instance/fitness landscape) to build the FLST
visualization. Viz SIMRA will then be used to display the visualization.
With Viz, user does not need to compute complex computations (e.g. distance information,
objective value average, fitness distance correlation ratio, etc) as Viz will do all the computation using the
information provided in the RunLog files.
Finally, we reckon that it is still best
to explain these modification changes via examples. In the table below,
we provide a set of our Iterated Local
Search (ILS) implementation (in C++), based from
(Stuetzle
and Hoos, 1999) paper for attacking Traveling Salesman Problem
(TSP). The codes have comments
to help you identify which parts of your SLS codes that needs to be
augmented. The modified TSPx instance file and the example configuration
file are also given.
Explanation |
Example
File |
Common code to record
RunLogs and configure SLS |
Common.h |
Code to process problem
specific information |
TSP.h |
Code for the SLS
implementation |
TSP_ILS.cpp |
Our compiled
code |
TSP_ILS.exe |
COP instance
with first line = BK objective value |
lin105.tspx |
Configuration file for TSP_ILS |
ILS-T.cfg |
The configuration file that is
actually used in Viz EW |
ILS-T.fac |
Compile this program and then run the
program with the following command:
TSP_ILS "lin105.tspx" "ILS-T.cfg"
1
You can modify ILS-T.cfg to adjust the behavior of
TSP_ILS.exe.
You can choose lin105.tspx for Viz EW problem design,
TSP_ILS.exe+ILS-T.fac for Viz EW algorithm design, set
replication: 1, and hit "Run and Examine" button in Viz EW.
Notes: We have tried to
make this document self-explanatory and as user friendly as possible. However, if you are still unable
to make Viz works for your OWN SLS/COP after following through this
documentation, please e-mail the main author at stevenhalim at gmail dot com
for personalized assistance.
Another notes: Currently
Viz supports visualization these SLS algorithms (TS-tabu tenure over
time|ILS-perturbation strength and acceptance rejection rate|SA-temperature
and probability value over time) and these COPs (TSP: the tour over
time|QAP: the visualization of flow and data matrices). Your SLS X and
COP Y may not be supported by default by Viz. In that case, the algorithm and/or problem specific visualization in Viz
will be disabled. That is okay, since Viz has several generic visualizations: FLST, OV, FDC, and EB, plus several
built-in
statistical tests embedded in the Text-Based Information Center. You
can still use these generic features, especially our main
visualization: the FLST visualization, to analyze your SLS even though the
algorithm-specific and problem-specific visualizations are not
available in the current version of Viz.
We will support more SLS and more COP in the future :). You can tell us which SLS and COP that you would like Viz to support
and provide some ideas on how to implement them, if any.
4. Release Notes
This version (3.2008.11.13) is the
stable version of Viz v3. For the details of what are the major features of Viz v3,
please click here. Viz was a completed research
project and will no longer be updated.
We will be very happy if you encounter success while
analyzing SLS using Viz. If that happens, do not forget to share your
experience in using Viz to us. Please drop us your
valuable feedback about Viz.
Happy designing, analyzing, and tuning your Stochastic Local Search
algorithms. =)
|
This document, download.html, has been accessed 241 times since 25-Jun-24 11:57:13 +08.
This is the 1st time it has been accessed today.
A total of 86 different hosts have accessed this document in the
last 138 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 13 times.
If you're interested, complete statistics for
this document are also available, including breakdowns by top-level
domain, host name, and date.
|
|