حل یک مساله درجه دوم پیوسته برای مساله افرازبندی متقارن با استفاده از الگوریتم ترکیبی سرد کردنتدریجی و جستجوی محلی

هدف مساله افرازبندی متقارن ،گراف افراز کردن راس های گراف ،است به طوری که مجموع وزن یال های بین مجموعه های افراز کمینه شود همچنین اختلاف مجموع وزن بین مجموعه های افراز نیز به کمترین مقدار خود برسد. مساله افرازبندی متقارن گراف در رده مسایل NP سخت است و بر اساس پژوهشهای انجام شده الگوریتمهای ارایه شده برای حل این مساله دو رده کلی الگوریتمهای دقیق و الگوریتمهای ابتکاری دسته بندی میشود. در مسایل افرازبندی متقارن گراف هم در طراحی الگوریتمهای دقیق و هم در طراحی الگوریتمهای ابتکاری از بهینه سازی پیوسته استفاده شده است. در این مقاله الگوریتم ترکیبی سرد کردن تدریجی (SA) و جستجوی محلی را برای حل یک مساله افراز بندی گراف متقارن را بیان کردهایم نتایج نشان میدهد که روش پیشنهادی جواب مناسبی را با سرعت محاسباتی قابل قبولی بدست آورده است

Keywords:

افرازبندی متقارن گراف , بهینه سازی پیوسته , جستجوی محلی , الگوریتم سرد کردن تدریجی.