A Parallel Genetic Algorithm Based on TBB for Resolving the Bin-Packing Problem

Author

Zhang Liyan ; Sun Yan ; Ma Jian ; Sun Jian

Author_Institution

Sch. of Transp. Eng., Tongji Univ., Shanghai, China

fYear

2011

fDate

12-14 Aug. 2011

Firstpage

1

Lastpage

4

Abstract

The paper presents a novel Three-tier Parallel Genetic Algorithm (TPGA) based on multi-core computer with Threading Building Blocks (TBB). The purpose of a new parallel function is to improve the running efficiency. TPGA is decomposed into three-tier: data coding parallelism, task processing parallelism and data decoding parallelism and it can improve the convergence rate. TBB offers a rich and complete approach to express parallelism in a C++ program. Sequential Genetic Algorithm (SGA) and TPGA are implemented based on TBB with C++ for bin-packing problem. Experiments show that the optimal solutions of TPGA and SGA are Consistent and the running efficiency of TPGA is also sooner than one of SGA.

Keywords

C++ language; bin packing; genetic algorithms; multi-threading; multiprocessing systems; parallel algorithms; sequential codes; C++ program; TBB; TPGA; bin packing problem; convergence rate; data coding parallelism; data decoding parallelism; multicore computer; running efficiency; sequential genetic algorithm; task processing parallelism; threading building block; three-tier parallel genetic algorithm; Algorithm design and analysis; Computers; Genetic algorithms; Instruction sets; Libraries; Parallel processing; Scalability;

fLanguage

English

Publisher

ieee

Conference_Titel

Management and Service Science (MASS), 2011 International Conference on

Conference_Location

Wuhan

Print_ISBN

978-1-4244-6579-8

Type

conf

DOI

10.1109/ICMSS.2011.5999321

Filename

5999321