AUTHORS: F. Choong, S. Phon-Amnuaisuk, M. Y. Alias

Download as PDF

ABSTRACT: Memetic algorithms (MAs) are hybrid evolutionary algorithms (EAs) that combine global and local search by using an EA to perform exploration while the local search method performs exploitation. Combining global and local search is a strategy used by many successful global optimization approaches, and MAs have in fact been recognized as a powerful algorithmic paradigm for evolutionary computing. This paper presents a hybrid heuristic model that combines particle swarm optimization (PSO) and simulated annealing (SA). This PSO/SA hybrid was applied on the multiprocessor scheduling problem to perform static allocation of tasks in a heterogeneous distributed computing system in a manner that is designed to minimize the cost. Additionally, this paper also focuses on the design and implementation of several enhancements to PSO based on diversity and efficient initialization using different distributions. The results show the effectiveness and superiority of the hybrid algorithms.

KEYWORDS: Memetic Algorithms, Particle Swarm Optimization, Simulated Annealing, Hybrid, Multiprocessor Scheduling, Optimization

REFERENCES:

[1] Pablo, M., NP Optimization Problems, Approximability and Evolutionary Computation: From Practice to Theory, Ph.D. Dissertation, Universidade Estadual de Campinas, Brazil, 2001.

[2] Kennedy, J., and R. Eberhart, Swarm Intelligence, Academic Press, 1st ed., San Diego, CA. 2001.

[3] Chen D.J., Lee C.Y., Park C.H., Mendes P., Parallelizing simulated annealing algorithms based on high-performance computer, J. Glob. Optim., Vol. 39, 2007, pp. 261–289.

[4] Abdelmageed, E.A, and B. Earl Wells, A Heuristic model for task allocation in heterogeneous distributed computing systems, The International Journal of Computers and Their Applications, Vol. 6, No. 1, 1999, pp. 746-753.

[5] Annie, S., W. Shiyun Jin, Kuo-Chi Lin and Guy Schiavone, Incremental Genetic Algorithm Approach to Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, Vol. 2, No. 5, 2004, pp. 135-142.

[6] Dar-Tzen Peng, G. S. Kang and F. Tarek Abdelzaher, Assignment and Scheduling Communicating Periodic Tasks in Distributed RealTime Systems, IEEE Transactions on Software Engineering. Vol. 23, No. 12, 1997.

[7] Ruey-Maw, C., and H. Yueh-Ming, Multiprocessor Task Assignment with Fuzzy Hopfield Neural Network Clustering Techniques, Journal of Neural Computing and Applications, Vol.10, No.1, 2001.

[8] Virginia, M.L., Heuristic algorithms for task assignment in distributed systems, IEEE Transactions on Computers, Vol. 37, No. 11, 1998, pp. 1384– 1397.

[9] Ioan, C. T., The particle swarm optimization algorithm: convergence analysis and parameter selection, Information Processing Letters, Vol. 85, 2003, pp. 317–325.

[10] Batainah, S., and M. AI-Ibrahim, Load management in loosely coupled multiprocessor systems, Journal of Dynamics and Control, Vol.8, No.1, 1998, pp. 107-116.

[11] Choong, F., S. Phon-Amnuaisuk, M.Y. Alias and W.L. Pang, Adaptive Genetic Algorithm: An Essential Ingredient in High-level Synthesis, Proceedings of the IEEE Congress on Evolutionary Computation (CEC), Vol. 5, No. 6, 2008, pp. 3837- 3844.

[12] Graham, R., Static, Multi-processor scheduling with Ant Colony Optimization and Local search, Master of Science thesis , University of Edinburgh, 2003.

[13] Peng-Yeng, Y., Y. Shiuh-Sheng, W. Pei-Pei and W. Yi-Te, A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems, Computer Standards & Interfaces, Vol.28, 2006, pp. 441-450.

[14] Yskandar, H., and S. Khalil Hindi, Assignment of program modules to processors: A simulated annealing approach, European Journal of Operational Research, Vol. 1, No. 22, 2000, pp.509-513.

[15] Tzu-Chiang, C., C. Po-Yin, and H. Yueh-Ming, Multi-Processor Tasks with Resource and Timing Constraints Using Particle Swarm Optimization, IJCSNS International Journal of Computer Science and Network Security. Vol.6, No.4, 2006.

[16] Shi, Y., and R. Eberhart, Parameter Selection in Particle Swarm Optimization, Evolutionary Programming VII, Proceedings of Evolutionary Programming, 1998, pp. 591-600.

[17] Maurice, C., and J. Kennedy, The Particle Swarm—Explosion, Stability, and Convergence in a Multidimensional Complex Space, IEEE Transactions on Evolutionary Computation, Vol. 6, No. 1, 2002.

[18] Zhang, Y., R. Kamalian, A.M. Agogino and C.H. Séquin, Hierarchical MEMS Synthesis and Optimization, Smart Structures and Materials, Smart Electronics, MEMS, BioMEMS, and Nanotechnology, Proceedings of SPIE, Vol. 5763, 2005, pp. 96-106.

[19] Liu, H., A. Abraham and W. Zhang, A Fuzzy Adaptive Turbulent Particle Swarm Optimization, International Journal of Innovative Computing and Applications, Vol 1, No. 1, 2007, pp. 39–47.

[20] Grosan, C., A. Abraham and M. Nicoara, Search Optimization Using Hybrid Particle SubSwarms and Evolutionary Algorithms, International Journal of Simulation Systems, Science & Technology, Vol. 6, No. 10&11, 2005, pp. 60–79.

[21] Engelbrecht, A.P., Fundamentals of Computational Swarm Intelligence, John Wiley & Sons Ltd., Chichester, 2005.

[22] Blackwell, T., and J. Branke, Multi-swarm optimization in dynamic environments, Applications of Evolutionary Computing, Vol. 3, No. 5, 2008, pp. 45-54.

[23] Grosan, C., A. Abraham and M. Nicoara, Search Optimization Using Hybrid Particle SubSwarms and Evolutionary Algorithms, International Journal of Simulation Systems, Science & Technology, Vol. 6, No. 10&11, 2005, pp. 60–79.

[24] Krohling, R.A., A Novel Particle Swarm Optimization Algorithm, In: Proc. of the 2004 IEEE Conference on Cybernetics and Intelligent Systems, 2004, pp. 372–376.

[25] Krohling, R.A., and L.S. Coelho, PSO-E: Particle Swarm with Exponential Distribution, In: IEEE Congress on Evolutionary Computation, 2006, pp. 1428–1433.