AMS-DEMO

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.

An example of optimization of ECG simulator output; left: a sketch of comparing solution in multi-objective setting, center: several Pareto fronts of solutions, right: the convergence of the algorithm.
An example of optimization of ECG simulator output; left: a sketch of comparing solution in multi-objective setting, center: several Pareto fronts of solutions, right: the convergence of the algorithm.

Multi-objective optimization is a generalizaiton of the more widely known single-objective optimization. In multi-objective optimization, the problem is characterized by multiple objective functions as the name suggests. The objectives are also mostly contradicting, therefore improving on one objective often requires to worsen another. To solve such problem thoroughly, the goal for multi-objective optimization is to find not one, but a set of Pareto dominant solutions. That is, a set of solutions for which different trade-offs between objectives have been selected, called also a Pareto front. In this set, though, there is no solution that would be worse from one of the included solutions in all the objectives.

An example of optimization of barrier placement for the minimization of heat flow due to natural convection; heat flow on the left and Pareto front of solutions on the right.
An example of optimization of barrier placement for the minimization of heat flow due to natural convection; heat flow on the left and Pareto front of solutions on the right.

We have developed a parallel differential evolution for multi-objective optimization, AMS-DEMO. The algorithm was designed for solving time demanding problems efficiently on both homogeneous and heterogeneous distributed computer architectures. To maximize flexibility and robustness, it uses a master-slave parallelization method that is modified to allow for asynchronous communication between computers.

Evaluation of selection lag, which is a consequence of parallel execution.
Evaluation of selection lag, which is a consequence of parallel execution.

AMS-DEMO was experimentally tested and found to be very flexible and efficient even on heterogeneous computer architectures. On homogeneous architectures and problems with constant-time fitness evaluation functions, however, the same performance as with AMS-DEMO could be achieved with simpler parallel algorithms.

Code repository

Code
Code

AMS-DEMO is open source and its source can be downloaded from the git repository. Compiling the code requires only the basic build toolset and a C++ compiler.

Related projects

Core research programme P2-0095

P-Lab team


Publications

M. Depolli, G. Kosec, R. Trobec; Parallel evolutionary optimization of natural convection problem, 2017 [COBISS: 30924071]
M. Depolli, G. Kosec; Assessment of differential evolution for multi-objective optimization in a natural convection problem solved by a local meshless method, Engineering optimization, vol. 49, 2017 [DOI: 10.1080/0305215X.2016.1197686][COBISS: 29639719] ::
M. Depolli, R. Trobec, B. Filipič; Asynchronous master-slave parallelization of differential evolution for multiobjective optimization, Evolutionary computation, vol. 21, 2013 [DOI: 10.1162/EVCO_a_00076][COBISS: 25824807] ::
M. Depolli, B. Filipič, R. Trobec; Parallelization of an evolutionary algorithm for multiobjective optimization : doctoral dissertation = Paralelizacija evolucijskega algoritma za večkriterijsko optimizacijo : doktorska disertacija, 2010 [COBISS: 252901376]