مقایسه الگوریتم جستجوی هارمونی و الگوریتم ژنتیک برای مساله بیشینه برش

مساله حداکثر برش یکی از مسایل NP – complete {در تئوری پیچیدگی محاسباتی، یک مسئله NP-کامل است وقتی که آن را می توان با یک کلاس محدود از الگوریتم های جستجوی نیروی بی رحم حل کرد و می توان آن را برای شبیه سازی هر مشکل دیگری با یک الگوریتم مشابه مورد استفاده قرار داد.} است و در زمینه‌های مختلف از جمله فرآیند طراحی برای تراشه‌های با مقیاس خیلی بزرگ)و نظریه شیشه اسپین در فیزیک آماری کاربرد دارد. در این مقاله، یک الگوریتم جستجوی هارمونی برای مساله بیشینه برش پیشنهاد شده‌است. در مقایسه با الگوریتم ژنتیک، الگوریتم جستجوی هارمونی از مزایای ایجاد یک بردار جدید پس از در نظر گرفتن تمامی بردارهای موجود و نیاز به تعداد اندکی از پارامترها قبل از اجرای الگوریتم است. برای ۳۱ نمودار معیار انواع مختلف، الگوریتم جستجوی هارمونی پیشنهادی با یک الگوریتم ژنتیک توسعه‌یافته جدید مقایسه شده و الگوریتم ژنتیک دیگری که از ادبیات اخیر گرفته شده‌است ارایه شده‌است. الگوریتم جستجوی هارمونی پیشنهادی نتایج بهتری نسبت به دو الگوریتم ژنتیک دارد.

The max-cut problem is one of well-known NP-complete problems and has applications in various fields such as the design process for VLSI (Very-Large-Scale Integration) chips and spin glass theory in statistical physics. In this paper, a harmony search algorithm for the max-cut problem is proposed. Compared to genetic algorithm, harmony search algorithm has advantages of generating a new vector after considering all of the existing vectors and requiring only a few number of parameters to be determined before the run of the algorithm. For 31 benchmark graphs of various types, the proposed harmony search algorithm is compared with a newly developed genetic algorithm and another genetic algorithm taken from the recent literature are presented. The proposed harmony search algorithm produced significantly better results than the two genetic algorithms.