========================================================================
PISA  (www.tik.ee.ethz.ch/pisa/)
========================================================================
Computer Engineering (TIK)
ETH Zurich
========================================================================
"epsilon"-MOEA

Implementation in C++ for the selector side.

Documentation

file: epsmoea_documentation.txt
author: Tobias Wagner, wagner@isf.de
last change: 21.12.2006
========================================================================


The Optimizer
=============

Laumanns et al. \cite{LTDZ02} proposed the "epsilon"-MOEA to combine the
convergence properties of an elitist MOEA like suggested by Rudolph and
Agapie \cite{RA00} with the need to preserve a diverse set of solutions.
The objective space is divided into a grid of boxes, whose size can be
adjusted by the choice of epsilon. Dominance is checked according
to the boxes where the solutions are positioned. The archive E holds one solution
for each non-dominated box. If the box of a new solution dominates other
boxes in the archive, the associated archive members are rejected.
In case of two solutions belonging to the same box, Laumanns et al. decline
the new solution except it dominates the old one. Later, Deb et al. \cite{DMM03b}
propose to select the solution, which is closer to the best corner of the box.
They also administrate a co-evaluated population P of constant size. If a new solution is
not dominated by any member of the population, it replaces a randomly chosen
member favoring dominated solutions. They also suggest a steady-state approach, where the offspring
is generated by a parent from P and a parent from E. A binary tournament regarding the
dominance relation is performed to choose the member of P for mating.
If two non-dominated solutions are chosen, a random decision will be applied.
The parent from E is chosen equiprobable. In the implemetation at hand, the
condition lambda = 1 has been relaxed in order to work within the PISA
environment which often requires mu == lambda. If more offspring solutions
have been produced, the population and the archive are updated for each
solution within one generation.

@article{LTDZ02,
 AUTHOR = {M.~Laumanns and L.~Thiele and K.~Deb and E.~Zitzler},
 TITLE = {Combining convergence and diversity in evolutionary multi-objective optimization},
 JOURNAL = {Evolutionary Computation},
 VOLUME = {10},
 NUMBER = {3},
 PAGES = {263--282},
 YEAR = {2002}
}

@inproceedings{RA00,
   author = {G.~Rudolph and A.~Agapie},
   booktitle = {Congress on Evolutionary Computation (CEC2000)},
   editor = {A.~Zalzala and R.~Eberhart},
   pages = {1010--1016},
   publisher = {IEEE Press},
   ADDRESS = {Piscataway NJ},
 	VOLUME = {2},
   title = {Convergence properties of some multi-objective evolutionary algorithms},
   year = {2000}
}

@techreport{DMM03b,
  author =       {K.~Deb and M.~Mohan and S.~Mishra},
  title =        {{A Fast Multi-objective Evolutionary Algorithm for
                   Finding Well-Spread Pareto-Optimal Solutions}},
  institution =  {Indian Institute of Technology, Kanpur, India},
  year =         2003,
  type =         {KanGAL report},
  number =       2003002
}


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

"epsilon"-MOEA uses the following values for the common parameters.
These parameters are specified in 'PISA_cfg'.

alpha    (population size)
mu       (number of parent individuals)
lambda   (number of offspring individuals)
dim      (number of objectives)

'PISA_cfg' is a PISA_configuration file.

"epsilon"-MOEA takes four local parameters which are given in a parameter
file. The name of this parameter file is passed to "epsilon"-MOEA as command
line argument. (See 'epsmoea_param.txt' for an example.)

epsilon f_1 ... f_m  (size of epsilon for each objective)
seed                 (seed for the random number generator)
tournament           (tournament size for mating selection)
outgen	             (number of generations after that the archive and the population are written to a file)


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

The source code for "epsilon"-MOEA is divided into four files:

'epsmoea.h' is the header file.

'epsmoea.c' contains the main function and implements the control flow.

'epsmoea_io.c' implements the file i/o functions.

'epsmoea_functions.c' implements all other functions including the
selection.

Additionally a Makefile, a PISA_configuration file with common
parameters and a PISA_parameter file with local parameters are
contained in the tar file.

Depending on whether you compile on Windows or on Unix (any OS having
<unistd.h>) uncomment the according '#define' in the 'epsmoea.h' file.


Usage
=====

Start "epsilon"-MOEA with the following arguments:

epsmoea paramfile filenamebase poll

paramfile: specifies the name of the file containing the local
parameters (e.g. epsmoea_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. This gives the following names for
the 'PISA_' filenamebase:

PISA_cfg - configuration file
PISA_ini - initial population
PISA_sel - individuals selected for variation (PISA_
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
"epsilon-MOEA" 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.



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

According to Deb, one parent of the archive and one
parent of the population are chosen for mating.
Thus, only mu = 2 is allowed.


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

The behaviour in state 5 and 9 is not determined by the interface but
by each variator module specifically. "epsilon"-MOEA behaves as follows:

state 5 (= variator terminated): set state to 6 (terminate as well).
state 9 (= variator resetted): set state to 10 (reset as well).
