printlogo
ETH Zuerich - Homepage
Systems Optimization (SOP)
 
Search

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to the latest Netscape.
More information

ETH Zürich - D-ITET - TIK - SOP - PISA
print page
  
this webpage might no longer be updated more...

Overview over PISA

What is a search algorithm?

Bugs

In the PISA context a search algorithm is a method which tries to find solutions to a given problem by iterating three steps: the evaluation of candidate solutions, the selection of promising candidates based on this evaluation and the generation of new candidates by variation of these selected candidates. As examples most evolutionary algorithms and simulated annealing fall into this category.

PISA is mainly dedicated to multi-objective search, where the optimization problem is characterized by a set of conflicting goals and not just one criterion that needs to be optimized.

What is PISA?

PISA consists of two parts:

What is PISA Performance Assessment?

PISA Performance Assessment is based on the above concept of separating the optimization process into the optimization problem and the selection process. It extends it by a set of statistical tools that allow to assess and compare different optimization methods..

Why is PISA useful?

A module on the selection side can be freely combined with any module on the problem side and vice versa. All modules can be made available as ready-to-use binaries.

Variator and Selector

PISA is a text-based interface for search algorithms. It splits an optimization process into two modules.

This partitioning is shown in the figure below:

selector and variator

All the problem specific parts are located in the problem module, the Variator. In the selection module Selector a candidate solution (called an individual) can be represented by an identifier (ID) and a set of objective values describing the quality of this individual. This is the only information passed from the problem module to the selection module.

The problem module (Variator) creates an initial collection of individuals and calculates the objective values. The selection module (Selector) then chooses a collection of parent individuals which it thinks are promising. The problem module variates these individuals in order to get a new collection of offspring individuals. The selection module again chooses the parents and so on. All this data exchange is established using text files. The synchronization of the two modules is achieved by writing a state variable into a text file which both programs can read and update. The modules can be programmed in different programming languages or even run on different (distributed) platforms.

PISA contains also libraries of state-of-the-art and ready-to-go selectors and a set of benchmark variators, see the corresponding library page.

PISA Performance Assessment

The purpose of PISA PA is to support the algorithm expert in testing and comparing new multi-objective optimization algorithms on different test problems and real-world problems. With PISA PA, he can reliably compare different algorithms on benchmark problems using appropriate indicators and statistical methods. To this end, the communication between the Variator and Selector module is controlled and observed by a Monitor module, see the figure below:

performance assessments

Objective values from various runs are collected in text files which are then further processed by

Together with the library of selectors (such as NSGA-II, SPEA2 and IBEA) and variators (benchmark problems), reliable performance assessment of multi-objective optimizers is made easy. For further information, look at the PISA PA page.

Further Information

For more information about the architecture and specification of PISA and PISA PA consult the documentation page.

top
© 2009 Institut TIK, ETH Zürich | Imprint | Last updated: Mon, 15 Jun 2009 18:01 | Valid XHTML 1.0! Valid CSS! Valid XHTML 1.0