A Parallel Particle Swarm Optimization Algorithm

6th World Congresses of Structural and Multidisciplinary Optimization Rio de Janeiro, 30 May - 03 June 2005, Brazil A Parallel Particle Swarm Optimization Algorithm Accelerated by Asynchronous Evaluations Gerhard Venter (gventer@vrand.com), Jaroslaw Sobieszczanski-Sobieski (j.sobieski@larc.nasa.gov) Vanderplaats Research and Development, Colorado Springs, USA NASA Langley Research Center, Hampton, USA 1. Abstract A parallel Particle Swarm Optimization (PSO) algorithm is presented. Particle swarm optimization is a fairly recent addition to the family of non-gradient based, probabilistic search algorithms that is based on a

simplified social model and is closely tied to swarming theory. Although PSO algorithms present several attractive properties to the designer, they are plagued by high computational cost as measured by elapsed time. One approach to reduce the elapsed time is to make use of coarse-grained parallelization to evaluate the design points. Previous parallel PSO algorithms were mostly implemented in a synchronous manner, where all design points within a design iteration are evaluated before the next iteration is started. This approach leads to poor parallel speedup in cases where a heterogeneous parallel environment is used and/or where the analysis time depends on the design point being analyzed. This paper introduces an asynchronous parallel PSO algorithm that greatly improves the parallel efficiency. The asynchronous algorithm is benchmarked on a cluster assembled of Apple Macintosh G5 desktop computers, using the multi-disciplinary optimization of a typical transport aircraft wing as an example. 2. Keywords: Particle Swarm Optimization, PSO, asynchronous parallel computing 3. Introduction Particle Swarm Optimization (PSO) is a fairly recent, but rapidly growing, addition to an expanding collection of non-gradient based, probabilistic search algorithms. Some widely used algorithms that fall into this category are genetic algorithms [1] that model Darwin’s principle of survival of the fittest and simulated annealing algorithms [2] that model the equilibrium of large numbers of atoms during an annealing process. This class of optimization algorithms provides the designer with several attractive characteristics. For example, these algorithms are generally easy to implement, can efficiently make use of large numbers of parallel processors, do not require continuity in response functions and are better suited for finding global or near global solutions. Although these non-gradient based algorithms provide the designer with several advantages, they should be applied with care. Due to their high computational cost, these algorithms should only be used when a gradient-based algorithm is not a viable alternative, such as integer/discrete and discontinuous problems. Many non-gradient based search algorithms are based on some natural phenomena, and PSO is no exception. Particle swarm optimization is based on a simplified social model that is closely tied to swarming theory and was first introduced by Kennedy and Eberhart [3, 4]. A physical analogy might be a school of fish that is adapting to its environment. In this analogy, each fish adapts to its environment by making use of its own memory as well as knowledge gained by the school as a whole. Although...

Website: bioserver.cpgei.ct.utfpr.edu.br | Filesize: -
No of Page(s): 10
Download A Parallel Particle Swarm Optimization Algorithm ... - Bioserver.pdf