مقایسه روش های بهینه سازی اکسترمال و الگوریتم ژنتیک در حل مسئله یافتن بزرگ ترین کلیک

سال انتشار: 1391
محل انتشار: یازدهمین کنفرانس سراسری سیستم های هوشمند
کد COI اختصاصی: ICS11_140
زبان مقاله: فارسی
تعداد مشاهده: 1026

نویسندگان

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

استادیار گروه کامپیوتر - نرم افزار، دانشگاه آزاد اسلامی واحد مشهد، مشهد

چکیده

مسئله یافتن بزرگ ترین کلیک، از جمله مسائل NP-Complete است که به یافتن بزرگ ترین زیر گراف کامل در یک گراف بدون جهت اشاره دارد. در این مقاله، ابتدا به بیان روش حل مبتنی بر بهینه سازی اکسترمال برای این مسئله می پردازیم و سپس با مقایسه نتایج آن با پاسخ های به دست آمده از الگوریتم ژنتیک، مزایا و معایب روش را بررسی خواهیم کرد. روش فرا اکتشافی بهینه سازی اکسترمال، رئوس کم ارزش را با احتمال بیشتری از بزرگ ترین کلیک فعلی حذف می کند، در نتیجه رئوس با ارزش بیشتر، احتمال حضور بیشتری نیز خواهند داشت. با هر جابه جایی جزئی، تغییرات زیادی در کلیک ایجاد می شود و مرحله به مرحله به سمت یافتن بزرگ ترین کلیک پیش می رود. نتایج حاصل از مقایسه پیاده سازی این دو روش روی گراف های DIMACS ، نشان می دهد که الگوریتم ژنتیک، همچنان جواب های دقیق تری را به دست می آورد اما سرعت همگرایی روش بهینه سازی اکسترمال در به دست آوردن بهترین جواب، بسیار بهتر از سایر روش هاست

کلیدواژه ها

بزرگ تری کلیک، بهینه سازی اکسترمال، کلیک، گراف

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.