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

چکیده مقاله

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

کلیدواژه‌ها

نویسندگان

سمیه امیری

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

علی حنانی

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

�میری، سمیه و حنانی، علی،1395،افراز گراف با استفاده از الگوریتم تکاملی قورباغه،سومین کنفرانس سراسری نوآوری های اخیر در مهندسی برق و کامپیوتر،تهران

ارائه‌شده در

مجموعه مقالات سومین کنفرانس سراسری نوآوری های اخیر در مهندسی برق و کامپیوتر19 شهریور 1395 · تهران