حل مسئله تخصیص فرکانس با استفاده از الگوریتم جستجوی گرانشی

نویسندگان

1 کارشناس ارشد الکترونیک، دانشکده مهندسی برق و کامپیوتر، دانشگاه بیرجند، ایران

2 دانشیار، دانشکده مهندسی برق و کامپیوتر، دانشگاه بیرجند، ایران

چکیده

امروزه به­طور گسترده­ای از روش­های ابتکاری برای حل مسائل گوناگون استفاده می­شود. دسته مهمی از این الگوریتم­ها با الهام از فرایندهای فیزیکی یا رفتارهای موجودات به وجود آمده­اند. الگوریتم جستجوی گرانشی (GSA) از سری الگوریتم­های بهینه یابی است که با الهام از قانون جاذبه و مفهوم جرم شکل یافته است و عامل­های جستجوگر، مجموعه­ای از اجرام می­باشند. در این مقاله با استفاده از این الگوریتم به حل مسئله تخصیص فرکانس (FAP) پرداخته شده است. برای محک قابلیت الگوریتم در حل مسئله، از نمونه­های محک استاندارد CALMA استفاده گشته و نتایج بدست آمده، گویای توانایی خوب الگوریتم جستجوی گرانشی در حل مسئله تخصیص فرکانس می­باشد.

کلیدواژه‌ها


[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