readme

Short description: A MAX-MIN Ant System (MMAS) implemented in the Hyper-Cube Framework for the appli

README file to the software package 'hc-mmas-upqp.tar'

This software package was developed in connection with the paper
"The Hyper-Cube Framework for Ant Colony Optimization"
that is available as a technical report 
TR/IRIDIA/2003-3, IRIDIA, Universite Libre de Bruxelles, Brussels, Belgium

The software package is freely availble subject to the 
GNU General Public Licence, which is included in file gpl.txt.

The software package provides a MAX-MIN Ant System implemented in the 
Hyper-Cube Framework for the application to Unconstrained Binary Quadratic 
Programming (UBQP). Executable: hc-mmas-ubqp

AIMS OF THE SOFTWARE: The aim of the software is rather of 'EDUCATIONAL' 
character. It shows how to implement a MAX-MIN Ant System in the Hyper-Cube 
Framework. Nevertheless, the results are close to state-of-the-art.


CONTENTS

The GNU General Public Licence:
gpl.txt

The main file:
hc-mmas-ubqp.cpp

The random generator:
Random.cc
Random.h

A class for keeping solutions to the problem:
Solution.cpp
Solution.h

A class for handling CPU time measurements:
Timer.cc
Timer.h

The ant class:
Unconstrained_Ant.cpp
Unconstrained_Ant.h

Additional routines that are used by the software components above:
utilstuff.cpp
utilstuff.h

Makefile

Some problem instances from the set by F.Glover and G.Kochenberger:
100-10d.blu
100-1d.blu
100-2d.blu
100-3d.blu
100-4d.blu
200-1e.blu
200-2e.blu
200-3e.blu
200-4e.blu
200-5e.blu
500-1f.blu
500-2f.blu

All the other problem instances are available from the OR-Library 
(see Internet)

COMPILATION

The software is developed in C++ under Linux, using the GNU 2.96 GCC version.
Therefore, we don't guarantee that it works under Windows.

Under Linux you just type 'make' and the executables will be produced.


USAGE

The main file 'hc-mmas-ubqp.cpp' is documented in a way such that it should be
very easy to understand the code.

The executable 'hc-mmas-ubqp' provides the following command line options:

Mandatory:
-i      : a problem instance
-t      : a maximum CPU time
or
-maxiter: a maximum number of iterations

Optional:
-nants  : the number of ants    (default: 10)
-lrate  : the learning rate     (default: 0.05)
-n      : the number of trials  (default: 1)
-ls     : usage of local search (default: yes)

So, an example for running an experiments would be:

hc-mmas-upqp -i 200-1e.blu -t 100.0


OUTPUT

Every experiment produces the following output. Every trial is started by

begin try <trial_number>

Then, each time the algorithm finds a new best solution the output is

best <best_value>   time <cpu_time>

Every trial is ended by

end try <trail_number>

Once all trials are executed the program writes out a line of statistics:

statistics <best_found_in_all_trials>  <average_of_bests_found>  <standard_dev_of bests_found>
<average_time_when_bests_found>  <standard_dev_of_times_when_bests_found>


Have fun, and if you have any comments please write to 

[e-mail]