称号及び氏名

博士（理学）

Md Maruf Hussain

学位授与の日付 令和 2 年 6 月 30 日
論文

名

論文審査委員GPU-based Parallel Single and Multi-objective
Particle Swarm Optimization for Large Swarms andHigh Dimensional Problems
単目的および多目的の高次元最適化問題を対象とした大規模粒子群最適化の GPU を用いた並列化
主査
副査
副査

藤本 典幸
宇野 裕之
瀬田 和久

GPU-based Parallel Single and Multi-objective
Particle Swarm Optimization forLarge Swarms and High Dimensional Problems

Abstract
The Particle Swarm Optimization (PSO) algorithm has been first introduced byEberhart and Kennedy in 1995, which is one of the most important populationbased

nondeterministic optimization algorithms for single objective optimization problems.
Since then, many successful applications of PSO have been reported. In many of those
applications, the PSO algorithm has shown several advantages over other swarm
intelligence based optimization algorithms due to its robustness, efficiency andsimplicity. Moreover, compared to other stochastic algorithms, it

usually requires lesscomputational effort and resources.
The PSO algorithm maintains a swarm of particles, where each of which represents apotential solution. Here a swarm can be identified as the population and a particle as anindividual. In a PSO system, each particle flows through a multidimensional search
space and adjusts its position based on its own experience with neighboring particles.
On a CPU, this process is implemented based on task scheduling into serial processing,whereas on a GPU, many particles can reach to their positions simultaneously, which
improves the PSO efficiency significantly. In recent years, a GPU becomes a very
popular platform for the realization of parallel computing, mainly due to changes inarchitecture and development of CUDA and OpenCL languages. Previously reported
works have shown that the PSO implementation on a GPU provides a better
performance than CPU-based implementations which makes us interested in this study.
At first, we implemented a good implementation for the Standard Particle Swarm
Optimization (SPSO) on a GPU based on the CUDA architecture, which uses atomic

function, a fast pseudorandom number generator, coalescing memory access. The
algorithm is evaluated on a suite of well-known benchmark optimization functions. The
experiments are performed on an NVIDIA GeForce GTX 980 GPU and a single core of
3.20 GHz Intel Core i5 4570 CPU and the test results demonstrate that the GPU
algorithm runs about maximum 170 times faster than the corresponding CPU
algorithm. Therefore, this proposed algorithm can be used to improve required time tosolve optimization problems. After that, we conducted experiments for testing the effectof the Pseudorandom Number Generators on the SPSO on a GPU. By using a single
step TausStep of the combined Tausworthe generator, the proposed parallel
implementation of SPSO provides up to 307 times speedup compared to a serial SPSO
implementation. Speedup is greatly accelerated for high dimensional problems, large
particles and complex benchmark functions.
The success of the PSO algorithm as a single objective optimizer has motivated us toextend its use in other areas. One of such areas is multi-objective optimization.
Multi-objective optimization problems (MOOPs) are very common in real-world
optimization fields, where the objectives to be optimized are normally in conflict witheach other. Moore and Chapman proposed the first extension of the PSO strategy forsolving MOOPs (Multi-Objective PSO, MOPSO) in an unpublished manuscript in 1999.
With big data becoming more important as time goes by, the necessity for fastermethods is growing. The previous implementations of serial and parallel cases ofMOPSO do not meet the requirements of big data. In addition, those implementations
could only handle a limited number of dimensions. The necessity for a better method issorely needed.
This thesis paper presents a new GPU-parallelized implementation of MOPSO (GPUMOPSO) based on a master-slave model for large swarms and high dimensional
optimization problems. This paper also presents a new serial implementation ofMOPSO (CPU MOPSO). Our CPU program uses a single core only although our CPU
has multiple cores. Our CPU MOPSO achieves faster performance for large swarms andhigh dimensional optimization problems. The experimental results show that theproposed GPU MOPSO increases the processing speed compared to previously proposed
approaches on a GPU based on the CUDA architecture. The proposed parallel
implementation of MOPSO using a master-slave model provides up to 157 times

speedup compared to the corresponding CPU implementation. Here, we investigate alarge number of iterations to reach good nondominated solutions which achieve good
Pareto fronts. Pareto fronts of both CPU MOPSO and GPU MOPSO implementations
match very closely to the true Pareto fronts. Performance of MOPSO is dependent uponan archiving technique. We propose a simple parallel archiving technique whichsignificantly speeds up the process. Our serial archiving technique is the same as theparallel archiving except that it is executed in serial. In our GPU MOPSO, the used
PRNG and coalescing memory access have a positive impact which improve
computational time.
In the literature, several models for parallel MOPSO have previously been proposed.
Some of these models are suited for costly platforms. For example, the island model issuitable for clusters and grids. The diffusion model of multi-objective evolutionary
algorithms is also suitable for another costly platform, massively parallel processors. Incontrast, there are models for more affordable platforms. The master-slave model andthe hierarchical model are both suitable for GPUs, but the hierarchical model tends tobe slower than the master-slave model.

The doctoral thesis is organized as follows. In Chapter 1, we introduce ourimplementations. In Chapter 2, we sketch out briefly PSO, SPSO, MOOPs, MOPSO,GPU computing, an overview of CUDA architecture, coalescing memory access, random
number generators, Thrust library, CUB library and parallel models. In Chapter 3, wepresent our CUDA Implementation of SPSO. In Chapter 4, we conduct experiments fortesting the effect of ten Pseudorandom Number Generators on the SPSO on a GPU. InChapter 5, we provide our MOPSO implementations on a CPU and a GPU, analyze
experimentalresultsandcompare

ourimplementationwiththeprevious

implementation in terms of execution time and speedup. Finally, in Chapter 6, we givesome concluding remarks and point out directions for future work.

List of Publications
Refereed Journal Paper
1.

GPU-based Parallel Multi-objective Particle Swarm Optimization for Large
Swarms and High Dimensional Problems, Md. Maruf Hussain and Noriyuki
Fujimoto, Parallel Computing, 19 pages, DOI: 10.1016/j.parco.2019.102589 (2020)(掲載決定).

Refereed International Conference Papers
1.

Effect of the Pseudorandom Number Generators on the Standard Particle Swarm
Optimization on a GPU, Md. Maruf Hussain and Noriyuki Fujimoto, Proc. of the2018 International Conference on Computational Science and Computational
Intelligence (CSCI), pp.295-300, DOI: 10.1109/CSCI46756.2018.00064 (Las Vegas,USA, 2018).

2.

Parallel Multi-Objective Particle Swarm Optimization for Large Swarm and High
Dimensional Problems, Md. Maruf Hussain and Noriyuki Fujimoto, Proc. of the2018 IEEE Congress on Evolutionary Computation (CEC), pp.1-10, DOI:
10.1109/CEC.2018.8477848 (Rio de Janeiro, Brazil, 2018).

3.

A CUDA Implementation of the Standard Particle Swarm Optimization, Md. MarufHussain, Hiroshi Hattori, and Noriyuki Fujimoto, Proc. of 18th International
Symposium on Symbolic and Numeric Algorithms for Scientific Computing(SYNASC), pp.219-226, DOI: 10.1109/SYNASC.2016.043 (Timisoara, Romania,2016).