检索结果-内蒙古大学图书馆

Rigorous Experimental Performance Analysis of parallel evolutionary algorithms on Multicore Platforms

IEEE LATIN AMERICA TRANSACTIONS 2014年第4期12卷 805-811页

作者： Pais, M. S. Yamanaka, K. Pinto, E. R. Inst Fed Goiano IFGOIANO Setor Sul Go Brazil Univ Fed Uberlandia Fac Engn Eletr Uberlandia MG Brazil Univ Fed Uberlandia Fac Matemat Uberlandia MG Brazil

As multicore processors become ubiquitous, the improved performance available to parallel programs is a great motivation to computationally demanding evolutionary algorithms (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.

关键词： parallel evolutionary algorithms Performance Evaluation Performance Measures Design of Experiments algorithms Experimentation

来源：评论

学校读者我要写书评

暂无评论

Design and analysis of migration in parallel evolutionary algorithms

引用

SOFT COMPUTING 2013年第7期17卷 1121-1144页

作者： Laessig, Joerg Sudholt, Dirk Univ Appl Sci Zittau Gorlitz Dept Elect Engn & Comp Sci Gorlitz Germany Univ Sheffield Dept Comp Sci Sheffield S10 2TN S Yorkshire England

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.

关键词： parallel evolutionary algorithms Island model Migration Distributed evolutionary algorithms Spatial structures Multi-deme model Runtime analysis

来源：评论

学校读者我要写书评

暂无评论

General Upper Bounds on the Runtime of parallel evolutionary algorithms

引用

evolutionary COMPUTATION 2014年第3期22卷 405-437页

作者： Laessig, Joerg Sudholt, Dirk Univ Appl Sci Zittau Gorlitz Dept Comp Sci Zittau Germany Univ Sheffield Dept Comp Sci Sheffield S10 2TN S Yorkshire England

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.

关键词： parallel evolutionary algorithms runtime analysis island model spatial structures

来源：评论

学校读者我要写书评

暂无评论

Analysis of speedups in parallel evolutionary algorithms and (1+λ) EAs for combinatorial optimization

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期551卷 66-83页

作者： Laessig, Joerg Sudholt, Dirk Univ Appl Sci Dept Comp Sci Zittau Gorlitz Germany Univ Sheffield Dept Comp Sci Sheffield S10 2TN S Yorkshire England

evolutionary algorithms 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 evolutionary algorithms 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.

关键词： parallel evolutionary algorithms Combinatorial optimization Island model Spatial structures Offspring populations Runtime analysis

来源：评论

学校读者我要写书评

暂无评论

Design and Analysis of Schemes for Adapting Migration Intervals in parallel evolutionary algorithms

引用

evolutionary COMPUTATION 2015年第4期23卷 559-582页

作者： Mambrini, Andrea Sudholt, Dirk Univ Sheffield Dept Comp Sci Sheffield S1 4DP S Yorkshire England

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.

关键词： parallel evolutionary algorithms island model migration interval runtime analysis theory

来源：评论

学校读者我要写书评

暂无评论

Visual and Audio Monitoring of Island Based parallel evolutionary algorithms

引用

JOURNAL OF GRID COMPUTING 2015年第3期13卷 309-327页

作者： Lutton, Evelyne Gilbert, Hugo Cancino, Waldo Bach, Benjamin Pallamidessi, Joseph Parrend, Pierre Collet, Pierre INRA UMR GMPA F-78850 Thiverval Grignon France ENSTA ParisTech F-91762 Palaiseau France INRIA Saclay Ile de France AVIZ Team F-91405 Orsay France Strasbourg Univ CS DC UNESCO UniTwin ICube Lab F-67084 Strasbourg France Strasbourg Univ CS DC UNESCO UniTwin ECCE E Lab F-67084 Strasbourg France ECAM Strasbourg Europe F-67012 Strasbourg France

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.

关键词： parallel evolutionary algorithms Island model Visualisation Audio monitoring Musicalisation EASEA Computational ecosystem

来源：评论

学校读者我要写书评

暂无评论

Hybrid MPI/OpenMP parallel evolutionary algorithms for Vehicle Routing Problems 17

引用

17th European Conference on Applications of evolutionary Computation (EvpApplications)

作者： Banos, Raul Ortega, Julio Gil, Consolacion Catholic Univ Murcia Dept Business Adm & Management E-30107 Murcia Spain Univ Granada CITIC UGR Dept Comp Architecture & Technol E-18071 Granada Spain Univ Almeria CeiA3 Dept Informat E-04120 Almeria Spain

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.

关键词： Multi-core processors parallel evolutionary algorithms MPI OpenMP Hybrid MPI/OpenMP Vehicle Routing Problems

来源：评论

学校读者我要写书评

暂无评论

Facilitating the Hybridization of parallel evolutionary algorithms in Cluster Computing Environments 22

Facilitating the Hybridization of Parallel Evolutionary Algo...

引用

Genetic and evolutionary Computation Conference (GECCO)

作者： Khalloof, Hatem Ciftci, Sergen Shahoud, Shadi Duepmeier, Clemens Foerderer, Kevin Hagenmeyer, Veit Karlsruhe Inst Technol IAI Karlsruhe Germany

ISBN: (纸本)9781450392686

evolutionary algorithms (EAs) need domain-specific adaptations for achieving better results, tend to converge to suboptimal solutions and are computationally expensive when they are applied to complex and large-scale optimization problems. For addressing these challenges, hybridizing EAs with other algorithms and methods and parallelizing them in cluster computing environments represent essential solutions. In the present paper, a new software solution for supporting the hybridizations of parallel EAs is proposed. Unlike other software solutions for hybridizing EAs, the proposed software solution provides a flexible, generic and scalable mechanism for integrating any algorithmic approach like a Machine Learning (ML) algorithm to seed the initial population of parallel EAs. It is designed based on three modern software technologies, namely microservices, container virtualization and the publish/subscribe messaging paradigm. The applicability and generality of the presented software solution is tested by hybridizing the General Learning evolutionary Algorithm and Method (GLEAM) with ML techniques for solving the problem of scheduling Distributed Energy Resources (DERs). The benchmarking tests are performed in a cluster computing environment. The obtained results show that the new software solution represents a successful approach to facilitate the hybridization of parallel EAs paving the road for future applications of EAs in several domains.

关键词： Hybrid evolutionary algorithms parallel evolutionary algorithms Global Model Microservice Virtualization Container Scheduling Distributed Energy Resources parallel Computing Scalability

来源：评论

学校读者我要写书评

暂无评论

General Scheme for Analyzing Running Times of parallel evolutionary algorithms

General Scheme for Analyzing Running Times of Parallel Evolu...

引用

11th International Conference on parallel Problem Solving from Nature

作者： Laessig, Joerg Sudholt, Dirk Int Comp Sci Inst Berkeley CA 94704 USA

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.

关键词： parallel evolutionary algorithms runtime analysis island model spatial structures

来源：评论

学校读者我要写书评

暂无评论

On the Effectiveness of Crossover for Migration in parallel evolutionary algorithms 11

On the Effectiveness of Crossover for Migration in Parallel ...

引用

13th Annual Genetic and evolutionary Computation Conference (GECCO)

作者： Neumann, Frank Oliveto, Pietro S. Rudolph, Guenter Sudholt, Dirk Univ Adelaide Sch Comp Sci Adelaide SA Australia Univ Birmingham Sch Comp Sci Birmingham W Midlands England Tech Univ Dortmund Fak Informat Dortmund Germany

ISBN: (纸本)9781450305570

Island models are popular ways of parallelizing evolutionary algorithms 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.

关键词： parallel evolutionary algorithms island model crossover recombination migration runtime analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：