Gravitational Search Algorithm for Frequency Assignment Problem

Abstract

Todays, various heuristic optimization methods have been developed. Many of these algorithms are inspired from physical processes or swarm behaviors in nature. Gravitational Search Algorithm (GSA) is an optimization algorithm based on the law of gravity and mass interactions. In the proposed algorithm, the search agents are a collection of masses. In this paper, mentioned algorithm is used to solve of the Frequency Assignment Problem (FAP). For ability test of the algorithm, CALMA benchmarks are used and results are good.

Keywords


[1]   T. S. Rappaport; "Wireless comunications principles and practice;" 2nd edition; Prentice-Hall of India Private Limited, New Delhi-110001. 2006.
[2]   K. I. Aardal, S. P. M. van Hoesel, A. M. C. A. Koster, C. Mannino, and A. Sassano, "Models and solution techniques for frequency assignment problems," Springer Science+Business Media. Ann Oper Res 153, pp. 79–129. 2007.
[3]   www.fap.zib.de
[4]   P. Kampstra, R. D. van der Mei, and A. E. Eiben, "Evolutionary Computing in Telecommunication Network Design: A Survey," Vrije Universiteit, Faculty of Exact Sciences and CWI, Advanced Communication Networks. Amsterdam, Netherlands. 2006.
[5]   E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi, "GSA: A Gravitational Search Algorithm, Information Sciences;" Elsevier. 2009.
[6]    ع. راشدی­ پور، ح. نظام آبادی پور و س. سریزدی، ”الگوریتم جستجوی گرانشی باینری“، هشتمین کنفرانس سیستم­های هوشمند، دانشگاه فردوسی، مشهد، سال 1386.
[7]   J. P. Malar Dhas, and R. S. Rajesh, "Particle swarm intelligence for Channel Assignment Problem in mobile cellular communication system," Int. J. Artificial Intelligence and Soft Computing, vol. 3, No. 1, 2012.
[8]   E. ruzgar, and O. Dagdeviren, "Performance evaluation of distributed synchronous greedy graph coloring algorithms on wireless Ad Hoc and sensor networks," International Journal of Computer Networks & Communications (IJCNC). Vol. 5, No. 2, March 2013.
[9]   CALMA website, EUCLID CALMA project, Publications and instances available at FTP Site:ftp://ftp.win.tue.nl/pub/techreports/CALMA/, 1995.
[10]            K. I. Aardal, C. A. J. Hurkens, J. K. Lenstra, and S. R. Tiourine, Algorithms for Frequency Assignment Problems (Extended Abstract), CWI Quarterly. vol. 9, pp. 1-8. 1996.
[11]            S. R. Tiourine, "Decision Support by Combinatorial Optimization: Case Studies," Eindhoven University of Technology. 1999.
[12]            A. Bouju, J. F. Boyce, C. H. D. Dimitropoulos, G. Vom Scheidt, and J. G. Taylor, Applied Decision Technologies {(ADT'95)}, London: 1995.
[13]            A. Kapsalis, P. Chardaire, V. J. Rayward-Smith, and G. D. Smith, "The Radio Link Frequency Assignment Problem: {A} Case Study Using Genetic Algorithms," Lecture Notes on Computer Science. vol. 993, pp. 117-131. 1995.
[14]            C. Crisan, and H. M{"u}hlenbein, "The Frequency Assginment Problem: {A} Look at the Performance of Evolutionary Search," Springer, Lecture Notes in Computer Science. vol. 1363, pp. 263-274. 1998.
[15]            A. W. J. Kolen, C. P. M. {v}an Hoesel, and R. {v}an {d}er Wal, A Constraint Satisfaction Approach to the Radio Link Frequency Assignment Problem, EUCLID CALMA project. 1994.
[16]            A. Bouju, J. F. Boyce, C. H. D. Dimitropoulos, G. Vom Scheidt, J. G. Taylor, A. Likas, G. Papageorgiou, and A. Stafylopatis, Int. Conf. For Digital Signal Processing {(DSP'95)}. Limassol, Cypres. 1995.
[17]            D. V. Pasechnik, An Interior Point Approximation Algorithm for a Class of Combinatorial Optimization Problems: Implementation and Enhancements, Delft University of Technology. 1998.
[18]            D. Allouche, S. {d}e Givry, and T. Schiex, (2010). Proc. of CP 2010, pp. 53-60.. Available: www.inra.fr
[19]            M. Sanchez, D. Allouche, S. {d}e Givry, and T. Schiex, (2009). Proc. of IJCAI'09, 2009. Available: www.ijcai.org
[20]            K. I. Aardal, C. P. M. {v}an Hoesel, A. M. C. A. Koster, C. Mannino, and A. Sassano, Models and Solution Techniques for the Frequency Assignment Problem. Konrad-Zuse-Zentrum f{"u}r Informationstechnik Berlin, Berlin, Germany. 2001. Available: www.zib.de