World of Seven - Viz: SLS Engineering Suite

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.

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.

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.

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.

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. =)

Download and Try Viz