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