Tomohiro Harada, Enrique Alba · ACM Computing Surveys · 2020
In this article, we encompass an analysis of the recent advances in parallel genetic algorithms (PGAs). We have selected these algorithms because of the deep interest in many research fields for techniques that can face complex applications where running times and other computational resources are greedily consumed by present solvers, and PGAs act then as efficient procedures that fully use modern computational platforms at the same time that allow the resolution of cutting-edge open problems. We have faced this survey on PGAs with the aim of helping newcomers or busy researchers who want to have a wide vision on the field. Then, we discuss the most well-known models and their implementations from a recent (last six years) and useful point of view: We discuss on highly cited articles, keywords, the venues where they can be found, a very comprehensive (and new) taxonomy covering different research domains involved in PGAs, and a set of recent applications. We also introduce a new vision on open challenges and try to give hints that guide practitioners and specialized researchers. Our conclusion is that there are many advantages to using these techniques and lots of potential interactions to other evolutionary algorithms; as well, we contribute to creating a body of knowledge in PGAs by summarizing them in a structured way, so the reader can find this article useful for practical research, graduate teaching, and as a pedagogical guide to this exciting domain.
Cited by 158
European Journal of Operational Research · 1989
Cited by 256
Jacob White, Alberto Sangiovanni‐Vincentelli · Kluwer international series in engineering and computer science · 1987
Cited by 0
W. Daniel Hillis, Guy L. Steele · Communications of the ACM · 1986
Parallel computers with tens of thousands of processors are typically programmed in a data parallel style, as opposed to the control parallel style used in multiprocessing. The success of data parallel algorithms—even on problems that at first glance seem inherently serial—suggests that this style of programming has much wider applicability than was previously thought.
Cited by 885Open access
WORLD SCIENTIFIC eBooks · 2002
Cited by 0
Fenglien Lee · 1992
Geometric algorithms have many important applications in science and technology. Some geometric problems require fast response time that could not be achieved by traditional sequential algorithms. However, the speed, power and versatility of parallel computers can be exploited to develop efficient geometric algorithms as shown in this dissertation. Our study focuses on designing efficient parallel geometric algorithms and analyzing their computational complexities. In this research, first we developed a parallel algorithm to find the maxima of a set of N points in the d-dimensional space, d $>$ 3, on a hypercube SIMD machine. Our algorithm is a parallel implementation from the sequential algorithm given by Kung, Luccio, and Preparata (KLP75). Although the time complexity, $O(N\sp{0.77}\log\sp{d-1}\ N),$ of our algorithm is not optimal, it is the first sublinear time algorithm for solving the high dimensional maxima problem. Next, we developed another parallel algorithm to construct the Voronoi diagram of a point set in the plane. Our algorithm is based on the sequential algorithm given by Brown (B79). We use an $N\times N$ mesh of trees (MOT) SIMD computer and get the optimal time complexity $O(log\sp2N).$. Finally, we developed another MOT algorithm to solve the congruent pattern problem. Given a simple polygon P with k edges and a planar graph G with N edges, $N>k.$ The problem is to find all the patterns (cycles) in G which are congruent to P. Our algorithm is based on the CREW PRAM algorithm given by Jeong, Kim, and Baek (JKB92). We also use an $N\times N$ MOT and get the optimal time complexity $O(k\log N).$.
Cited by 0Open access
Fevzi Oktay Ozbek, Ozbek Fevzi Oktay, Hough Transform et al. · 1992
I would like to acknowledge the guidance and support of my advisor, Professor Meghanad D. Wagh. This thesis was possible because of his patience and great knowledge. I would also like thank to all my friends in Lehigh University. iii
Cited by 0
Sebastian Raaphorst · 2004
In algebra, and particularly in the study of the algebraic structures known as fields, there are a number of problems that enjoy efficient sequential algorithms. Many of these sequential algorithms do not present immediately obvious parallel algorithms, but from a theoretical perspective, it is still interesting to study the parallel complexity of these problems. We investigate three specific algebraic topics, namely the greatest common divisor problem, the modular polynomial exponentiation problem, and the polynomial factorization problem. The currently best known parallel algorithms are presented and their complexities analyzed. While these algorithms do not lend themselves well to implementation due to the fact that they rely on a number of processors polynomial in the size of the input, they do give us an upper bound on the parallel complexity of these problems. While polynomial GCD has been shown to be in N C, it is not currently known if the other two problems are in this parallel class. 1
Cited by 0
Lars S. Nyland, Jan F. Prins · 1992
A prototyping approach to the implementation of complex parallel algorithms on actual parallel machines is proposed as a way to bridge the gap between theoretical descriptions of parallel algorithms and the implementationlevel details required in current low-level parallel programming languages. Prototypes are constructed using the wide-spectrum parallel programming language Proteus and can be executed using a Proteus interpreter. The widespectrum nature of the Proteus language permits key aspects of the implementation to be carefully investigated while other, ancillary, aspects can remain at a convenient level of abstraction. Manual and automatic techniques are under investigation to transform prototypes to low-level programming languages for specific machines. In this paper several different N-body force calculation techniques are used to introduce Proteus, including a preliminary implementation study of the 3-dimensional fast multipole algorithm of Greengard, an algorithm of current...
Cited by 0
John H. Reif · 1989
Abstract : Investigations of several subproblems in the area of derivation of parallel programs were continued during the current quarter. These investigations include: (1) Derivation of various parallel algorithms, parallel graph connectivity and parallel list ranking; (2) Automatic Parallel Compilation from segmented straight line programs; (3) Derivation of pipelined algorithms on small networks; (4) Programming Languages: Common Prototype Language (CPL); (5) Duke Algorithm Derivation Seminar; (6) Planning a textbook on Synthesis of Parallel Algorithms.
Cited by 3
Gabriel Luque, Enrique Alba · Studies in computational intelligence · 2011
Cited by 104
Xiaobo Li, Zhixi Fang · Parallel Computing · 1989
Cited by 112
Seyed H. Roosta · 2000
Cited by 2
Gerhard Winkler · 2003
Cited by 1
David Robillard · 2010
distribuer et vendre des theses partout dans le monde, a des fins commerciales ou autres, sur support microforme, papier, electronique et/ou autres formats.
Cited by 0Open access
Yousif, H.M · UPT. Syiah Kuala University Library (Syiah Kuala University) · 1986
A Doctoral Thesis. Submitted in partial fulfilment of the requirements for the award of Doctor of Philosophy of Loughborough University.
Cited by 0Open access
Wojciech Rytter · Chapman & Hall/CRC computer and information science series · 2007
Cited by 0
M. M. Maksimov, V. V. Galushko, A. B. Kutcherov et al. · SPE Symposium on Reservoir Simulation · 1993
Abstract This paper presents a new technique for solving the linear equations arising in reservoir simulation using multiple processors in parallel. The parallel algorithms for the Nested Factorization method are developed and implemented on a network cluster of highperformance IBM RISC System/6000 workstations as well as on a network of transputers. It is demonstrated on different 3-D data sets varying from 10,000 to 750,000 grid cells that a very high efficiency is achieved on MIMD, local memory, parallel platforms.
Cited by 4
Herendi Tamás, Nagy Benedek · 2019
Nowadays the parallelization of various computations becomes more and more important. In this book the theoretical models of parallel computing are presented. Problems that can be solved and problems that cannot be solved in these models are described. The parallel extensions of the traditional computing models, formal languages and automata are presented, as well as properties and semi-automatic verifications and generations of parallel programs. The concepts of theory of parallel algorithms and their complexity measures are introduced by the help of the (parallel) Super Turing-machine. The parallel extensions of context-free grammars, such as L-systems, CD and PC grammar systems; multihead automata (including various Watson-Crick automata), traces and trace languages are described. The theory and applications of Petri nets are presented by their basic concepts, special and extended models. From the practical, programming point of view, parallelization of (sequential) programs is investigated based on discovering of dependencies.
Cited by 8
Parallel algorithms and applications · 1994
Cited by 24