Data Partition and Communication on Parallel Heuristik Model Based on Clonal Selection Algorithm
Abstract: This research
conducted experiments on population-based heuristic parallel algorithms, which
are inspired by the clonal selection, called Clonal Selection Algorithm (CSA).
Course-grained parallelism model applied to improve execution time.
Inter-process communication overhead is addressed byadjusting communication
frequencies and size of data communicated. Experiments on six parallelcomputing
models represent all possible partitions and communications and using data of
NP-Problem,Traveling Salesman Problem (TSP). The algorithm is implemented using
model of message passinglibraries MPJExpress and ran in a cluster computation
environment. Result shows the best parallelismmodel is achieved by partitioning
initial population data at the beginning of communication and the end of generation.
Communication frequency can be up to per 1% of a population size generated.
Using four dataset from TSPLib, experiments show the effect of communication
frequency that increased best cost, from 44.16% to 87.01% for berlin52.tsp;
from 9.61% to 53.43% for kroA100.tsp, and from 12.22% to 17.18% for tsp225.tsp.
With eight processors, using communication frequency will be reduced executiontime
e.g 93.07%, 91.60%, 89.60%, 74.74% for burma14.tsp, berlin52.tsp, kroA100.tsp,
and tsp225.tsp respectively. We conclude that frequency of communication
greatly affects execution time, and also best cost. It improved execution time
and best cost.
Keywords: clonal selection
algorithm, parallel clonal selection algorithm, parallel heuristic model, data partition,
coarse-grained communication, traveling salesman problem, message passing
interface, MPJExpress
Author: Ayi Purbasari
Journal Code: jptkomputergg150028
