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

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

کلیدواژه ها:

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