REPOZITORIJ > REZULTATI

Povzetek

Solving real-life optimization problems numerically is often very time demanding, because
of high complexity of the simulations that are usually involved. Solving such problems
becomes highly impractical for this reason and can even lead to use of less complex and
also less accurate models. Fortunately, evolutionary algorithms, often used in numerical
optimization, can be parallelized with relative ease, which significantly reduces the time
required for optimization on parallel computer architectures.
By parallelizing DEMO – an evolutionary algorithm for multiobjective optimization,
we create AMS-DEMO. The algorithm was designed for solving time demanding problems
efficiently on both homogeneous and heterogeneous parallel computer architectures. To
maximize flexibility and robustness, it uses a master-slave parallelization method that is
modified to allow for asynchronous communication between computers.
AMS-DEMO performance is analyzed on two complex real-life multiobjective optimization
problems and compared against a simpler but related algorithm, parallelized
using the conventional master-slave method. Experimental tests are performed on two
different parallel setups, one homogeneous and one heterogeneous, while the theoretical
analysis extends the test results to cover a few hypothetical setups as well. AMS-DEMO is
found to be very flexible and can be efficiently used on heterogeneous computer architectures.
On homogeneous architectures and problems with constant-time fitness evaluation
functions, however, the same performance as with AMS-DEMO can be achieved with
much simpler parallel algorithms.
Selection lag is identified as the key property of evolutionary algorithms parallelized
using asynchronous master-slave method. It explains how the behavior of the algorithm
changes depending on parallel computer architecture, mainly on the number of processors
that a given architecture offers. The dependence of algorithm efficiency on selection lag
is shown, completing the link between efficiency and the number of processors in the
parallel computer running the algorithm.