افراز گراف با استفاده از الگوریتم تکاملی قورباغه

Publish Year:

1395

نوع سند:

مقاله کنفرانسی

زبان:

Persian

View:

636

This Paper With 15 Page And PDF and WORD Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

COMCONF03_233

تاریخ نمایه سازی: 6 اردیبهشت 1396

Abstract:

مسیله بخشبندی گراف یکی از مهم ترین مسایل در زمینه بهینه سازی و تیوری گراف می باشد که در بسیاری از زمینه ها مورد مطالعه و بررسی قرار گرفته است و روش های گوناگونی برای حل آن ارایه شده است. ما در این پایان نامه در ابتدا مروری نظام مند بر کارایی ها، زیر مسایل، روش های حل، و ابزار های ارایه شده برای این مسیله پر اهمیت را ارایه داده ایم.سپس سعی در حل مسیله بخشبندی متوازن گراف های غیر جهت دار را داشته ایم. به این صورت که یک گراف ده هزار راسی را به دسته های مختلفی تقسیم می کنیم به صورتی که تعداد ریوسی که در هر بخش وجود دارد نسبت به هم به صورت بهینه متوازن باشند. این مسیله در رده مسایل NP قرار می گیرد و راه حل دقیق در یک زمان خطی برای آن وجود ندارد. روش پیشنهادی ما برای دست یافتن به یک جواب بهینه یک الگوریتم فرا ابتکاری به نام الگوریتم جهش قورباغه می باشد. ما ساختار مسیله را به گونه ای نمایش می دهیم که بتوان آنرا از طریق الگوریتم ذکر شده حل کرد. سپس با استفاده از یک تابع شایستگی میزان برازندگی جواب های بدست آمده را در هر مرحله می سنجیم. در آزمایشات انجام شده برای سنجش کارایی این روش، الگوریتم های دیگری مانند الگوریتم ژنتیک و ماهی های مصنوعی پیاده سازی و مقایسه شده است. نتایج بدست آمده کارایی الگوریتم را نشان می دهد.

Keywords:

بخشبندی گراف , کاربرد های بخشبندی گراف , زیر مسایل بخشبندی گراف , الگوریتم جهش قورباغه

Authors

سمیهامیری
سمیه امیری

دانشجوی کارشناسی ارشد مهندسی کامپیوتر، واحد علوم و تحقیقات کرمانشاه، دانشگاه آزاد اسلامی، کرمانشاه، ایران / دانشجوی مهندسی کامپیوتر، واحد کرمانشاه، دانشگاه آزاد اسلامی، کرمانشاه، ایران

علیحنانی
علی حنانی

عضو هیات علمی، گروه مهندسی کامپیوتر، مرکز سنقر کلیایی، دانشگاه آزاد اسلامی، سنقر کلیایی، کرمانشاه، ایران/گروه مهندسی کامپیوتر، واحد کرمانشاه، دانشگاه آزاد اسلامی، کرمانشاه، ایران

مراجع و منابع این Paper:

لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :
  • امیری سمیه، حنانی علی، (1395)، "مروری بر کابرد های مسئله ...
  • امیری سمیه، حنانی علی، (1395) مروری نظام _ بر بهینه ...
  • B. Junker and F. Schreiber, (2008), "Analysis of Biological Networks", ...
  • R. Mondaini. Biomat, (2009), "Internationt Symposium on Mathematicat and Computational ...
  • S. Fortunato. (2009), "Community Detection in Graphs", CoRR, abs/0906.0612 ...
  • P. Erd"os, A. Gy arf as, and L. Pyber, (1991), ...
  • C. Aykanat, B. B. Cambazoglu, F. Findik, and T. Kurc. ...
  • MUZAFFAR EUSUFF, KEVIN LANSEY, and FAYZUI PASHA, (2006) "Shuffled frog-leaping ...
  • M. Zhou, O. Sahni, et al. (2010), "Controlling Unstructured Mesh ...
  • U. Lauther. (2004), "An Extremely Fast, Exact Algorithm for Finding ...
  • P. Sanders and C. Schulz, Think Locally, (2013), "Act Globally: ...
  • S. T. Barnard and H. D. Simon. (1993), _ Fast ...
  • C. Lanczos. (1950), ":An Iteration Method for the Solution of ...
  • G. Karypis and V. Kumar. (1998), _ Fast and High ...
  • A. George and J. W. H. Liu.(1981), "Computer Solution of ...
  • _ R. Ford and D. R. Fulkerson. (1956), "Maximal Flow ...
  • C. Farhat and M. Lesoinne.(1 993), "Automatic Partitioning of Unstructured ...
  • R. D. Williams. (1991), "Performance of Dynamic Load Balancing Algorithms ...
  • A. H. Land and A. G. Doig. (1960), "An Automatic ...
  • _ _ Fiduccia and R. M. Mattheyses. (1982), _ Linear-Time ...
  • H. D. Simon and S. H. Teng. (1997), "How Good ...
  • Aidin B, Henning M, Ilya s, Peter S, and Cristian ...
  • G. Karypis and V. Kumar. (1999), "Multilevel k-Way Hypergraph Partitioning", ...
  • G. Karypis and V. Kumar (1996), "Parallel Multilevel k-way Partitioning ...
  • C. Chevalier and F. (2008), "Pellerini. PT-Scotch: A Tool for ...
  • B. Monien and S. Schamberger. (2004), "Graph Partitioning with the ...
  • Pavla Kabel 1kov , (2006), "Graph Partitioning Using Spectral Methods", ...
  • R. Rajabioun, (2011), "Cuckoo Optimization Algorithm" ; Elsevier; Applied Soft ...
  • Sina Zangbari Kouhi, Faranak Nejati, Jaber Karimpour, (2013), "Solving the ...
  • _ Catalyirek and C. Aykanat. (2011), "PaToH: Partitioning Tool for ...