مقایسه روش های بهینه سازی اکسترمال و الگوریتم ژنتیک در حل مسئله یافتن بزرگ ترین کلیک
Publish place: 11th Intelligent Systems Conference
Publish Year: 1391
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 927
This Paper With 10 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
این Paper در بخشهای موضوعی زیر دسته بندی شده است:
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ICS11_140
تاریخ نمایه سازی: 14 مهر 1392
Abstract:
مسئله یافتن بزرگ ترین کلیک، از جمله مسائل NP-Complete است که به یافتن بزرگ ترین زیر گراف کامل در یک گراف بدون جهت اشاره دارد. در این مقاله، ابتدا به بیان روش حل مبتنی بر بهینه سازی اکسترمال برای این مسئله می پردازیم و سپس با مقایسه نتایج آن با پاسخ های به دست آمده از الگوریتم ژنتیک، مزایا و معایب روش را بررسی خواهیم کرد. روش فرا اکتشافی بهینه سازی اکسترمال، رئوس کم ارزش را با احتمال بیشتری از بزرگ ترین کلیک فعلی حذف می کند، در نتیجه رئوس با ارزش بیشتر، احتمال حضور بیشتری نیز خواهند داشت. با هر جابه جایی جزئی، تغییرات زیادی در کلیک ایجاد می شود و مرحله به مرحله به سمت یافتن بزرگ ترین کلیک پیش می رود. نتایج حاصل از مقایسه پیاده سازی این دو روش روی گراف های DIMACS ، نشان می دهد که الگوریتم ژنتیک، همچنان جواب های دقیق تری را به دست می آورد اما سرعت همگرایی روش بهینه سازی اکسترمال در به دست آوردن بهترین جواب، بسیار بهتر از سایر روش هاست
Keywords:
Authors
محدثه گریوانی
دانشجوی کارشناسی ارشد مهندسی کامپیوتر - نرم افزار، دانشگاه آزاد اسلامی واحد مشهد، مشهد
مجید وفایی جهان
استادیار گروه کامپیوتر - نرم افزار، دانشگاه آزاد اسلامی واحد مشهد، مشهد
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :