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

جداسازی نقاط رنگی یکی از مسائل مهم در هندسه محاسباتی است که در بخش های مختلف علوم کاربرد دارد واز آن جمله می توان به مکان یابی تسهیلات، پردازش تصویر و خوشه بندی اشاره کرد. در این بین، یکی از مسائل پرکاربرد هندسه محاسباتی دردنیای واقعی، مساله پوشش و جداسازی نقاط با مستطیل است و ما قصد داریم در این مقاله به مساله جداسازی مجموعه نقاط دو رنگ با استفاده از سه مستطیل بپردازیم. در واقعهدف ما جداسازی نقاط مطلوب به رنگ ابی از نقاط نامطلوب به رنگ قرمز توسط سه مستطیل است، به گونه ای که این سه مستطیل شامل بیشترین نقاط مطلوب باشند. بدین منظور یک الگوریتم فراابتکاری مبتنی بر روش شبیه سازی انجماد ارائه می دهیم که نقاط آبی را از بین n نقطه ورودی در زمانی با مرتبه O(n) توسط سه مستطیل جدا می کند. الگوریتم مذکور با سی شارپ پیاده سازی شده و با نتایج الگوریتم بهینه مورد مقایسه و ارزیابی قرار گرفته است.نتایج ارزیابی نشان می دهد که الگوریتم پیشنهادی ما نزدیک بهینه است و در مواردی نیز پاسخ بهینه را به دست می دهد.

Keywords:

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