NUS HomeDownload
Home | Up


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 11048 times since 14-Sep-06 18:41:16 SGT. This is the 2nd time it has been accessed today.

A total of 5323 different hosts have accessed this document in the last 6406 days; your host, ec2-54-205-238-173.compute-1.amazonaws.com, has accessed it 1 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.