As multicore processors become ubiquitous, the improved performance available to parallel programs is a great motivation to computationally demanding evolutionaryalgorithms (EAs) to turn into parallel EAs (PEAs) and ...
详细信息
As multicore processors become ubiquitous, the improved performance available to parallel programs is a great motivation to computationally demanding evolutionaryalgorithms (EAs) to turn into parallel EAs (PEAs) and to be able to exploit the power of multicores. parallel computing is a powerful way to reduce the computation time and to improve the quality of EAs solutions. To the stochastic nature of EAs, the known variability of the parallel programs execution times on multicores adds more complexity on PEAs performance evaluations. Performance evaluation methodologies need to adequately deal with the non-determinism in the experimental set. To obtain correct conclusions it is necessary to apply rigorous statistical procedures. The usual estimation of the speedup of a parallel program as the ratio of the sequential execution time and the parallel execution time may not be appropriated if some care is not taken. A correct estimation of the speedup as a performance measure is presented. A method based on the factorial experimental design is proposed to identify which are the significant factors on the performance of a PEA executed on a multicore processor. A case study of the performance analysis of a PEA solving a benchmark test function is presented.
parallelization is becoming a more important issue for solving difficult optimization problems. Island models combine phases of independent evolution with migration where genetic information is spread out to neighbore...
详细信息
parallelization is becoming a more important issue for solving difficult optimization problems. Island models combine phases of independent evolution with migration where genetic information is spread out to neighbored islands. This can lead to an increased diversity within the population. Despite many successful applications, the reasons behind the success of island models are not well understood. We perform a first rigorous runtime analysis for island models and construct a function where phases of independent evolution as well as communication among the islands are essential. A simple island model with migration finds a global optimum in polynomial time, while panmictic populations as well as island models without migration need exponential time, with very high probability. Our results lead to new insights into the usefulness of migration, how information is propagated in island models, and how to set parameters such as the migration interval. This is a novel contribution to the theoretical foundation of parallel EAs. Further, we provide empirical results that complement the theoretical results, investigate the robustness with respect to the choice of the migration interval and compare various migration topologies using statistical tests.
We present a general method for analyzing the runtime of parallel evolutionary algorithms with spatially structured populations. Based on the fitness-level method, it yields upper bounds on the expected parallel runti...
详细信息
We present a general method for analyzing the runtime of parallel evolutionary algorithms with spatially structured populations. Based on the fitness-level method, it yields upper bounds on the expected parallel runtime. This allows for a rigorous estimate of the speedup gained by parallelization. Tailored results are given for common migration topologies: ring graphs, torus graphs, hypercubes, and the complete graph. Example applications for pseudo-Boolean optimization show that our method is easy to apply and that it gives powerful results. In our examples the performance guarantees improve with the density of the topology. Surprisingly, even sparse topologies such as ring graphs lead to a significant speedup for many functions while not increasing the total number of function evaluations by more than a constant factor. We also identify which number of processors lead to the best guaranteed speedups, thus giving hints on how to parameterize parallel evolutionary algorithms.
Monitoring and visualisation tools are currently attracting more and more attention in order to understand how search spaces are explored by complex optimisation ecosystems such as parallel evolutionary algorithms bas...
详细信息
Monitoring and visualisation tools are currently attracting more and more attention in order to understand how search spaces are explored by complex optimisation ecosystems such as parallel evolutionary algorithms based on island models. Multilevel visualisation is actually a desirable feature for facilitating the monitoring of computationally expensive runs involving several hundreds of computers during hours or even days. In this paper we present two components of a future multilevel monitoring system: MusEAc, a high level, audio monitoring allowing to listen to a run and tune it in real time and GridVis, a lower lever, more precise a posteriori visualisation tool that lets the user understand why the algorithm has performed well or bad.
evolutionaryalgorithms are popular heuristics for solving various combinatorial problems as they are easy to apply and often produce good results. Island models parallelize evolution by using different populations, c...
详细信息
evolutionaryalgorithms are popular heuristics for solving various combinatorial problems as they are easy to apply and often produce good results. Island models parallelize evolution by using different populations, called islands, which are connected by a graph structure as communication topology. Each island periodically communicates copies of good solutions to neighboring islands in a process called migration. We consider the speedup gained by island models in terms of the parallel running time for problems from combinatorial optimization: sorting (as maximization of sortedness), shortest paths and Eulerian cycles. The results show in which settings and up to what degree evolutionaryalgorithms can be parallelized efficiently. Our results include offspring populations in (1 + lambda) EAs as a special case. Potential speedups depend on many design choices such as the search operators, representations and fitness functions used on the islands, and also the parameters of the island model. In particular, we show that a natural instance for Eulerian cycles leads to exponential vs. logarithmic speedups, depending on the frequency of migration. (C) 2014 Elsevier B.V. All rights reserved.
The migration interval is one of the fundamental parameters governing the dynamic behaviour of island models. Yet, there is little understanding on how this parameter affects performance, and how to optimally set it g...
详细信息
The migration interval is one of the fundamental parameters governing the dynamic behaviour of island models. Yet, there is little understanding on how this parameter affects performance, and how to optimally set it given a problem in hand. We propose schemes for adapting the migration interval according to whether fitness improvements have been found. As long as no improvement is found, the migration interval is increased to minimise communication. Once the best fitness has improved, the migration interval is decreased to spread new best solutions more quickly. We provide a method for obtaining upper bounds on the expected running time and the communication effort, defined as the expected number of migrants sent. Example applications of this method to common example functions show that our adaptive schemes are able to compete with, or even outperform, the optimal fixed choice of the migration interval, with regard to running time and communication effort.
The traditional fields of improvement in parallelism have been orientated to experimentation on high-budget equipment, such as clusters of computers or shared memory machines thanks to their high-performance and scala...
详细信息
ISBN:
(纸本)9783662455234;9783662455227
The traditional fields of improvement in parallelism have been orientated to experimentation on high-budget equipment, such as clusters of computers or shared memory machines thanks to their high-performance and scalability. In recent years, the generalization of multicore microprocessors in almost all the computing platforms makes it possible to take advantage of parallel processing even for the desktop computer user. This paper analyzes how to improve the performance of population-based meta-heuristics using MPI, OpenMP, and hybrid MPI/OpenMP implementations in a workstation having a multi-core processor. The results obtained when solving large scale instances of the Capacitated Vehicle Routing Problem with hard Time Windows (VRPTW) show that, in all cases, the parallel implementations produce better quality solutions for a given amount of runtime than the sequential algorithm, and also solutions of similar quality in less runtime.
Island models are popular ways of parallelizing evolutionaryalgorithms as they can decrease the parallel running time at low communication costs and lead to an increased population diversity. This in particular provi...
详细信息
ISBN:
(纸本)9781450305570
Island models are popular ways of parallelizing evolutionaryalgorithms as they can decrease the parallel running time at low communication costs and lead to an increased population diversity. This in particular provides a good setting for crossover as this operator relies on a good diversity between parents. We consider the effect of recombining migrants with individuals on the target island. We rigorously prove, for a test function in pseudo-Boolean optimization, exponential performance gaps between island models with strongly connected topologies and a panmictic (mu+1) EA as long as the migration interval is not too small. We then choose vertex cover as a classical NP-hard problem. By considering instances with a clear building block structure we prove that, also in this more practical setting, island models with a particular topology drastically outperform panmictic populations. Both the theoretical and empirical results show that for strongly connected topologies, such as ring, the performance drops by decreasing the migration interval, while this is not the case for topologies connected weakly such as the single receiver model.
We present new methods for the running time analysis of parallel evolutionary algorithms with spatially structured populations. These methods are applied to estimate the speed-up gained by parallelization in pseudo-Bo...
详细信息
ISBN:
(纸本)9783642158438
We present new methods for the running time analysis of parallel evolutionary algorithms with spatially structured populations. These methods are applied to estimate the speed-up gained by parallelization in pseudo-Boolean optimization. The possible speed-up increases with the density of the topology. Surprisingly, even sparse topologies like ring graphs lead to a significant speed-up for many functions while not increasing the total number of function evaluations. We also give practical hints towards choosing the minimum number of processors that gives an optimal speed-up.
We present two adaptive schemes for dynamically choosing the number of parallel instances in parallel evolutionary algorithms. This includes the choice of the offspring population size in a (1-lambda) EA as a special ...
详细信息
ISBN:
(纸本)9781450306331
We present two adaptive schemes for dynamically choosing the number of parallel instances in parallel evolutionary algorithms. This includes the choice of the offspring population size in a (1-lambda) EA as a special case. Our schemes are parameterless and they work in a black-box setting where no knowledge on the problem is available. Both schemes double the number of instances in case a generation ends without finding an improvement. In a successful generation, the first scheme resets the system to one instance, while the second scheme halves the number of instances. Both schemes provide near-optimal speed-ups in terms of the parallel time. We give upper bounds for the asymptotic sequential time (i. e., the total number of function evaluations) that are not larger than upper bounds for a corresponding non-parallel algorithm derived by the fitness-level method.
暂无评论