Data Partition and Communication On Parallel Heuristik Model Based on Clonal Selection Algorithm

Ayi Purbasari, Iping Supriana Suwardi, Oerip Slamet Santoso, Rila Mandala

Abstract


Researchers conducted experiments on parallel algorithms, which are inspired by the clonal selection, called Clonal Selection Algorithm (CSA). This algorithm is a population-based heuristic solution. Course-grained parallelism model applied to improve the execution time. Inter-process communication overhead is addressed by adjusting the communication frequencies and size of data communicated. In this research, conducted experiments on six parallel computing models represent all possible partitions and communications. Experiments conducted using data of NP-Problem, Traveling Salesman Problem (TSP). The algorithm is implemented using the model of message passing libraries using MPJExpress. Experiments conducted in a cluster computation environment. Result shows the best parallelism model is achieved by partitioning the initial population data at the beginning of communication and the end of generation. Communication frequency can be up to per 1% of the population size generated. Using four dataset from TSPLib, this reseache shows effect of the communication frequency that increased the 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 the execution time 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 the execution time, and also the best cost. It improved execution time and best cost.

Full Text:

PDF

References


Alsharhan S, J.R. Al-Enezi. Abbod MF, "Artificial Immune Systems – Models , Algorithms and Applications," International Journal of Research and Reviews in Applied Science (IJRRAS), pp. 118-131, May 2010.

Mark Baker, Bryan Carpenter, and Aamir Shafi, "MPJ Express: towards thread safe Java HPC," in IEEE International Conference on Cluster Computing, 2006.

Gaber J Bakhouya M, "An Immune Inspired-based Optimization Algorithm : Application to the Traveling Salesman Problem," AMO - Advanced Modeling and Optimization, vol. 9, no. 1, pp. 105-116., 2007.

Blaise Barney. (2012) Introduction to Parallel Computing. [Online]. https://computing.llnl.gov/tutorials/parallel_comp/#Designing

Jason Brownlee, "Clonal Selection Algorithms," Complex Intelligent Systems Laboratory, Centre for Information Technology Research, , Faculty of Information Communication Technology, Swinburne University of Technology, Melbourne, Australia , Technical 2009.

Leandro N. de Castro and Fernando J. Von Zuben, "Learning and Optimization Using the Clonal Selection Principle," IEEE Transactions On Evolutionary Computation, vol. 6, no. 3, pp. 239-251, June 2002.

Jacek Dabrowski and Marek Kubale, "Computer Experiments with a Parallel Clonal Selection Algorithm for the Graph," in IEEE International Symposium on Parallel and Distributed Processing, Miami, FL, 2008, pp. 1-6.

Donald Davendra, Traveling Salesperson Problem: Theory and Application, Donald Davendra, Ed. Croatia: InTechWeb.Org, 2010.

Ian Foster. (1995) Designing and Building Parallel Programs. [Online]. http://www.mcs.anl.gov/~itf/dbpp/

Zhu Hongbing, Chen Sicheng, and Wu Jianguo, "Paralleling Clonal Selection Algorithm with OpenMP," in 3rd International Conference on Intelligent Networks and Intelligent Systems (ICINIS), Shenyang, 1-3 Nov. 2010, pp. 463 - 466.

Jonathan Timmis and Leandro Nunes Castro, Artificial Immune Systems: A New Computational Approach. London: Springer Verlag, 2002.

TSPLIB. [Online]. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/

Kulturel-Konak S Ulutas BH, "A Review of Clonal Selection Algorithm and Its Applications," Artificial Intelligence Review, 2011.

Andrew Watkins, Xintong Bi, and Amit Phadke, "Parallelizing an Immune-Inspiring Algorithm for Efficient Pattern Recognition," in Intelligent Engineering Systems through Artificial Neural Networks: Smart Engineering, 2003, pp. 225-230.




DOI: http://dx.doi.org/10.12928/telkomnika.v13i1.728

Article Metrics

Abstract view : 229 times
PDF - 230 times

Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Universitas Ahmad Dahlan

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

TELKOMNIKA Telecommunication, Computing, Electronics and Control
ISSN: 1693-6930, e-ISSN: 2302-9293
Universitas Ahmad Dahlan, 4th Campus, 9th Floor, LPPI Room
Jl. Ringroad Selatan, Kragilan, Tamanan, Banguntapan, Bantul, Yogyakarta, Indonesia 55191
Phone: +62 (274) 563515, 511830, 379418, 371120 ext. 4902, Fax: +62 274 564604

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

View TELKOMNIKA Stats