Parallelization of hybrid multi-objective evolutionary algorithm on multi-core architectures

Many real world optimization problems involve multiple conflicting objectives, constraints and parameters. Multi-objective optimization (MOO) techniques are used to solve these problems. The goal of MOO is to find a set of optimal solutions, or the Pareto optimal front. Multi-objective evolutionary algorithms are heuristics that evolve a population of candidate solutions to find the Pareto optimal front in a single run. The selection criterion used to select individuals in the population play an important role in determining the quality of the solutions. Pareto-based algorithms use the Pareto selection criterion to evolve different parts of the solution space introducing diverse solutions, but converge slowly to the optimal front. On the other hand, non- Pareto selection Criterion (NPC) algorithms converge faster to the Pareto front, but in the process eliminate other diverse solutions. To compensate for the strengths and weaknesses of PC and NPC, hybrid frameworks such as BCE (bi-criterion evolutionary) have been proposed. In BCE, the PC and NPC algorithms evolve separately, but also co-operate by exchanging information to explore and exploit the objective space. In the literature, two well-known evolutionary algorithms, Non-dominated Sorting Genetic Algorithm II (NSGA-II) (PC) and Multi-objective Evolutionary Algorithm based on Decomposition (MOEA/D) (NPC) have been used as a case study in the BCE framework. However, the individual algorithms are computationally expensive. In this thesis, we study the parallelization of the BCE framework. NSGA-II is highly data parallel, and is well suited for single instruction multiple data architectures. MOEA/D is non-data parallel with some parts of the algorithm being sequential. Therefore, we design the parallel NSGA-II algorithm on the GPU multi-core accelerator and parallel MOEA/D algorithm on multi-core CPU machines using an island model. Using the travelling salesperson benchmark data sets we analyze the performance of the parallel hybrid algorithm quantitatively and qualitatively using metrics such as IGD scores, scalability, and speedup.

Author dc:creator

• Sun, Zhuoran

Advisor dc:contributor.supervisor

• Thulasiraman, Parimala

• Multi-objective Optimization Problem (MOP)
• Evolutionary Multi-objective Optimization (EMO) Algorithm
• Bi-Criterion Evolution (BCE) Framework
• Parallel Computing

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1993/37951

OAI identifier oai:identifier

oai:mspace.lib.umanitoba.ca:1993/37951