PARALLEL IMPLEMENTATION OF MULTI-OBJECTIVE PARTICLE SWARM OPTIMIZATION

Abstract

Nature has helped mankind in every fields and computer science is not an exception. - To solve compute intensive NP hard problems, it is required to obtain the solution in polynomial time. For such problems, algorithm as well as implementation need to be revised. For the implementation of such compute-intensive problems, supercomputing is a key solution, but it has limitations. Due to rapid advancement in computer science field, Moore law is now saturated, hence, it is essential to explore more and more options. Particle swarm optimization (PSO) is nature inspired algorithm, in which particles search solution in a given space by using personal and global experiences. PSO is iterative in nature, thus we can obtain the solution in polynomial time. PSO is proven to be efficient in multi-objective domain and can be used to find the solutions of Multi-Objective Problem (MOP) by storing non-dominated solutions. Complexity of the MOPSO algorithm depends on the fitness function and archiving method. Clusters are "loosely coupled systems", in which nodes are interconnected by high-speed LAN and communicate through message passing. "Tightly coupled systems" such as GPUs are set of streaming processors, who share memory and communication between them is carried through shared global memory. For parallel implementation of MOPSO, it follows parallel models defined for MOEA. However, parallel implementation of MOPSO is highly platform dependent. It is essential to know the performance of MOPSO on different platforms. In this report, implementations of MOPSO on GPU and cluster using multi-objective benchmark functions are explained. Novel archiving methods are proposed for parallel as well as serial implementation of MOPSO. Performances of parallel MOPSO on GPU and clusters are compared. Finally, hybrid parallel model of MOPSO for GPU cluster is proposed.