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

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

کلیدواژه ها:

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