========================================================================
PISA  (www.tik.ee.ethz.ch/pisa/)
========================================================================
Computer Engineering (TIK)
ETH Zurich	 
========================================================================
LOTZ2 - Leading Ones Trailing Zeros 

Pseudo-Boolean bi-objective problem implemented with PISALib
 
Documentation
  
file: lotz2_documentation.txt
author: Marco Laumanns, laumanns@tik.ee.ethz.ch

revision by: Stefan Bleuler, bleuler@tik.ee.ethz.ch
last change: $date$
========================================================================

The Problem
===========

LOTZ2 (Leading Ones Trailing Zeros) is a simple 2-dimensional
optimization problem that operates on binary strings. The first
objective is to maximize the number of consecutive ones at one end of
the string. The second objective is to maximize the number of
consecutive zeros at the other end. 


The Variation
=============

LOTZ2 uses a bit vector representation for the individuals. 
There is a choice between different mutation and recombination
operators (see 'The Parameters' section).


The Parameters
==============

LOTZ2 uses the following values for the common parameters.
These parameters are specified in 'PISA_cfg'.

alpha   (size of the initial population)
mu      (number of parent individuals)
lambda  (number of offspring individuals, has to be equal to mu)
dim     (number of objectives, has to be 2)


LOTZ2 takes 9 local parameters which are given in a parameter file. 
The name of this parameter file is passed to LOTZ2 as command line
argument. (See 'lotz2_param.txt' for an example.)

seed                      (seed for the random number generator)

length                    (length of the binary string)

maxgen                    (maximum number of generations)

outputfile                (name of file for output of the last
                           population in archive)

mutation_type             (choose '0' for no mutation, '1' for one-bit
                           mutation, and '2' for independet-bit mutation)

recombintaion_type        (choose '0' for no recombination, '1' for one-point
                           crossover, and '2' for uniform crossover)

mutation_probability      (probability that a given individual is mutated)

recombination_probability (probability that a given pair of
			   individuals undergoes crossover)

bit_turn_probability      (probability that a bit is flipped for each bit,
                           only used with mutation type 2)



Source Files
============

The source code for LOTZ2 is divided into six files.

Four generic files are taken from PISALib:

'variator.{h,c}' is a taken from PISALib. It contains the main
function and all functions implementing the control flow.

'variator_internal.{h,c}' is taken from PISALib. It contains functions
that are called by the functions in the 'variator' part and do the
work in the background (file access etc.). 
  
'variator_user.{h,c}' defines and implements the LOTZ2 specific
operations.

Additionally a Makefile, a PISA_cfg file with common
parameters and a lotz2_param.txt file with local parameters are
contained in the tar file.

For compiling on Windows change the according '#define' in the
'variator_user.h' file.


Usage
=====

Call LOTZ2 with the following arguments:

lotz2 paramfile filenamebase poll

paramfile: specifies the name of the file containing the local
parameters (e.g. lotz2_param.txt)

filenamebase: specifies the name (and optionally the directory) of the
communication files. The filenames of the communication files and the
configuration file are built by appending 'sta', 'var', 'sel','ini',
'arc' and 'cfg' to the filenamebase. E.g., this gives the following names
for the '../PISA_' filenamebase:

../PISA_cfg - configuration file
../PISA_ini - initial population
../PISA_sel - individuals selected for variation (parents)
../PISA_var - variated individuals (offspring)
../PISA_arc - individuals in the archive

Caution: the filenamebase must be consistent with the name of
the configuration file and the filenamebase specified for the selector
module.

poll: gives the value for the polling time in seconds (e.g. 0.5). This
      polling time must be larger than 0.01 seconds.


Output
======

LOTZ2 writes the content of the archive in the last generation to a
specified output file. One individual is written per line using the
following format:

ID #(leading ones) #(trailing zeros) chromosome


Limitations
===========

This LOTZ2 module can only handle mu == lambda. If an odd number is
chosen for mu and lambda, the last individual in the mating pool can
only undergo mutation, as it has no recombination partner. Since the
lotz problem has two objectives dim needs to be set to 2.


Stopping and Resetting
======================

The behaviour in state 7 and 11 is not determined by the interface but
by each variator module specifically. LOTZ2 behaves as follows:

state 7 (= selector terminated): set state to 4 (terminate as well).
state 11 (= selector resetted): set state to 0 (start again).

The user can change the state variable in the sta file using a text
editor, e.g., for stopping both processes or for resetting. LOTZ2
assumes that the variator is resetted before the selector, i.e., state
8 is present before state 10.